Преимущество «одномерного» хеша над массивом в Perl

Question

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

Основная причина, которую я хотелиспользовать хеш для этой цели, чтобы я мог использовать функцию существующие, чтобы увидеть, существует ли уже «запись».Хэши также отлично подходят для дублирования ключей, верно?С массивами мне нужно было бы настроить мои собственные проверки с использованием grep, которые, как я полагаю, были бы медленнее.

Этот хеш / массив затем будет повторяться для определенных операций.

Я хотел бы услышать любое понимание этого, и спасибо заранее!

Answer 1

exists $hash{ $key } 

- это хорошее, короткое выражение, понятное и простое в использовании.Очевидно,

!!grep { $_ eq $key } @array

не так коротко, но

$key ~~ @array # smart match

еще короче.Таким образом, начиная с 5.10, просто синтаксически легко проверить умное совпадение как exists.

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

Тем не менее, вы должны Тестировать производительность в любом случае.

---

И вот почему.На Strawberry Perl, даже с размером списка 1, поиск по хешу превосходит совпадение строк:

array_lookup  577701/s           --         -46%
hash_lookup  1068376/s          85%           --

С двумя элементами в списке:

array_lookup  464684/s           --         -57%
hash_lookup  1068376/s         130%           --

И с 20 элементами:

array_lookup  181554/s           --         -83%
hash_lookup  1068376/s         488%           --

Я бы использовал хеш.

Answer 2

В математическом смысле хеш-ключами являются множеств , а массивами - кортежей . Например, кортежи ('apple', 'banana') и ('banana', 'apple') являются разными сущностями, тогда как наборы {'apple', 'banana'} и {'banana', 'apple'} являются одинаковыми.

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

Если вам нужно выполнить операции над множествами, вы можете использовать Set :: Object вместо записи операций с нуля каждый раз.

Если вы собираетесь использовать хеш-ключи для представления набора, установка значений undef вместо 1 может уменьшить объем памяти, который может иметь значение, если ваши наборы большие.

Answer 3

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

Answer 4

Это абсолютно стандартная техника в Perl. Мои собственные сценарии полны кода, подобного этому:

my @elements = (...);
my %is_element = map { $_ => 1 } @elements;

Существует множество примеров переполнения стека, например, здесь и здесь .

Поиск ключа в хэше примерно равен O (1) .