根据以前的排序进行排序

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).

把这些规则变成算法让我很难过.这是我到目前为止所拥有的:

1. 从数据库中获取最新的排序映射.对于每一对唯一的ID,我最多只能获得一条记录.

2. 从排序图中删除循环.怎么样？或者更简单地忽略循环作为第4步的一部分？

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

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

   一个.查找包含ID1或ID2使用步骤#3中的哈希表的所有排序映射条目.

   湾 如果我已经有一个记录包含两个ID1并且ID2在排序图中,停止 - 我们知道哪一个应该是第一个!

   C.如果在排序图中找不到ID1和ID2,那么它就是一个平局.返回确定性的任意结果(例如,较低的ID获胜).

   d.如果一个ID在排序图中但另一个不在,则停止.找到的应该先排序.

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

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

有想法吗？

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

---

如果你很好奇,这就是这个算法的现实需求:

我们公司为送货司机构建移动应用程序,他们每天访问他们负责的100-150个地区的大约20个地点.每天的位置列表是根据每个位置的库存动态分配的.库存较低的地点可以获得新库存的交付,而不会访问仍有足够库存的地点.

司机可以按任意顺序自由访问地点,但他们通常每天都会采取类似的路线(例如,当早上交通清淡时,访问城镇南部的地点,然后在交通较重时访问城镇北部的地点南).

我们选择不使用自动确定最有效驾驶路线的第三方路线软件.相反,我们发现让驾驶员选择路线更好,因为路线软件很难受到诸如"建筑物的装卸码头通常仅在早上7点之前免费"或"需要签署交货收据的人员提前离开"的限制周五"对交货时间表有很大影响.

无论如何,我们希望使用驾驶员的历史选择来按照驾驶员上次访问相同位置的顺序对每天的行程进行排序.这将为司机每天安排一个符合他偏好的精心安排的行程,除非在特殊情况下,他不必手动重新安排时间表.这将使司机每天节省一两分钟,这会随着时间的推移而增加.

每个历史行程都是这样的列表(ID1,ID2,ID3,...,IDN,时间戳),但作为存储数百个过去时间表的替代方案,我认为分解每个N机器的历史行程更容易成对的机器.这意味着我必须存储最多N*N-1个元组,因为较新的排序总是将较旧的排序从排序图中取出.如果这是一个简单的简化,请告诉我.;-)

Answer 1

我将提出一种替代方法，但如果我误解了业务需求，请告诉我。

有一个类似（DriverId、LocationId、Priority）的表，用于存储每个驱动程序的位置的相对优先级。

每当您需要处理完整的行程时，请从列表底部（最后访问的位置）开始，并为每个位置运行以下算法，在列表中向上移动：

• 如果该位置的优先级尚未大于其下方位置的优先级，则 newPriority =priorityBelow + 1。（如果下方没有任何内容，则priorityBelow = 0）

处理完列表后，将优先级点重新规范化为 1,2,3...（通过使最低优先级 = 1，第二低优先级 = 2，依此类推）

然后，当您需要订购新行程时，您只需按该司机的相对优先级值对位置进行排序即可。

您考虑过这种方法吗？

编辑：添加下面每个评论的示例代码。

给定 4 个历史行程：ABCD（最新）、ACBE、CBDF、CBDFA（最旧），我将如何对新行程 ABCDEF 进行排序？

static Dictionary<string, int> Priorities = new Dictionary<string, int>();

static void Main(string[] args)
{
    var itineraries = new string[][]{   
        new string[] { "C", "B", "D", "F", "A" },
        new string[] { "C", "B", "D", "F" },
        new string[] { "A", "C", "B", "E" },
        new string[] { "A", "B", "C", "D" } };

    //process past itineraries
    foreach (var itinerary in itineraries)
        ProcessItinerary(itinerary);

    //sort new itinerary
    string[] newItinerary = { "A", "B", "C", "D", "E", "F" };
    string[] sortedItinerary = newItinerary.OrderByDescending(
        x => Priorities.ContainsKey(x) ? Priorities[x] : 1).ToArray();

    Console.WriteLine(String.Concat(sortedItinerary));
    Console.ReadKey();
}

static void ProcessItinerary(string[] itinerary)
{
    itinerary.Reverse().Aggregate((below, above) =>
    {
        int priBelow = Priorities.ContainsKey(below) ?
            Priorities[below] : Priorities[below] = 1;

        if (!(Priorities.ContainsKey(above) &&
            Priorities[above] > priBelow))
            Priorities[above] = priBelow + 1;

        return above;
    });

    //normalize priorities
    // (note: running in reverse so that if priorities tie, 
    //  the older location has higher priority)
    int i = Priorities.Count;
    foreach (var pair in Priorities.OrderByDescending(x => x.Value))
        Priorities[pair.Key] = i--;
}

这将打印出：ABCDFE