En Sayılar Algoritması toplayın

7 Cevap php

Ben bir sayı grubundan 10 düşük numaraları ile sonuna kadar bir algoritma (veya PHP kodu, sanırım) arıyorum. Ben mevcut sayısı dizideki sayılardan biri daha düşük olup olmadığını görmek için kontrol, on madde dizi yapmayı düşünüyordum, ve eğer öyleyse, dizideki en yüksek sayı bulma ve mevcut numarası ile değiştirilmesi.

Ancak, binlerce düşük 10 numaralarını bulmak planlıyorum, ve bunu yapmak için daha hızlı bir yolu olabilir düşünüyordum. PHP bu uygulama planı, bu nedenle herhangi bir doğal PHP fonksiyonları kullanılabilir.

7 Cevap

Ne arıyorsanız selection algorithm denir. Konuyla ilgili Wikipedia sayfası selecting k küçük veya en büyük elemanları birkaç alt bölümleri section. When the list is large enough, you can beat zaman naif "tüm listeyi sıralamak ve seçmek ilk 10" algoritması için gerekli bulunmaktadır.

Diziyi sıralamak ve son on / ilk girişleri kullanabilirsiniz.

Dürüst: bin girişleri ile bir dizi sıralama daha yanıp sizi daha az zaman maliyeti.

Naif bir yaklaşım, sadece giriş sıralamak için. Yeterince hızlı olasılıkla, bu yüzden sadece denemek ve daha karmaşık bir şey yapmadan önce profili.

Yaklaşım potansiyel olarak daha hızlı: Lineer girişi aramak, ama tutmak çıkış dizisi sonraki giriş dizide ya ait olmadığını daha kolay belirlemek için yapmak sınıflandırılmaktadır. Pseudocode:

output[0-9] = input[0-9];
sort(output);
for i=10..n-1
  if input[i] < output[9]
    insert(input[i])

burada insert (x) doğru noktaya (ikili arama) bulmak ve uygun vites yapacağız.

Ama cidden, sadece ilk naif yaklaşım deneyin.

Nereye Bu sayı grubunu alıyorsanız?

Numaralarının listesi bir dizi zaten eğer sadece bir sort() yapabileceğini, ve sonra array_slice() ilk 10 almak.

Ben, küçük bir dizi için çok önemli değil, ama bu işlem hızını artırmak için hızlı ve kolay bir şekilde büyüdükçe dizi anahtarı indeksleme yararlanmak için hangi 1 değirmen için. satırlar zaman yaklaşık% 40 kullanır. Örnek:

// sorting array values

$numbers = array();
for($i = 0; $i < 1000000; ++$i)
{
    $numbers[$i] = rand(1, 999999);
}

$start = microtime(true);
sort($numbers);
$res = array_slice($numbers, 0, 10, true);
echo microtime(true) - $start . "\n";
// 2.6612658500671
print_r($res);

unset($numbers, $res, $start);


// sorting array keys

$numbers = array();
for($i = 0; $i < 1000000; ++$i)
{
    $numbers[rand(1, 999999)] = $i;
}

$start = microtime(true);
ksort($numbers);
$res = array_keys(array_slice($numbers, 0, 10, true));
echo microtime(true) - $start . "\n";
// 0.9651210308075
print_r($res);

Dizi veri veritabanından Ama eğer hızlı sadece orada sıralamak için muhtemelen:

SELECT number_column FROM table_with_numbers ORDER BY number_column LIMIT 10

Bir sıralı kümesi oluşturma (Java TreeSet, PHP hakkında bilmiyorum), ve ilk 10 numaralar eklemek. Şimdi tüm sayılar üzerinde numaraların geri kalanı üzerinde yineleme yineleme yenisini eklemek, sonra kümesinden büyük numarayı kaldırmak.

N >> 10 Bu algoritma O (n) 'dir.

Ben 10 elemanları ve ağacın kökünde yüksek numaralı bir heap kullanmak istiyorsunuz. Sonra sayıların listesinin başında başlar:

  • Yığın az 10 eleman varsa: listeye numara eklemek
  • Aksi takdirde, sayı öbek yüksek sayı daha küçükse, yığın yüksek numarasını kaldırmak ve daha sonra listeye mevcut numarasını eklemek
  • Aksi halde, bunu görmezden.

Siz öbek 10 düşük numaraları ile sona erecek. Eğer yığın veri yapısı gibi bir dizi kullanıyorsanız, o zaman sadece dizi doğrudan kullanabilirsiniz.

(Alternatif: Eğer biraz daha hızlı olacak, ilk 10 unsurları dilim, yerine yukarıdaki ilk adımı kullanarak onları heapify edebilirsiniz).

Ancak, diğer insanlar 1000 öğeleri için, belirtildiği gibi, sadece listeyi sıralamak ve ilk 10 elemanları alır.

etiketler