私は
ListBuffer[List[String]]
を持っています
。リストの中で共通の要素を見つけたいです。
サンプル入力:
ListBuffer[List["a", "b", "c", "d"], List["a", "c", "e", "f"], List["a", "c", "g"]]
出力:
List["a", "c"]
私は次のことをしていますが、効率的ではなく、大きなリストの場合は時間がかかります。
val _length = _listBuffer.length
val _flattenList = _listBuffer.flatten
val _commonValues = _flattenList.groupBy(identity).mapValues(_.size)
.filter({ case (x, y) => y == _length })
.keys
回答 2 件
解決する方法の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)
シーケンスを処理しているため、この操作は、ネストされた各リスト内の個々のアイテムの合計に比例する複雑さ(最悪の場合のシナリオ)にバインドされています。
ただし、これまでに調査したアイテムの共通要素が空であることがわかっている時点に達したら、早期に終了できます。
Scastieでこのコードを試すことができます。
このプロパティを確認するには、イテレータで動作するようにロジックを書き直し、それに無限のイテレータを供給しようとします。
Scastieでもこのコードを試すことができます。
両方の実装はスタックセーフです(
@tailrec
を介してコンパイラーによって静的にチェックされます) アノテーション)。最悪の場合のシナリオは、依然として同じ複雑さを持ちます。
データによっては、他のアプローチを使用することもできます。時間の複雑さをスペースの複雑さと引き換えに喜んでいるなら、
Set
との間でコピーできます。 s、これは重複排除に理想的です。この3番目の例は、Scastieでも利用できます。
このアプローチは、メモリ使用量を犠牲にして(特定の条件でアイテムを別のデータ構造にコピーしているため)時間的に賢明に機能します。もちろん、手元の問題に応じて選択を測定および調整する必要があります。
最後の例として、両方のアプローチを同時に使用できます(
Set
を使用して実際の改善が見られる場合 s)(次のスニペットのように)(通常、Scastieで利用可能です):