ruby ​​içinde iki sıralı listeleri birleştirmek için bir yöntem yerleşik

Question

İki foo nesnesi listesi var. Her Foo nesnesinin bir zaman damgası vardır, Foo.timestamp. Her iki liste başlangıçta zaman damgası tarafından azalan düzende sıralanır.

Son listenin ayrıca zaman damgası tarafından azalan sıraya göre sıralandığı bir şekilde Foo nesnelerinin listelerini birleştirmek istiyorum.

Bunu uygulamak zor değil, ancak yerleşik yöntemlerin en iyi performansı vereceğini varsayarsak, bunu yapabilecek herhangi bir yerleşik Ruby yöntemi olup olmadığını merak ediyordum.

Teşekkürler.

Answer 1

Bu çalışacaktır ama zaten önceden sıralanmakta olan listelerden yararlanmak çünkü büyük bir performans vermeyecektir: Ben does herhangi yerleşik fonksiyonun bilmiyorum

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

Ne istiyorsunuz.

Answer 2

Array#sort ve Enumerable#sort uygulamalarına hızlı bir bakış attı ve her ikisi de quicksort'u kullanıyor görünüyor. Böylece, , iki potansiyel öğeden hangisinin sırayla yeni listeye çıkarılacağını seçen bir merge sort kullanarak elinizdeki kadar verimli olmayabilir.

Ancak a nice article about self-implemented sorting algorithms yatan quicksort daha iyi yapmak için bir programcının çabaları sefil başarısız olduğunu gösteriyor - o doğrudan sahip olduğunuz soruna yaklaşım yoktu, ama onun sayılar ı Enumerable#sort_by ilk sıralama varsayılan çalışacaktı yeterince göz korkutucu hale getirir, ve sadece çok yavaş hissedilirse, kendinden yazılı bir birleştirme türünü denemeye döneceğim. ikisini birleştirme

Answer 3

Kötü kokulu şart süreci ...

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 

Belki .slice kullanarak! İlk unsuru ele almak, tersine dönmekten ve haşhaş etmekten daha iyi olurdu? Dördüncü yorumun sonra düzenlenmiş

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

:

Sağ ... Başka oyun yaşadım ama gerçek iş ile devam etmeliyim ya da kovulmalıyım ;-)

Çok sayıda tamsayıda, orijinal yöntemim sort_by'yi kullanmaktan daha hızlı çalışır, ancak dizileri 100.000 OpenStruct nesnesiyle doldurduktan sonra ve sıralama bir öznitelikte, sort_by 100 kat daha hızlıydı. Yani Netice görünüyor

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 

oldukça hızlı bir şekilde çalışacak düzeni korurken onları karıştırmak sağlayacak bir yöntem yazabilirsiniz olmak (ve dışarı sıkmak için muhtemelen biraz daha verimlilik var: Burada

benim kıyaslama sonuçları var shift_merge yönteminin, ama ekstra yararı için, o gerçekten değer değil sadece onları biraraya tıpalanması sorunu ve bunun kolaylığı için sort_by kullanarak? :-)

Bu saptıran olarak sayılmaz umut ..