Как объединить и упорядочить несколько списков вместе с помощью Ruby?

Question

У меня есть 2 списка, которые имеют даты и данные. Каждый список находится в правильном порядке, указанном порядковым номером. Теперь мне нужно объединить 2 списка и сохранить все в правильном порядке.

Например:

Список А
20101001 A данные 1 секв1
20101001 A данные 2 сек2
20101005 данные 3 сек3

Список B
20101001 B data 1 seq1
20101003 B data 2 seq2

и т.д ...

Мне нужен новый список, чтобы он выглядел так:

20101001 A данные 1 секв1
20101001 A данные 2 сек2
20101001 B data 1 seq3
20101003 B data 2 seq4
20101005 данные 3 сек5

2 вещи, о которых я думал, это объединение списков и применение порядкового номера до вставки их в базу данных, или я могу вставить их в базу данных с текущей последовательностью и снова вытащить их обратно, чтобы объединить вместе, но это выглядит как дополнительный шаг и глупый.

Есть какие-нибудь идеи о том, как это сделать?

Answer 1

Предполагая, что ваши списки находятся в массивах Ruby, а объекты в списках имеют определенные атрибуты (например, obj.sequence_number), один из способов объединения и сортировки списков будет следующим:

Сначала объедините списки какобъединение:

@merged_list = @list_a | @list_b

Затем сортируйте объединенный список с соответствующим правилом сортировки:

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

Редактировать:

После сортировки объединенного массива вы можете повторноопределить номер_последовательности:

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

Редактировать:

То же самое применимо, если ваши объекты в списках сами по себе являются простыми массивами:

@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

Используется with_index, который является хорошим способом добавить значение индекса для итератора:

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

---

Вот некоторые варианты с тестами:

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)

Это хорошо для сравнения.

Answer 3

Это алгоритм объединения произвольного количества отсортированных списков за более или менее линейное время:

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]

Для каждой итерации он находит список с наименьшим первым элементом и удаляет этот элемент изэто на список результатов.Это происходит до тех пор, пока все списки не станут пустыми.

Я говорю более или менее линейное время, так как на самом деле это O (n × m), где n - количество списков, а m - общее числоэлементов в списках, но я думаю, что это можно смело упростить до O (m) для большинства случаев, так как n будет небольшим по сравнению с m.

Answer 4

Попробуйте это:

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