C - Сравнение массивов (наборов) целых чисел - хеширование или попытки

Question

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

• Целые бы между 0 и около 200 000
• Количество чисел в одном массиве произвольно, но я полагаю, меньше чем 200
• Порядок целых чисел не имеет значения. Повторения не имеют значения. Таким образом, массив 5 5 7 19 следует рассматривать так же, как 7 5 19 7 7 (их следует рассматривать как множества, а не массивы, в основном)
• Количество создаваемых массивов было бы в сотни тысяч, так что мне это нужно, чтобы быть эффективным

Я думал об использовании некоторой структуры данных trie. Для этого мне нужно будет отсортировать массив, а затем пересечь trie, игнорируя последовательные дубликаты.

Однако попытки обычно используются для символов, где вы знаете, что у всех узлов будет, например, 26 детей, поэтому дети могут быть легко сохранены и обнаружены в массиве из 26 элементов. В моем случае, однако, у меня есть целые числа, которые могут достигать 200 000 - поэтому, очевидно, множество детей недопустимо. Можно ли создать эффективный trie для таких целых чисел?

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

И, наконец, какой из них был бы более эффективным? Или, может быть, какая-то другая структура данных, о которой я не думал?

Answer 1

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