Самый эффективный способ проверить, существует ли строка в сетке Java - PullRequest
Новая
       2

Самый эффективный способ проверить, существует ли строка в сетке Java

1 голос
/ 18 октября 2011

Все,

Мне интересно, как наиболее эффективно проверить, существует ли уже строка в списке?,У объекта Foo есть пара ключ / значение (а также другие поля, которые не применимы к этому вопросу).Каждый набор в списке уникален.

В качестве примера: 

List[
 Set<Foo>[Foo_Key:A, Foo_Value:1][Foo_Key:B, Foo_Value:3][Foo_Key:C, Foo_Value:4]
 Set<Foo>[Foo_Key:A, Foo_Value:1][Foo_Key:B, Foo_Value:2][Foo_Key:C, Foo_Value:4]
 Set<Foo>[Foo_Key:A, Foo_Value:1][Foo_Key:B, Foo_Value:3][Foo_Key:C, Foo_Value:3]
]

Я хочу иметь возможность проверить наличие нового набора (например: Set [Foo_Key: A, Foo_Value: 1] [Foo_Key: B, Foo_Value:3] [Foo_Key: C, Foo_Value: 4]) существует в списке.

Каждый набор может содержать от 1 до 20 объектов Foo.Список может содержать от 1 до 100 000 комплектов.Не гарантируется, что Foo будут в одном и том же порядке в каждом наборе (так что их придется каким-то образом предварительно отсортировать для правильного порядка, например TreeSet)

Идея 1: Будет ли разумнее повернуть этов матрицу?Где каждый столбец будет Foo_Key, а каждая строка будет содержать Foo_Value?Пример: 

A B C
-----
1 3 4
1 2 4
1 3 3

А затем искать строку, содержащую новые значения?

Идея 2. Будет ли более разумным создать хэш каждого набора, а затем сравнить его с хешемнового набора?

Есть ли более эффективный способ, о котором я не думаю?

Спасибо

Ответы [ 2 ]

2 голосов
/ 18 октября 2011

Если вы используете TreeSets для своего Sets, вы не можете просто сделать list.contains(set), поскольку TreeSet будет обрабатывать проверку equals?

Также рассмотрите возможность использования класса MultSet в Guava. Multiset

0 голосов
/ 18 октября 2011

Я бы порекомендовал вам использовать менее странную структуру данных. Что касается поиска вещей: как правило, есть способы хеширования или сортировки + бинарный поиск или деревья, в зависимости от того, сколько вы ожидаете вставки / удаления. Прочитайте книгу об основных структурах данных и алгоритмах, а не пытайтесь заново изобрести колесо.

Наконец: если это не чисто академический вопрос, прокрутите списки и проведите сравнение. Скорее всего, это приемлемо быстро. Даже 100 000 записей займут доли секунды, и поэтому не имеют значения в 99% всех случаев использования.

Мне нравится цитировать Кнута: Преждевременная оптимизация - корень всего зла.

...