Питон:Zope's BTree OOSet, IISet и т. д. Эффективны ли для этого требования?

StackOverflow https://stackoverflow.com/questions/1183428

  •  19-09-2019
  •  | 
  •  

Вопрос

Я задал еще один вопрос: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
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top