2

Вопрос по complexity-theory, dictionary, hashtable, memory, python – Оптимизация наихудшего случая Временная сложность до O (1) для python dicts [закрыто]

Я должен хранить 500M двухзначный символ Unicode в памяти (RAM). Структура данных, которую я использую, должна иметь: Worst Case Space Complexity: O(n) Worst Case Time Complexity: O(1) Я думал о выборе dict, который представляет собой ...

<span>@ UtxD: я понимаю - я думал о 32-битной системе, в которой int занимал бы столько же места, что и два символа юникода, но в 64-битной системе ...</span>

от David Robinson

<span>@ UtxD: Конечно, я знаю этовозможно. Не уверен, почему тыбуду использовать пары символов вместо целых, но я полагаю,Это то же самое. Во всяком случае, другие ответы верны.</span>

от David Robinson

<span>@ UtxD: 500 миллионов уникальных пар символов юникода? Хлоп.</span>

от David Robinson

<span>@DavidRobinson: я думаю, Unicode может предоставить 110 000 * 110 000 уникальных пар. Мы используем его для создания уникальных ключей здесь.</span>

от codersofthedark

3 ответа

2

Словарь технически имеет худший случай O (n), но это 'очень маловероятно, чтобы произойти и, вероятно, выигралт в твоем случае. Я'попробуйте использовать словарь и переключаться на другую реализацию, только еслит достаточно для того, что вы хотите сделать.

Вот полезная ветка на эту тему

4

Чаще всего хиты производительности (обычно принимаемые при столкновении) амортизируются по всем вызовам. Так что для наиболее реалистичного использования вы не получитеO(n) за каждый звонок. На самом деле, единственный случай, когда вы понесетеO(n) попадание на каждый звонок происходит в патологическом случае, когда каждый ключхеш сталкивается с существующим ключомs хэш-значение (т.е. наихудшее (или самое неудачное) использование хеш-таблицы).

Например, если вы заранее знаете свой набор ключей и знаете, что у них не будет коллизий хешей (т. Е. Все их хэши уникальны), вы не столкнетесь с коллизиями. Другой крупныйO(n) операция имеет изменение размера хеш-таблицы, но частота этого зависит от реализации (коэффициент расширения / хэш-функция / схема разрешения коллизий и т. д.), и она также будет варьироваться в зависимости от входного набора.

В любом случае вы можете избежать внезапного замедления времени выполнения, если сможете предварительно заполнить dict всеми ключами. значения могут быть просто установлены на None, а затем заполнены их реальными значениями. Это должно вызвать единственное заметное снижение производительности, когда "грунт» Первоначально диктовка с ключами и будущее значение должны быть постоянными.

Совершенно другой вопрос, как вы собираетесь читать / запрашивать структуру? Вам нужно прикрепить отдельные значения и иметь доступ к ним через ключ? это должно быть заказано? возможноset может быть более подходящим, чемdict, так как вам на самом деле не требуетсяkey:value отображение.

Обновить:

Исходя из вашего описания в комментариях, это начинает звучать больше как работа для базы данных, даже если вы работаете с временным набором. Вы можете использовать реляционную базу данных в памяти (например, с SQLite). Кроме того, вы можете использовать ORM, такой как SQLAlchemy, для более питонного взаимодействия с базой данных без необходимости написания SQL.

Может даже показаться, что для начала вы читаете данные из базы данных, так что, может быть, вы можете использовать это дальше?

Хранение / запрос / обновление огромного количества типизированных записей с уникальным ключом - это именно то, что СУБДs были специализированы на протяжении десятилетий разработки и исследований. Использование версии в памяти ранее существовавшей реляционной базы данных (такой как SQLite 's) вероятно, будет более прагматичным и устойчивым выбором.

Попробуйте использовать Pythonвстроенныйsqlite3 модуль и попробуйте версию в памяти, предоставив":memory:" как путь к файлу БД на стройке:

con = sqlite3.connect(":memory:")
2

Есть ли причина, по которой вы заботитесь о производительности в худшем случае, а не о средней производительности? Любая разумная хеш-таблица даст вам среднюю производительность O (N).

Если вы действительно хотите производительность O (1) в худшем случае, вот два возможных подхода:

  1. Есть векторmax(charCode)-min(charCode) записей и непосредственно найдите нужное значение из кода символа Unicode. Это будет хорошо работать, если ваши ключи попадают в достаточно компактный диапазон, чтобы вы могли разместить его в оперативной памяти.

  2. Используйте метод грубой силы, чтобы выбрать хеш-функции или размеры словаря (используя пользовательскую реализацию словаря, который позволяет вам управлять этим), и продолжайте пробовать новые функции и / или размеры, пока не получите одну из них без коллизий. Ожидайте, что это займет очень много времени.Я не рекомендую это.

РЕДАКТИРОВАТЬ:

Предположим, что вы знаете, что минимальный код символа, который выувидим 1234 и максимум у тебяПосмотрим, будет 98765. Далее, предположим, что у вас достаточно ОЗУ для хранения 98765-1234 элементов. Я'также предположим, что выготовы использоватьnumpy библиотека или другая эффективная реализация массива. В этом случае вы можете сохранить значения в векторе следующим образом:

# configuration info
max_value = 98765 # replace with your number
min_value = 1234  # replace with your number
spread = (max_value - min_value)
dtype = object # replace with a primitive type if you want to store something simpler

# create the big vector
my_data = numpy.empty((spread,), dtype=dtype)

# insert elements
my_char_code              = ...
my_value_for_my_char_code = ...

assert min_value <= my_char_code < max_value
my_data[my_char_code - min_value] = my_value_for_my_char_code

# extract elements
my_char_code              = ...
assert min_value <= my_char_code < max_value
my_value_for_my_char_code = my_data[my_char_code - min_value]

Это O (1), потому что поиск реализован с использованием арифметики указателей иНе зависит от количества элементов, хранящихся в массиве.

Этот подход может быть чрезвычайно бесполезным в ОЗУ, если количество элементов, которые вы действительно хотите сохранить, намного меньше, чемspread, Например, еслиspread 4 миллиарда (все UTF32) тогдаmy_data один будет потреблять не менее 4 миллиардов * 8 байт / указатель = 32 ГБ ОЗУ (и, вероятно, намного больше; я нене знаю, насколько большие ссылки на Python). С другой стороны, еслиmin_value 3 миллиардаmax_value = min_value + 100, то использование памяти будет крошечным.

Похожие вопросы