Наборы в python не имеют никаких гарантий относительно заказа. На самом деле это обычно, когда порядок не поддерживается. Например, в моих реализациях Python-2.7 и 3.5.2:
>>> a = set([3,10,19])
>>> a
set([19, 10, 3])
>>> a.add(1)
>>> a
set([19, 1, 10, 3])
>>> a.pop()
19
>>> a.pop()
1
>>> a
set([10, 3])
Порядок иногда поддерживается с set, потому что именно так работают хеш-таблицы. Обычно set начинается как хеш-таблица с size=a*len(hash_table) сегментами. Элемент value вставляется в номер ковша value % size. Для маленьких и плотных целых чисел value < size. Это означает, что в таких случаях value вставляется в номер корзины value, который является сортировкой порядка значений.
Это показывает, что в некоторых случаях неудивительно, когда set поддерживает отсортированный порядок, но это не так. Дело в том, почему класс RandomizedCollection работает.
На самом деле обе реализации
RandomizedCollection имеют одинаковую концептуальную структуру данных.
self.stack варианта на основе списка читается и обновляется точно так же, как
self.nums варианта на основе
set. Они оба поддерживают плоский список всех элементов в объекте
RandomizedCollection.
Реализация на основе списка использует тот факт, что self.myMap[val] является отсортированным списком только в remove() at:
last_val = self.stack[-1]
self.myMap[last_val].pop() ## removes the last index
Поскольку self.myMap[last_val] является отсортированным списком индексов, его последний элемент должен быть последним last_val элементом в self.stack. Поскольку last_val было взято с конца self.stack, то последний элемент self.myMap[last_val] гарантированно указывает на len(self.stack)-1). Это означает, что выталкивание последних элементов как self.stack, так и self.myMap[last_val] сохранит структуру данных согласованной. За исключением двух вышеупомянутых строк, создание self.myMap[val] отсортированного списка приводит только к затратам. Поиск по индексу в списке O(log K) и вставка O(K).
Решение на основе set работает в другом порядке. Вместо удаления индекса, который указывает на конец стека в O (1):
self.myMap[last_val].pop() # (Sorted list variant)
Стирает тот же элемент, используя возможности O (1) set:
self.num_map[last_val].remove(last_index)
Эффект тот же. В обоих случаях карта больше не указывает на последний элемент в стеке. Заказывать set не нужно, только чтобы можно было удалить элементы в O (1). В конце концов, последний элемент в стеке будет удален простым self.stack.pop() или self.nums.pop().
Иногда это был не последний элемент, который нужно было удалить, но код все равно удалил его. Идея состоит в том, чтобы затем удалить правильный элемент и поместить «неправильно» удаленный элемент вместо него. Решение с отсортированным списком усердно работает в O (K), чтобы заново вставить удаленный элемент:
insert_pos = bisect.bisect_left(self.myMap[last_val],idx_to_remove)
self.myMap[last_val].insert(insert_pos,idx_to_remove)
В случае set это довольно просто, так как заказ не требуется:
self.num_map[last_val].add(index)
И, наконец, массив, который содержит фактические значения (self.nums и self.stack), обновляется таким образом, чтобы последний элемент был окончательно удален и снова вставлен вместо элемента, который должен был быть удален в первую очередь.
Подводя итог, обе структуры данных эквивалентны. В одном набор индексов поддерживается как отсортированный список, а в другом - как
set. Код в варианте отсортированного списка иногда использует тот факт, что список отсортирован, чтобы удалить самый большой элемент в O (1). Однако для случая
set такая оптимизация не требуется, поскольку для удаления любого элемента используется O (1), и вместо
pop(). можно использовать
remove().