Найти большую коллекцию строк в большой коллекции строк

Question

У меня есть коллекция строк, которые я хочу отфильтровать.Они будут выглядеть следующим образом:

xxx_xxx_xxx_xxx

, поэтому всегда последовательность букв или цифр, разделенных тремя подчеркиваниями.Максимальная длина каждой строки будет 60 символов.У меня может быть несколько миллионов таких в моей коллекции.

Какую структуру данных я могу использовать, чтобы эффективно сделать что-то вроде этого:

Получить все строки, начинающиеся с: "abc_123_456"

Получить все строки начинается с: "def_999_888"

и т. Д.

Например, я мог бы сделать это:

List<String> matched = new ArrayList<String>();
for (String it : strings) {
    if (it.startsWith(match)) {
        matched.add(it);
    }
}

ноэто заняло бы много времени, если бы моя коллекция имела порядок миллионов строк, и еще хуже, если число подходящих строк также велико.

Проблема высокого уровня в том, что я хочу ответить на следующий вопрос для приложения, которое я пишу: «кто из моих друзей рекомендовал продукт A для продукта B?».Я мог бы сохранить эту информацию в таблице sql и выполнить следующую инструкцию:

select recommender from recs where username='me' and prodIdA='a' and prodIdB='b';

Мне интересно, может ли что-то нестандартное в java / C / C ++ работать быстрее, используя закодированные плоские строки, как у меня было выше:

myusername_prodIdA_prodIdB_recommenderusername

Идея состоит в том, что вы можете выполнить операцию запуска с всей коллекцией закодированных строк, чтобы получить ответ.

IЯ знаю, что попытка реализовать собственное решение, подобное этому, скорее всего, не пригодна для использования в производственной среде, поэтому некоторые sql db были бы лучше, просто любопытно,

Спасибо

Answer 1

Для этого в Java вы можете использовать структуру Trie .

Как говорится, я не думаю, что это хорошая идея. Сброс «нескольких миллионов» записей в память не всегда будет работать.

Вот для чего нужны базы данных; с правильным дизайном и надлежащим индексированием вы можете добиться очень хорошей производительности только с БД.

Answer 2

Первое, что приходит мне в голову, - это предварительная обработка строк в некую структуру данных, чтобы их можно было эффективно искать.Если вы собираетесь вызывать функцию поиска много раз, я думаю, было бы хорошо, если бы вы поместили все строки в хеш-таблицу для поиска в постоянном времени.Потребовалось бы больше вычислительной мощности для создания массива строк, но это упростило бы задачу их поиска.

Answer 3

Я знаю, что попытка реализовать собственное решение, подобное этому, скорее всего, не пригодна для использования в производственной среде, поэтому некоторые sql db были бы лучше, хотя и любопытно

Если только дляРади любопытства вы можете поместить все существующие разные комбинации "myusername_prodIdA_prodIdB" в хеш-таблицу.И для каждой комбинации сохраните список релевантных результатов.

Итак, структура будет выглядеть как Map<String, List<String>> и использоваться как hash.get("def_999_888").Постоянное время (O (1))

Вы можете избавиться от внутреннего списка и оптимизировать его многими способами, но это идея.

Answer 4

Я думаю, что вы ищете SortedMap.

"headMap (K toKey) Возвращает представление части этой карты, ключи которой строго меньше, чем toKey. "