Сортировка 2d-вектора по значению индекса в ленивую последовательность в ближайшие - PullRequest
Новая
       3

Сортировка 2d-вектора по значению индекса в ленивую последовательность в ближайшие

1 голос
/ 19 января 2012

Я читаю Joy Of Clojure и столкнулся с реализацией быстрой сортировки, в которой используются ленивые последовательности для достижения лучшей производительности, чем O (n log n), когда берут только первые несколько cons-ячеек из ленивой последовательности. Я пытаюсь заставить его работать для двумерного массива целых чисел, но, похоже, не совсем понимаю: Пока это то, что у меня есть: 

(defn sort-parts2
  "Lazy, tail-recursive, incremental quicksort. Works against
   and creates partitions based on the pivot, defined as 'work'."
  [work]
  (lazy-seq
    (loop [[part & parts] work]
      (if-let [[pivot & xs] (seq part)]
        (let [smaller? #(< % pivot)]
          (recur (list*
                 (filter smaller? xs)
                 pivot
                 (remove smaller? xs)
                 parts)))
      (when-let [[x & parts] parts] 
      (cons x (sort-parts2 parts)))))))



   sort.joy=> a
    [[5 9 0 6 5 1 4 4 8 7]
     [2 6 8 2 6 7 0 1 8 1]
     [8 8 0 5 9 9 7 7 1 6]
     [9 8 5 3 0 2 0 6 9 3]
     [8 8 5 8 9 8 2 3 8 5]
     [7 9 2 8 5 6 6 8 3 4]
     [4 8 2 4 6 6 7 4 4 1]
     [8 5 1 7 3 0 2 4 2 3]
     [9 1 2 9 0 1 0 2 2 9]
     [4 0 2 6 8 5 6 1 7 7]]

что я хочу получить для ввода (sort-parts2 a 0) // индекс для первого элемента подвекторов: 

   sort.joy=> aSorted
     [[2 6 8 2 6 7 0 1 8 1]
     [4 0 2 6 8 5 6 1 7 7]
     [4 8 2 4 6 6 7 4 4 1]
     [5 9 0 6 5 1 4 4 8 7]
     [7 9 2 8 5 6 6 8 3 4]
     [8 5 1 7 3 0 2 4 2 3]
     [8 8 0 5 9 9 7 7 1 6]
     [8 8 5 8 9 8 2 3 8 5]
     [9 1 2 9 0 1 0 2 2 9]
     [9 8 5 3 0 2 0 6 9 3]]

как есть, вот что я сейчас получаю: 

sort.joy=> (sort-parts a)
(0
 1
 4
 4
 5
 5
 6
 7
 8
 9
 [2 6 8 2 6 7 0 1 8 1]
 0
 1
 5
 6
 7
 7
 8
 8
 9
 9
 [9 8 5 3 0 2 0 6 9 3]
 2
 3
 5
 5
 8
 8
 8
 8
 8
 9
 [7 9 2 8 5 6 6 8 3 4]
 1
 2
 4
 4
 4
 4
 6
 6
 7
 8
 [8 5 1 7 3 0 2 4 2 3]
 0
 0
 1
 1
 2
 2
 2
 9
 9
 9
 [4 0 2 6 8 5 6 1 7 7])

Может кто-нибудь помочь мне найти способ остановить цикл от полной деструкции 2-го вектора, возвращая ленивый вектор с головой, являющейся вектором строки? У меня есть компараторы для рядов, спасибо!

edit Более общая постановка задачи: я хочу отсортировать 2d-вектор, обозначенный a ниже, в ленивую последовательность, где head - это следующий субвектор, упорядоченный по индексу , Чтобы сделать это не лениво, я использую: 

(defn sortVector 
  "sorts a 2d vector by the given index"
  [index coll]
  (sort-by #(nth % index) coll))

1 Ответ

1 голос
/ 20 января 2012

Вы можете получить функцию sort-parts-by из кода JoC, если вы начнете с оригинала и замените функцию smaller? на функцию, которая сравнивает значения некоторой ключевой функции на pivot и другого элемента, а ненепосредственно элементы: 

(let [pivot-key (keyfn pivot)
      smaller? #(.compare ^java.util.Comparator comp
                          (keyfn %1)
                          pivot-key)]
  ...)

Имена keyfn и comp взяты из clojure.core/sort-by - см. его строку документации / реализацию для намеченного значения.

Обратите внимание, что sort-partsне предназначен для вызова фактической последовательности, которая должна быть отсортирована - вы должны сначала обернуть ее в какой-нибудь seqable (возможно, вектор);см. определение qsort в JoC для примера.Вы, вероятно, захотите, чтобы qsort-by выполнял функции, описанные выше.

...