Питон:Zope's BTree OOSet, IISet и т. д. Эффективны ли для этого требования?
Вопрос
Я задал еще один вопрос:https://stackoverflow.com/questions/1180240/best-way-to-sort-1m-records-in-python где я пытался определить лучший подход для сортировки 1 миллиона записей.В моем случае мне нужно иметь возможность добавлять в коллекцию дополнительные элементы и использовать их.Мне предложили использовать для этой задачи BTree от Zope.Прочитав немного, я немного озадачен тем, какие данные я бы поместил в набор.
По сути, для каждой записи у меня есть два фрагмента данных.1.Уникальный идентификатор, который соответствует пользователю и 2.интересующее значение для сортировки.
Я вижу, что могу добавлять элементы в OOSet в виде кортежей, где значение для сортировки имеет индекс 0.Так, (200, 'id1'),(120, 'id2'),(400, 'id3')
и полученный набор будет отсортирован с помощью id2, id1 and id3
чтобы.
Однако частью требования для этого является то, чтобы каждый идентификатор появлялся в наборе только один раз.Я буду периодически добавлять в набор дополнительные данные, и новые данные могут включать или не включать повторяющиеся «идентификаторы».Если они дублируются, я хочу обновить значение, а не добавлять дополнительную запись.Итак, основываясь на приведенных выше кортежах, я мог бы добавить (405, 'id1'),(10, 'id4')
в набор и хотел бы, чтобы результат имел id4, id2, id3, id1
чтобы.
Любые предложения о том, как это сделать.Извините за мою новизну в этой теме.
* РЕДАКТИРОВАТЬ - дополнительная информация *
Вот реальный код из проекта:
for field in lb_fields:
t = time.time()
self.data[field] = [ (v[field], k) for k, v in self.foreign_keys.iteritems() ]
self.data[field].sort(reverse=True)
print "Added %s: %03.5f seconds" %(field, (time.time() - t))
Foreign_keys — это исходные данные в словаре, где каждый идентификатор является ключом, а словарь дополнительных данных — значением.data — словарь, содержащий списки отсортированных данных.
В качестве примечания: при каждой итерации поля for в lb_fields время сортировки увеличивается - ненамного...но это заметно.После того, как 1 миллион записей был отсортирован для каждого из 16 полей, он использует около 4 гигабайт или ОЗУ.В конечном итоге это будет работать на машине с 48 гигабайтами.
Решение
Я не думаю, что BTrees или другие традиционные структуры отсортированных данных (красно-черные деревья и т. д.) помогут вам, потому что они сохраняют порядок по ключу, а не по соответствующему значению - другими словами, поле, которое они гарантируют как уникальное, одно и то же. тот, который они заказывают.Ваши требования разные, потому что вам нужна уникальность по одному полю и сортировка по другому.
Каковы ваши требования к производительности?С довольно простой реализацией на чистом Python, основанной на диктатах Python для уникальности и сортировках Python, на не очень быстром ноутбуке я получаю 5 секунд для исходной конструкции (по сути, сортировка по миллиону элементов, начиная с них как dict) и около 9 секунд для «обновления» с 20 000 новыми парами идентификатор/значение, половина из которых «перекрывает» (таким образом, перезаписывает) существующий идентификатор, а половина — новые (я могу реализовать обновление более быстрым способом, около 6,5 секунд, но эта реализация имеет аномалию:если одна из «новых» пар в точности идентична одной из «старых», как по идентификатору, так и по значению, она дублируется — защита от такого «дублирования идентичных» — это то, что подталкивает меня с 6,5 секунд до 9, и я представляю вам потребуются такие же меры предосторожности).
Насколько эти 5 и 9 секунд далеки от ваших требований (с учетом фактической скорости компьютера, на котором вы будете работать, по сравнению с процессором Core Duo 2,4 ГГц, 2 ГБ ОЗУ и типичными проблемами производительности этого ноутбука?) пользуюсь)?IOW, достаточно ли это близко к «дистанции удара», чтобы стоит повозиться и попытаться выжать последние несколько циклов, или вам нужна производительность на порядки выше?
Я пробовал несколько других подходов (с базой данных SQL, с C++ и его std::sort &c,...), но все они медленнее, поэтому, если вам нужна гораздо более высокая производительность, я не уверен, что вы можете сделать. .
Редактировать:поскольку ОП говорит, что эта производительность будет хорошей, но он не может ее достичь, я думаю, мне лучше показать сценарий, который я использовал для измерения этого времени...:
import gc
import operator
import random
import time
nk = 1000
def popcon(d):
for x in xrange(nk*1000):
d['id%s' % x] = random.randrange(100*1000)
def sorted_container():
ctr = dict()
popcon(ctr)
start = time.time()
ctr_sorted = ctr.items()
ctr_sorted.sort(key=operator.itemgetter(1))
stend = time.time()
return stend-start, ctr_sorted
def do_update(ctr, newones):
start = time.time()
dicol = dict(ctr)
ctr.extend((k,v) for (k,v) in newones if v!=dicol.get(k,None))
dicnu = dict(newones)
ctr.sort(key=operator.itemgetter(1))
newctr = [(k,v) for (k,v) in ctr if v==dicnu.get(k,v)]
stend = time.time()
return stend-start, newctr
def main():
random.seed(12345)
for x in range(3):
duration, ctr = sorted_container()
print 'dict-to-sorted, %d: %.2f sec, len=%d' % (x, duration, len(ctr))
newones = [('id%s' % y, random.randrange(nk*100))
for y in xrange(nk*990,nk*1010)]
duration, ctr = do_update(ctr, newones)
print 'updt-to-sorted, %d: %.2f sec, len=%d' % (x, duration, len(ctr))
del ctr
gc.collect()
main()
и это типичный запуск:
$ time python som.py
dict-to-sorted, 0: 5.01 sec, len=1000000
updt-to-sorted, 0: 9.78 sec, len=1010000
dict-to-sorted, 1: 5.02 sec, len=1000000
updt-to-sorted, 1: 9.12 sec, len=1010000
dict-to-sorted, 2: 5.03 sec, len=1000000
updt-to-sorted, 2: 9.12 sec, len=1010000
real 0m54.073s
user 0m52.464s
sys 0m1.258s
общее затраченное время на несколько секунд больше, чем общее количество, которое я измеряю, очевидно, потому что оно включает в себя время, необходимое для заполнения контейнера случайными числами, генерации «новых данных» также случайным образом, уничтожения и сбора мусора в одно и то же время. конце каждого запуска и так далее.
Это с поставляемым системой Python 2.5.2 на Macbook с Mac OS X 10.5.7, Intel Core Duo 2,4 ГГц и 2 ГБ ОЗУ (время не сильно меняется, когда я использую разные версии Python).
Другие советы
Вполне возможно решить вашу проблему.Для этого вам следует просто отметить, что типы контейнеров в Python всегда сравнивайте объекты, вызывая их методы.Поэтому вам следует сделать что-то вроде:
class Record:
'Combination of unique part and sort part.'
def __init__(self, unique, sort):
self.unique = unique
self.sort = sort
def __hash__(self):
# Hash should be implemented if __eq__ is implemented.
return hash(self.unique)
def __eq__(self, other):
return self.unique == other.unique
def __lt__(self, other):
return self.sort < other.sort
records = btree((Record(u, s) for u, s in zip(unique_data, sort_data)))
print(records.pop())
Примечания:
- в зависимости от того, как реализован ваш любимый тип контейнера, вам также может потребоваться добавить методы для !=, <=, >, >=.
- это не нарушит связь между == и <=, пока
x.unique == y.unique
==>x.sort == y.sort