Python : Zope의 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 백만 레코드를 정렬하기위한 최상의 접근법을 결정하려고했던 곳. 제 경우에는 컬렉션에 추가 항목을 추가하고 리조트를 할 수 있어야합니다. 이 작업에 Zope의 Btrees를 사용해 보라고 제안되었습니다. 몇 가지 독서를 한 후에 나는 세트에 어떤 데이터를 넣을 것인지에 대해 약간 혼란스러워합니다.

기본적으로 각 레코드마다 두 개의 데이터가 있습니다. 1. 사용자에게 매핑하는 고유 ID 및 2. 정렬을위한 관심 가치.

정렬 값이 색인 0에있는 튜플로 ooset에 항목을 추가 할 수 있습니다. (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))

외국 _keys는 각 ID를 키로 사용하는 사전의 원래 데이터이며 추가 데이터의 사전은 값으로 값입니다. 데이터는 정렬 된 데이터 목록을 포함하는 사전입니다.

부수적으로, LB_Fields의 For Field의 각 반복이 실행됨에 따라 분류 할 시간은 크게 증가하지는 않지만 눈에 띄게됩니다. 16 개의 필드 각각에 대해 1 백만 개의 레코드가 정렬 된 후 약 4 개의 공연 또는 RAM을 사용하고 있습니다. 결국 이것은 48 개의 공연이있는 기계에서 실행됩니다.

도움이 되었습니까?

해결책

나는 Btrees 또는 기타 전통적인 분류 데이터 구조 (Red-Black Tree 등)가 해당 값이 아니라 키에 따라 주문을 유지하기 때문에 도움이 될 것이라고 생각하지 않습니다. 즉, 고유 한 필드는 동일합니다. 하나는 그들이 주문합니다. 한 필드를 따라 독창성을 원하지만 다른 필드는 분류를 원하기 때문에 요구 사항은 다릅니다.

성능 요구 사항은 무엇입니까? 독창성과 파이썬 정렬을위한 파이썬 딕트를 기반으로 한 단순한 순수한 파이썬 구현을 통해, 불가피하게 빠른 노트북에서, 나는 원래 구조에 대해 5 초를 얻습니다 (본질적으로 백만 개 이상의 요소를 넘어서서, 그들로 시작). , 20,000 개의 새로운 ID/값 쌍이있는 "업데이트"의 약 9 초 동안 절반 "오버 랩"(따라서 덮어 쓰기) 기존 ID와 절반은 새로 새로운 것입니다 (약 6.5 초 동안 더 빠른 방식으로 업데이트를 구현할 수 있습니다. 그 구현에는 변칙이 있습니다. "새로운"쌍 중 하나가 "오래된"쌍 중 하나와 정확히 동일하다면, ID와 가치가 모두 복제된다. 9 시까 지, 나는 당신이 같은 종류의 예방 조치가 필요하다고 생각합니다).

요구 사항에서 5-9 초가되는 시간 (2.4GHz 코어 듀오, 2GB RAM 및이 노트북 I의 일반적인 노트북 성능 문제에서 실행할 기계의 실제 속도를 고려하여 얼마나 멀리 떨어져 있습니까? 'm 사용)? IOW, "눈에 띄는 거리"에 충분히 가깝습니까? 마지막 몇 사이클을 짜내고 짜내려고 할 가치가 있습니까?

나는 몇 가지 다른 접근법을 시도했지만 (C ++ 및 std :: sort & c, ...) SQL DB와 함께 사용했지만 모두 느리기 때문에 더 높은 성능이 필요하면 무엇을 할 수 있는지 확실하지 않습니다. .

편집하다: OP는이 성능이 괜찮을 것이라고 말하지만 근처에서는 달성 할 수 없다고 말하면서이 시간을 측정하는 데 사용한 대본을 가장 잘 보여줄 것 같습니다 ... :

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을 사용하면 시간이 크게 변경되지 않음).

다른 팁

문제를 해결하는 것이 완벽하게 가능합니다. 이를 위해서는 컨테이너가 파이썬의 유형에 유의해야합니다. 언제나 방법을 호출하여 물체를 비교하십시오. 따라서 다음과 같은 작업을 수행해야합니다.

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