Ordina un array di numeri in base a un determinato ordine

Ho due array. Il primo array contiene l'ordinamento. Il secondo array contiene un numero arbitrario di elementi.Ordina un array di numeri in base a un determinato ordine

Ho la proprietà che tutti gli elementi (valore-saggio) dal secondo array sono garantiti per essere nel primo array e sto solo lavorando con i numeri.

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

Quando ho sorta A, vorrei gli elementi ad apparire nell'ordine specificato da Order:

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

Nota che i duplicati sono gioco equo. Gli elementi in A non dovrebbero essere modificati, ma solo riordinati. Come posso fare questo?

fonte

2012-05-13 MxyL

Non si devono iniziare i nomi delle variabili con lettere maiuscole, poiché diventano costanti. Inoltre, non ci sono valori in 'A' diversi da quelli in' Ordine'? –

In questo caso particolare, sì, non ci sono altri valori. Se alcuni array avevano originariamente altri valori, sarebbero stati filtrati prima di arrivare a questo 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]

fonte

2012-05-13 18:18:25 Gareth

+1. Mi hai battuto per 19 secondi, ho cancellato la mia risposta :-) –

@MichaelKohl hai fatto un buon punto che se questo array rischia di diventare grande allora l'approccio potrebbe probabilmente essere riconsiderato, ma questo dovrebbe essere abbastanza veloce per la maggior parte degli scopi – Gareth

Se (e solo se!) @ Risposta di Gareth risulta essere troppo lento, invece andare 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)

fonte

2012-05-13 18:41:16 Phrogz

'# sort_by' già genera internamente una matrice temporanea di valori di mappatura - questa cache hash è più efficiente della serie di tuple [a cui si fa riferimento nella documentazione] (http://apidock.com/ruby/Enumerable/sort_by)? – Gareth

@Gareth Sì, perché per i valori _n_ in un array di dimensioni _m_ utilizzando 'Array # index' richiede in media _n * m/2_ operazioni (caso peggiore: _n * m_), mentre l'uso della ricerca hash utilizza sempre solo operazioni _m_ (o _n + m_ per il caso in cui stai includendo il tempo di hashing nel calcolo). Inoltre, il _n_ per 'index' deve avere luogo in Slow Ruby land, mentre il _n_ con la preparazione di hash avviene quasi interamente in C. Vedi la mia modifica. – Phrogz

@Gareth Ma, come hai detto nel tuo commento, la tua risposta sarà probabilmente "abbastanza veloce" il più delle volte. Ad esempio, l'ordinamento di una matrice di 50 elementi con uno di 10 valori è di circa 30μs a modo tuo e 15-20μs a modo mio. :) – Phrogz

Un'altra possibile soluzione senza cernita esplicita:

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)

fonte

2012-05-14 14:05:57

Ordina un array di numeri in base a un determinato ordine

risposta

Problemi correlati