Swoole Advanced : Comment utiliser le multithreading pour implémenter un algorithme de tri à grande vitesse

Swoole est un framework de communication réseau hautes performances basé sur le langage PHP. Il prend en charge la mise en œuvre de plusieurs modes IO asynchrones et de plusieurs protocoles réseau avancés. Sur la base de Swoole, nous pouvons utiliser sa fonction multi-threading pour implémenter des opérations algorithmiques efficaces, telles que des algorithmes de tri à grande vitesse.

Le tri rapide est un algorithme de tri courant. En localisant un élément de référence, les éléments sont divisés en deux sous-séquences. Celles plus petites que l'élément de référence sont placées à gauche, et celles supérieures ou égales à celui-ci. Les éléments de référence sont placés à gauche, puis les sous-séquences gauche et droite sont triées de manière récursive, et enfin une séquence ordonnée est obtenue. Dans le cas d'un seul thread, la complexité temporelle de l'algorithme de tri à grande vitesse est O(nlogn), mais dans le cas du multi-thread, nous pouvons allouer la tâche de tri à plusieurs threads en même temps, améliorant ainsi la efficacité d'exécution de l'algorithme.

Cet article expliquera comment utiliser le multi-threading Swoole pour implémenter un algorithme de tri à grande vitesse et analysera la différence de performances entre le multi-threading et le mono-threading.

1. Implémentation monothread d'un algorithme de tri à grande vitesse

Tout d'abord, voyons comment implémenter un algorithme de tri à grande vitesse sous un seul thread. Ce qui suit est une implémentation simple de code PHP :

function quickSort($arr) {
    $len = count($arr);
    if($len <= 1) {
        return $arr;
    }
    $left = $right = array();
    $pivot = $arr[0];
    for($i=1; $i<$len; $i++) {
        if($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    return array_merge(quickSort($left), array($pivot), quickSort($right));
}

$arr = array(3, 4, 2, 7, 5, 8, 1, 9, 6);
print_r(quickSort($arr));

Dans ce code, nous utilisons la récursion de fonction pour implémenter un algorithme de tri à grande vitesse. Tout d’abord, calculez la longueur du tableau, et si la longueur est inférieure ou égale à 1, renvoyez directement le tableau. Ensuite, sélectionnez le premier élément du tableau comme élément de base et placez les éléments du tableau qui sont plus petits que l'élément de la sous-séquence de gauche, et les éléments supérieurs ou égaux à l'élément du tableau sont placés dans la sous-séquence droite. Enfin, les sous-séquences gauche et droite sont triées de manière récursive, et les sous-séquences gauche et droite sont finalement fusionnées. Les trois tableaux de base et de droite sont les tableaux ordonnés.

2. Multi-threading pour implémenter un algorithme de tri à grande vitesse

Dans le framework Swoole, nous pouvons utiliser la classe swoole_process pour créer plusieurs sous-processus, puis attribuer le tâche de tri vers plusieurs sous-processus pour un fonctionnement simultané, améliorant ainsi l'efficacité d'exécution de l'algorithme. Ce qui suit est une implémentation simple de code PHP multithread :

function quickSort($arr, $worker_num) {
    $len = count($arr);
    if($len <= 1) {
        return $arr;
    }
    $left = $right = array();
    $pivot = $arr[0];
    for($i=1; $i<$len; $i++) {
        if($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    $pid = array();
    if($worker_num > 1) { //多进程排序
        $p_left = new swoole_process(function($process) use($left, $worker_num) {
            $process->write(quickSort($left, $worker_num)); //递归排序左侧子序列
        }, true);
        $p_left->start();
        $pid[] = $p_left->pid;

        $p_right = new swoole_process(function($process) use($right, $worker_num) {
            $process->write(quickSort($right, $worker_num)); //递归排序右侧子序列
        }, true);
        $p_right->start();
        $pid[] = $p_right->pid;

        swoole_process::wait(); //等待子进程结束
        swoole_process::wait();
        $left = $p_left->read(); //获取左侧子序列排序结果
        $right = $p_right->read(); //获取右侧子序列排序结果
    } else { //单进程排序
        $left = quickSort($left, 1);
        $right = quickSort($right, 1);
    }
    return array_merge($left, array($pivot), $right);
}

$arr = array(3, 4, 2, 7, 5, 8, 1, 9, 6);
$worker_num = 2; //设置进程数
print_r(quickSort($arr, $worker_num));

Dans ce code, nous déterminons d'abord le nombre de processus. Si le nombre de processus est supérieur à 1, utilisez la classe swoole_process pour en créer deux. sous-processus pour les sous-séquences gauche et droite respectivement. Tri récursif, et enfin fusionner les tableaux de gauche, de base et de droite. Si le nombre de processus est égal à 1, le tri mono-processus est mis en œuvre par récursion. Dans le même temps, afin d'éviter de surcharger le système en raison d'un trop grand nombre de processus, nous pouvons équilibrer le nombre de threads et les performances en définissant un nombre raisonnable de processus.

3. Tests et analyses de performances

Afin de vérifier si l'algorithme implémenté par multi-threading présente des avantages en termes de performances, nous avons effectué un ensemble de tests de performances. L'environnement de test est un système Windows 10 avec un processeur i7-9750H à 2,60 GHz, et des méthodes monothread et multithread sont utilisées pour trier un tableau aléatoire de longueur 100 000, et le temps d'exécution des deux algorithmes est comparé.

Les résultats du test sont les suivants :

Un seul fil : 58,68300s
Plusieurs fils : 22,03276s

On voit que lorsque le nombre de processus est défini Lorsqu'il est égal à 2, le temps d'exécution de l'algorithme multithread est nettement meilleur que celui de l'algorithme monothread, et le temps d'exécution est raccourci d'environ 2/3, ce qui prouve que le multi -l'algorithme threadé peut améliorer considérablement l'efficacité d'exécution de l'algorithme. Lorsque le nombre de processus est défini sur 4, l’efficacité d’exécution de l’algorithme multithread diminue car un trop grand nombre de processus entraîne une surcharge du système, ce qui affecte à son tour l’efficacité d’exécution de l’algorithme.

4. Résumé

Cet article présente comment implémenter un algorithme de tri à grande vitesse dans le framework multi-thread Swoole en attribuant des tâches d'algorithme à plusieurs threads pour une exécution simultanée, l'efficacité de l'algorithme peut être considérablement améliorée. Dans le même temps, nous avons également analysé les différences de performances entre les implémentations multithread et monothread, et avons rappelé aux lecteurs de faire attention au nombre de processus lors de l'utilisation du multithread pour éviter de surcharger le système en raison d'un trop grand nombre de processus.

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!