內置方法來合併ruby中的兩個排序列表

Question

我有兩個Foo對象列表。每個Foo對象都有一個時間戳Foo.timestamp。兩個列表最初都按照時間戳降序排列。

我想合併兩個Foo對象的列表，最終列表也按時間戳按降序排序。

實現這一點並不難，但我想知道是否有任何內置的Ruby方法可以做到這一點，因爲我認爲內置方法會產生最佳性能。

謝謝。

Answer 1

這是可行的，但它不會給出色的性能，因爲它不會花費已經預先被排序的名單優勢：

list = (list1 + list2).sort_by(&:timestamp) 

我不知道任何內置的函數，它的你想要什麼。

Answer 2

我快速查看了Array#sort和Enumerable#sort的實現，並且兩者似乎都使用了quicksort。因此，他們可能不如您手動使用merge sort那樣有效，它會依次選擇將兩個潛在元素中的哪一個輸出到新列表。

然而，a nice article about self-implemented sorting algorithms表明，一個程序員的努力做多標的快速排序更好的悲慘地失敗了 - 他沒有直接接近你有問題，但他的數字是令人望而生畏，以至於我想嘗試的默認排序Enumerable#sort_by第一，只有當感覺太慢時，我纔會回到嘗試自我合併排序。

Answer 3

合併兩個臭勢在必行過程...

a = [1,3,7,11] 
b = [2,4,6,14] 

c = merge_sorted_arrays(a,b) 

def merge_sorted_arrays(a,b) 
    a.reverse! 
    b.reverse! 
    output = [] 

    loop do 
    break if a.empty? || b.empty? 
    output << (a.last < b.last ? a.pop : b.pop) 
    end 
    return output + a.reverse + b.reverse 
end 

也許使用.slice！採取第一個元素會比倒車和彈出更好？

====================

第四評論後編輯：

對......我有另一齣戲，但需要開展真正的工作，否則我會被解僱;-)

對於大量的整數，我的原始方法比使用sort_by更快，但在用100,000個OpenStruct對象填充數組後，在一個屬性上，sort_by快了100倍。

這裏是我的基準測試結果：

def pop_merge_sorted_arrays(array1,array2) 
    array1.reverse! 
    array2.reverse! 
    output = [] 

    loop do 
    break if array1.empty? || array2.empty? 
    output << (array1.last.my_field < array2.last.my_field ? array1.pop : array2.pop) 
    end 
    return output + array1.reverse + array2.reverse 
end 

def shift_merge_sorted_arrays(array1,array2) 
    output = [] 
    loop do 
    break if array1.empty? || array2.empty? 
    output << (array1.first.my_field < array2.first.my_field ? array1.shift : array2.shift) 
    end 
    return output + array1 + array2 
end 

def slice_merge_sorted_arrays(array1,array2) 
    output = [] 
    loop do 
    break if array1.empty? || array2.empty? 
    output << (array1.first.my_field < array2.first.my_field ? array1.slice!(0) : array2.slice!(0)) 
    end 
    return output + array1 + array2 
end 

a=(1..100000).map{|x|OpenStruct.new(:my_field => rand)}.sort_by(:my_field) 
b=(1..100000).map{|x|OpenStruct.new(:my_field => rand)}.sort_by(:my_field) 

# method 1 
t=Time.now;w=pop_merge_sorted_arrays(a.clone,b.clone);puts Time.now-t 
# average of five runs: 185.96seconds 

# method 2 
t=Time.now;x=shift_merge_sorted_arrays(a.clone,b.clone);puts Time.now-t 
# average of five runs: 0.77seconds 

# method 3 
t=Time.now;y=slice_merge_sorted_arrays(a.clone,b.clone);puts Time.now-t 
# average of five runs: 8.46seconds 

# method 4 
t=Time.now;z=(a.clone + b.clone).sort_by(&:my_field);puts Time.now-t 
# average of five runs: 2.13seconds 

所以結果似乎是，你可以寫洗牌他們，而維持秩序，將運行相當迅速的方法（也有可能是一些更高的效率擠走該shift_merge方法，但對於額外的好處，是不是真的值得不只是bunging在一起，並使用sort_by爲了便於呢？:-)

我希望這並不算是題外話了.. 。