Быстрое сопоставление строк с низким энергопотреблением и процессором в Android

Question

Я работаю над приложением, которое принимает голосовой ввод и сопоставляет его с известными элементами в манифесте.

Каждый элемент в манифесте имеет список псевдонимов, поэтому элементы с длинными заголовками могутбыть сопоставленными с более короткими именами.

Например:

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;
        }
    }
}

Это прекрасно работает с тестовой партией из двадцати пяти предметов в прототипе, но в конечном итоге потребуется обработать от 5000 до 10000 предметов как можно ближе к реальному времени на телефоне.

Основной вопрос:

Если предположить, что я могу хранить 10 000 таких элементов в памяти (пример составляет около 64 килобайт, то есть меньше, чем мегабайт для 10 000 элементов), какая коллекция лучше?использовать на Android для хранения этих объектов в памяти, и какой самый быстрый способ заполнить этот объект данными, а затем найти соответствующие элементы?

Answer 1

Вы можете легко сделать это с 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 не имеет смысла, если вы не делаете префиксные совпадения.Набор не имеет смысла, потому что вы можете только сказать «существует ли он», а не «какая вещь соответствует».Карта перейдет от всего к исходному Product, из которого вы можете получить имя.

Кроме того, ваш алгоритм подбора грубой силы, переписанный на Kotlin, находится в ответе на ваш другой вопрос: https://stackoverflow.com/a/52565549/3679676