PHP verwendet Binärheap, um den TopK-Algorithmus zu implementieren

Dieser Artikel stellt Ihnen hauptsächlich die Methode zur Verwendung von PHP zur Implementierung des TopK-Algorithmus mithilfe von Binärheaps vor. Die Einführung im Artikel ist sehr detailliert und bietet einen gewissen Referenz- und Lernwert für alle Freunde, die sie benötigen um gemeinsam zu lernen.

Vorwort

In der Vergangenheit stand ich beim Arbeiten oder Vorstellungsgespräch oft vor dem Problem, wie man einen massiven TopN erreicht, also in einem Sehr großes Ergebnis Um schnell die größten Top-10- oder Top-100-Zahlen in einem Satz zu finden und gleichzeitig Speicher- und Geschwindigkeitseffizienz sicherzustellen, besteht unsere erste Idee möglicherweise darin, die Sortierung zu verwenden und dann die Top-10- oder Top-100-Zahlen abzufangen. Wenn die Sortierung nicht geeignet ist Die Menge ist nicht besonders groß, aber solange die Menge extrem groß ist, ist es unmöglich, diese Aufgabe abzuschließen, wenn ein Array oder eine Textdatei Hunderte Millionen Zahlen enthält Es ist unmöglich, sie alle in den Speicher einzulesen, daher ist die Verwendung der Sortierung zur Lösung dieses Problems nicht die beste Lösung. Deshalb verwenden wir hier PHP, um einen kleinen Top-Heap zu implementieren, um dieses Problem zu lösen Heap

Binärer Heap Ein binärer Heap ist ein vollständiger Binärbaum oder ein annähernd vollständiger Binärbaum. Es gibt zwei Arten von binären Heaps und der minimale Heap: Der Schlüsselwert des übergeordneten Knotens ist immer größer oder gleich jedem untergeordneten Knoten der Schlüsselwert eines beliebigen untergeordneten Knotens

Minimaler Heap-(Bild aus dem Internet)

Binäre Heaps werden im Allgemeinen durch Arrays dargestellt (siehe Bild oben) Beispielsweise ist die Position des Wurzelknotens im Array 0 und die untergeordneten Knoten an der n-ten Position sind jeweils bei 2n+1 und 2n+2, also sind die untergeordneten Knoten an Position 0 bei 1 und 2 Untergeordnete Knoten an Position 1 befinden sich an 3 und 4 usw. Diese Speichermethode erleichtert das Auffinden von übergeordneten und untergeordneten Knoten.

Ich werde hier nicht näher auf die spezifischen konzeptionellen Probleme eingehen. Wenn Sie Fragen zu binären Heaps haben, können Sie diese Datenstruktur gut verstehen. Als nächstes werden wir PHP-Code zur Implementierung und Lösung verwenden Um die oben genannten TopN-Probleme zu erkennen, verwenden wir zunächst die Sortierung, um sie zu implementieren und zu sehen, wie sie funktioniert.

Schnellsortierungsalgorithmus verwenden, um TopN zu implementieren

//为了测试运行内存调大一点
ini_set('memory_limit', '2024M');

//实现一个快速排序函数
function quick_sort(array $array){
 $length = count($array);
 $left_array = array();
 $right_array = array();
 if($length <= 1){
  return $array;
 }
 $key = $array[0];
 for($i=1;$i<$length;$i++){
  if($array[$i] > $key){
   $right_array[] = $array[$i];
  }else{
   $left_array[] = $array[$i];
  }
 }
 $left_array = quick_sort($left_array);
 $right_array = quick_sort($right_array);
 return array_merge($right_array,array($key),$left_array); 
}

//构造500w不重复数
for($i=0;$i<5000000;$i++){
 $numArr[] = $i; 
}
//打乱它们
shuffle($numArr);

//现在我们从里面找到top10最大的数
var_dump(time());
print_r(array_slice(quick_sort($all),0,10));
var_dump(time());

Das Ergebnis nach dem Ausführen

Sie können sehen, dass die Top-10-Ergebnisse oben gedruckt sind und die Laufzeit ausgegeben wird, die etwa 99 Sekunden beträgt, aber das ist nur ein 5 Millionen Zahlen und wenn alles in den Speicher geladen werden kann, wenn wir eine Datei mit 5 kW oder 500 Millionen Zahlen haben, wird es definitiv einige Probleme geben.

Verwenden Sie den binären Heap-Algorithmus, um TopN implementieren

Der Implementierungsprozess ist:

1. Lesen Sie zuerst 10 oder 100 Zahlen in das Array ein ist unsere topN-Nummer.

2. Rufen Sie die Funktion „Kleinen oberen Heap generieren“ auf, um eine kleine obere Heap-Struktur aus diesem Array zu generieren. Zu diesem Zeitpunkt muss der obere Teil des Heaps der kleinste sein.

3. Durchlaufen Sie alle verbleibenden Zahlen aus der Datei oder dem Array nacheinander

4. Vergleichen Sie bei jedem Durchlauf die Größe mit dem Element oben im Heap. Wenn es kleiner ist als das Element oben auf dem Heap, wird es verworfen 🎜> 5. Nachdem Sie das oberste Element des Heaps ersetzt haben, rufen Sie die Funktion „Kleinen oberen Heap generieren“ auf, um mit der Generierung des kleinen oberen Heaps fortzufahren, da Sie den kleinsten finden müssen.

6. Wiederholen Sie den Vorgang Die oben genannten Schritte 4 bis 5 bedeuten, dass sich nach Abschluss aller Durchläufe das größte topN in unserem kleinen oberen Heap befindet, da unser kleiner oberer Heap immer den kleinsten ausschließt und den größten verlässt, und die Geschwindigkeit beim Anpassen des kleinen oberen Heaps beträgt auch sehr schnell. Es handelt sich nur um eine relative Anpassung, solange der Wurzelknoten kleiner ist als der linke und der rechte Knoten. 7. In Bezug auf die Komplexität des Algorithmus, gemäß den Top 10 im schlimmsten Fall SzenarioDas heißt, jedes Mal, wenn eine Zahl durchquert wird und sie durch die Oberseite des Heaps ersetzt wird, muss sie zehnmal angepasst werden, was schneller als die Sortiergeschwindigkeit ist. Darüber hinaus wird nicht der gesamte Inhalt in den Speicher eingelesen . Es ist verständlich, dass es sich bei der Leistung um eine lineare Durchquerung handelt >

Sie können sehen, dass das Endergebnis auch nur in den Top 10 liegt. Es dauerte jedoch nur etwa 1 Sekunde und sowohl der Speicher als auch die Zeiteffizienz erfüllten unsere Anforderungen. Und das Beste an der Sortierung ist, dass wir dies nicht tun Wir müssen alle Datensätze in den Speicher einlesen, da wir sie nicht sortieren müssen. Das Obige dient der Demonstration, sodass 5 Millionen Elemente direkt im Speicher erstellt werden können Lesen Sie sie dann Zeile für Zeile zum Vergleich, da der Kernpunkt unserer Datenstruktur die lineare Durchquerung ist und sich viele Elemente im Speicher befinden. Vergleichen Sie die kleinen Top-Heap-Strukturen und erhalten Sie schließlich TopN.

Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, er wird für das Studium aller hilfreich sein.

Verwandte Empfehlungen:

PHP zur Erlangung hexadezimaler Konvertierung_php-Fähigkeiten

Anleitung Kompilieren Sie Redis und PHPredis unter Linux_php-Tipps

PHPSo verwenden Sie die Mysqli-Klassenbibliothek, um einen perfekten Paging-Effekt zu erzielen_php-Tipps

Das obige ist der detaillierte Inhalt vonPHP verwendet Binärheap, um den TopK-Algorithmus zu implementieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!