我正在开发一个应用程序,该应用程序接受语音输入,并将该输入与 list 中的已知项目进行匹配。
list 中的每个项目都有一个别名列表,以便长标题的项目可以与较短的名称相匹配。
例如:
class Product
{
itemname: "Old Stinky's Western Kentucky Big Rig Polish",
aliases: ["old stinky", "other alias"]
}
然后加载到内存中:
public List<Product> Collection;
Collection.Add(alltheproducts);
然后通过以下方式进行匹配:
public String isProductOrAlias(String lowertext)
for (Product p: products.Collection) {
if(lowertext.equals(p.name.toLowerCase()))
return p.name;
if(p.aliases != null) {
for (String s: p.aliases) {
if(lowertext.equals(s.toLowerCase()))
return p.name;
}
}
}
这对于原型(prototype)中 25 个项目的测试批处理效果很好,但最终需要在手机上尽可能实时地处理 5,000-10,000 个项目。
核心问题:
假设我可以在内存中保存 10,000 个这些项目(样本时钟约为 64 KB,因此 10,000 个项目总共不到 1 MB),在 Android 上使用什么集合来将这些对象存储在内存中,用数据填充该对象然后找到匹配元素的最快方法是什么?
最佳答案
假设没有重复的别名或产品名称,您可以使用Map
轻松完成此操作。 Kotlin 版本是:
data class Product(val name: String, val aliases: Array<String>)
fun test() {
val products = listOf<Product>( ... )
// Do this once, create a map from name and aliases to the product
val productIndex = products.asSequence().flatMap { product ->
val allKeys = sequenceOf(product.name) + product.aliases
allKeys.map { it.toLowerCase() to product }
}.toMap()
// now name => product and each alias => product are mapped in productIndex
val matchingProduct = productIndex["something"] // search lower case name
println(matchingProduct?.name ?: "<not found>")
}
除非进行前缀匹配,否则 Trie 没有意义。 Set 没有任何意义,因为你只能判断“它是否存在”,而不能判断“哪个东西匹配”。 map 将从任何内容到原始的 Product
,您可以从中获取名称。
此外,您用 Kotlin 重写的暴力匹配算法是对您的其他问题的回答:https://stackoverflow.com/a/52565549/3679676
关于java - Android 中快速、低功耗/CPU 字符串匹配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52563292/