Le tas PHP implémente l'exemple d'algorithme TopK

Le tas binaire est un type spécial de tas. Un tas binaire est un arbre binaire complet ou un arbre binaire approximativement complet. Il existe deux types de tas binaires, le tas maximum et le tas minimum : la valeur clé du parent. Le nœud est toujours supérieur ou égal à la valeur clé de tout nœud enfant ; tas minimum : la valeur clé du nœud parent est toujours inférieure ou égale à la valeur clé de tout nœud enfant.

Petit tas supérieur-(photo d'Internet)

---

Le tas binaire est généralement représenté par un tableau (voir l'image ci-dessus ), Par exemple, la position du nœud racine dans le tableau est 0 et les nœuds enfants à la nième position sont respectivement à 2n+1 et 2n+2. Par conséquent, les nœuds enfants à la 0ème position sont à 1 et 2. , et les nœuds enfants de 1 sont en 3 et 2n+2 4. Par analogie, cette méthode de stockage facilite la recherche des nœuds parents et des nœuds enfants.

Je n'entrerai pas ici dans les détails des problèmes conceptuels spécifiques. Si vous avez des questions sur les tas binaires, vous pouvez avoir une bonne compréhension de cette structure de données. Ensuite, nous utiliserons le code PHP pour. implémentez et résolvez les principaux problèmes ci-dessus, afin de voir la différence, utilisons d'abord la méthode de tri pour voir l'effet.

Utilisez l'algorithme de tri rapide pour implémenter TopN

//为了测试运行内存调大一点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());

Le résultat après l'exécution de

---

c'est OK, j'ai vu que les 10 meilleurs résultats ont été imprimés ci-dessus et que le temps d'exécution a été affiché, ce qui est d'environ 99 secondes. Cependant, ce n'est le cas que lorsque 5 millions de nombres peuvent être chargés dans la mémoire si nous avons un fichier de 5 kW. ou 500 millions de nombres, il y aura certainement des problèmes

Utilisez l'algorithme de tas binaire pour implémenter TopN
Le processus d'implémentation est :
1 Commencez par lire 10 ou 100. nombres dans le tableau À l'intérieur, c'est notre numéro topN.
2.Appelez la fonction générer un petit tas supérieur pour générer une petite structure de tas supérieur à partir de ce tableau. À ce stade, le haut du tas doit être le plus petit. 🎜>3. À partir du fichier ou du tableau en séquence Parcourez tous les nombres restants
4. Chaque fois qu'un nombre est parcouru, comparez la taille avec l'élément en haut du tas. le haut du tas, jetez-le. S'il est supérieur à l'élément en haut du tas, remplacez-le
5. Comparez-le avec l'élément en haut du tas, appelez. la fonction générer un petit tas supérieur pour continuer à générer le petit tas supérieur, car vous devez trouver le plus petit
6. Répétez les 4 à 5 étapes ci-dessus, de sorte que lorsque toutes les traversées sont terminées, notre petit tas supérieur quoi. est à l'intérieur du tas le plus grand topN, car notre petit tas supérieur exclut toujours le plus petit et laisse le plus grand, et l'ajustement du petit tas supérieur est également très rapide. C'est juste un ajustement relatif, tant que le nœud racine est. plus petit que les nœuds gauche et droit.
7 En termes de complexité de l'algorithme, le pire des cas est que chaque fois qu'un nombre est parcouru, s'il est remplacé par le haut du tas, il doit être ajusté de 10. fois, ce qui est plus rapide que la vitesse de tri, et ce n'est pas tout le contenu est lu dans la mémoire. On peut comprendre que la réalisation est un parcours linéaire

//生成小顶堆函数function Heap(&$arr,$idx){
    $left  = ($idx << 1) + 1;    $right = ($idx << 1) + 2;    if (!$arr[$left]){        return;
    }    if($arr[$right] && $arr[$right] < $arr[$left]){        $l = $right;
    }else{        $l = $left;
    }    if ($arr[$idx] > $arr[$l]){         $tmp = $arr[$idx]; 
         $arr[$idx] = $arr[$l];         $arr[$l] = $tmp;
         Heap($arr,$l);
    }
}//这里为了保证跟上面一致，也构造500w不重复数/*
  当然这个数据集并不一定全放在内存，也可以在
  文件里面，因为我们并不是全部加载到内存去进
  行排序
*/for($i=0;$i<5000000;$i++){    $numArr[] = $i;    
}//打乱它们shuffle($numArr);//先取出10个到数组$topArr = array_slice($numArr,0,10);//获取最后一个有子节点的索引位置//因为在构造小顶堆的时候是从最后一个有左或右节点的位置//开始从下往上不断的进行移动构造（具体可看上面的图去理解）$idx = floor(count($topArr) / 2) - 1;//生成小顶堆for($i=$idx;$i>=0;$i--){
    Heap($topArr,$i);
}

var_dump(time());//这里可以看到，就是开始遍历剩下的所有元素for($i = count($topArr); $i < count($numArr); $i++){    //每遍历一个则跟堆顶元素进行比较大小
    if ($numArr[$i] > $topArr[0]){        //如果大于堆顶元素则替换
        $topArr[0] = $numArr[$i];        /*
          重新调用生成小顶堆函数进行维护，只不过这次是从堆顶
          的索引位置开始自上往下进行维护，因为我们只是把堆顶
          的元素给替换掉了而其余的还是按照根节点小于左右节点
          的顺序摆放这也就是我们上面说的，只是相对调整下，并
          不是全部调整一遍
        */
        Heap($topArr,0);
    }
}
var_dump(time());

<.>Après avoir exécuté le résultat

vous pouvez voir que le résultat final est également top10, mais cela ne prend que 1 seconde environ, et la mémoire et l'efficacité du temps répondent à nos exigences, et la meilleure chose à propos du tri est que nous n'avons pas besoin de lire tous les ensembles de données dans la mémoire, car nous n'avons pas besoin de trier, et ce qui précède est à titre de démonstration, donc 5 millions d'éléments sont construits directement dans la mémoire, mais nous pouvons tous les transférer. de ceci dans le fichier, puis lisez et comparez ligne par ligne, car le point central de notre structure de données est le parcours linéaire et la mémoire. Comparez les très petites structures de tas supérieur à l'intérieur et obtenez enfin TopN.

---

Fin

La dernière chose que je veux dire est Algorithme + structure des données
C'est vraiment très important, un bon algorithme peut grandement améliorer notre efficacité.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!