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());

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.

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!