Swoole Advanced: Cara menggunakan multi-threading untuk melaksanakan algoritma pengisihan berkelajuan tinggi

Swoole ialah rangka kerja komunikasi rangkaian berprestasi tinggi berdasarkan bahasa PHP Ia menyokong pelaksanaan berbilang mod IO tak segerak dan berbilang protokol rangkaian lanjutan. Berdasarkan Swoole, kita boleh menggunakan fungsi berbilang benang untuk melaksanakan operasi algoritma yang cekap, seperti algoritma pengisihan berkelajuan tinggi.

Isih Pantas ialah algoritma pengisihan biasa Dengan mencari elemen penanda aras, elemen dibahagikan kepada dua jujukan Elemen yang lebih kecil daripada elemen penanda aras diletakkan di sebelah kiri, dan elemen yang lebih besar daripada atau sama dengan elemen penanda aras. diletakkan di sebelah kiri Di sebelah kanan, urutan kiri dan kanan diisih secara rekursif untuk mendapatkan urutan tertib. Dalam kes benang tunggal, kerumitan masa algoritma pengisihan berkelajuan tinggi ialah O(nlogn), tetapi dalam kes berbilang benang, kita boleh memperuntukkan tugas pengisihan kepada berbilang benang pada masa yang sama, dengan itu meningkatkan kecekapan pelaksanaan algoritma.

Artikel ini akan memperkenalkan cara menggunakan berbilang benang Swoole untuk melaksanakan algoritma pengisihan berkelajuan tinggi dan menganalisis perbezaan prestasi antara berbilang benang dan benang tunggal.

1. Pelaksanaan algoritma pengisihan berkelajuan tinggi dalam utas tunggal

Pertama, mari kita lihat cara melaksanakan algoritma pengisihan berkelajuan tinggi dalam utas tunggal. Berikut ialah pelaksanaan kod PHP mudah:

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

Dalam kod ini, kami menggunakan pengulangan fungsi untuk melaksanakan algoritma pengisihan berkelajuan tinggi. Mula-mula, hitung panjang tatasusunan, dan jika panjangnya kurang daripada atau sama dengan 1, kembalikan tatasusunan secara terus. Kemudian, pilih elemen pertama tatasusunan sebagai elemen asas, dan letakkan elemen dalam tatasusunan yang lebih kecil daripada elemen dalam urutan kiri, dan elemen yang lebih besar daripada atau sama dengan elemen dalam tatasusunan diletakkan dalam urutan kanan Akhirnya, urutan kiri dan kanan diisih secara rekursif, dan urutan kiri dan kanan akhirnya digabungkan.

2. Multi-threading untuk melaksanakan algoritma pengisihan berkelajuan tinggi

Di bawah rangka kerja Swoole, kita boleh menggunakan kelas swoole_process untuk mencipta berbilang sub-proses, dan kemudian menetapkan tugas pengisihan kepada berbilang sub-proses untuk beroperasi pada masa yang sama, dengan itu meningkatkan kecekapan Perlaksanaan algoritma. Berikut ialah pelaksanaan kod berbilang benang PHP yang mudah:

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

Dalam kod ini, kita mula-mula menentukan bilangan proses Jika bilangan proses lebih daripada 1, gunakan kelas swoole_process untuk mencipta dua sub-. proses untuk mengisih urutan kiri dan kanan masing-masing secara rekursif, dan akhirnya menggabungkan tiga tatasusunan kiri, asas dan kanan. Jika bilangan proses adalah sama dengan 1, pengisihan satu proses dilaksanakan menggunakan rekursi. Pada masa yang sama, untuk mengelak membebankan sistem akibat terlalu banyak proses, kita boleh mengimbangi bilangan utas dan prestasi dengan menetapkan bilangan proses yang munasabah.

3. Ujian dan analisis prestasi

Untuk mengesahkan sama ada algoritma yang dilaksanakan oleh pelbagai benang mempunyai kelebihan dalam prestasi, kami menjalankan satu set ujian prestasi. Persekitaran ujian ialah sistem Windows 10 dengan CPU i7-9750H @ 2.60GHz, dan kaedah single-threaded dan multi-threaded digunakan untuk mengisih tatasusunan rawak panjang 100000, dan masa berjalan kedua-dua algoritma dibandingkan.

Keputusan ujian adalah seperti berikut:

Urut tunggal: 58.68300s
Berbilang benang: 22.03276s

Ia boleh dilihat apabila bilangan proses adalah ditetapkan kepada 2, algoritma berbilang benang Masa berjalan jauh lebih baik daripada algoritma berbenang tunggal, dan masa berjalan dipendekkan kira-kira 2/3, yang membuktikan bahawa algoritma berbilang benang boleh meningkatkan kecekapan pelaksanaan dengan ketara. algoritma. Apabila bilangan proses ditetapkan kepada 4, kecekapan pelaksanaan algoritma berbilang benang ini kerana terlalu banyak proses membawa kepada sistem terbeban, yang seterusnya menjejaskan kecekapan pelaksanaan algoritma.

4. Ringkasan

Artikel ini memperkenalkan cara melaksanakan algoritma pengisihan berkelajuan tinggi di bawah rangka kerja berbilang benang Swoole Dengan memperuntukkan tugas algoritma kepada berbilang urutan untuk pelaksanaan serentak, kecekapan pelaksanaan algoritma boleh dipertingkatkan dengan ketara. Pada masa yang sama, kami juga menganalisis perbezaan prestasi antara pelaksanaan multi-thread dan single-threaded, dan mengingatkan pembaca untuk memberi perhatian kepada bilangan proses apabila menggunakan multi-threading untuk mengelak membebankan sistem akibat terlalu banyak proses.

Atas ialah kandungan terperinci Swoole Advanced: Cara menggunakan multi-threading untuk melaksanakan algoritma pengisihan berkelajuan tinggi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!