Detaillierte Erläuterung der Schritte des PHP-Interpolationssuchalgorithmus für die geordnete Listensuche

Dieses Mal werde ich Ihnen eine detaillierte Erklärung der Schritte des PHP-Suchalgorithmus für die geordnete Tabellensuche geben. Was sind die Vorsichtsmaßnahmen des PHP-Suchalgorithmus für die geordnete Tabellensuche? Hier ist ein praktischer Fall , lass uns einen Blick darauf werfen.

Vorwort:

Wir haben die Binäre Suche bereits früher eingeführt, aber denken wir mal darüber nach, warum müssen wir sie einbinden die Hälfte? Anstatt es in ein Viertel oder mehr zu falten?

Wenn Sie beispielsweise in einem englischen Wörterbuch nach „Apple“ suchen und das Wörterbuch öffnen, blättern Sie dann unbewusst zur Titelseite oder zur Rückseite? Wenn Sie „Zoo“ erneut ankreuzen, wie werden Sie es dann überprüfen? Offensichtlich fängt man nicht in der Mitte des Wörterbuchs an, nach oben zu schauen, sondern man blickt mit einem bestimmten Ziel vorwärts oder rückwärts.

Ebenso, wenn wir zum Beispiel 5 in einem Array mit 100 Elementen im Wertebereich von 0 bis 10000 gleichmäßig verteilt von klein nach groß finden wollen, betrachten wir natürlich zuerst das Array Der Index ist relativ klein.

Die obige Analyse ist eigentlich die Idee der Interpolationssuche, die eine Verbesserung der binären Suche darstellt.

Grundidee:

Suchmethode basierend auf dem Vergleich des zu findenden Schlüsselwortschlüssels mit den Schlüsselwörtern der größten und kleinsten Datensätze in der Suche Tabelle, deren Kern in der Interpolationsberechnungsformel liegt. Schauen wir uns zunächst die Berechnungsformel der Halbsuche an:

Die Interpolationssuche soll die Hälfte davon verbessern und ändern Sie es in das folgende Berechnungsschema:

Der Kern des Interpolationssuchalgorithmus liegt in der Berechnungsformel der Interpolation:

$num - $arr[$lower]
——————————————
$arr[$high] - $arr[$lower]

Code:

<?php
//插值查找(前提是数组必须是有序数组) 事件复杂度　O(logn)
//但对于数组长度比较大，关键字分布又是比较均匀的来说，插值查找的效率比折半查找的效率高
$i = 0; //存储对比的次数
//@param 待查找数组
//@param 待搜索的数字
function insertsearch($arr,$num){
 $count = count($arr);
 $lower = 0;
 $high = $count - 1;
 global $i;
 while($lower <= $high){
  $i ++; //计数器
  if($arr[$lower] == $num){
   return $lower;
  }
  if($arr[$high] == $num){
   return $high;
  }
  // 折半查找 ： $middle = intval(($lower + $high) / 2);
  $middle = intval($lower + ($num - $arr[$lower]) / ($arr[$high] - $arr[$lower]) * ($high - $lower)); 
  if($num < $arr[$middle]){
   $high = $middle - 1;
  }else if($num > $arr[$middle]){
   $lower = $middle + 1;
  }else{
   return $middle;
  }
 }
 return -1;
}
$arr = array(0,1,16,24,35,47,59,62,73,88,99);
$pos = insertsearch($arr,62);
print($pos);
echo "<br>";
echo $i;

Zusammenfassung:

Aus Sicht der Zeitkomplexität ist es auch O(logn) , aber für Nachschlagetabellen mit relativ langen geordneten Listen und relativ gleichmäßiger Verteilung der Schlüsselwörter ist die durchschnittliche Leistung des Interpolationssuchalgorithmus viel besser als die der binären Suche. Im Gegenteil, wenn die Verteilung im Array ähnlich ist wie {0, 1, 2, 2000, 2001,. . . 999998, 999999} Für diese Art extrem ungleichmäßiger Daten ist die Verwendung der Interpolationssuche möglicherweise keine sehr geeignete Wahl.

Ich habe selbst ein Beispiel erstellt:

$arr = array(0,1,2,2000,2001,2002,2003,2004,5555,69666,99999,100000);
echo "位置：".binsearch($arr,5555);
echo "<br>";
echo "比较次数：".$i;
$i = 0; //重置比较次数
echo "<br>";
echo "位置：".insertsearch($arr,5555);
echo "<br>";
echo "比较次数：".$i;

Ergebnisausgabe:

位置：8
比较次数：2
位置：8
比较次数：9

Es ist ersichtlich, dass bei extrem ungleichmäßigen Daten die Interpolationssucheffizienz geringer ist als bei der Halbsuche.

PS: Für die oben erwähnte binsearch()-Funktion können Sie auf den vorherigen Artikel „PHP-geordnete Tabellensuche – binäre Suche (halbiert)“ verweisen

Ich glaube, Sie haben gelesen In diesem Artikel beherrschen Sie die Fallmethode. Weitere spannende Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website.

Empfohlene Lektüre:

PHP-Anwendungsfallanalyse für lange Verbindungen

So implementieren Sie den PHP-Datenexport

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Schritte des PHP-Interpolationssuchalgorithmus für die geordnete Listensuche. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!