클로저에서 천천히 '빠른 정렬'

Question

나는 clojure에서 빠른 정렬 기능을 작성했지만 매우 느리게 실행됩니다. 때로는 입력 컬렉션이 커지면 스택 오버플로가 발생할 수 있습니다.

내 코드에 문제가 있습니까?

(defn qsort [coll] 
    (if (<= (count coll) 1) 
    coll 
    (let [pivot (last coll) 
      head-half (filter #(< % pivot) (drop-last coll)) 
      tail-half (filter #(>= % pivot) (drop-last coll))] 
     (concat (qsort head-half) (vector pivot) (qsort tail-half))))) 

또한 clojure.core의 정렬 기능을 읽었지만 혼란 스럽습니다.

01 (defn sort 
02 "Returns a sorted sequence of the items in coll. If no comparator is 
03 supplied, uses compare. comparator must 
04 implement java.util.Comparator." 
05 {:added "1.0" 
06 :static true} 
07 ([coll] 
08 (sort compare coll)) 
09 ([^java.util.Comparator comp coll] 
10 (if (seq coll) 
11  (let [a (to-array coll)] 
12  (. java.util.Arrays (sort a comp)) 
13  (seq a)) 
14  ()))) 

순환이 일어나는 유일한 장소는 라인 (12)에있다 그것은 단지 두 개의 입력 매개 변수를 교환! 이 코드가 실행되는 이유를 설명해 주시겠습니까?

Answer 1

(. java.util.Arrays (sort a comp))이 호출은 배열 정렬 함수이며 clojure.core 정렬 함수에 대한 재귀 호출은 아닙니다.

빠른 정렬이 imperative algorithm이므로 코드가 느립니다. 즉, 장소 배열 변경과 같은 명령형 프로그래밍의 개념을 기반으로합니다. 코드가 좋지만 문제는 컬렉션을 여러 번 통과하며 많은 중간 컬렉션이 만들어집니다.

배열 및 장소 배열 변이를 사용하여 빠른 정렬을 빠르게 할 수 있습니다.

Answer 2

Clojure의 정렬 기능은 Java의 표준 java.util.Arrays/sort 메소드를 내부적으로 사용합니다. 그것은 100 % 클로저 구현이 아닙니다.

퀵 소트는 요소의 빠른 O (1) 교환이있는 컬렉션 유형에 따라 달라지기 때문에 관용적 인 클로저에 정말 어울리지 않습니다. 구현시, 콜은 모든 콜을 수행하고 (마지막 콜 콜) 콜은 게으른 seq이므로 둘 다 O (n)이므로 콜을 수행함으로써 성능을 향상시킬 수 있어야합니다. 계정 ~ ​​아마도 중간 컬렉션 유형으로 변경할 수없는 seq 대신 java 배열을 사용합니다.

Answer 3

스택 오버 플로우 문제는 필터에 지연 필터를 재귀 적으로 넣는 것입니다. 그게 아니라 여기에서 설명하는 것 : 다른 질문에 대해서는

Recursive function causing a stack overflow

: 라인 12 년, 그는 Clojure의 정렬 기능에는 호출하지만, 배열-정렬 함수에 대한 호출이 없습니다. 사용자 코드에서 일반적으로 도트 구문 대신 (java.util.Arrays/sort a comp)을 작성합니다.

Answer 4

qsort는 대부분의 시간을 객체 할당에 소비하고 있습니다.

• 통화
  각 통과
• 연결에 대한 호출에 대한 각 번호의 게으른 단점 인스턴스를 할당 필터링 버전이 내 의견에 더 잘 읽고 있지만 각 번호

또 다른 객체를 할당하기 HTTP :

에서의 Clojure 문서에있어서