Come posso unire e ordinare più elenchi usando Ruby?

Question

Ho 2 elenchi con date e dati. Ogni lista è nell'ordine corretto come indicato dal numero di sequenza. Ora ho bisogno di unire le 2 liste insieme e mantenere tutto nell'ordine corretto.

Ad esempio:

elenco A
20101001 A dati 1 seq1
20101001 A dati 2 SEQ2
20101005 A dati 3 SEQ3

Elenco B
20101001 B dati 1 SEQ1
20101003 B data 2 seq2

ecc ...

ho bisogno la nuova lista di simile a questa:

20101001 A Dati 1 SEQ1
20101001 A Dati 2 seq2
20.101.001 i dati 1 SEQ3
20.101.003 dati 2 seq4
20101005 A data 3 seq5

2 cose che ho pensato di unire le liste insieme e applicando il numero di sequenza prima di inserirli in un db o posso inserirli nel db con la sequenza corrente e rimuoverli di nuovo per unirli insieme, ma questo sembra un ulteriore passaggio e kludgy.

Qualche idea sul modo migliore per farlo?

Answer 1

Assumendo che le liste siano in Ruby Arrays e gli oggetti nelle liste abbiano attributi definiti (come ad esempio obj.sequence_number), un modo per unire e ordinare le liste sarebbe:

Prima unire le liste come unione:

@merged_list = @list_a | @list_b 

quindi ordinare la merged_list con la regola di ordinamento appropriata:

@merged_list.sort! {|a, b| a.date <=> b.date # or whatever your sorting rule is... } 

Edit:

Una volta che l'array unito è ordinato, è possibile ri-definire il sequence_number:

@merged_list.each_with_index {|obj, index| obj.sequence_number = "seq#{index+1}"} 

Edit:

La stessa cosa si applica se gli oggetti negli elenchi sono essi stessi le matrici solo semplici:

@merged_list.sort! {|a, b| a[0] <=> b[0] # or whatever your sorting rule is... } 
@merged_list.each_with_index {|obj, index| obj[2] = "seq#{index+1}"} 

Answer 2

Prova questo:

(listA + listB).sort!{|a, b| a.sequence_no <=> b.sequence_no} 

Answer 3

Si tratta di un algoritmo per la fusione di un numero arbitrario di elenchi ordinati in un tempo più o meno lineare:

def merge_sorted(*lists) 
    # the lists will be modified, so make (shallow) copies 
    lists = lists.map(&:dup) 
    result = [] 
    loop do 
    # ignore lists that have been exhausted 
    lists = lists.reject(&:empty?) 
    # we're done if all lists have been exhausted 
    break if lists.empty? 
    # find the list with the smallest first element 
    top = lists.inject do |candidate, other| 
     candidate.first < other.first ? candidate : other 
    end 
    result << top.shift 
    end 
    result 
end 

list1 = [1, 2, 5, 6, 9] 
list2 = [2, 3, 4, 11, 13] 
list3 = [1, 2, 2, 2, 3] 

p merge_sorted(list1, list2, list3) 
    # => [1, 1, 2, 2, 2, 2, 2, 3, 3, 4, 5, 6, 9, 11, 13] 

Per ogni iterazione trova l'elenco con il primo elemento più piccolo e sposta questo elemento da esso nell'elenco dei risultati. Lo fa fino a quando tutte le liste sono vuote.

dico più o meno tempo lineare dal momento che è in realtà O (n × m), dove n è il numero di liste e m è il numero totale di elementi negli elenchi ma penso che questo può tranquillamente essere semplificata in O (m) per la maggior parte dei casi poiché n sarà piccolo rispetto a m.

Answer 4

Questo utilizza with_index che è un bel modo per aggiungere un valore di indice di un iteratore:

result = (list_a + list_b).sort_by { |a| a[0 .. -2] }.map.with_index { |a, i| a[0 .. -2] + (1 + i).to_s } 
puts result 
# >> 20101001 A data 1 seq1 
# >> 20101001 A data 2 seq2 
# >> 20101001 B data 1 seq3 
# >> 20101003 B data 2 seq4 
# >> 20101005 A data 3 seq5 

---

Ecco alcune varianti con parametri di riferimento:

require 'benchmark' 

list_a = [ 
    '20101001 A data 1 seq1', 
    '20101001 A data 2 seq2', 
    '20101005 A data 3 seq3' 
] 

list_b = [ 
    '20101001 B data 1 seq1', 
    '20101003 B data 2 seq2' 
] 

# #1 
result = (list_a + list_b).sort_by { |a| a[0 .. -2] }.map.with_index { |a, i| a[0 .. -2] + (1 + i).to_s } 
result # => ["20101001 A data 1 seq1", "20101001 A data 2 seq2", "20101001 B data 1 seq3", "20101003 B data 2 seq4", "20101005 A data 3 seq5"] 

# #2 
result = (list_a + list_b).map{ |r| r[0 .. -2] }.sort.map.with_index { |a, i| a + (1 + i).to_s } 
result # => ["20101001 A data 1 seq1", "20101001 A data 2 seq2", "20101001 B data 1 seq3", "20101003 B data 2 seq4", "20101005 A data 3 seq5"] 

# #3 
i = 0 
result = (list_a + list_b).map{ |r| r[0 .. -2] }.sort.map { |a| i += 1; a + i.to_s } 
result # => ["20101001 A data 1 seq1", "20101001 A data 2 seq2", "20101001 B data 1 seq3", "20101003 B data 2 seq4", "20101005 A data 3 seq5"] 

# #4 
i = 0; result = (list_a + list_b).sort.map { |a| i += 1; a[-1] = i.to_s; a } 
result # => ["20101001 A data 1 seq1", "20101001 A data 2 seq2", "20101001 B data 1 seq3", "20101003 B data 2 seq4", "20101005 A data 3 seq5"] 

n = 75000 
Benchmark.bm(7) do |x| 
    x.report('#1') { n.times { (list_a + list_b).sort_by { |a| a[0 .. -2] }.map.with_index { |a, i| a[0 .. -2] + (1 + i).to_s } } } 
    x.report('#2') { n.times { (list_a + list_b).map{ |r| r[0 .. -2] }.sort.map.with_index { |a, i| a + (1 + i).to_s } } } 
    x.report('#3') { n.times { i = 0; (list_a + list_b).map{ |r| r[0 .. -2] }.sort.map { |a| i += 1; a + i.to_s } } } 
    x.report('#4') { n.times { i = 0; (list_a + list_b).sort.map { |a| i += 1; a[-1] = i.to_s } } } 
end 
# >>    user  system  total  real 
# >> #1  1.150000 0.000000 1.150000 ( 1.147090) 
# >> #2  0.880000 0.000000 0.880000 ( 0.880038) 
# >> #3  0.720000 0.000000 0.720000 ( 0.727135) 
# >> #4  0.580000 0.000000 0.580000 ( 0.572688) 

E 'bello benchmark.