Как реализовано равенство фрозенцет в Python?

Question

Как реализовано равенство фрозенцет в CPython? В частности, я хочу знать, как отдельные элементы в fronzenset сравниваются друг с другом и их общая сложность по времени.

Я взглянул на набор и разницу между фрозэнсетом в реализации и https://stackoverflow.com/a/51778365/5792721.

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

Answer 1

Рассматриваемая реализация может быть найдена здесь . Алгоритм работает примерно так, учитывая, что мы хотим проверить, равны ли два sets v и w:

1. Проверьте, равны ли их размеры. Если это не так, верните false.

Это ссылка на атрибут size PySetObject, так что это операция с постоянным временем.

2. Проверьте, являются ли оба sets frozensets. Если это так, и их хэши разные, верните false.

Опять же, это ссылается на атрибут hash PySetObject, который является операцией с постоянным временем. Это возможно, потому что frozensets являются неизменяемыми объектами и, следовательно, их хэши вычисляются при их создании.

3. Проверьте, является ли w подмножеством v.

Это делается путем итерации каждого элемента v и проверки его наличия в w.

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

Тестирование членства для sets в общем случае требует постоянного времени в среднем случае и линейного времени в худшем случае; объединение этих двух значений дает время, линейное в размере v в среднем случае и время, пропорциональное len(v) * len(w) в худшем случае.

В некотором смысле это средний случай наихудшего случая, поскольку предполагается, что первые две проверки всегда возвращают true. Если ваши данные редко имеют равный размер sets, которые также имеют одинаковые хэши, но содержат разные объекты, то в среднем случае сравнение все равно будет выполняться в постоянное время.

Answer 2

Обе set и frozenset используют функцию set_richcompare() для тестов на равенство. Здесь нет никакой разницы.

set_richcompare(), как уже упоминалось в других ответах, сравнивает размеры и затем хэши. Затем он проверяет, является ли одно подмножеством другого , которое просто зацикливается на каждом элементе в наборе 1, и проверяет, находится ли он в наборе 2. В остальном эта проверка идентична , проверяющей, является ли элемент находится в наборе . Это делается путем поиска в хеш-таблице с линейным поиском по элементам с равными хешами. Сложность для проверки существования O (1) амортизируется или O (len (s)) наихудший случай , поэтому проверка для set_issubset() имеет сложность O (len (s1)) амортизируется, или O (len (s1) * len (s2)) наихудший случай.