Sıralama 10 numara için en hızlı yolu? (sayılar 32 bit)

SORU

23 AĞUSTOS 2015, Pazar

Sıralama 10 numara için en hızlı yolu? (sayılar 32 bit)

Bir sorunu çözüyorum ve çok hızlı bir şekilde 10 sayı (ınt32) sıralama içerir. Başvurum 10 numaraları milyonlarca kez mümkün olduğunca hızlı sıralama gerekiyor. Elementler ve 10 numaraları (basitleştirilmiş) almak ve onları (ve sıralanmış 10 öğe listesinden bir sonuca varmak) sıralamak istiyorum her zaman milyarlarca veri bir dizi örnekleme yapıyorum.

Şu anda eklemeli sıralama kullanıyorum ama çok hızlı bir özel eklemeli sıralama yeneceğine 10 sayı belirli sorunum için sıralama algoritması uygulamak sanırım olabilir.

Kimse bu sorunu yaklaşım hakkında bir fikriniz var mı?

CEVAP

24 AĞUSTOS 2015, PAZARTESİ

(Değerini atamak öneri sıralama ağları içine bakmak için takip.)

29-karşılaştırma/takas ağı 10-giriş bir sıralama yapmak için en hızlı yolu gibi görünüyor. Sadece if deyimleri, karşılaştırma ve takas listesi olarak doğrudan C çevirmek, hangi Javascript bu örnekte, ağ 1969 yılında Waksman tarafından keşfedilen kullandım.

function sortNet10(data) {	// ten-input sorting network by Waksman, 1969
    var swap;
    if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; }
    if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; }
    if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; }
    if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; }
    if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; }
    if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; }
    if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; }
    if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; }
    if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; }
    if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; }
    if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; }
    if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; }
    if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; }
    if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; }
    if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; }
    if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; }
    if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; }
    if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; }
    if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; }
    if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; }
    if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; }
    if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; }
    if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; }
    if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; }
    if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; }
    if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; }
    if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; }
    if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; }
    if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; }
    return(data);
}

alert(sortNet10([5,7,1,8,4,3,6,9,2,0]));

İşte bu ağ, bağımsız aşamadan grafik gösterimi.

Paralel işleme yararlanmak için, 5-4-3-4-4-4-3-2 gruplama 4-4-4-4-4-4-3-2 bir gruplandırma içine değiştirilebilir.