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'
]

有时您想将相同类型的元素分组在一起（想象一个希望将同一类型的所有元素组合在一起存储的UnitOfWork）

$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

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

include 'vendor/autoload.php';

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

$result = $sorter->sort();

实现

tl;dr：对于常规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命令来尝试它。