được xây dựng trong phương pháp để hợp nhất hai danh sách được sắp xếp trong ruby ​​

Question

Tôi có hai danh sách đối tượng Foo. Mỗi đối tượng Foo có dấu thời gian, Foo.timestamp. Cả hai danh sách ban đầu được sắp xếp theo dấu thời gian theo thứ tự giảm dần.

Tôi muốn hợp nhất cả hai danh sách đối tượng Foo theo cách mà danh sách cuối cùng cũng được sắp xếp theo dấu thời gian theo thứ tự giảm dần.

Thực hiện điều này không khó, nhưng tôi đã tự hỏi liệu có phương pháp Ruby tích hợp nào có thể thực hiện điều này hay không, vì tôi cho rằng các phương thức dựng sẵn sẽ mang lại hiệu suất tốt nhất.

Cảm ơn.

Answer 1

này sẽ làm việc, nhưng nó sẽ không cung cấp hiệu suất tuyệt vời bởi vì nó sẽ không tận dụng lợi thế của các danh sách đã được sắp xếp trước:

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

Tôi không biết về bất kỳ chức năng built-in mà không bạn muốn gì.

Answer 2

Tôi đã xem nhanh các triển khai Array#sort và Enumerable#sort và cả hai xuất hiện để sử dụng quicksort. Do đó, chúng có thể không hoạt động hiệu quả khi bạn sử dụng một cách thủ công merge sort để chọn yếu tố nào trong hai yếu tố tiềm năng sẽ xuất sang danh sách mới.

Tuy nhiên, a nice article about self-implemented sorting algorithms cho thấy rằng những nỗ lực một lập trình viên để làm tốt hơn so với quicksort tiềm ẩn thất bại thảm hại - ông không trực tiếp tiếp cận vấn đề mà bạn có, nhưng số lượng của ông đang làm nản lòng đủ mà tôi muốn thử mặc định Enumerable#sort_by sắp xếp đầu tiên, và chỉ khi nó cảm thấy quá chậm, tôi sẽ quay trở lại để thử một loại hợp nhất tự viết.

Answer 3

quá trình Hôi cấp bách của việc sáp nhập hai ...

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 

Có thể sử dụng .slice! để lấy yếu tố đầu tiên sẽ tốt hơn đảo ngược và popping?

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

sửa sau khi bình luận thứ tư:

Phải rồi ... Tôi đã chơi khác , nhưng cần phải tiếp tục với công việc thực sự hoặc tôi sẽ bị sa thải ;-)

Trên một mảng lớn các số nguyên, phương pháp gốc của tôi hoạt động nhanh hơn sử dụng sort_by, nhưng sau khi điền các mảng với 100.000 đối tượng OpenStruct và sắp xếp trên một thuộc tính, sort_by nhanh gấp 100 lần.

Dưới đây là kết quả điểm chuẩn của tôi:

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 

Vì vậy, các Kết quả cuối cùng có vẻ là bạn có thể viết một phương pháp mà sẽ xáo trộn chúng trong khi giữ gìn trật tự mà sẽ chạy khá nhanh chóng (và có lẽ một số hiệu quả hơn để bóp ra của phương pháp shift_merge, nhưng đối với lợi ích bổ sung, là nó thực sự có giá trị không chỉ bunging chúng lại với nhau và sử dụng sort_by cho sự dễ dàng của nó? :-)

Tôi hy vọng điều này không được tính như là một digression .. .