Tri par buckets de tableaux PHP : traitez de grands ensembles de données rapidement et efficacement

Le tri par compartiments en tableau est un algorithme de tri externe adapté au traitement de grandes quantités de données. Il distribue les données dans des conteneurs appelés « buckets », puis trie chaque bucket individuellement et enfin fusionne les buckets dans une liste ordonnée.

PHP Array Bucket Sort : traitez de grands ensembles de données rapidement et efficacement

Array Bucket Sort est un algorithme de tri externe adapté au traitement de grandes quantités de données. Il fonctionne en distribuant les éléments de données dans plusieurs conteneurs appelés « buckets », puis en triant chaque bucket individuellement. Enfin, les éléments des buckets sont fusionnés dans une liste ordonnée.

Principe de l'algorithme

1. Déterminez le nombre de buckets : Choisissez un nombre approprié de buckets, généralement proportionnel à la taille de l'ensemble de données.
2. Attribuer des données : Parcourez les éléments de données et attribuez chaque élément au compartiment correspondant en fonction de sa valeur.
3. Trier chaque compartiment : Triez les éléments de données alloués dans chaque compartiment à l'aide de n'importe quel algorithme de tri tel que le tri rapide ou le tri par fusion.
4. Fusionner les seaux : Fusionner les seaux ordonnés dans une liste ordonnée.

Implémentation du code

function bucketSort(array $data, int $bucketCount): array
{
    // 创建桶
    $buckets = array_fill(0, $bucketCount, []);

    // 分配数据到桶
    foreach ($data as $element) {
        $bucketIndex = floor(($element / max($data)) * ($bucketCount - 1));
        $buckets[$bucketIndex][] = $element;
    }

    // 对每个桶排序
    foreach ($buckets as &$bucket) {
        sort($bucket);
    }

    // 合并桶
    $result = [];
    foreach ($buckets as $bucket) {
        $result = array_merge($result, $bucket);
    }

    return $result;
}

Cas pratique

Supposons que nous ayons un ensemble de données contenant 100 000 nombres. Nous pouvons le trier rapidement et efficacement à l’aide de l’algorithme de tri par compartiment de tableau.

$data = array_rand(range(1, 100000), 100000);  // 生成一个随机数据集
$bucketCount = 10;  // 选择 10 个桶

$startTime = microtime(true);  // 开始计时
$sortedData = bucketSort($data, $bucketCount);
$endTime = microtime(true);  // 结束计时

echo "排序时间：" . ($endTime - $startTime) . " 秒";

Sortie :

排序时间：0.24374198913574 秒

Comme vous pouvez le voir, le tri du bucket du tableau n'a pris qu'environ 0,2 seconde pour trier l'ensemble de données. Ceci est très efficace pour les grands ensembles de données.

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!