пытаясь найти наиболее оптимальную структуру данных в python3 для более сложной задачи, которую я должен разработать, только что понял, что сложность использования модуля bisect для упорядочения в реальном времени insert - это не O (nlog n), как должно быть, а вместо этого растет в геометрической прогрессии. Я не знаю причины этого, так что я хотел спросить вас, ребята, на всякий случай, узнайте что-нибудь об этом, потому что я нахожу это действительно интересным.
думаю, что я использую модуль правильно, так что это не должно быть проблемой с моей стороны, в любом случае, вот код, используемый для вставки объектов узлов, определяющий, что вставка с помощью случайных узлов значения f имеет.
bisect.insort(self._frontier, (node._f, node))
получение большого количества объектов за несколько секунд, но не так много с течением времени. Бакуриу предложил мне задать этот вопрос, поскольку он также нашел его интересным после выполнения некоторых тестов и получения таких же результатов, как и у меня. код, который он использовал для проверки, был следующим:
python3 -m timeit -s 'import bisect as B; import random as R;seq=[]' 'for _ in range(100000):B.insort(seq, R.randint(0, 1000000))'
Это были его выводы:
10 тыс. Вставок все в порядке (80 мс и до этого момента оно в основном масштабируется линейно [имейте в виду, что это O (nlog n), так что это немного хуже, чем линейное)), но при 100 тыс. Это занимает целую вечность вместо 10 раз больше. Список из 100 тыс. Элементов не так уж велик, а log (100 тыс.) - 16, поэтому он не такой большой.
любая помощь будет высоко ценится!