Ordenar una matriz de números según un orden dado

Tengo dos matrices. La primera matriz contiene el orden de clasificación. La segunda matriz contiene una cantidad arbitraria de elementos.Ordenar una matriz de números según un orden dado

Tengo la propiedad de que todos los elementos (en cuanto a los valores) del segundo conjunto están garantizados en el primer conjunto, y solo estoy trabajando con números.

A = [1,3,4,4,4,5,2,1,1,1,3,3] 
Order = [3,1,2,4,5]

Cuando especie A, me gustaría que los elementos que aparecen en el orden especificado por Order:

[3, 3, 3, 1, 1, 1, 1, 2, 4, 4, 4, 5]

Tenga en cuenta que los duplicados son presa. Los elementos en A no deben ser alterados, solo reordenados. ¿Cómo puedo hacer esto?

Fuente

2012-05-13 MxyL

No debe comenzar sus nombres de variable con letras mayúsculas, ya que se convierten en constantes. Además, ¿no hay valores en 'A' que no sean los de' Order'? –

Para este caso particular, sí, no hay otros valores. Si alguna matriz originalmente tuviera otros valores, se eliminarían por filtración antes de llegar a este tipo. – MxyL

>> source = [1,3,4,4,4,5,2,1,1,1,3,3] 
=> [1, 3, 4, 4, 4, 5, 2, 1, 1, 1, 3, 3] 
>> target = [3,1,2,4,5] 
=> [3, 1, 2, 4, 5] 
>> source.sort_by { |i| target.index(i) } 
=> [3, 3, 3, 1, 1, 1, 1, 2, 4, 4, 4, 5]

Fuente

2012-05-13 18:18:25 Gareth

+1. Me pegaste con eso por 19 segundos, borré mi respuesta :-) –

@MichaelKohl, hiciste una buena observación que si este arreglo es probable que sea grande, entonces el enfoque podría ser reconsiderado, pero esto debería ser lo suficientemente rápido para la mayoría de los propósitos. – Gareth

Si (y sólo si!) @ Respuesta de Gareth resulta ser demasiado lento, en lugar de ir con:

# Pre-create a hash mapping value to index once only… 
index = Hash[ Order.map.with_index.to_a ] #=> {3=>0,1=>1,2=>2,4=>3,5=>4} 

# …and then sort using this constant-lookup-time 
sorted = A.sort_by{ |o| index[o] }

Benchmarked:

require 'benchmark' 

order = (1..50).to_a.shuffle 
items = 1000.times.map{ order.sample } 
index = Hash[ order.map.with_index.to_a ] 

Benchmark.bmbm do |x| 
    N = 10_000 
    x.report("Array#index"){ N.times{ 
    items.sort_by{ |n| order.index(n) } 
    }} 
    x.report("Premade Hash"){ N.times{ 
    items.sort_by{ |n| index[n] } 
    }} 
    x.report("Hash on Demand"){ N.times{ 
    index = Hash[ order.map.with_index.to_a ] 
    items.sort_by{ |n| index[n] } 
    }} 
end 

#=>      user  system  total  real 
#=> Array#index  12.690000 0.010000 12.700000 (12.704664) 
#=> Premade Hash  4.140000 0.000000 4.140000 ( 4.141629) 
#=> Hash on Demand 4.320000 0.000000 4.320000 ( 4.323060)

Fuente

2012-05-13 18:41:16 Phrogz

'# sort_by' ya genera internamente una matriz temporal de valores de asignación: ¿es esta caché Hash más eficiente que la matriz de tuplas [a la que se hace referencia en la documentación] (http://apidock.com/ruby/Enumerable/sort_by)? – Gareth

@Gareth Sí, porque _n_ valores en una matriz de tamaño _m_ que usa 'Array # index' requiere en promedio _n * m/2_ operaciones (peor caso: _n * m_), mientras usa la búsqueda hash siempre usa solo _m_ operations (o _n + m_ para el caso en el que se incluye el tiempo hash en el cálculo). Por otra parte, el _n_ for 'index' tiene que tener lugar en la lenta tierra de Ruby, mientras que _n_ con la preparación de hash tiene lugar casi por completo en C. Vea mi edición. – Phrogz

@Gareth Pero, como dijo en su comentario, su respuesta probablemente será "lo suficientemente rápida" la mayor parte del tiempo. Por ejemplo, ordenar una matriz de 50 elementos con uno de 10 valores es de aproximadamente 30μs usando tu camino y 15-20μs a mi manera. :) – Phrogz

Otra solución posible sin clasificación explícita:

source = [1,3,4,4,4,5,2,1,1,1,3,3] 
target = [3,1,2,4,5] 
source.group_by(&lambda{ |x| x }).values_at(*target).flatten(1)

Fuente

2012-05-14 14:05:57

Ordenar una matriz de números según un orden dado

Respuesta

Cuestiones relacionadas