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

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

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

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

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))
 }
}
5 ответов

Если мне что-то не хватает, почему бы не просто пройти список и выбрать 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-килограммовых случайных Интов, и это заняло в среднем 40 мс. Ваш метод elite занимает около 850 мс, а ваш метод elite2 занимает около 4100 мс. Таким образом, это более чем на 20% быстрее, чем ваш самый быстрый.


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

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

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

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

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


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


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

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 ****** = Array.fill(100000000)(util.Random.nextInt)
time(topNs(******,100)
//Elapsed time 3006.05485 msecs
val myTopSet = new TopNSet[In](100)
time(******.foreach(myTopSet.tryElement(_)))
//Elapsed time 4334.888546 msecs

Итак, не намного медленнее и, безусловно, намного более гибко


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

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 будет использовать некоторую технику для выбора значения "поворота" для разбиения списка. partition разделил бы список на два: lt (элементы, меньшие, чем точка поворота) и gt (элементы больше, чем точка поворота). Разумеется, вам нужно будет выровнять элементы, равные оси в одной из этих групп, или же обрабатывать эту группу отдельно. Это не имеет большого значения, если вы не знаете, как это сделать.

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

licensed under cc by-sa 3.0 with attribution.