비교에 기반한 파이썬의 정렬 된 컨테이너

Question

C++ 배경에서 오는 것은 비교에만 기반하고 해시가 필요없는 멋진 정렬 컨테이너가 누락되었습니다.

아무도 균형 잡힌 트리를 잘 구현하는지 알 수 있습니까? 또는 (표준) 라이브러리에 다른 정렬 된 컨테이너가 있으며 사용하기 쉽습니다.

이것은 내가 지금 풀려고하는 나의 유스 케이스이다 : A는 삼각형이있는 서페이스를 기술하는 파일을 가지고있다. 각 삼각형은 3 개의 노드를 가지며 많은 노드가 동일합니다. 이 표면을 재구성해야하고 어떤 노드가 동일한 지 알아야합니다. 불행히도, ASCII 입력에서 같은 노드에 속해있는 경우에도 인쇄 된 float간에 작은 차이가있을 수 있습니다. 그래서 나는 그들이 평등한지 비교하기 위해 간단한 텍스트를 사용할 수 없다.

C++에서 내 솔루션은 그들 사이의 거리가 작은 경우 노드를 동등하게 취급하는 'softcompare'로 노드를 저장하기 위해 std :: map을 만드는 것입니다. 그런 다음 파일을 파싱하는 동안 노드를 추가하고 인덱스를 사용하여 표면을 빌드 할 수 있습니다.

그러나 파이썬에서는 똑같이 효율적으로 똑같이 처리하려고 애 쓰고 있습니다.

감사합니다, 누가 복음

---

감사합니다 귀하의 모든 기여!

하려면 goncalopp : 정렬은 각 삽입에 대해 최악의 경우이므로 (N log (n)) 최악의 경우입니다. bisect와 동일합니다. 그것은 검색에는 좋으나 삽입에는 적합하지 않습니다. 최악의 경우에 O (n) 인 불균형 트리를 유지하고 목록에있는 다음 삽입은 O (n)입니다.

To Aaron : 나는 우아한 코드를 작성하는 것이 목표라는 데 전적으로 동의합니다. 나를 위해, 올바른 컨테이너 (데이터 구조)를 선택하는 것이 종종 이것을 수행하는 첫 번째 단계입니다. 당신의 솔루션은 O (n)입니다. 이것은 균형 잡힌 나무보다 훨씬 빠르며, 매우 훌륭합니다. 그리고 나는 라운드()로 트릭을 좋아합니다. 나는 생각하지 않았습니다. 이제 int의 무한한 정밀도 때문에 파이썬에서 작동한다는 것을 알게되었습니다. 그래서 나는 당신의 건설과 함께 갈 것입니다.

MrE : bintree에 대한 링크를 제공해 주셔서 감사합니다. 내 질문 (균형 잡힌 나무)에 대한 해결책처럼 보입니다. 전에 blist를 찾았지만 내부 dict 및 검색 용 해시를 사용하므로 작동하지 않지만 bintree가 훨씬 좋아 보입니다.

Answer 1

C++에서는 모든 것이 효율성에 관한 것입니다. Python에서는 아름다움이 똑같이 중요합니다. Python 개발자는 먼저 우아한 알고리즘을 찾으려고 노력합니다. 실제로는 너무 느린 경우가 거의 없기 때문에 몇 줄을 최적화하여 충분히 빠르지 않게 만듭니다.

귀하의 경우, 서로 가깝게있는 점을 찾아야합니다. 하나의 접근 방식은 귀하가 묘사하는 방법입니다. 다음은이 문제를 해결하는 방법입니다.

좌표가 얼마나 정확해야하는지 결정하십시오. 얼마나 많은 소수의 소수를 유지하고 싶습니까? 1, 2?

입력을 읽는 동안 좌표를 적절한 소수 자릿수로 잘라내거나 반올림 한 후 튜플 키를 만듭니다. 이제 표준 파이썬 사전을 사용할 수 있습니다 :

def round(x): 
    return int(round(x*100)) # Keep 2 decimal places, return int for precision (and speed) 

filter = {} 
filteredPoints = [] 
for x,y,z in points: 
    x,y,z = round(x),round(y),round(z) 
    key = (x,y,z) 
    index = filter.get(key, None) 
    if index is None: 
     index = len(filteredPoints) 
     filteredPoints.append(key) 
     filter[key] = index