いくつかの基準に従ってトップn値を取る慣習的な方法は何ですか？

Question

私は次のコードを持っている：予想通り

Sighting.all 
     .iterator 
     .map(s => (s, haversineDistance(s, ourLocation))) 
     .toSeq 
     .sortBy(_._2) 
     .take(5) 

を、それがourLocationに5目撃のclosestsを返します。

しかし、非常に多数の目撃については、うまく調整できません。代わりに、すべての目撃情報O（N）を調べ、それらをすべてソートしてO（N * logN）を実行する代わりに、5つの最も近いものを見つけることができます。どのように慣用的に行うのですか？

Answer 1

以前の質問と同様に、foldが役に立つかもしれません。この場合、私は、PriorityQueueを、予想されるデータセットよりも大きな値に初期化した上で折りたたみたいという誘惑を受けるだろう。

import scala.collection.mutable.PriorityQueue 

... 
.iterator 
.foldLeft(PriorityQueue((999,"x"),(999,"x"),(999,"x"),(999,"x"),(999,"x")){ 
    case (pq, s) => pq.+=((haversineDistance(s, ourLocation), s)).tail 
} 

結果は、5（距離、照準）タプルのPriorityQueueが、わずか5点の最小距離です。

あなたは次のように5要素のリストを維持しながら、一度だけ、リスト内の各要素を反復処理により大きなリストをソートを回避することができ

Answer 2

：

1. は降順での距離によって並べ替え5要素のリストをキープ（5が小さいため、ソートのコストは無視できる）。
2. 各繰り返しで、元のリストの現在の要素の距離がhead要素の現在の要素よりも短い場合は、 5要素のリストは、head要素を現在の要素で置き換えます。
   ：特に反復を完了すると、現在の5要素のリスト

を保つ、5要素のリストは、TOP5リストを与える昇順に距離によって最短距離と最終選別を有する要素で構成されます

val list = Sighting.all. 
    iterator. 
    map(s => (s, haversineDistance(s, ourLocation))). 
    toSeq 

// For example ... 
res1: list = List(
    ("a", 5), ("b", 2), ("c", 12), ("d", 9), ("e", 6), ("f", 15), 
    ("g", 9), ("h", 7), ("i", 6), ("j", 3), ("k", 10), ("l", 5) 
) 

val top5 = list.drop(5). 
    foldLeft(list.take(5).sortWith(_._2 > _._2))(
    (l, e) => if (e._2 < l.head._2) 
       (e :: l.tail).sortWith(_._2 > _._2) 
       else 
       l 
). 
    sortBy(_._2) 
// top5: List[(String, Int)] = List((b,2), (f,3), (h,5), (a,5), (e,6)) 

[UPDATE]

以下はうまくいけばfoldLeft式は以下圧倒的に見える上記top5値の割り当ての詳細なバージョンです。ここで

val initialTop5Sorted = list.take(5).sortWith(_._2 > _._2) 

val originalListTail = list.drop(5) 

def updateTop5Sorted = (list: List[(String, Int)], element: (String, Int)) => { 
    if (element._2 < list.head._2) 
    (element :: list.tail).sortWith(_._2 > _._2) 
    else 
    list 
} 

val top5 = originalListTail. 
    foldLeft(initialTop5Sorted)(updateTop5Sorted). 
    sortBy(_._2) 

は、ご参考のためfoldLeftの署名です：

def foldLeft[B](z: B)(op: (B, A) => B): B 

Answer 3

は、ここで少し異なるアプローチです：

def topNBy[A, B : Ordering](xs: Iterable[A], n: Int, f: A => B): List[A] = { 
    val q = new scala.collection.mutable.PriorityQueue[A]()(Ordering.by(f)) 
    for (x <- xs) { 
    q += x 
    if (q.size > n) { 
     q.dequeue() 
    } 
    } 
    q.dequeueAll.toList.reverse 
} 

foldは便利、とに慣れるの価値がある、しかし、あなたはしている場合各反復で動作する新しいオブジェクトを作成せず、既存のオブジェクトを変更するだけではforループよりも優れていません。そして私はPriorityQueueに依存して、効率的なO（log n）の実装を考えれば、独自のロールアップよりもソートを行うほうが好きです。機能的な純粋主義者は、これをもっと不可欠であると主張しているかもしれませんが、わかりやすく簡潔にするためには価値があります。変更可能な状態は、単一のローカルデータ構造に制限されています。

あなたも暗黙のクラスにそれを置くことができます：

implicit class IterableWithTopN[A](xs: Iterable[A]) { 
    def topNBy[B : Ordering](n: Int, f: A => B): List[A] = { 
    ... 
    } 
} 

をそして好き、それを使用します。

Sighting.all.topNBy(5, s => haversineDistance(s, ourLocation))