Scalaリストの重複を削除する

投稿日: 2022-11-11 2022-11-11
タグ: list, Scala Collections

1. 序章

このチュートリアルでは、Scalaリストから重複する値を削除する方法を見ていきます。

これは、いくつかの慣用的な構成を教えてくれる単純な問題です。それは頻繁に現れます、そしてその解決策はそれが一見するかもしれないほど明白ではありません。

2. ソリューションの説明

この問題の解決策を考えるときは、期待される出力がどうあるべきかを考慮する必要があります。

最良のシナリオでは、重複する要素のないリストで、結果のリストは入力リストと同じである必要があります
最悪の場合、すべての要素が同一のリストの場合、結果は単一の要素を持つリストになります。
そして、空のリストの退化したケースでは、結果も空のリストになるはずです

この問題が些細なことではない原因となるいくつかの要因があります。

2.1. 重複があいまいです

アトミック値の場合、同等性の評価は簡単です。オブジェクトの場合、同等性はクラスのフィールドのサブセットに基づいている可能性があるため、これだけでは不十分です。

2.2. リストは効率的なコレクションではありません

リストは非常に直感的なコレクションであり、多くの目的に最適です。これらは、一部の操作（最初に要素を挿入するなど）や再帰的アルゴリズムの構築に適しています。

そうは言っても、リストはインデックスを持たないコレクションです。その要素へのランダムアクセスはなく、どのタイプの固有の順序もありません。実際には、リストから重複を削除することは、他のコレクションよりも複雑で費用がかかります。実際、複製を許可しないコレクション（セット）や、マップのように自然にインデックス付けされるコレクション（たとえば、IDによって）があります。

リストから重複を削除したい場合、リストコレクションにはアルゴリズムがないため、そのためのアルゴリズムを作成する必要があります。さらに、上記の考慮事項のために、それが超高速ではないことを認識する必要があります。

2.3. 怠惰は使用できません

もう1つの注意点は、リストだけでなく、どのコレクションにも言えることですが、リストから重複を見つけて削除することは、有限のリストに対してのみ機能するということです。機能の世界では、必要に応じて要素を怠惰な方法で計算するだけの無限のコレクションを見つけることがよくあります。 作成するアルゴリズムが有限リストで機能することを確認する必要があります。無限リストから重複要素を削除することは、ストリームから要素をフィルタリングして、すでに受信されている要素を削除することと同じです。

3. 重複排除のテスト

重複排除アルゴリズムのコーディングを開始する前に、記述内容が正しいかどうかをテストする方法が必要です。

2つのケースをテストします。

整数のリスト
オブジェクトのリスト

3.1. 整数のリストでの重複排除

これは最も単純なケースです。

class DuplicatesRemoverSpec extends AnyWordSpec {
  // ...
  "DuplicatesRemover" should {
    "return a shorter integers list without duplicates" in {
      val withDuplicates = List(3, 7, 2, 7, 1, 3, 4)
      val withoutDuplicates = List(3, 7, 2, 1, 4)
      assertResult(withoutDuplicates)(
        DuplicatesRemover.removeDuplicatesRecursively(withDuplicates))
      assertResult(withoutDuplicates)(
        DuplicatesRemover.removeDuplicatesIteratively(withDuplicates))
    }
  // ...
}

3.2. オブジェクトのリストでの重複排除

テストは次のように開始されます。

class DuplicatesRemoverSpec extends AnyWordSpec {

  "DuplicatesRemover" should {
    // ...
     "de-duplicate lists of objects" in {
      case class FullIdentityPerson(userId: String, firstName: String, lastName: String)

      // First, let's test full equivalence
      val withFullDuplicates = List(
        FullIdentityPerson(userId = "mm01", firstName = "Mickey", lastName = "Mouse"),
        FullIdentityPerson(userId = "jw04", firstName = "John", lastName = "Wayne"),
        FullIdentityPerson(userId = "mm01", firstName = "Marilyn", lastName = "Manson"),
        FullIdentityPerson(userId = "sh01", firstName = "Sherlock", lastName = "Holmes"),
        FullIdentityPerson(userId = "mm01", firstName = "Mickey", lastName = "Mouse"),
        FullIdentityPerson(userId = "jw04", firstName = "John", lastName = "Watson")
      )
      val withoutFullDuplicates = List(
        FullIdentityPerson(userId = "mm01", firstName = "Mickey", lastName = "Mouse"),
        FullIdentityPerson(userId = "jw04", firstName = "John", lastName = "Wayne"),
        FullIdentityPerson(userId = "mm01", firstName = "Marilyn", lastName = "Manson"),
        FullIdentityPerson(userId = "sh01", firstName = "Sherlock", lastName = "Holmes"),
        FullIdentityPerson(userId = "jw04", firstName = "John", lastName = "Watson")
      )
      assertResult(withoutFullDuplicates)(
        DuplicatesRemover.removeDuplicatesRecursively(withFullDuplicates))
      assertResult(withoutFullDuplicates)(
        DuplicatesRemover.removeDuplicatesIteratively(withFullDuplicates))
      // ...
    }
  }
}

4. 再帰的アプローチ

ここで説明する最初のアプローチは最も効率的ではありませんが、非常に直感的でエレガントであり、より効率的なアプローチへの道を開くという利点があります。

主なアイデアは非常に単純です。次のような再帰関数を使用します。

リストの最後の要素と、最後の要素のないリストを別々に受け取ります
最後の要素がすでにリストにあるかどうかを調べます
- そうである場合は、重複する要素を削除し、最後の要素を添付して、受信したリストを返します
- それ以外の場合は、受信したリストのみを返し、重複する要素を削除します

上記の説明のキートークンは、再帰的な呼び出しであるため、「重複する要素が削除された」です。コードは次のようになります。

def removeDuplicatesRecursively[T](list: List[T]): List[T] = {
  def assessRemoval(init: List[T], last: T): List[T] =
    if (init.isEmpty) List(last)
    else {
      val recursiveList = assessRemoval(init.init, init.last)
      if (init.contains(last)) recursiveList
      else recursiveList :+ last
    }

  if (list.isEmpty) list
  else assessRemoval(list.init, list.last)
}

5. 反復アプローチ

上記の再帰的アプローチは、エレガントで理解しやすいものです。残念ながら、それは大きな問題を抱えています。 再帰関数は末尾再帰ではないため、連続して呼び出すたびに、より多くのヒープメモリが消費されます。したがって、非常に長いリストの場合、メモリの枯渇が発生するポイントがあります。

これを回避するには、非再帰的なアプローチを設計する必要があります。 すべてのシーケンスから派生したコレクションが持つ非常に効率的で非常に用途の広いメカニズムである折りたたみを利用します。

空のリストから始めて、元のリストの各要素をスキャンし、それがすでに新しいリストにある場合は無視します。それ以外の場合は、新しいリストに追加します。

def removeDuplicatesIteratively[T](list: List[T]): List[T] =
  list.foldLeft(List.empty[T]) { (partialResult, element) =>
    if (partialResult.contains(element)) partialResult
    else partialResult :+ element
  }

5.1. 可能な最適化

前に述べたように、リストは比較を実行するための最も効率的な構造ではありません。 この問題がメモ化の形で最適化の機会を提供し、要素がすでにリストにあるかどうかを記録するための追加の構造を使用していることを理解するのは難しくありません。重複が多い場合、これにより、より多くのメモリとより複雑な実装を犠牲にして、プロセスの実行時間を短縮できます。

6. Scalaライブラリの使用

よくあることですが、Scalaライブラリは、私たちが現場で直面する問題の多くに対して効率的なソリューションを実装しています。この特定のケースでは、 Seq 基本クラス（ List は特殊化）には、distinctというメソッドがあります。したがって、実装は次のように単純に見える可能性があります。

def removeDuplicatesWithLibrary[T](list: List[T]): List[T] =
  list.distinct

比較が実行される前に要素を変換する関数を受け入れるdistinctメソッド、またはより柔軟なdistinctByを常に直接使用できます。

ListをSetに一時的に変換してから、 List に戻すことで、重複する要素を削除することもできます。これは、Listの基本機能の1つです。 X183X] Set は、重複する要素を許可しないということです。

def removeDuplicatesViaSet[T](list: List[T]): List[T] = list.toSet.toList

ただし、 Set は順序付けられていないコレクションであるため、結果の List で要素の順序が変更される危険性があるため、このアプローチはお勧めしません。

7. 結論

リストから重複する要素を削除することは、アルゴリズム的に言えば興味深い問題です。学術演習や技術面接に頻繁に登場します。それが専門分野に現れるとき、それは通常、リストの要素の数がそれほど多くなく、厳しいパフォーマンスの制約がない、制御された状況で行われます。

実際の状況では、長いリストに重複が含まれている可能性があり、それらが削除される場合、最善の哲学は、そもそも問題に直面しないように代替構造を考えることです。

いつものように、記事の完全なソースコードはGitHubで入手できます。

getdocs

13036