bugfix> scala > 投稿

私は 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 件
  • シーケンスを処理しているため、この操作は、ネストされた各リスト内の個々のアイテムの合計に比例する複雑さ(最悪の場合のシナリオ)にバインドされています。

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

    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)
    
    

あなたの答え