Проверка на наличие дублирующихся массивов, когда у меня огромное количество массивов

Question

Я считаю различные шаблоны в графах и храню соответствующую информацию в defaultdict списков пустых массивов размера N, где значения индекса являются целыми числами.

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

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

Спасибо.

Answer 1

Основная идея заключается в следующем: «Как я могу использовать свои собственные hash (и, возможно, ==) для хранения вещей по-разному в set / dict?» (Где «по-разному» включает в себя «без повышения * 1005»).* за отсутствие хэширования).

первая часть ответа определяет вашу хэш-функцию, например, следуя комментарию myrtlecat .Однако остерегайтесь стандартного отсутствия ответа на его основе: сохраните пользовательский хэш каждого объекта в set (или сопоставьте его, скажем, с исходным объектом с dict).То, что вам не нужно предоставлять реализацию равенства, является намеком на то, что это неправильно: хеш-значения не всегда всегда уникальны!(Исключение: если вы хотите «хешировать по идентичности» и знать, что все ваши ключи переживут карту, id действительно предоставляют уникальные «хэши».)

Ответ rest состоит в том, чтобы обернуть нужные ключи в объекты, которые отображают ваши функции хеширования / равенства как __hash__ и __eq__.Обратите внимание, что переопределение не хэш-возможности изменяемых типов сопровождается обязательством не изменять (базовых) ключей!(Программисты на С часто называют это неопределенным поведением .)

Код см. В старом ответе xperroni (который включает в себя возможность повысить безопасность, основываясравнения для частных копий, которые с меньшей вероятностью будут изменены каким-либо другим кодом), хотя я бы добавил __slots__ для борьбы с перегрузкой памяти.