8

次の 2 つのシーケンスがあるとします。

val index = Seq(2,5,1,4,7,6,3)
val unsorted = Seq(7,6,5,4,3,2,1)

1 番目は、2 番目のソートに使用するインデックスです。私の現在の解決策は、インデックスをトラバースし、ソートされていないシーケンスから見つかった要素を使用して新しいシーケンスを構築することです。

val sorted  = index.foldLeft(Seq[Int]()) { (s, num) => 
  s ++ Seq(unsorted.find(_ == num).get)
}

しかし、この解決策は非常に非効率的でエラーが発生しやすいようです。反復ごとに、ソートされていない完全なシーケンスを検索します。また、インデックスと並べ替えられていないリストが同期していない場合は、エラーがスローされるか、要素が省略されます。どちらの場合も、順序付けられたシーケンスに非同期要素を追加する必要があります。

この問題に対するより効率的で確実な解決策はありますか? または、このパラダイムに適合するソートアルゴリズムはありますか?

注：これは構築例です。実際には、mongodb ドキュメントのリストをドキュメント ID の順序付きリストでソートしたいと考えています。

更新 1

Marius Danila からの回答を選択しました。これは、私の問題に対するより高速でスケーラなソリューションと思われるためです。同期されていないアイテムのソリューションは付属していませんが、これは簡単に実装できます。

したがって、更新されたソリューションは次のとおりです。

def sort[T: ClassTag, Key](index: Seq[Key], unsorted: Seq[T], key: T => Key): Seq[T] = {
  val positionMapping = HashMap(index.zipWithIndex: _*)
  val inSync = new Array[T](unsorted.size)
  val notInSync = new ArrayBuffer[T]()
  for (item <- unsorted) {
    if (positionMapping.contains(key(item))) {
      inSync(positionMapping(key(item))) = item
    } else {
      notInSync.append(item)
    }
  }

  inSync.filterNot(_ == null) ++ notInSync
}

更新 2

Bask.cc によって提案されたアプローチは正しい答えのようです。また、同期していない問題も考慮されていませんが、これも簡単に実装できます。

val index: Seq[String]
val entities: Seq[Foo]
val idToEntityMap = entities.map(e => e.id -> e).toMap
val sorted = index.map(idToEntityMap)
val result = sorted ++ entities.filterNot(sorted.toSet)
4

7 に答える 7

3

これはあなたのユースケースに正確に対応していないかもしれませんが、Google 社員はこれが役に立つと思うかもしれません:

scala> val ids = List(3, 1, 0, 2)
ids: List[Int] = List(3, 1, 0, 2)

scala> val unsorted = List("third", "second", "fourth", "first")
unsorted: List[String] = List(third, second, fourth, first)

scala> val sorted = ids map unsorted
sorted: List[String] = List(first, second, third, fourth)
于 2015-05-13T23:36:21.153 に答える
1

Ok。

最初から始めましょう。unsorted毎回リストを再スキャンしているという事実に加えて、SeqオブジェクトはデフォルトでListコレクションを作成します。したがって、foldLeft毎回リストの最後に要素を追加していますが、これはO(N^2)操作です。

改善点は

val sorted_rev  = index.foldLeft(Seq[Int]()) { (s, num) => 
  unsorted.find(_ == num).get +: s
}
val sorted = sorted_rev.reverse

しかし、それはまだO(N^2)アルゴリズムです。もっとうまくやることができます。

次の並べ替え関数が機能するはずです。

def sort[T: ClassTag, Key](index: Seq[Key], unsorted: Seq[T], key: T => Key): Seq[T] = {
  val positionMapping = HashMap(index.zipWithIndex: _*) //1
  val arr = new Array[T](unsorted.size) //2
  for (item <- unsorted) { //3
    val position = positionMapping(key(item))
    arr(position) = item
  }
  arr //6
}

この関数は、ソートしようとしているオブジェクトから id を抽出するために関数が使用されるunsorted一連のインデックスindexでアイテムのリストをソートします。key

1 行目は逆インデックスを作成し、各オブジェクト ID を最終的な位置にマッピングします。

行 2 は、ソートされたシーケンスを保持する配列を割り当てます。一定時間のランダム位置セットのパフォーマンスが必要なため、配列を使用しています。

3 行目から始まるループは、並べ替えられていないアイテムのシーケンスをトラバースし、positionMapping逆インデックスを使用して各アイテムを本来の位置に配置します。

6 行目は、ラッパーSeqを使用して暗黙的に a に変換された配列を返します。WrappedArray

逆インデックスは immutableHashMapであるため、通常のケースではルックアップに一定の時間がかかります。実際の逆インデックスの作成には、インデックス シーケンスのサイズに応じてO(N_Index)時間がかかります。N_IndexソートされていないシーケンスのトラバースにはO(N_Unsorted)時間がかかります。ここN_Unsortedで、 はソートされていないシーケンスのサイズです。

したがって、複雑さは ですO(max(N_Index, N_Unsorted))。これは、その状況でできる最善のことだと思います。

特定の例では、次のように関数を呼び出します。

val sorted = sort(index, unsorted, identity[Int])

実際のケースでは、おそらく次のようになります。

val sorted = sort(idList, unsorted, obj => obj.id)
于 2013-09-02T16:20:03.180 に答える