ListBuffer [List [String]]の共通要素を見つける効率的な方法は何ですか？

シーケンスを処理しているため、この操作は、ネストされた各リスト内の個々のアイテムの合計に比例する複雑さ（最悪の場合のシナリオ）にバインドされています。

ただし、これまでに調査したアイテムの共通要素が空であることがわかっている時点に達したら、早期に終了できます。

import scala.collection.mutable
import scala.annotation.tailrec
val buffer = mutable.ListBuffer(List("a", "b", "c", "d"),
                                List("a", "c", "e", "f"),
                                List("a", "c", "g"))
def dups[X](xss: Seq[Seq[X]]): Seq[X] = {
  @tailrec
  def loop(xss: Seq[Seq[X]], dup: Set[X]): Seq[X] =
    xss match {
      case _ if dup.isEmpty || xss.isEmpty => dup.toSeq
      case head +: tail                    => loop(tail, dup intersect head.toSet)
    }
  if (xss.isEmpty) return Seq.empty[X]
  else loop(xss.tail, xss.head.toSet)
}
println(dups(buffer))

Scastieでこのコードを試すことができます。

このプロパティを確認するには、イテレータで動作するようにロジックを書き直し、それに無限のイテレータを供給しようとします。

import scala.collection.mutable
import scala.annotation.tailrec
val buffer = mutable.ListBuffer(List("a", "b", "c", "d"),
                                List("a", "c", "e", "f"),
                                List("a", "c", "g"))
def dups[X](xss: Iterator[Seq[X]]): Seq[X] = {
  @tailrec
  def loop(dup: Seq[X], xss: Iterator[Seq[X]]): Seq[X] =
    if (dup.isEmpty || !xss.hasNext) dup
    else loop(dup intersect xss.next, xss)
  if (!xss.hasNext) return Seq.empty[X]
  else loop(Seq(xss.next: _*), xss)
}
println(dups(buffer.iterator))
println(dups(buffer.iterator ++ Iterator.single(Seq()) ++ Iterator.continually(Seq("a", "c"))))

Scastieでもこのコードを試すことができます。

両方の実装はスタックセーフです（ @tailrec を介してコンパイラーによって静的にチェックされます）  アノテーション）。

最悪の場合のシナリオは、依然として同じ複雑さを持ちます。

データによっては、他のアプローチを使用することもできます。時間の複雑さをスペースの複雑さと引き換えに喜んでいるなら、 Set との間でコピーできます。 s、これは重複排除に理想的です。

import scala.collection.mutable
val buffer = mutable.ListBuffer(List("a", "b", "c", "d"),
                                List("a", "c", "e", "f"),
                                List("a", "c", "g"))
def dups[X](xss: Seq[Seq[X]]): Seq[X] =
  xss.view.map(_.toSet).reduceOption(_ intersect _).getOrElse(Set.empty[X]).toSeq
println(dups(buffer))

この3番目の例は、Scastieでも利用できます。

このアプローチは、メモリ使用量を犠牲にして（特定の条件でアイテムを別のデータ構造にコピーしているため）時間的に賢明に機能します。もちろん、手元の問題に応じて選択を測定および調整する必要があります。

---

最後の例として、両方のアプローチを同時に使用できます（ Set を使用して実際の改善が見られる場合 s）（次のスニペットのように）（通常、Scastieで利用可能です）：

import scala.collection.mutable
import scala.annotation.tailrec
val buffer = mutable.ListBuffer(List("a", "b", "c", "d"),
                                List("a", "c", "e", "f"),
                                List("a", "c", "g"))
def dups[X](xss: Seq[Seq[X]]): Seq[X] = {
  @tailrec
  def loop(xss: Seq[Seq[X]], dup: Set[X]): Seq[X] =
    xss match {
      case _ if dup.isEmpty || xss.isEmpty => dup.toSeq
      case head +: tail                    => loop(tail, dup intersect head.toSet)
    }
  if (xss.isEmpty) return Seq.empty[X]
  else loop(xss.tail, xss.head.toSet)
}
println(dups(buffer))

解決する方法の1つは、 ListBuffer にリダクションを適用することです 、バッファ内のリストと交差：

val buffer = ListBuffer(List("a", "b", "c", "d"), List("a", "c", "e", "f"), List("a", "c", "g"))
val result = buffer.reduce{ _.intersect(_) }
println(result)
// List(a, c)