Какую структуру данных я должен использовать для хэша без значений?

Question

Мне нужно проверить, существует ли скаляр в наборе скаляров. Каков наилучший способ хранения этого набора скаляров?

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

Answer 1

Используйте хеш, но не используйте значения. Там действительно нет лучшего способа.

Answer 2

Хеш должен работать нормально. Вы можете использовать undef для значения и использовать exists($h{$k}), или вы можете использовать 1 и использовать $h{$k}.

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

Answer 3

Затраты памяти на использование хэша для проверки на членство в наборе минимальны и значительно превышают стоимость повторных последовательных поисков в массиве. Есть много способов создать хэш стиля членства:

my %set = map {$_ => 1} ...;

my %set; $set{$_}++ for ...;

my %set; @set{...} = (1) x num_of_items;

Каждый из них позволяет использовать поиск по хэшу напрямую в условном выражении без какого-либо дополнительного синтаксиса.

Если ваш хеш будет огромным, и вы беспокоитесь об использовании памяти, вы можете сохранить undef в качестве значения для каждого ключа. Но в этом случае вам придется использовать exists $set{...} в ваших условных выражениях.

Answer 4

Этот раздел часто задаваемых вопросов может оказаться полезным:

Как узнать, содержится ли определенный элемент в списке или массиве?

Answer 5

HashTable - лучший вариант.

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

Answer 6

Можно выполнить итерацию по массиву:

my @arr = ( $list, $of, $scalars );
push @arr, $any, $other, $ones;

Просматривать дорого, но не так дорого, если у вас нет огромного списка:

grep { $_ eq $what_youre_looking_for } @arr;

Метод хеширования также работает:

my %hash = ( $list => 1, $of => 1, $scalars => 1 );
$hash{$another} = 1;

if ( exists $hash{$what_youre_looking_for} ) {
    ...
}

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