Выборка одного элемента из набора с временной сложностью O(1)
У меня есть набор в Python, и я хочу выбрать из него один элемент, например, с помощью метода random.sample(). Проблема в том, что sample() преобразует набор в кортеж внутри, что равно O(n), и я должен сделать это наиболее оптимальным способом.
Есть ли функция, которую я могу использовать для выборки элемента из набора с временной сложностью O (1), или единственный способ сделать это — создать собственную реализацию набора?
Ответы 1
Поскольку расположение данных нерегулярно, невозможно получить выборку равномерно из основанного на хэше set за O(1), за исключением случаев запросов ω(n) путем предварительной обработки в какой-то массив. (Конечно, такой массив можно сохранить при построении set, но это не исходная точка, и его добавление не быстрее, чем преобразование tuple.)