Продвинутые алгоритмы обработки данных на PHP

В PHP можно использовать различные алгоритмы и структуры данных для решения сложных задач.

Сортировка слиянием (Merge Sort):

Сортировка слиянием — это эффективный алгоритм сортировки, который использует принцип «разделяй и властвуй». Он разбивает массив на две части, сортирует каждую из них и затем сливает их в один отсортированный массив.

function mergeSort(array $array): array
{
    if (count($array) <= 1) {
        return $array;
    }

    $middle = count($array) / 2;
    $left = array_slice($array, 0, $middle);
    $right = array_slice($array, $middle);

    $left = mergeSort($left);
    $right = mergeSort($right);

    return merge($left, $right);
}

function merge(array $left, array $right): array
{
    $result = [];
    $leftIndex = $rightIndex = 0;

    while ($leftIndex < count($left) && $rightIndex < count($right)) {
        if ($left[$leftIndex] < $right[$rightIndex]) {
            $result[] = $left[$leftIndex++];
        } else {
            $result[] = $right[$rightIndex++];
        }
    }

    return array_merge($result, array_slice($left, $leftIndex), array_slice($right, $rightIndex));
}

$array = [5, 2, 1, 7, 6, 8, 4, 3];
$sortedArray = mergeSort($array);
print_r($sortedArray);

Поиск подстроки алгоритмом Кнута-Морриса-Пратта (KMP):

Алгоритм KMP — это эффективный алгоритм поиска подстроки в строке. Он использует префикс-функцию для ускорения поиска.

function kmpSearch(string $text, string $pattern): ?int
{
    $n = strlen($text);
    $m = strlen($pattern);
    $lps = computeLPSArray($pattern, $m);

    $i = $j = 0;
    while ($i < $n) {
        if ($pattern[$j] === $text[$i]) {
            $i++;
            $j++;
        }

        if ($j === $m) {
            return $i - $j;
        } elseif ($i < $n && $pattern[$j] !== $text[$i]) {
            if ($j !== 0) {
                $j = $lps[$j - 1];
            } else {
                $i++;
            }
        }
    }

    return null;
}

function computeLPSArray(string $pattern, int $m): array
{
    $lps = [0];
    $len = 0;
    $i = 1;

    while ($i < $m) {
        if ($pattern[$i] === $pattern[$len]) {
            $len++;
            $lps[$i] = $len;
                  $i++;
        } else {
            if ($len !== 0) {
                $len = $lps[$len - 1];
            } else {
                $lps[$i] = 0;
                $i++;
            }
        }
    }

    return $lps;
}

$text = "ABABDABACDABABCABAB";
$pattern = "ABABCABAB";
$position = kmpSearch($text, $pattern);

if ($position !== null) {
    echo "Pattern found at position: " . $position . PHP_EOL;
} else {
    echo "Pattern not found." . PHP_EOL;
}
   

Дерево отрезков (Segment Tree):

Дерево отрезков — это структура данных, которая используется для выполнения диапазонных запросов и обновлений на массиве.

Оно позволяет выполнять операции, такие как поиск суммы элементов, минимального и максимального значения в заданном диапазоне, эффективно и быстро.

class SegmentTree
{
    private array $tree;
    private int $n;

    public function __construct(array $array)
    {
        $this->n = count($array);
        $this->tree = array_fill(0, 4 * $this->n, 0);
        $this->build($array, 0, 0, $this->n - 1);
    }

    private function build(array &$array, int $index, int $left, int $right)
    {
        if ($left === $right) {
            $this->tree[$index] = $array[$left];
            return;
        }

        $mid = ($left + $right) >> 1;
        $this->build($array, 2 * $index + 1, $left, $mid);
        $this->build($array, 2 * $index + 2, $mid + 1, $right);
        $this->tree[$index] = $this->tree[2 * $index + 1] + $this->tree[2 * $index + 2];
    }

    public function query(int $queryLeft, int $queryRight): int
    {
        return $this->queryHelper(0, 0, $this->n - 1, $queryLeft, $queryRight);
    }

    private function queryHelper(int $index, int $left, int $right, int $queryLeft, int $queryRight): int
    {
        if ($queryLeft <= $left && $right <= $queryRight) {
            return $this->tree[$index];
        }

        if ($queryRight < $left || $right < $queryLeft) {
            return 0;
        }

        $mid = ($left + $right) >> 1;
        return $this->queryHelper(2 * $index + 1, $left, $mid, $queryLeft, $queryRight) +
            $this->queryHelper(2 * $index + 2, $mid + 1, $right, $queryLeft, $queryRight);
    }
}

$array = [1, 2, 3, 4, 5, 6, 7, 8, 9];
$segmentTree = new SegmentTree($array);
$sum = $segmentTree->query(2, 6); // Query the sum of elements from index 2 to 6
echo "The sum of elements from index 2 to 6 is: " . $sum . PHP_EOL;

Динамическое программирование (Dynamic Programming):

Динамическое программирование (DP) — это метод оптимизации алгоритмов, основанный на разбиении задачи на подзадачи, которые решаются однократно, а их результаты сохраняются в таблице для последующего использования.

Это может значительно уменьшить время выполнения некоторых алгоритмов.

Пример алгоритма DP — нахождение чисел Фибоначчи:

function fibonacci(int $n): int
{
    $fib = array_fill(0, $n + 1, 0);
    $fib[1] = 1;

    for ($i = 2; $i <= $n; $i++) {
        $fib[$i] = $fib[$i - 1] + $fib[$i - 2];
    }

    return $fib[$n];
}

$fibonacciNumber = fibonacci(10);
echo "The 10th Fibonacci number is: " . $fibonacciNumber . PHP_EOL;

Поиск кратчайшего пути алгоритмом Дейкстры:

Алгоритм Дейкстры — это алгоритм поиска кратчайшего пути во взвешенном графе с неотрицательными весами ребер.

function dijkstra(array $graph, int $source): array
{
    $distances = array_fill(0, count($graph), INF);
    $distances[$source] = 0;
    $visited = array_fill(0, count($graph), false);

    while (true) {
        $minDistance = INF;
        $minVertex = -1;

        foreach ($distances as $vertex => $distance) {
            if (!$visited[$vertex] && $distance < $minDistance) {
                $minDistance = $distance;
                $minVertex = $vertex;
            }
        }

        if ($minVertex === -1) {
            break;
        }

        $visited[$minVertex] = true;

        foreach ($graph[$minVertex] as $neighbor => $weight) {
            $distances[$neighbor] = min($distances[$neighbor], $distances[$minVertex] + $weight);
        }
    }

    return $distances;
}

$graph = [
    [0, 10, INF, INF, INF, 5],
    [INF, 0, 1, INF, INF, 2],
    [INF, INF, 0, 4, 2, 8],
    [7, INF, 6, 0, INF, INF],
    [INF, INF, 2, INF, 0, 5],
    [INF, 3, 9, 2, INF, 0],
];

$source = 0;
$distances = dijkstra($graph, $source);
echo "Shortest distances from vertex " . $source . " to all other vertices: " . implode(', ', $distances) . PHP_EOL;

Вышеуказанные примеры демонстрируют разнообразие продвинутых алгоритмов обработки данных, которые могут быть реализованы на PHP.