¿Cómo puedo combinar y ordenar varias listas usando Ruby?

Question

Tengo 2 listas que tienen fechas y datos. Cada lista está en el orden correcto según lo indicado por el número de secuencia. Ahora necesito unir las 2 listas y mantener todo en el orden correcto.

Por ejemplo:

Lista A
20101001 A datos 1 seq1
20101001 datos A 2 SEQ2
20101005 datos A 3 seq3

Lista B
20101001 B de datos 1 seq1
20101003 B datos 2 seq2

etc ...

necesito la nueva lista para el siguiente aspecto:

20101001 datos A 1 SEQ1
20101001 datos A 2 SEQ2
20101001 B de datos 1 seq3
20101003 B de datos 2 SEQ4
20101005 A data 3 seq5

2 cosas que pensé en fusionar las listas y aplicando el número de secuencia antes de insertarlos en un db o puedo insertarlos en el db con la secuencia actual y sacarlos de nuevo para unirlos, pero eso parece un paso extra y kludgy.

¿Alguna idea sobre la mejor manera de hacerlo?

Answer 1

Suponiendo que sus listas están en matrices de Ruby, y los objetos en las listas tienen atributos definidos (como obj.sequence_number), una forma de combinar y ordenar las listas sería:

Primera fusionar las listas como una unión:

@merged_list = @list_a | @list_b 

Luego, ordenar la merged_list con la regla de clasificación correspondiente:

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

Editar:

Una vez que se haya ordenado el conjunto combinado, puede volver a definir el número de secuencia:

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

Editar:

Lo mismo se aplica si los objetos en las listas son en sí mismas matrices simples:

@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

Prueba esto:

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

Answer 3

Este es un algoritmo para la fusión de una número arbitrario de listas ordenadas en tiempo más o menos lineal:

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] 

Para cada iteración, encuentra la lista con el primer elemento más pequeño y desplaza este elemento fuera de la lista de resultados. Hace esto hasta que todas las listas estén vacías.

digo más o menos tiempo lineal, ya que en realidad es O (n × m), donde n es el número de listas y m es el número total de elementos en las listas, pero creo que esto de forma segura se puede simplificar a O (m) para la mayoría de los casos, dado que n será pequeño en comparación con m.

Answer 4

Esto utiliza with_index que es una buena manera de añadir un valor de índice a un iterador:

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 

---

Aquí hay algunas variaciones con puntos de referencia:

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 bueno referencia.