¿La manera más fácil de decidir si la Lista contiene duplicados?

Question

Una forma es esta

list.distinct.size != list.size 

¿Hay alguna manera mejor? Hubiera sido bueno tener un método

Answer 1

Suponiendo que "mejor" significa "más rápido", consulte los enfoques alternativos referenciados en this question, que parece mostrar algunos métodos más rápidos (aunque tenga en cuenta que distinct usa un HashSet y ya es O (n)). YMMV, por supuesto, dependiendo del caso de prueba específico, la versión scala, etc. Probablemente cualquier mejora significativa sobre el enfoque "distinct.size" vendría de una salida temprana tan pronto como se encuentre un duplicado, pero ¿cuánto de una aceleración es realmente obtenido dependería fuertemente de cuán comunes son en realidad los duplicados en su caso de uso.

Si usted quiere decir "mejor" en el que desea escribir list.containsDuplicates en lugar de containsDuplicates(list), utilice una implícita:

implicit def enhanceWithContainsDuplicates[T](s:List[T]) = new { 
    def containsDuplicates = (s.distinct.size != s.size) 
} 

assert(List(1,2,2,3).containsDuplicates) 
assert(!List("a","b","c").containsDuplicates) 

Answer 2

containsDuplicates También puede escribir:

list.toSet.size != list.size 

Sin embargo, el resultado será el mismo porque es distinct ya implemented with a Set. En ambos casos, la complejidad del tiempo debe ser O (n): debe atravesar la lista y la inserción Set es O (1).

Answer 3

Creo que esto sería detendrá tan pronto como se encontró un duplicado y es probablemente más eficaz que haciendo distinct.size - desde asumo distinct mantiene un conjunto así:

@annotation.tailrec 
def containsDups[A](list: List[A], seen: Set[A] = Set[A]()): Boolean = 
    list match { 
    case x :: xs => if (seen.contains(x)) true else containsDups(xs, seen + x) 
    case _ => false 
} 

containsDups(List(1,1,2,3)) 
// Boolean = true 

containsDups(List(1,2,3)) 
// Boolean = false 

Soy consciente de que pidió fácil y no lo hago ahora que esta versión es, pero encontrar un duplicado también es encontrar si hay un EL ement que se ha visto antes:

def containsDups[A](list: List[A]): Boolean = { 
    list.iterator.scanLeft(Set[A]())((set, a) => set + a) // incremental sets 
    .zip(list.iterator) 
    .exists{ case (set, a) => set contains a } 
} 

Answer 4

@annotation.tailrec 
def containsDuplicates [T] (s: Seq[T]) : Boolean = 
    if (s.size < 2) false else 
    s.tail.contains (s.head) || containsDuplicates (s.tail) 

no medí esto, y piensan que es similar a la solución de huynhjl, pero un poco más fácil de entender.

Vuelve pronto, si se encuentra un duplicado, así que busqué en el origen de Seq.contains, si esto retorna temprano, si.

En SeqLike, 'contiene (e)' se define como 'existe (== _ e)', y existe se define en TraversableLike:

def exists (p: A => Boolean): Boolean = { 
    var result = false 
    breakable { 
    for (x <- this) 
     if (p (x)) { result = true; break } 
    } 
    result 
} 

estoy curioso cómo acelerar las cosas con colecciones paralelas en varios núcleos, pero supongo que es un problema general con el retorno anticipado, mientras que otro hilo continuará ejecutándose, porque no sabe, que la solución ya se ha encontrado.

Answer 5

Resumen: He escrito una función muy eficiente que devuelve tanto List.distinct y una List que consiste en que cada elemento que aparece más de una vez y el índice en el cual apareció el elemento duplicado.

Nota: Esta respuesta es una straight copy of the answer on a related question.

Detalles: Si usted necesita un poco más de información acerca de los propios duplicados, como lo hice, me han escrito una función más general que itera a través de una List (como ordenamiento fue significativa) exactamente una vez y devuelve un Tuple2 que consiste del original List deducido (todos duplicados después de que se elimine el primero, es decir, lo mismo que invocar distinct) y un segundo List mostrando cada duplicado y un índice Int en el que ocurrió dentro del List original.

Aquí está la función:

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

Una continuación se muestra un ejemplo que puede que sea un poco más intuitivo. Teniendo en cuenta la 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 el siguiente:

val (deduped, dupeAndIndexs) = 
    filterDupes(withDupes) 

... los resultados son los siguientes:

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 lo que desea el duplicados, simplemente map en dupeAndIndexes e invoque distinct:

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

... o todos en una sola llamada:

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

... o si se prefiere una Set, omita distinct e invocar toSet ...

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

... o todo en una sola llamada:

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

Ésta es una copia directa de la filterDupes funcio n de mi biblioteca de código abierto Scala, ScalaOlio. Se encuentra ubicado en org.scalaolio.collection.immutable.List_._.