Сильно-ли замедляется доступ к объектам словаря при большом количестве?

Question

[Ivan Yakushenko]

К примеру, есть словарь, в котором используются статусы функций во время исполнения программы, потенциально их может стать большое количество. Когда словарь почти пустой, то команда типа status.get(pid) выполняется мгновенно, но если объектов в словаре будет 100/1000/10000/... с какой скоростью будет осуществляться доступ и вообще будет-ли происходить замедление?

Comments

[rPman]

обычно разработчики в таких случаях за минуту пишут тестовое приложение из 10 строчек и тестируют в своих условиях и на своих данных.

Answer 1

[Roman K]

Если у ключей будет плохая хэш-функция (__hash__) — замедление будет сильное. Например, если все ключи будут отдавать хэш 42. Тогда открытая адресация просто умрёт, пытаясь найти очередную свободную ячейку в хэш-таблице.

В остальном, хоть 100, хоть 10000000 — неважно. Вероятность коллизии примерно одинаковая. И амортизированная сложность вставки/получения/удаления элемента — O(1)

Comments

[Ivan Yakushenko]

Не использовал хэш.
Просто заполняю status.update(pid, get_status()) и потом обращаюсь if status.get(pid) == 0:

[Roman K]

Ivan Yakushenko, что является ключом? pid — это число или строка? Тогда идеально

[Ivan Yakushenko]

Roman Kitaev, pid - это число.

[Ivan Yakushenko]

Roman Kitaev, еще одно - раз в сутки скрипт перезапускается, соответственно status очищается. Пока что максимальное кол-во обращений было в районе 1500, соответственно и записей типа pid = {024635: 0} такое-же.

[Roman K]

Ivan Yakushenko, 1500 — это вообще не данные. Когда будет несколько миллионов — приходите.

[Ivan Yakushenko]

Roman Kitaev,

что является ключом? pid — это число или строка? Тогда идеально

А что должно быть в ячейке, что-бы было "не идеально"? Другой словарь/список?

[Roman K]

Ivan Yakushenko, другой словарь/список ты не сможешь сделать ключом. Например, объект собственно написанного класса.

Answer 2

[alternativshik]

https://wiki.python.org/moin/TimeComplexity
Для dict там внизу данные.

Answer 3

[aRegius]

Big-O Efficiency of Python Dictionary Operations

Answer 4

[Владимир]

если много дынных то лучше использовать redis

Comments

[sim3x]

Нет

[Владимир]

sim3x, глубина мысли и особенно аргументы меня поразили, согласен. Ваш аргумент сильнее и я просто безропотно перед ним склоняюсь

[Roman K]

Владимир, Ну а кто тебе виноват, что ты херню советуешь? Скорость редиса и скорость словаря просто несравнимы. Редис нужен для других целей.

[Владимир]

Roman Kitaev, ИМХО, судя по вопросам автора он делает что-то многопоточное с высокой скоростью записи. также понятно, что он новичок в питоне. поэтому, по моему мнению, ему проще и безопаснее будет освоить редис как хранилище. можете быть несогласным, это Ваше право.

[Ivan Yakushenko]

Владимир, неа, многие вопросы от совершенно разных приложений.
В целом для приложения, для которого хотел "прикрутить" базу я пробовал redis, postgresql. Redis жрет много ОЗУ - был выкинут сразу, "объемные" sql запросы слишком сильно засоряли код, т.к. их было много, хотя в целом о postgresql лично для себя сделал только один вывод: "зачем?". Пробовал извращение типа tinydb - то-ли я дурак (это факт, но в случае tinydb возможно было исключение), то-ли tinydb хлама кусок: частенько происходила "кривая" запись в db.json, из-за чего он становился невалидным и все крашилось, за скорость работы, ввиду выключенного кэширования по определенным обстоятельствам, я вообще молчу - ниже, такое ощущение, быть она в принципе не может. Читал много хвалебных отзывов о mongo, мол тоже построен на концепции документов json - попробую, но не сейчас. В любом случае в приложении была полностью изменена логика - все теперь работает сугубо в динами, а выходные данные, которые прям очень нужно сохранить - записываю в csv.

[Roman K]

Владимир, многопоточное как раз может юзать один пошареный словарь. Если бы у него было несколько процессов — другой вопрос. Хотя и там через менеджер можно получить пошаренный словарь. Но я бы не стал.