list - remove - linq eliminate duplicates

¿Cómo encontrar duplicados en una lista?

Question

Tengo una lista de enteros sin clasificar y quiero encontrar aquellos elementos que tienen duplicados.

val dup = List(1,1,1,2,3,4,5,5,6,100,101,101,102)

Puedo encontrar los distintos elementos del conjunto con dup.distinct, por lo que escribí mi respuesta de la siguiente manera.

val dup = List(1,1,1,2,3,4,5,5,6,100,101,101,102)
val distinct = dup.distinct
val elementsWithCounts = distinct.map( (a:Int) => (a, dup.count( (b:Int) => a == b )) )
val duplicatesRemoved = elementsWithCounts.filter( (pair: Pair[Int,Int]) => { pair._2 <= 1 } )
val withDuplicates = elementsWithCounts.filter( (pair: Pair[Int,Int]) => { pair._2 > 1 } )

¿Hay una manera más fácil de resolver esto?

Answer 1

Mi favorito es

def hasDuplicates(in: List[Int]): Boolean = {
  val sorted = in.sortWith((i, j) => i < j)
  val zipped = sorted.tail.zip(sorted)
  zipped.exists(p => p._1 == p._2)
}

Answer 2

Otro enfoque es usar foldLeft y hacerlo de la manera más difícil.

Comenzamos con dos sets vacíos. Uno es para los elementos que hemos visto al menos una vez. El otro para los elementos que hemos visto al menos dos veces (también conocidos como duplicados).

Atravesamos la lista. Cuando el elemento actual ya se ha visto ( seen(cur) ) es un duplicado y, por lo tanto, se agrega a los duplicates . De lo contrario lo añadimos a seen . El resultado es ahora el segundo conjunto que contiene los duplicados.

También podemos escribir esto como un método genérico.

def dups[T](list: List[T]) = list.foldLeft((Set.empty[T], Set.empty[T])){ case ((seen, duplicates), cur) => 
  if(seen(cur)) (seen, duplicates + cur) else (seen + cur, duplicates)      
}._2

val dup = List(1,1,1,2,3,4,5,5,6,100,101,101,102)

dups(dup) //Set(1,5,101)

Answer 3

Prueba esto:

val dup = List(1,1,1,2,3,4,5,5,6,100,101,101,102)
dup.groupBy(identity).collect { case (x, List(_,_,_*)) => x }

El groupBy asocia cada entero distinto con una lista de sus ocurrencias. La collect es básicamente un map donde se ignoran los elementos no coincidentes. El siguiente patrón de coincidencia coincidirá con los enteros x que están asociados con una lista que se ajusta a la List(_,_,_*) patrones List(_,_,_*) , una lista con al menos dos elementos, cada uno representado por un guión bajo, ya que en realidad no necesitamos almacene esos valores (y esos dos elementos pueden ir seguidos de cero o más elementos: _* ).

También podrías hacer:

dup.groupBy(identity).collect { case (x,ys) if ys.lengthCompare(1) > 0 => x }

Es mucho más rápido que el enfoque que proporcionó, ya que no tiene que pasar repetidamente por los datos.

Answer 4

Un poco tarde para la fiesta, pero aquí hay otro enfoque:

dup.diff(dup.distinct).distinct

diff le proporciona todos los elementos adicionales sobre los del argumento ( dup.distinct ), que son los duplicados.

Answer 5

Resumen: escribí una función muy eficiente que devuelve tanto List.distinct como una List consta de cada elemento que apareció más de una vez y el índice en el que apareció el elemento duplicado.

Detalles: si necesita un poco más de información sobre los duplicados, como lo hice yo, escribí una función más general que se repite en una List (ya que el pedido fue significativo) exactamente una vez y devuelve una Tuple2 consta de la List original deducida (todo se eliminan los duplicados después del primero, es decir, lo mismo que invocar distinct ) y una segunda List muestra cada duplicado y un índice Int en el que ocurrió dentro de la List original.

He implementado la función dos veces según las características de rendimiento generales de las colecciones de Scala ; filterDupesL (donde la L es para lineal) y filterDupesEc (donde la Ec es para efectivamente constante).

Aquí está la función "lineal":

def filterDupesL[A](items: List[A]): (List[A], List[(A, Int)]) = {
  def recursive(
      remaining: List[A]
    , index: Int =
        0
    , accumulator: (List[A], List[(A, Int)]) =
        (Nil, Nil)): (List[A], List[(A, Int)]
  ) =
    if (remaining.isEmpty)
      accumulator
    else
      recursive(
          remaining.tail
        , index + 1
        , if (accumulator._1.contains(remaining.head)) //contains is linear
          (accumulator._1, (remaining.head, index) :: accumulator._2)
        else
          (remaining.head :: accumulator._1, accumulator._2)
      )
  val (distinct, dupes) = recursive(items)
  (distinct.reverse, dupes.reverse)
}

El siguiente es un ejemplo que podría hacerlo un poco más intuitivo. Teniendo en cuenta esta lista de valores de cadena:

val withDupes =
  List("a.b", "a.c", "b.a", "b.b", "a.c", "c.a", "a.c", "d.b", "a.b")

... y luego realizar lo siguiente:

val (deduped, dupeAndIndexs) =
  filterDupesL(withDupes)

... los resultados son:

deduped: List[String] = List(a.b, a.c, b.a, b.b, c.a, d.b)
dupeAndIndexs: List[(String, Int)] = List((a.c,4), (a.c,6), (a.b,8))

Y si solo quieres los duplicados, simplemente dupeAndIndexes e invoca distinct :

val dupesOnly =
  dupeAndIndexs.map(_._1).distinct

... o todo en una sola llamada:

val dupesOnly =
  filterDupesL(withDupes)._2.map(_._1).distinct

... o si se prefiere un Set , omita el distinct e invoque toSet ...

val dupesOnly2 =
  dupeAndIndexs.map(_._1).toSet

... o todo en una sola llamada:

val dupesOnly2 =
  filterDupesL(withDupes)._2.map(_._1).toSet

Para listas muy grandes, considere el uso de esta versión más eficiente (que usa un Set adicional para cambiar el control de los contenidos en un tiempo efectivamente constante):

Aquí está la función "Efectivamente constante":

def filterDupesEc[A](items: List[A]): (List[A], List[(A, Int)]) = {
  def recursive(
      remaining: List[A]
    , index: Int =
        0
    , seenAs: Set[A] =
        Set()
    , accumulator: (List[A], List[(A, Int)]) =
        (Nil, Nil)): (List[A], List[(A, Int)]
  ) =
    if (remaining.isEmpty)
      accumulator
    else {
      val (isInSeenAs, seenAsNext) = {
        val isInSeenA =
          seenAs.contains(remaining.head) //contains is effectively constant
        (
            isInSeenA
          , if (!isInSeenA)
              seenAs + remaining.head
            else
              seenAs
        )
      }
      recursive(
          remaining.tail
        , index + 1
        , seenAsNext
        , if (isInSeenAs)
          (accumulator._1, (remaining.head, index) :: accumulator._2)
        else
          (remaining.head :: accumulator._1, accumulator._2)
      )
    }
  val (distinct, dupes) = recursive(items)
  (distinct.reverse, dupes.reverse)
}

Ambas de las funciones anteriores son adaptaciones de la función filterDupes en mi biblioteca de código abierto Scala, ScalaOlio . Se encuentra en org.scalaolio.collection.immutable.List_._ .