실제로 'treedict'(또는 treemap)를 실제로 사용할 수 있습니까?

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

문제

파이썬에서 'treedict'클래스를 개발하고 있습니다. 이것은 기본적으로 Java의 Treemap Collection 클래스와 마찬가지로 키 값 쌍을 정렬 된 순서로 검색 할 수있는 독점입니다.

관계형 데이터베이스의 고유 인덱스를 사용할 수있는 방식을 기반으로 일부 기능을 구현했습니다. 예를 들어 기능은 다양한 키에 해당하는 값을 검색 할 수 있습니다. 또는 정렬 된 순서로 특정 접두사가있는 튜플 등

불행히도, 나는 이와 같은 수업이 필요한 실제 문제를 생각할 수 없습니다. 나는 우리가 파이썬에서 묘기를 분류하지 않은 이유는 실제로 가치가있을만큼 자주 필요하지 않지만 잘못되기를 원한다고 생각합니다.

'treedict'의 특정 응용 프로그램을 생각할 수 있습니까? 이 데이터 구조에 의해 가장 잘 해결 될 실제 문제가 있습니까? 나는 이것이 그만한 가치가 있는지 확실히 알고 싶습니다.

도움이 되었습니까?

해결책

키 순서대로 사전을 거쳐야 할 때 유용합니다. 가끔 나타납니다. 나는 실제로 특정 프로그래밍 콘테스트에서 다른 것 (ACM을 생각하는 등)에서 무한히 더 흔한 것을 발견했습니다.

Treemap의 가장 유용한 특징은 Min 또는 Max 키를 빠르게 찾고 싶을 때입니다. 정렬 된 사전 사용 종종 단일 메소드 호출입니다. 모음이 풀리지 않은 경우 최소/최대를 찾는 각 키를 반복하는 대신 알고리즘 적으로 O (log (n)) 시간으로 수행 할 수 있습니다. 기본적으로 훨씬 더 친근한 인터페이스.

내가 겪고있는 더 일반적인 시간 중 하나는 객체가 특정 이름으로 식별 될 때이며, 이름에 따라 순서 대상 객체를 인쇄하려고합니다. 디렉토리 이름에서 디렉토리의 파일 수로 매핑을 가정하십시오.

내가 사용한 다른 곳 중 하나는 Excel 스프레드 시트 래퍼에 있습니다. 행 번호에서 행 객체까지 매핑. 이를 통해 각 행을 반복하지 않고 마지막 행 색상을 신속하게 찾을 수 있습니다.

또한 키에 대한 비교 관계를 쉽게 정의 할 수 있지만 해시 맵에 필요에 따라 반드시 해싱 함수는 아닙니다. 내가 생각할 수있는 가장 좋은 (약한) 예는 Case Insensitive String Keys입니다.

다른 팁

"순서 시퀀스"기능을 가리키는 몇 가지 답변을 보았습니다. 실제로 중요하지만 다른 큰 기능을 강조하는 것은 없습니다. 이것은 거기에서 "걷기"할 필요가없는 경우에도 많은 용도를 가지고 있습니다.

예를 들어 (이것은 최근에 답변으로 나타났습니다) 주어진 상대 주파수로 의사 랜덤 값을 생성하고 싶다고 말합니다. d:

{'wolf': 42, 'sheep': 15, 'dog': 23, 'goat': 15, 'cat': 5}

그리고 100 개 중 42 개 (100이 주어진 상대 주파수의 총이기 때문에), '양'15 개 등의 '늑대'를 생성하는 방법이 필요합니다. 상대 주파수와 마찬가지로 별개의 값의 수는 상당히 클 수 있습니다.

그런 다음 주어진 값 (모든 순서로)을 트리 맵의 값으로 저장하고 해당 키는 해당 지점까지 "총 누적 주파수"입니다. 즉:

def preprocess(d):
    tot = 0
    for v in d:
        tot += d[v]
        treemap.insert(key=tot, value=v)
    return tot, treemap

이제 값을 생성하는 것은 매우 빠를 수 있습니다 (O(log(len(d)))), 다음과 같이 :

def generate(tot, treemap, r=random):
    n = r.randrange(tot)
    return treemap.firstGTkey(n).value

어디 firstGTKey 첫 번째 항목을 반환하는 메소드입니다 ( .key 그리고 .value 이 가상의 예에서) 주어진 인수. 예를 들어 B- 트리로 저장된 큰 파일과 함께이 접근법을 사용했습니다 (예 : 사용 bsddb.bt_open 그리고 set_location 방법).

요소를 정렬 된 순서로 유지하는 이유는 더 빠른 검색입니다. 사전의 모든 값을 정렬 된 범위로 원한다고 가정 해 봅시다. 이것은 일반 해시 맵을 사용하면 treedict의 경우 훨씬 빠릅니다. 기본적으로 사전의 모든 것을 정렬 된 순서로 유지할 수 있습니다. 현재 작업중 인 응용 프로그램에서 이와 같은 클래스를 사용하여 기본적으로 데이터 구조를 쿼리합니다.

나는 종종 사용한다 Dict<DateTime, someClassOrValue> 산업 공정 데이터와 함께 작업 할 때- 밸브 오픈/닫기, 기계 시작/정지 등

키를 정렬하는 것은 적절한 시간에 시작/정지 또는 열린 이벤트 간의 시간 간격을 비교해야 할 때 특히 유용합니다.

그러나 C#에서 LINQ를 사용할 수 있었기 때문에 ienumerables와 함께 작업하고 iqueryable 확장 방법을 사용하여 필요한 정보를 얻는 것이 더 쉽다는 것을 알았습니다.

거의 모든 "그룹에 의한 그룹"보고서에는 정렬 된 사전이 필요합니다.

summary = sortedDefaultDict()
for row in somePileOfData:
    summary[row.group_by] += row.balance
for k in sorted(summary.keys()):
    print k, summary[k]

이것은 데이터웨어 하우스 응용 프로그램에서 자주 수행되므로 이것이 중심인지 표현하기가 어렵습니다.

만약 sorted 기능 호출은 작동하지 않으며 장기적으로 많은 시간을 절약합니다.

당신은 그것을 본 적이 있습니까 : http://code.activestate.com/recipes/576998/ ?

주오

다양한 알고리즘을 쉽게 구현할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top