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

Я не думаю, что 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