Tengo las siguientes matrices:
a = [1, 1, 1, 1, 3] b = [2, 3, 2, 3, 3] c = [1, 1, 1, 1, 3]mi objetivo es calcular la cantidad de repeticiones adicionales para cada columna. Lo que significa en este caso que [1,2,1] aparece dos veces, lo que significa 1 duplicado, y lo mismo para [1,3,1], por lo que en total la cantidad de duplicados es 2, una para [1,2,1] y otra para [1,3,1]. He desarrollado las siguientes 2 soluciones pero, para ser honesto, no sé cuál es la que mejor funciona y por qué:
Solución 1:
sum = 0 zip = a.zip(b, c) zip.group_by { |e| e} .select { |_, value| value.size > 1 } .each_value { |value| sum += (value.size - 1) } return sumSolución 2:
zip = a.zip(b, c) hash = Hash.new(0) zip.each { |e| hash.store(e, hash[e]+1) } hash.each{|e, _| hash[e] -= 1} return hash.sum {|e, _| hash[e] }gracias de antemano
Ilustrando la evaluación comparativa:
require 'benchmark' v1 = [1, 1, 1, 1] v2 = [2, 3, 2, 3] v3 = [1, 1, 1, 1 ] def sol_1(a,b,c) sum = 0 zip = a.zip(b, c) zip.group_by { |e| e} .select { |_, value| value.size > 1 } .each_value { |value| sum += (value.size - 1) } return sum end def sol_2(a,b,c) zip = a.zip(b, c) hash = Hash.new(0) zip.each { |e| hash.store(e, hash[e]+1) } hash.each{|e, _| hash[e] -= 1} return hash.sum {|e, _| hash[e] } end n=1_000 Benchmark.bmbm do |x| x.report("sol_1"){n.times{sol_1(v1, v2, v3)} } x.report("sol_2"){n.times{sol_2(v1, v2, v3)} } endResultados en:
Rehearsal ----------------------------------------- sol_1 0.011076 0.000000 0.011076 ( 0.011091) sol_2 0.012276 0.000000 0.012276 ( 0.012355) -------------------------------- total: 0.023352sec user system total real sol_1 0.007206 0.000000 0.007206 ( 0.007212) sol_2 0.011452 0.000000 0.011452 ( 0.011453)Entonces, con solo leerlo, ambas soluciones tienen un enfoque muy similar. Si bien no estoy 100% seguro de lo que quiere decir con most performing , supongo que se refiere a la complejidad computacional de ambas soluciones, por lo que el costo computacional para entradas grandes. Cuando hay muchas columnas, el único elemento de la solución que toma tiempo es iterar sobre la matriz de columnas; todo lo demás tomará muy poco tiempo en comparación.
Entonces, en la primera solución, está iterando 3 veces: una para agrupar las columnas, la segunda para seleccionar las que tienen duplicados y luego la tercera vez para contar las repeticiones (sin embargo, aquí, en el peor de los casos, la matriz sobre la que itera tiene como máximo N/2 elementos). Entonces, en total, tiene 2.5 iteraciones sobre una matriz de columnas.
En la segunda solución, también está iterando 3 veces. En primer lugar, sobre la matriz de columnas para contar cuántas veces aparecen, luego sobre el resultado (que en el peor de los casos tiene la misma cantidad de elementos) para restar uno de cada número y finalmente para sumar los números: esto da aproximadamente 3 iteraciones .
Por lo tanto, la primera solución podría ser un poco más eficaz; sin embargo, cuando se trata de complejidad, observamos el tipo de función ignorando el número que tiene delante; en este caso, ambas soluciones son lineales. Además, los diferentes métodos se optimizan de manera diferente en Ruby. Entonces, la única esperanza de determinar cuál tiene más rendimiento sería con los puntos de referencia: repetir esos algoritmos 100 veces para (las mismas) 10000 columnas toma 10.5 segundos para la primera solución y 18 segundos para la segunda solución.
Aquí hay una solución ligeramente (20%) más rápida para el punto de referencia de @steenslag:
require 'matrix' def sol_3(matrix) Matrix. columns(matrix). to_a. each_with_object({}) { |e, a| digest = e.hash a[digest] = a[digest].nil? ? 1 : a[digest] + 1 }.sum { |_, v| v > 1 ? 1 : 0 } end user system total real sol_1 0.006908 0.000008 0.006916 ( 0.006917) sol_2 0.011866 0.000018 0.011884 ( 0.011902) sol_3 0.005532 0.000008 0.005540 ( 0.005555)Guión completo: https://gist.github.com/jaredbeck/edc708df10fcc0267db80bf1c31c8298