Лучшие n элементов в списке (включая дубликаты)

Question

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

Сначала я попробовал сортировку и нарезку, что работает.Но это кажется ненужным.Вам не нужно сортировать очень большой список, если вы просто хотите, чтобы 20 лучших участников.Итак, я написал рекурсивную процедуру, которая создает список top-n.Это также работает, но намного медленнее, чем нерекурсивный!

Вопрос: Какая моя вторая процедура (elite2) намного медленнее, чем elite, и как мне сделать это быстрее?Мой код прилагается ниже.Спасибо.

import scala.collection.SeqView
import scala.math.min
object X {

    def  elite(s: SeqView[Int, List[Int]], k:Int):List[Int] = {
        s.sorted.reverse.force.slice(0,min(k,s.size))
    }

    def elite2(s: SeqView[Int, List[Int]], k:Int, s2:List[Int]=Nil):List[Int] = {
        if( k == 0 || s.size == 0) s2.reverse
        else {
            val m = s.max
            val parts = s.force.partition(_==m)
            val whole = if( parts._1.size > 1) parts._1.tail:::parts._2 else parts._2
            elite2( whole.view, k-1, m::s2 )
        }
    }

    def main(args:Array[String]) = {
        val N = 1000000/3
        val x = List(N to 1 by -1).flatten.map(x=>List(x,x,x)).flatten.view
        println(elite2(x,20))
        println(elite(x,20))
    }
}

Answer 1

Не переоценивайте, насколько велик log(M), для большого списка длины M. Для списка, содержащего миллиард элементов, log(M) равно только 30. Таким образом, сортировка и выборка не такой уж неразумный метод. На самом деле сортировка массива целых чисел происходит намного быстрее благодаря сортировке списка (и массив также занимает меньше памяти), поэтому я бы сказал, что ваша лучшая (короткая) ставка (которая безопасна для коротких или пустых списков благодаря takeRight )

val arr = s.toArray
java.util.Arrays.sort(arr)
arr.takeRight(N).toList

Есть несколько других подходов, которые можно использовать, но реализации менее просты. Вы можете использовать частичную быструю сортировку, но у вас есть те же проблемы с наихудшими сценариями, что и для быстрой сортировки (например, если ваш список уже отсортирован, наивный алгоритм может быть O(n^2)!). Вы можете сохранить верхнюю N в кольцевом буфере (массиве), но для этого потребуется O(log N) бинарный поиск на каждом шаге, а также O(N/4) скольжение элементов - хорошо, только если N довольно мало. Более сложные методы (например, основанные на двойной поворотной быстрой сортировке) более сложны.

Поэтому я рекомендую вам попробовать сортировку массивов и посмотреть, достаточно ли это быстро.

(Конечно, ответы различаются, если вы сортируете объекты вместо чисел, но если ваше сравнение всегда можно уменьшить до числа, вы можете s.map(x => /* convert element to corresponding number*/).toArray, а затем взять выигрышные баллы и снова просмотреть список, считая от числа, которое вам нужно взять для каждого счета, как вы находите их, это немного бухгалтерия, но не сильно замедляет все, кроме карты.)

Answer 2

Классический алгоритм называется QuickSelect.Это похоже на QuickSort, за исключением того, что вы спускаетесь только на половину дерева, так что в среднем получается O (n).

Answer 3

Если я что-то не упустил, почему бы просто не пройтись по списку и выбрать 20 лучших по ходу дела?Пока вы отслеживаете наименьший элемент из топ-20, не должно быть никаких накладных расходов, кроме как при добавлении в топ-20, что должно быть относительно редко для длинного списка.Вот реализация:

  def topNs(xs: TraversableOnce[Int], n: Int) = {
    var ss = List[Int]()
    var min = Int.MaxValue
    var len = 0
    xs foreach { e =>
      if (len < n || e > min) {
        ss = (e :: ss).sorted
        min = ss.head
        len += 1
      }
      if (len > n) {
        ss = ss.tail
        min = ss.head
        len -= 1
      }                    
    }
    ss
  }  

(отредактировано, потому что я изначально использовал SortedSet, не понимая, что вы хотите сохранить дубликаты.)

Я протестировал это для списка из 100 тыс. Случайных Ints, иэто заняло в среднем 40 мс.Ваш метод elite занимает около 850 мс, а метод elite2 - около 4100 мс.Так что это более чем в 20 раз быстрее, чем ваш самый быстрый.

Answer 4

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

    import util.Sorting.quickSort

    class TopNSet[T](n:Int) (implicit ev: Ordering[T], ev2: ClassManifest[T]){
      val ss = new Array[T](n)
      var len = 0

      def tryElement(el:T) = {
        if(len < n-1){
          ss(len) = el
          len += 1
        }
         else if(len == n-1){
          ss(len) = el
          len = n
          quickSort(ss)
        }
        else if(ev.gt(el, ss(0))){
          ss(0) = el
          quickSort(ss)
        }
      }
      def getTop() = {
        ss.slice(0,len)
      }
    }

Оценка по сравнению с принятым ответом:

val myInts = Array.fill(100000000)(util.Random.nextInt)
time(topNs(myInts,100)
//Elapsed time 3006.05485 msecs
val myTopSet = new TopNSet[In](100)
time(myInts.foreach(myTopSet.tryElement(_)))
//Elapsed time 4334.888546 msecs

Итак, не намного медленнее и, конечно, намного более гибким

Answer 5

Вот псевдокод для алгоритма, который я бы использовал:

selectLargest(n: Int, xs: List): List
  if size(xs) <= n
     return xs
  pivot <- selectPivot(xs)
  (lt, gt) <- partition(xs, pivot)
  if size(gt) == n
     return gt
  if size(gt) < n
     return append(gt, selectLargest(n - size(gt), lt))
  if size(gt) > n
     return selectLargest(n, gt)

selectPivot будет использовать некоторую технику для выбора значения "pivot" для разбиения списка. partition разделит список на две части: lt (элементы меньше, чем пивот) и gt (элементы больше, чем пивот). Конечно, вам нужно добавить элементы, равные центру в одной из этих групп, или обрабатывать эту группу отдельно. Это не имеет большого значения, если вы помните, чтобы справиться с этим делом как-то .

Не стесняйтесь редактировать этот ответ или опубликовать свой собственный ответ в Scala-реализации этого алгоритма.