objects - Ruby: ¿Cómo encontrar y devolver un valor duplicado en una matriz?

ruby select

Question

arr es una matriz de cadenas, por ejemplo: ["hello", "world", "stack", "overflow", "hello", "again"] .

¿Cuál sería una manera fácil y elegante de verificar si arr tiene duplicados, y si es así, devolver uno de ellos (no importa cuál).

Ejemplos:

["A", "B", "C", "B", "A"]    # => "A" or "B"
["A", "B", "C"]              # => nil

Answer 1

Algo así funcionará

arr = ["A", "B", "C", "B", "A"]
arr.inject(Hash.new(0)) { |h,e| h[e] += 1; h }.
    select { |k,v| v > 1 }.
    collect { |x| x.first }

Es decir, ponga todos los valores en un hash donde key es el elemento de array y value es el número de ocurrencias. Luego selecciona todos los elementos que ocurren más de una vez. Fácil.

Answer 2

Aquí está mi opinión sobre un gran conjunto de datos, como una tabla de dBase heredada para encontrar piezas duplicadas

# Assuming ps is an array of 20000 part numbers & we want to find duplicates
# actually had to it recently.
# having a result hash with part number and number of times part is 
# duplicated is much more convenient in the real world application
# Takes about 6  seconds to run on my data set
# - not too bad for an export script handling 20000 parts

h = {};

# or for readability

h = {} # result hash
ps.select{ |e| 
  ct = ps.count(e) 
  h[e] = ct if ct > 1
}; nil # so that the huge result of select doesn''t print in the console

Answer 3

Aquí hay dos formas más de encontrar un duplicado.

Usa un conjunto

require ''set''

def find_a_dup_using_set(arr)
  s = Set.new
  arr.find { |e| !s.add?(e) }
end

find_a_dup_using_set arr
  #=> "hello" 

Use select en lugar de find para devolver una matriz de todos los duplicados.

Usar la Array#difference

class Array
  def difference(other)
    h = other.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 }
    reject { |e| h[e] > 0 && h[e] -= 1 }
  end
end

def find_a_dup_using_difference(arr)
  arr.difference(arr.uniq).first
end

find_a_dup_using_difference arr
  #=> "hello" 

Suelta. .first para devolver una matriz de todos los duplicados.

Ambos métodos devuelven nil si no hay duplicados.

Propuse que la Array#difference se agregara al núcleo de Ruby. Más información está en mi respuesta here .

Punto de referencia

Vamos a comparar los métodos sugeridos. Primero, necesitamos una matriz para probar:

CAPS = (''AAA''..''ZZZ'').to_a.first(10_000)
def test_array(nelements, ndups)
  arr = CAPS[0, nelements-ndups]
  arr = arr.concat(arr[0,ndups]).shuffle
end

y un método para ejecutar los puntos de referencia para diferentes matrices de prueba:

require ''fruity''

def benchmark(nelements, ndups)
  arr = test_array nelements, ndups
  puts "/n#{ndups} duplicates/n"    
  compare(
    Naveed:    -> {arr.detect{|e| arr.count(e) > 1}},
    Sergio:    -> {(arr.inject(Hash.new(0)) {|h,e| h[e] += 1; h}.find {|k,v| v > 1} ||
                     [nil]).first },
    Ryan:      -> {(arr.group_by{|e| e}.find {|k,v| v.size > 1} ||
                     [nil]).first},
    Chris:     -> {arr.detect {|e| arr.rindex(e) != arr.index(e)} },
    Cary_set:  -> {find_a_dup_using_set(arr)},
    Cary_diff: -> {find_a_dup_using_set(arr)}
  )
end

No incluí la respuesta de @JjP porque solo se devuelve un duplicado, y cuando se modifica su respuesta para hacer eso, es lo mismo que la respuesta anterior de @ Naveed. Tampoco incluí la respuesta de @ Marin, que, aunque se publicó antes de la respuesta de @ Naveed, devolvió todos los duplicados en lugar de uno solo (un punto menor pero no tiene sentido evaluar ambos, ya que son idénticos cuando devuelven solo un duplicado).

También modifiqué otras respuestas que devolvían todos los duplicados para devolver solo el primero encontrado, pero eso no debería tener ningún efecto en el rendimiento, ya que computaron todos los duplicados antes de seleccionar uno.

Primero suponga que la matriz contiene 100 elementos:

benchmark(100, 0)
0 duplicates
Running each test 64 times. Test will take about 2 seconds.
Cary_set is similar to Cary_diff
Cary_diff is similar to Ryan
Ryan is similar to Sergio
Sergio is faster than Chris by 4x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(100, 1)
1 duplicates
Running each test 128 times. Test will take about 2 seconds.
Cary_set is similar to Cary_diff
Cary_diff is faster than Ryan by 2x ± 1.0
Ryan is similar to Sergio
Sergio is faster than Chris by 2x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(100, 10)
10 duplicates
Running each test 1024 times. Test will take about 3 seconds.
Chris is faster than Naveed by 2x ± 1.0
Naveed is faster than Cary_diff by 2x ± 1.0 (results differ: AAC vs AAF)
Cary_diff is similar to Cary_set
Cary_set is faster than Sergio by 3x ± 1.0 (results differ: AAF vs AAC)
Sergio is similar to Ryan

Ahora considere una matriz con 10.000 elementos:

benchmark(10000, 0)
0 duplicates
Running each test once. Test will take about 4 minutes.
Ryan is similar to Sergio
Sergio is similar to Cary_set
Cary_set is similar to Cary_diff
Cary_diff is faster than Chris by 400x ± 100.0
Chris is faster than Naveed by 3x ± 0.1

benchmark(10000, 1)
1 duplicates
Running each test once. Test will take about 1 second.
Cary_set is similar to Cary_diff
Cary_diff is similar to Sergio
Sergio is similar to Ryan
Ryan is faster than Chris by 2x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(10000, 10)
10 duplicates
Running each test once. Test will take about 11 seconds.
Cary_set is similar to Cary_diff
Cary_diff is faster than Sergio by 3x ± 1.0 (results differ: AAE vs AAA)
Sergio is similar to Ryan
Ryan is faster than Chris by 20x ± 10.0
Chris is faster than Naveed by 3x ± 1.0

benchmark(10000, 100)
100 duplicates
Cary_set is similar to Cary_diff
Cary_diff is faster than Sergio by 11x ± 10.0 (results differ: ADG vs ACL)
Sergio is similar to Ryan
Ryan is similar to Chris
Chris is faster than Naveed by 3x ± 1.0

Tenga en cuenta que find_a_dup_using_difference(arr) sería mucho más eficiente si se implementara Array#difference en C, que sería el caso si se añadiera al núcleo de Ruby.

Answer 4

Lamentablemente, la mayoría de las respuestas son O(n^2) .

Aquí hay una solución O(n) ,

a = %w{the quick brown fox jumps over the lazy dog}
h = Hash.new(0)
a.find { |each| (h[each] += 1) == 2 } # => ''the"

¿Cuál es la complejidad de esto?

• Se ejecuta en O(n) y se rompe en el primer partido
• Utiliza memoria O(n) , pero solo la cantidad mínima

Ahora, dependiendo de cuán frecuentes sean los duplicados en su matriz, estos tiempos de ejecución podrían mejorar aún más. Por ejemplo, si la matriz de tamaño O(n) se ha muestreado de una población de k << n diferentes elementos, solo la complejidad para el tiempo de ejecución y el espacio se vuelve O(k) , sin embargo, es más probable que el póster original valide la entrada y quiere asegurarse de que no haya duplicados. En ese caso, tanto el tiempo de ejecución como la complejidad de la memoria O(n) ya que esperamos que los elementos no tengan repeticiones para la mayoría de las entradas.

Answer 5

Los objetos de Ruby Array tienen un excelente método, select .

select {|item| block } → new_ary
select → an_enumerator

La primera forma es lo que te interesa aquí. Le permite seleccionar objetos que pasen una prueba.

Los objetos de Ruby Array tienen otro método, count .

count → int
count(obj) → int
count { |item| block } → int

En este caso, está interesado en duplicados (objetos que aparecen más de una vez en la matriz). La prueba apropiada es a.count(obj) > 1 .

Si a = ["A", "B", "C", "B", "A"] , entonces

a.select{|item| a.count(item) > 1}.uniq
=> ["A", "B"]

Usted declara que solo quiere un objeto. Así que elige uno.

Answer 6

Puedes hacerlo de varias maneras, siendo la primera opción la más rápida:

ary = ["A", "B", "C", "B", "A"]

ary.group_by{ |e| e }.select { |k, v| v.size > 1 }.map(&:first)

ary.sort.chunk{ |e| e }.select { |e, chunk| chunk.size > 1 }.map(&:first)

Y una opción O (N ^ 2) (es decir, menos eficiente):

ary.select{ |e| ary.count(e) > 1 }.uniq

Answer 7

Sé que este hilo trata específicamente sobre Ruby, pero aterricé aquí buscando cómo hacerlo en el contexto de Ruby on Rails con ActiveRecord y pensé que también compartiría mi solución.

class ActiveRecordClass < ActiveRecord::Base
  #has two columns, a primary key (id) and an email_address (string)
end

ActiveRecordClass.group(:email_address).having("count(*) > 1").count.keys

Lo anterior devuelve una matriz de todas las direcciones de correo electrónico que están duplicadas en la tabla de la base de datos de este ejemplo (que en Rails sería "active_record_classes").

Answer 8

Si está comparando dos arreglos diferentes (en lugar de uno contra sí mismo), una forma muy rápida es usar el operador de intersección & proporcionado por la clase Array de Ruby .

# Given
a = [''a'', ''b'', ''c'', ''d'']
b = [''e'', ''f'', ''c'', ''d'']

# Then this...
a & b # => [''c'', ''d'']

Answer 9

Simplemente busque la primera instancia donde el índice del objeto (contando desde la izquierda) no es igual al índice del objeto (contando desde la derecha).

arr.detect {|e| arr.rindex(e) != arr.index(e) }

Si no hay duplicados, el valor de retorno será nulo.

Creo que esta es la solución más rápida publicada en el hilo hasta ahora, ya que no se basa en la creación de objetos adicionales, y #index y #rindex se implementan en C. El tiempo de ejecución de la gran O es N ^ 2 y por lo tanto más lento que el de Sergio, pero el tiempo de pared podría ser mucho más rápido debido al hecho de que las partes "lentas" se ejecutan en C.

Answer 10

find_all() devuelve una array contiene todos los elementos de enum para los que el block no es false .

Para obtener elementos duplicate

>> arr = ["A", "B", "C", "B", "A"]
>> arr.find_all { |x| arr.count(x) > 1 }

=> ["A", "B", "B", "A"]

O duplicar elementos uniq

>> arr.find_all { |x| arr.count(x) > 1 }.uniq
=> ["A", "B"] 

Answer 11

detect solo encuentra un duplicado. find_all los encontrará a todos:

a = ["A", "B", "C", "B", "A"]
a.find_all { |e| a.count(e) > 1 }

Answer 12

each_with_object es tu amigo!

input = [:bla,:blubb,:bleh,:bla,:bleh,:bla,:blubb,:brrr]

# to get the counts of the elements in the array:
> input.each_with_object({}){|x,h| h[x] ||= 0; h[x] += 1}
=> {:bla=>3, :blubb=>2, :bleh=>2, :brrr=>1}

# to get only the counts of the non-unique elements in the array:
> input.each_with_object({}){|x,h| h[x] ||= 0; h[x] += 1}.reject{|k,v| v < 2}
=> {:bla=>3, :blubb=>2, :bleh=>2}

Answer 13

a = ["A", "B", "C", "B", "A"]
a.detect{ |e| a.count(e) > 1 }

Answer 14

a = ["A", "B", "C", "B", "A"]
a.each_with_object(Hash.new(0)) {|i,hash| hash[i] += 1}.select{|_, count| count > 1}.keys

Este es un procedimiento O(n) .

Alternativamente, puede hacer cualquiera de las siguientes líneas. También O (n) pero solo una iteración

a.each_with_object(Hash.new(0).merge dup: []){|x,h| h[:dup] << x if (h[x] += 1) == 2}[:dup]

a.inject(Hash.new(0).merge dup: []){|h,x| h[:dup] << x if (h[x] += 1) == 2;h}[:dup]

Answer 15

a = ["A", "B", "C", "B", "A"]
b = a.select {|e| a.count(e) > 1}.uniq
c = a - b
d = b + c

Resultados

 d
=> ["A", "B", "C"]

Answer 16

def firstRepeatedWord(string)
  h_data = Hash.new(0)
  string.split(" ").each{|x| h_data[x] +=1}
  h_data.key(h_data.values.max)
end

Answer 17

r = [1, 2, 3, 5, 1, 2, 3, 1, 2, 1]

r.group_by(&:itself).map { |k, v| v.size > 1 ? [k] + [v.size] : nil }.compact.sort_by(&:last).map(&:first)