Wie kann ich mehrere Listen mit Ruby zusammenführen und sortieren?

Question

Ich habe 2 Listen, die Daten und Daten haben. Jede Liste befindet sich in der richtigen Reihenfolge, wie in der Sequenznummer angegeben. Jetzt muss ich die 2 Listen zusammenführen und alles in der richtigen Reihenfolge halten.

Zum Beispiel:

Liste A
20101001 A-Daten 1 SEQ1
20101001 A-Daten 2 seq2
20101005 A Daten 3 SEQ3

Liste B
20101001 B-Daten 1 SEQ1
20101003 B Daten 2 Seq2

etc ...

ich die neue Liste müssen wie folgt aussehen:

20101001 Daten 1 seq1
20101001 Daten 2 seq2
20101001 B Daten 1 SEQ3
20.101.003 B-Daten 2 Seq4
20101005 A data 3 seq5

2 Dinge, an die ich gedacht habe, ist die Zusammenführung der Listen und Die Sequenznummer vor dem Einfügen in eine db anwenden oder ich kann sie in die db mit der aktuellen Sequenz einfügen und sie wieder herausziehen, um sie zusammenzufügen, aber das scheint wie ein zusätzlicher Schritt und kludgy.

Irgendwelche Ideen über den besten Weg, um darüber zu gehen?

Answer 1

Angenommen, Ihre Listen befinden sich in Ruby-Arrays und die Objekte in den Listen haben Attribute definiert (z. B. obj.sequence_number), eine Art und Weise zu verschmelzen und die Listen zu sortieren wäre:

zuerst die Listen als Union fusionieren:

@merged_list = @list_a | @list_b 

Dann sortieren Sie den merged_list mit der entsprechenden Sortierregel:

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

Bearbeiten:

Sobald das zusammengeführte Array sortiert ist, können Sie die Sequenznummer neu definieren:

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

Edit:

Gleiche gilt, wenn Ihre Objekte in den Listen sind selbst nur einfache Arrays:

@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

Versuchen Sie folgendes:

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

Answer 3

Dieser Algorithmus ist ein für die Zusammenführung beliebig viele sortierte Listen in mehr oder weniger linearer Zeit:

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] 

Es findet für jede Iteration die Liste mit dem kleinsten ersten Element und verschiebt dieses Element daraus in die Ergebnisliste. Dies geschieht so lange, bis alle Listen leer sind.

Ich sage mehr oder weniger lineare Zeit, da es eigentlich O (n × m) ist, wo n ist die Anzahl der Listen und m ist die Gesamtzahl der Elemente in den Listen, aber ich denke, das kann sicher zu O vereinfacht werden (m) für die meisten Fälle, da n im Vergleich zu m klein ist.

Answer 4

Dies verwendet with_index, die eine nette Weise ist einen Indexwert zu einem Iterator hinzuzufügen:

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 

---

Hier einige Varianten mit Benchmarks:

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) 

Es Benchmark gut ist.