순서가있는 집합과 순서가없는 집합의 차이점을 이해하며 여러 목적에서 순서 집합이 필요하지 않은 이유를 이해합니다. 그러나 모든 집합 작업은 여전히 주문 된 세트에서 가능하며, 세트는 어쨌든 어떤 순서로 내부적으로 저장되어야합니다. 그러면 왜 세트가 기본적으로 주문되지 않습니까? 집합 순서를 유지하면 성능에 미치는 영향이 너무 크나요?
설명
- " 정렬되지 않은 컬렉션에있는 값의 "는 게재 순서에 더 많이 의존 할 수 있으며 값 자체에는 덜 의존 할 수 있습니다. ' 일반적으로 사용되는 순서가 아닙니다 (수학적 용어에서 유래).
- 이 질문은 주제에서 벗어난 것으로 간주 될 수 있습니다. ' t 특정 프로그램을 개발하는 것이 아니라 언어 설계에 대한 것입니다.
- @outis ' 올바른 하위 사이트가 확실하지 않습니다. 다른 사이트가 있습니까?
답변
요점은 오버 헤드가 특별히 크다는 것이 아니라 거기에 더 많다는 것입니다. 전혀 .
언어 기능은 항상 비용 효율성의 균형을 유지해야합니다. 딕셔너리는 파이썬 프로그래밍의 절대적인 기본이므로 대부분의 경우 순서가 필요하지 않은 경우 삽입 순서를 유지하기 위해 필요한 것보다 약간 느리게하는 것은 매우 나쁩니다. 올바른 결정이었습니다. 약간 더 빠른 액세스를 위해 삽입 순서를 버리고 특수 클래스에 대해 순서를 유지하는 데이터 구조를 남겨 둡니다. dict가 할 수있는 모든 작업을 수행 할 수있는 다른 데이터 구조가 있고 dict가 언어의 덜 사용되는 주름 인 경우 다르게 보일 수 있습니다.
댓글
- 내 반론은 다음과 같습니다. 내부 사전에 대해보다 효율적인 순서없는 dict 데이터 유형을 사용합니다 (예 : '의
deque는 다른 특정 상황에서 성능을 최적화하지만 기본 사용자 지향 dict 데이터 유형이 순서를 유지하도록합니다. - 또한 3.6의 CPython 구현이 실제로 삽입 순서를 유지한다는 것을 이해하는 것이 맞습니까? dicts?
답변
항목이 일부 주문과 함께 내부적으로 저장된다는 것이 맞지만이 내부 주문은 키의 해시 코드에 의해 결정되므로 검색 속도가 빨라집니다. 따라서 집합 / 딕셔너리를 정렬해야하는 경우이를 위해 별도의 내부 데이터 구조 (예 : 정렬 된 키 목록)를 유지해야합니다.
물론 크기가 늘어납니다. 그러나 더 나쁜 것은 성능에 영향을 미칠 것입니다. 예를 들어 세트에서 항목을 제거하는 것은 O (1) 작업이지만 내부 순서 목록에서도 키를 제거해야하는 경우 O (n)이됩니다. 이러한 비용은 일부 응용 프로그램에서 재앙이 될 것입니다. 정렬 된 세트가 필요한 경우는 매우 드물기 때문에 표준 세트 / 딕셔너리 유형에 대해서는 그러한 절충이 가치가 없습니다.
Answer
전제가 잘못되었습니다. Python 3.6부터 dict는 게재 순서를 기억합니다 . 이것은 구현 세부 사항이며 3.7에서 전체 언어 기능으로 승격되었습니다. 3.6에서는 **kwargs의 특정 사례에 대해 주문 보존이 특별히 보장됩니다.
댓글
- 예, 질문을했을 때 '이 사실을 인식하지 못했습니다. ' 아직 언어 기능이 아니라 구현 일뿐입니다. 하나의 구현에서 세부 사항. 그러나 적어도 사전이 장기적으로 주문되고 설정되기를 바랍니다.
- @oulenz it ' 더 이상 구현 세부 사항이 아닙니다. div id = “006cf49e55″>
는 Python 3.7부터 필요합니다.
Answer
set은 저장 될 요소가 처음에 순서 (즉, 비교 방법)를 가질 때만 가능하지만 항상 주어진 것은 아닙니다.
요즘 대부분의 환경에서 기본 세트 / 맵 구현은 다음과 같습니다. 다음과 같은 장점이있는 자동 크기 조정 해시 테이블을 기반으로합니다.
- 더 빠름
- 더 적은 메모리 사용
- 순서를 제공하기 위해 요소가 필요하지 않음
어쨌든 주문과 함께 세트를 내부적으로 저장해야합니다.
그러나이 내부 질서는 반드시 어떤 의미도 가지고 있지도 않으며 동일하게 유지되지도 않습니다. 실제로 경험이없는 개발자를 혼란스럽게하는 해시 테이블의 한 가지 속성은 내부 순서를 기반으로 하는 반복 순서가 요소가 추가 될 때 (즉, 크기 조정이 트리거 될 때) 또는 서로간에 완전히 변경 될 수 있다는 것입니다. 실행합니다.
댓글
- 나는 ' 당신의 첫 발언을 이해하지 못합니다. ' 비교 방법이 필요하지 않습니다. 순서는 상속 될 수 있습니다. 목록 또는 문자열 리터럴
{3, 5, 4}. - @oulenz : 순서에 신경 쓰지 않으면 ' 무의미하고 시간이 지남에 따라 변하면 모든 세트가 순서가 지정됩니다. 일부 종류의 반복 순서가 있기 때문입니다. 그러나 " 정렬 된 집합 "은 순서가 요소에 대한 의미 론적이며 항상 가능한 것은 아닙니다. 나는 ' 모든 세트를 주문하려는 이유를 정말로 이해하지 못합니다.
- " 주문 세트 "는 순서가 의미 론적이라는 것을 의미하지 않고 단지 몇 가지 순서가 있음을 의미합니다. 물론이 순서가 설정되면 내용이 수정되지 않는 한 보존됩니다.
- 죄송합니다. ' 의미가 존재한다는 사실을 인식하지 못했습니다. 어떤 사람들을 위해. 나는 단순히 수학에서 선형 적으로 정렬 된 집합을 염두에 두었다. en.wikipedia.org/wiki/Total_order
- @jameslarge 주문 관계가 없음 ' 나에게 알려지지 않아야합니다. 목록에서 정렬 된 집합을 추출하면 그 순서가 정확히 무엇인지 압니다. 특정 순서를 확인하려면 세트를 정렬 할 수 있습니다. 그러나 ' 주문이 필요하지 않은 경우 무시해도됩니다.
답변
집합 또는 사전의 일반적인 개념은 많은 조회 작업을 수행 할 계획이라는 것입니다. 대부분의 경우 O (1) 조회를 허용하는 해시를 사용하여 상기 조회 작업에 최적화되어 있습니다.
순서는 배열 또는 연결 목록을 사용하여 이루어지며 실제로 순서가 중요한 작업을 수행하며 최적화됩니다. 끝에 또는 시작 부분에 값을 추가하는 것과 같은 그 를 위해.
이 두 데이터 구조의 특성상 둘 다 최적화되어 있지 않습니다. 이것이 가능하지 않다고 말하는 것은 아니지만 조회 및 주문 기반 작업을 모두 최적화하려면 두 데이터 구조를 모두 포함합니다.
따라서 다음과 같은 절충안이 있습니다.
조회 작업 최적화 < => 주문 기반 작업 < => 메모리 사용량
일반적인 합의는 프로그래머로서 일반적으로 둘 중 하나를 최적화하고 싶지만 둘 다에 최적화하고 싶지 않으며 필요한 경우에만 메모리 사용량을 두 배로 늘리는 것을 주장하는 사람은 없습니다. 둘 중 하나를 최적화합니다.
즉, 둘 다 또는 적어도 Java로 구현 된 구현이 있습니다 . 특히 LinkedHashMap는 배열과 해시입니다. 기반 사전. 때로는 둘 다 필요할 수도 있지만 목록 만 필요한 경우 ArrayList를 사용하고 사전 만 필요한 경우 HashMap를 사용하는 것이 좋습니다. .
댓글
- 어? Java LinkedHashMap은 " 배열 및 해시 기반 사전 "이 아닙니다. '는 기본적으로 HashMap (즉, 내부적으로 배열을 사용)과 연결 목록이 겹쳐서 삽입 순서로 반복 할 수 있습니다.
- 선형 데이터 구조는 다음과 같습니다. ' 유일하게 정렬 된 데이터 구조는 아닙니다. 이진 트리도 정렬 할 수 있습니다 (예 : 빨강-검정 및 AVL 트리). 트레이드 오프에 포함될 수있는 또 다른 작업은 삽입입니다 (배열은 조회, 반복 및 메모리 사용 측면에서 매우 효율적이지만 삽입시 가장 느림).