如何使用Ruby合并和排序多个列表？

Question

我有两个列表，其中包含日期和数据。每个列表都按照序列号的顺序排列正确。现在我需要合并这两个列表，并保持所有内容的正确顺序。

例如：

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 等等...

我需要新列表看起来像这样： 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

我想到的两件事是将列表合并并在插入到数据库之前应用序列号，或者可以使用当前序列将其插入到数据库中，然后再将它们拉回来合并在一起，但这似乎是多余的步骤和笨拙的方式。

您有关于最佳方法的任何想法吗？

- cswebgrl

Answer 1

假设您的列表在Ruby数组中，并且列表中的对象已定义属性（例如obj.sequence_number），合并和排序列表的一种方法是：

首先将列表作为联合体合并：

@merged_list = @list_a | @list_b

然后按照适当的排序规则对merged_list进行排序：

@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}"}

- Dave Sims

Answer 2

这是一个合并任意数量已排序列表的算法，时间复杂度大致为线性：

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)，因为相对于m，n将很小。

- Theo

Answer 3

试试这个：

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

- Harish Shetty

Answer 4

这里使用了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)

进行基准测试是很好的。

- the Tin Man