Python : Zope의 BTree OOSet, IISet 등 ...이 요구 사항에 효과적입니까?

Question

나는 또 다른 질문을했다. https://stackoverflow.com/questions/1180240/best-way-to-sort-1m-records-in-python 나는 1 백만 개의 레코드를 분류하는 최선의 방법을 결정하려고 애썼다. 필자의 경우 컬렉션에 추가 항목을 추가 할 수 있어야합니다. 이 작업을 위해 Zope의 BTrees를 사용해 보도록 제안되었습니다. 몇 가지 독서를 한 후에 나는 어떤 데이터를 세트에 넣을 지에 대해 다소 혼란 스럽습니다.

기본적으로 각 레코드에 대해 두 가지 데이터가 있습니다. 1. 사용자에게 매핑되는 고유 ID 및 2. 정렬에 대한 관심 값.

OOSet에 항목을 튜플로 추가 할 수 있습니다. 여기서 정렬을위한 값은 인덱스 0에 있습니다. 따라서 (200, 'id1'),(120, 'id2'),(400, 'id3')과 결과 집합은 id2, id1 and id3 순으로 정렬됩니다.

그러나이 요구 사항의 일부는 각 ID가 집합에 한 번만 표시된다는 것입니다. 나는 주기적으로 추가 데이터를 추가 할 것이고 새로운 데이터는 중복 된 'ids'를 포함 할 수도 있고 포함하지 않을 수도 있습니다. 중복 된 경우 값을 업데이트하고 추가 항목을 추가하지 않습니다. 위의 튜플에 기반하여 (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 키와 사전의 각 ID로 사전에 원본 데이터입니다 추가 데이터를 값으로 사용합니다. data는 정렬 된 데이터 목록을 포함하는 사전입니다.

부수적으로, lb_fields의 for 필드의 각 itereation이 실행됨에 따라 정렬 시간이 늘어나지 만별로 눈에 띄지 않습니다. 16 개의 필드 각각에 대해 1 백만 개의 레코드가 정렬 된 후 약 4 개의 기가 또는 RAM을 사용합니다. 결국 이것은 48 기가의 컴퓨터에서 실행됩니다.

Answer 1

BTrees 또는 기타 전통적인 정렬 된 데이터 구조 (빨간색 - 검은 색 나무 등)가 해당 값으로가 아니라 키별로 정렬을 유지하기 때문에 도움이 될 것이라고 생각하지 않습니다. 즉, 고유 한 항목은 주문한 항목과 동일합니다. 한 필드에서 고유성을 원하지만 다른 필드에서는 정렬을 원하기 때문에 요구 사항이 다릅니다.

성능 요구 사항은 무엇입니까? 독창성과 파이썬 정렬을 기반으로하는 Python을 기반으로 한 다소 단순한 순수 Python 구현을 사용하여 필자가보기에 너무 빠르지 않은 랩톱에서 원래 구성 (기본적으로 DML으로 시작하는 백만 개 요소를 정렬) , 기존 ID와 절반의 "중복"(따라서 덮어 쓰기)이 절반 인 새로운 ID/값 쌍 20,000 개가있는 "업데이트"의 경우 약 9 초 (새로운 방법은 6.5 초 정도 소요됩니다. 이 구현에는 예외가 있습니다. "새로운"쌍 중 하나가 "이전"것 중 하나 인 ID와 값 모두 정확히 일치하면 중복됩니다. "동일 함의 중복"에 대한 경합은 6.5 초 ~ 9, 그리고 나는 당신이 같은 종류의 예방책을 필요로한다고 상상한다).

요구 사항의 5 초 및 9 초 소요 시간 (2.4 GHz Core Duo, 2GB RAM 및 일반적인 노트북 성능 문제에 대해 실행중인 시스템의 실제 속도를 고려하십시오) 내가 사용하고있는이 노트북의)?IOW, "거리를 두드려서"땜질 할 가치가 있고 마지막 몇 사이클을 짜내는 데 충분합니까? 아니면 몇 배 빠른 성능이 필요합니까?

나는 (SQL DB와 함께 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 

전체 경과 시간은 임의의 숫자와 컨테이너를 채우는 데 필요한 시간을 포함하기 때문에 내가 분명히 측정하고 있습니다 합계보다 몇 초 더되고, "새로운 데이터"를 생성한다. 무작위로, 각 실행의 끝에서 물건을 파괴하고 쓰레기를 모으는 등등.

Mac OS X 10.5.7, 2.4GHz Intel Core Duo 및 2GB RAM이 장착 된 Macbook의 시스템 제공 Python 2.5.2 (다른 버전의 Python을 사용하면 시간이 많이 변하지 않습니다.).

Answer 2

문제를 완벽하게 해결할 수 있습니다. 이를 위해서는 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