c# - 基于先前排序的排序

Question

我正在尝试根据“排序映射”对 ID 列表进行排序，该映射是 (ID1, ID2, timestamp) 的数组元组确定哪些 ID 应该在其他 ID 之前排序。以下是规则:

ID1应该排在 ID2 之前.

时间戳可用于打破与较旧时间戳的较新时间戳的联系。例如给定排序键 (C, A, 1/1/1900), (C, B, 1/1/2000)然后 B排在 A 之前.

可以有循环，例如(A, B, 1/1/1950), (B, C, 1/1/1980), (C, A, 1/1/1900) .时间戳可用于中断循环，循环中较旧的时间戳记录将从排序映射中删除，直到循环消失

如果排序映射中不存在 ID，则将其排序在排序映射中存在的任何 ID 之后

示例:给定排序图 (C, A, 1/1/1900), (C, B, 1/1/2000) ，以及列表 (A, B, C, D)要排序，排序后的输出将是 (C, B, A, D) .

将这些规则转化为算法让我很难过。这是我到目前为止所拥有的:

从数据库中获取最新的排序图。对于每对唯一的 ID，我最多可以获得一条记录。

从排序图中删除循环。 如何？或者在步骤 4 中简单地忽略循环是否更容易？

转换内存中的排序映射以获得最佳性能。例如，构建一个哈希表，其键是排序映射中的每个唯一 ID，以便我可以快速找到包含特定 ID 的所有排序映射行。

使用接受任意两个 ID 的自定义比较函数，使用通用二进制排序库对我的 ID 数组进行排序 ID1和 ID2参数。比较功能:

一种。查找所有包含 ID1 的排序映射条目或 ID2使用第 3 步中的哈希表。

湾如果我已经有一个包含 ID1 的记录和 ID2在排序图中，停下来——我们知道哪个应该排在第一位!

C。如果在排序图中既没有找到 ID1，也没有找到 ID2，那么它就是平局。返回确定性的任意结果(例如，较低的 ID 获胜)。

d.如果一个 ID 在排序映射中，而另一个不在，则停止。找到的应该先排序。

e.如果我们到这里，两个 ID 都在排序图中，但排序图中没有可用的直接比较。 怎么办？

性能不是一个大问题，因为排序映射的最大大小低于 20K 行，并且被排序的最大 ID 数低于 30。

有想法吗？

FWIW，我们将使用 .NET 的 List<T>.Sort(Comparison<T>) 在 C# 中进行排序，但底层算法显然与语言和平台无关。

如果你很好奇，这里是这个算法的实际需求:

我们公司为送货司机构建移动应用程序，他们每天访问他们负责的 100-150 个地点中的大约 20 个地点。每天的位置列表是根据每个位置的库存动态分配的。库存低的位置会收到新库存的交付，而仍然有足够库存的位置不会被访问。

司机可以按任何顺序自由访问地点，但他们通常每天都会采取类似的路线(例如，早上交通量较少时访问城镇南部的地点，然后交通较重时访问城镇北部的地点南)。

我们选择不使用自动确定最有效驾驶路线的 3rd-party 路由软件。相反，我们发现让司机选择路线更好，因为路由软件很难受限制，例如“该建筑物的装卸码头通常只在早上 7 点前免费”或“需要签署送货收据的人提前​​离开星期五”对交货时间表有很大影响。

无论如何，我们希望使用司机的历史选择来按照司机上次访问相同地点的相同顺序对每天的行程进行排序。这将为司机每天提供一个符合他喜好的精心安排的行程，除特殊情况外，他无需手动重新安排时间表。这将为司机每天节省一两分钟，随着时间的推移而增加。

每个历史行程实际上是一个这样的列表(ID1、ID2、ID3、...、IDN、时间戳)，但作为存储数百个过去时间表的替代方案，我认为分解每个 N 机历史行程会更容易成对的机器。这意味着我最多必须存储 N*N-1 个元组，因为新的排序总是将旧的排序从排序映射中剔除。如果这是一个不好的简化，请告诉我。 ;-)

Answer 1

您正在寻找的是一个 Topological sorting .使用该搜索词，您可能会找到非常好的资源。

在您的特定领域中存在一种复杂情况:周期(因为随着时间的推移，驱动程序的行为不一致)。您需要打破依赖循环这一事实是正确的，否则拓扑排序将失败。

您还需要打破所有长度大于 2 的循环。

让我们将 ID-map 视为图形:ID(地点)是节点。 map 中的条目是边(从地点 ID1 到地点 ID2)。一个简单的方法是这样的:

while true
 allCycles = getListOfAllCycles();
 if (allCycles.length == 0) break;
 breakNode = chooseBreakNode(allCycles); //defined later
 deleteBreakNodeFrom(allCycles);

chooseBreakNode:
 chose the node which has been driven to the least //node is not important
 if ambiguous: chose the node in the dependency graph which is present in the highest number of cycles //breaks multiple cycles at once
 if ambiguous: chose the node which is in the longest cycle
 if ambiguous: pick an arbitrary node

可能我没收到 chooseBreakNode非常正确。这是一种启发式方法，您可以根据自己的需要进行调整。