Большие сортируемые структуры данных? Словарь или что-то еще?

Question

У меня большой словарь Python (65535 ключ: пары значений), где ключ - это диапазон (0, 65536), а значения - целые числа.

Решение, которое я нашел для сортировки этой структуры данных, размещено здесь: Сортировать словарь Python по значению

Это решение работает, но не обязательно очень быстро.

Чтобы еще больше усложнить проблему, у меня есть возможность иметь много (тысячи) этих словарей, которые я должен объединить перед сортировкой. В настоящее время я объединяю эти словари, перебирая пары в одном словаре, выполняя поиск ключей в другом словаре и добавляя / обновляя запись по мере необходимости.

Это делает мой вопрос двояким:

1) Является ли словарь правильной структурой данных для этой проблемы? Будет ли смысл иметь собственное дерево или что-то еще?

2) Если словарь - разумный, разумный выбор, каков идеальный способ объединить кратные словари и затем отсортировать их?

Одним из решений для меня может быть перепроектирование потока моей программы, чтобы уменьшить количество поддерживаемых словарей до одного, хотя это скорее последнее средство.

Спасибо

Answer 1

Словарь, заполненный 65535 записями с ключами из диапазона (0: 65536), звучит подозрительно как массив.Если вам нужны отсортированные массивы, почему вы используете словари?

Обычно в Python вы используете список данных этого типа.В вашем случае, поскольку значения являются целыми числами, вы также можете рассмотреть возможность использования модуля массива.Вы также должны взглянуть на модуль heapq, поскольку, если ваши данные могут быть представлены таким образом, есть встроенная функция слияния, которую можно использовать.

В любом случае, если вам нужно объединить структуры данных ив результате вы получите отсортированную структуру данных, лучше всего использовать алгоритм слияния, и одна из возможностей - алгоритм слияния.

Answer 2

С таким количеством данных я бы укусил пулю и использовал встроенный модуль sqlite.Да, вы отказываетесь от некоторой гибкости Python и вынуждены использовать SQL, но сейчас он сортирует 65k значений;Следующим будет поиск значений, соответствующих определенным критериям.Таким образом, вместо того, чтобы изобретать реляционные базы данных, просто идите по пути SQL.

Answer 3

Здесь недостаточно информации, чтобы сказать, какую структуру данных вам следует использовать, потому что мы не знаем, что еще вы с ней делаете.

Если вам нужно быстро вставить записи вструктура данных позже по одному, тогда вам нужна древовидная структура данных, которая, к сожалению, не имеет стандартной реализации (или даже стандартного интерфейса для некоторых операций) в Python.

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

Вот простой пример, преобразование dicts в список или кортежи, сортировка комбинированных результатови использование модуля bisect для поиска элементов.

Обратите внимание, что у вас могут быть дубликаты ключей, которые отображаются более чем в одном поле.Это легко сделать: они будут естественным образом отсортированы, а разделение на две части даст вам диапазон [start, end), содержащий все эти ключи.

Если вы хотите добавить блоки данных позже, добавьте ихдо конца и пересортировать список;Сортировка Python хороша в этом и, вероятно, будет намного лучше, чем O (n log n).

Этот код предполагает, что ваши ключи, как вы сказали, целые.

dataA = { 1: 'data1', 3: 'data3', 5: 'data5', 2: 'data2' }
dataB = { 2: 'more data2', 4: 'data4', 6: 'data6' }

combined_list = dataA.items() + dataB.items()
combined_list.sort()
print combined_list

import bisect
def get_range(data, value):
    lower_bound = bisect.bisect_left(data, (value, ))
    upper_bound = bisect.bisect_left(data, (value+1, ))
    return lower_bound, upper_bound

lower_bound, upper_bound = get_range(combined_list, 2)
print lower_bound, upper_bound
print combined_list[lower_bound:upper_bound]