README

此库提供了多种拓扑排序（topSort）的实现。除了普通的排序算法外，它还提供了分组拓扑排序的实现，这意味着您可以传递带有类型的项，这些项将在排序中一起分组。由于它使用字符串而不是数组，其速度比普通实现快20多倍。

这是什么？

拓扑排序对于确定依赖加载很有用。它告诉您哪些元素需要首先进行，以便以正确的顺序满足所有依赖项。

示例用法：工作单元（关系），简单的包管理器，依赖注入，...

示例

$sorter = new StringSort();

$sorter->add('car1', ['owner1', 'brand1']);
$sorter->add('brand1');
$sorter->add('brand2');
$sorter->add('owner1', ['brand1']);
$sorter->add('owner2', ['brand2']);

$result = $sorter->sort();
// output would be:
[
 'brand1',
 'owner1',
 'car1',
 'brand2',
 'owner2'
]

有时您想将相同类型的项分组在一起（想象一个要将同一类型的所有元素组合在一起存储的工作单元）

$sorter = new GroupedStringSort();

$sorter->add('car1', 'car', ['owner1', 'brand1']);
$sorter->add('brand1', 'brand');
$sorter->add('brand2', 'brand');
$sorter->add('owner1', 'user', ['brand1']);
$sorter->add('owner2', 'user', ['brand2']);

$result = $sorter->sort();
// output would be:
[
 'brand2',
 'brand1',
 'owner2',
 'owner1',
 'car1'
]

$groups = $sorter->getGroups();
[
   {type: 'brand', level: 0, position: 0, length: 2},
   {type: 'user', level: 1, position: 2, length: 2},
   {type: 'car', level: 2, position: 4, length: 1},
]
//of course there may be several groups with the same type, if the dependency graphs makes this necessary.

foreach ($groups as $group) {
   $firstItem = $result[$group->position];
   $allItemsOfThisGroup = array_slice($result, $group->position, $group->length);
}

您只能存储字符串作为元素。要排序PHP对象，您可以存储其哈希值。 $sorter->add(spl_object_hash($obj1), [spl_object_hash($objt1Dep)])。

安装

使用composer包：[marcj/topsort)[https://packagist.org.cn/packages/marcj/topsort]

{
    "require": {
        "marcj/topsort": "~0.1"
    }
}

include 'vendor/autoload.php';

$sorter = new GroupedStringSort;
$sorter->add(...);

$result = $sorter->sort();

实现

简而言之：对于普通topSort，请使用FixedArraySort，对于分组topSort，请使用GroupedStringSort，因为它们总是最快的，并且内存占用良好。

ArraySort

这是使用普通PHP数组的最基本、效率最低的topSort实现。

FixedArraySort

这使用php的SplFixedArray，因此内存占用更少。

StringSort

这使用字符串作为存储，因此没有数组开销。因此它略快，并且与FixedArraySort具有几乎相同的内存占用。小缺点：您不能存储包含空字节的元素ID。

GroupedArraySort

这是使用普通PHP数组的最基本、效率不高的分组topSort实现。

GroupedStringSort

这使用字符串作为存储，因此没有数组操作开销。它非常快，并且比GroupedArraySort有更好的内存占用。小缺点：您不能存储包含空字节的元素ID。

PHP 7.0.9的基准测试

测试数据：1/3有两个边，1/3有一个边，1/3没有边。使用./bin/console中的benchmark命令来尝试。