Получение n наименьших чисел в последовательности

Question

Какой самый эффективный способ взять n наименьших чисел из последовательности,

[ [1 2 3] [9 2 1] [2 3 4] [5 6 7] ]

Я бы хотел взять 2 наименьших из последовательности на основе первого элемента,

[1 2 3] [2 3 4]

В настоящее время я сортирую весь список, затем беру первые n элементов, но это, вероятно, не самый эффективный способ, это большой список, и мне нужно делать это часто.

Answer 1

Радость Clojure , глава 6.4, описывает ленивый алгоритм сортировки. Прелесть ленивой сортировки состоит в том, что она будет выполнять столько работы, сколько необходимо для поиска первых значений x.Поэтому, если x << n, этот алгоритм равен O (n).Вот модифицированная версия этого алгоритма. </p>

(defn sort-parts                                                                                                                                                                                                            
  [work f]                                                                                                                                                                                                                  
  (lazy-seq                                                                                                                                                                                                                 
   (loop [[part & parts] work]                                                                                                                                                                                              
     (if-let [[pivot & xs] (seq part)]                                                                                                                                                                                      
       (let [psmaller? (partial f pivot)]                                                                                                                                                                                   
         (recur (list* (filter psmaller? xs)                                                                                                                                                                                
                       pivot                                                                                                                                                                                                
                       (remove psmaller? xs)                                                                                                                                                                                
                       parts)))                                                                                                                                                                                             
       (when-let [[x & parts] parts]                                                                                                                                                                                        
         (cons x                                                                                                                                                                                                            
               (sort-parts parts f)))))))                                                                                                                                                                                   

(defn qsort [xs f] (sort-parts (list xs) f))                                                                                                                                                                                

(defn cmp [[a _ _] [b _ _]] (> a b))                                                                                                                                                                                        

(def a [[1 2 3] [9 2 1]  [2 3 4] [5 6 7]])                                                                                                                                                                                   

(take 2 (qsort a cmp)) 

Answer 2

Как уже упоминалось, вы можете использовать алгоритм медианы медиан, чтобы выбрать k-й наименьший элемент за линейное время, а затем разбить на линейное время.Это даст вам k наименьших элементов в O (n).Однако элементы будут не отсортированы, поэтому, если вы хотите отсортировать k наименьших элементов, это будет стоить вам еще O (klogk).

Несколько важных замечаний:

1. Во-первыххотя сложность составляет O (n), небольшие константы не гарантируются, и вы можете найти минимальное улучшение, особенно если ваше n достаточно мало.Существуют алгоритмы случайного линейного выбора, которые выполняются в лучшие фактические времена (обычно ожидаемое время выполнения O (n) с худшими худшими случаями, но они имеют меньшие константы, чем детерминированные).

2. Почему вы не можете поддерживать массив в отсортированном виде?Это, вероятно, будет гораздо более производительным.Вам просто нужно будет вставить каждый элемент в правильное место, которое стоит O (logn), но нахождение k наименьшего будет O (1) (или O (k), если вам нужно построить массив заново).

3. Если вы примете решение против приведенного выше примечания, то альтернативой является сохранение массива отсортированным после каждой такой процедуры, предоставление вставки в O (1) до конца массива и затем выполнение «слияния»сортировать "каждый раз, когда вам нужно найти k самых маленьких элементов.Т.е. вы сортируете только новых и затем объединяете их в линейное время.Так что это будет стоить O (mlogm + n), где m - количество элементов, добавленных с момента последней сортировки.

Answer 3

Если n мало, вы можете создать второй список размера n, который вы продолжите сортировать, чтобы у вас всегда был быстрый доступ к самому большому в этом списке; переберите большой список, проверяя, меньше ли каждый из них в списке; если это так, вставьте его в небольшой список ... небольшой список заполнен, выкините предыдущий самый старый.

Если n меньше 3 или 4, вы можете просто перебрать его. Если n может быть больше, вам нужно выполнить бинарный поиск, чтобы найти точку вставки для каждого. Если n может быть очень большим, тогда может быть другой механизм.