наиболее эффективная структура данных Java для поиска троек строк

Question

Предположим, у меня есть большой список (около 10 000 записей) трёх строк:

car    noun    yes
dog    noun    no
effect noun    yes
effect verb    no

Предположим, мне представлена ​​двойная строка - например, (эффект, глагол) - и мне нужно быстро просмотреть список, чтобы увидеть, появляется ли пара и, если да, имеет ли она значение да или нет. (Для этого примера двойное число действительно появляется, и значение равно «нет».)

Какова лучшая структура данных в Java для хранения списка и наиболее эффективный способ поиска? Я провожу сотни тысяч таких поисков, поэтому скорость важна.

Спасибо!

Answer 1

Вы можете рассмотреть возможность использования HashMap<YourDouble, String>. Поиски будут O (1).

Вы можете либо создать объект, YourDouble, который содержит первые два значения, либо добавить одно к другому (если значения все еще будут уникальными) и использовать HashMap<String, String>.

Answer 2

10k не кажется мне таким большим.Вы пробовали БД?

Место для поиска такой информации - Semantic Web .Ряд проектов работают на Triple Stores именно этого типа.Внизу страницы Triple Store есть список реализаций.

Что касается Java, ваши алгоритмы почти наверняка будут зависеть от языка, и если вы найдете хороший алгоритм, реализованный в C, его Java-порт также будет быстрым.

Кроме того, как выглядит ваш набор данных?Много ли 2 совпадений, так что тема и глагол часто совпадают?Сколько матчей вы ожидаете получить?MapReduce будет хорошо работать для поиска одного совпадения в 10k, но не будет работать так же хорошо, выполняя запрос, который возвращает 8k из 10k, где запрос не может быть легко разбит на части.

Существует язык запросов, созданный только дляэта проблема тоже: SPARQL .В блоге bigdata есть несколько хороших идей, но опять же 10k кажется не таким уж большим.

Answer 3

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

В качестве альтернативы кажется, что слов во втором столбце будет меньше, поскольку они представляют категории.У вас может быть HashMap<String, HashMap<String, Boolean>>, где вы сначала индексируете, например, «существительное», «глагол» и т. Д., А затем вы индексируете, например, «машина», «собака», «эффект», чтобы добраться до логического значения.Это, вероятно, будет более экономичным.

Answer 4

Я бы создал HashMultimap для каждого типа поиска, который вы хотите, например, «все три», «каждая пара» и «каждое отдельное поле». Когда вы строите список, заполняете все карты, и вы можете выбрать любую карту, подходящую для вашего запроса.

(Недостатком является то, что вам понадобится тип по крайней мере для каждой арности, например, используйте просто String для карт с одним полем, но Pair для карт с двумя полями и Triple для карта с тремя полями.)