排序算法以保持排序位置数字更新

Question

偶尔我需要处理用户可以手动排序的元素列表。

在大多数情况下，我尝试使用一个有序敏感的容器模型，但这并不总是可能的，因此我会添加一个位置字段到我的数据中。这个位置字段是双精度类型，因此我总是可以计算两个数字之间的位置。然而，这并不理想，因为我担心会出现边缘情况，无法保证足够的数值精度来继续在两个数字之间插入。

我对于维护我的位置数值的最佳方法存在疑虑。第一种想法是遍历所有行，在每次插入后给它们一个圆整的数字，例如：

在将一行放置在2和3之间后：

1   2   2.5   3   4    5

位置编号更新后：

1   2   3     4   5    6

当然，如果我有大量记录，可能会变得很重。这不是特指内存，而是要将所有新值存回磁盘/数据库中。我通常使用某种ORM和移动软件。更新所有代码将使每个对象从磁盘中读取并设置为脏数据，导致重新验证所有相关的数据模型验证规则。

我也可以等待精度不足以计算两个位置之间的数字。但是用户体验会很差，因为相同的操作将不再需要相同的时间。

我认为，在这些情况下，有一种标准算法可以定期且一致地更新位置编号，或仅更新其中一些位置编号。理想情况下，它应该是O(log n)，在最坏和最好的情况下没有大的时间差异。

老实说，我也认为任何必须由用户/排序的东西都不会像其最坏情况那样变得非常大，成为真正的问题。极端情况似乎也非常少见，即使我试图通过推动边界数字来寻找解决方案。然而，我仍然相信存在解决此问题的标准已知解决方案，但我不知道它是什么，我想了解一下。

- SystematicFrank

---

不，这是不切实际的。任何更改都必须立即保存回磁盘，而不知道如何保存。 - SystematicFrank

如果有一种浮点数类型具有无限的数字精度，那么它是否能满足要求？ - Avi Cohen

是的，这样就可以了。这个问题的根源在于无法无限次计算和存储两个浮点数之间的位置。 - SystematicFrank

听起来似乎是一个可能的解决方案，但是仅仅使用这种方法的想法让我感到...“肮脏”，害怕我晚上睡觉时会想着我的生命意义，因为我采用了这样的欺骗性技巧，害怕有一天我会因为犯下的算法罪行而在床上出汗做噩梦。使用字符串会增加存储和排序的成本，不是从可用性的角度，而是从实际-4-这个问题的角度。我编写了基于启发式的解决方案，我的目标是其算法版本。 - SystematicFrank

我相信你！你可以允许一个维护期吗？如果可以的话，那么你就可以使用你原来的解决方案，在重负工作后进行“放松”阶段。 - Avi Cohen

Answer 1

第二次尝试。

考虑完整的 position 值范围，比如 0 -> 1000。

我们插入的第一项应该具有位置为 500。现在我们的列表是：

(0) -> 500 -> (1000).

如果您在第一个位置插入另一个项目，我们最终会得到：

(0) -> 250 -> 500 -> (1000).

如果我们一直在第一个位置插入项目，我们会遇到问题，因为我们的范围不平衡......等等...平衡？这不是听起来像二叉树的问题吗？

基本上，您将列表存储为二叉树。插入节点时，根据周围的节点为其分配位置。当您的树变得不平衡时，旋转节点以使其再次平衡，并重新计算旋转节点的位置！

所以：

- 大多数情况下，添加节点不需要更改其他节点的位置。 - 当需要平衡时，只有一部分项目会发生变化。 - 这是O(log n)！ 编辑

- Nicolas Repiquet

---

你的提议存在一些问题。二叉树并不是天然平衡的，也许你想到的是AVL树。这个问题涉及到连续节点，因此B样式树可能会有优势。你还提到“将列表存储为二叉树”，但是我的后端是数据库，ORM将其映射到内存中，而我的数据模型则对此进行摘要。我希望在存储级别之前不泄露我的设计。我更喜欢在我的模型类中做一些事情。我考虑过暂时反向构建一个B+树（避免B*压缩），将边缘节点推开...但还不够好 :( - SystematicFrank

@Nicolas：你不需要解释 自平衡二叉树 如何一般地工作。但是在我评论中描述的特定情况下，你的建议如何工作？（问题在于自平衡二叉树平衡 树的高度，而在这个问题中，我们需要平衡数字在范围内的 分布，并且不清楚平衡一个是否也会平衡另一个。） - Gareth Rees

哇！刚看到你最近的编辑。我理解了你想要重新平衡范围的方式，但我仍然担心你如何想要将重新平衡的位置值“包含”在一个部分内（并避免修改的传播）。更像是：我有[0,8,10,11,50]，想要在10和11之间插入。使用10.5？推10？最好将11推到50/2，因为它有更多的空间（只需一个包含级别的推动）。 - SystematicFrank

@GarethRees 当然，这个人为他的答案付出了努力，并且由于他的工作，我给了他一个赞。但我认为这仍然不是一个好的解决方案。看看我之前的评论示例。它似乎指向一个方向，即容器并不重要，易于实现，但也许不是正确的方法。当然，它似乎很有前途，因为随着更多的边缘位置数字被推开，它可以向上增长。 - SystematicFrank

@Nicolas：我同意，对于一棵平衡树，我们可以计算出平衡的数字分布。但是我还没有被说服，即每次对平衡树的更新只会导致O(log n)的重新分配。如果一个节点改变了深度（就像在旋转之后可能发生的那样），它可能只有改变深度之前可用范围的一半：纠正这个问题可能需要将大部分后代的数字重新分配。特别是你最后一步（“重新应用范围”）看起来像是O(n)。 - Gareth Rees

Answer 2

经过几天没有有效答案后，这是我的理论：

真正的挑战在于实际解决方案。也许有一个数学上正确的解决方案，但随着时间的推移，看起来实施起来会非常复杂。一个好的解决方案不仅应该在数学上是正确的，而且还应该平衡问题的本质，遇到它的可能性较低以及其次要影响。就像用子弹杀苍蝇一样无用，尽管极其有效。

我开始相信一个好的答案可能是：扔掉正确的解决方案，把它留作一个行计算，并接受极少数情况下两个元素排序可能失败的情况。增加复杂性和投入时间或资金在如此微小的问题上毫无意义，这是如此罕见，不会造成数据损坏，只是暂时的用户体验故障。

- SystematicFrank

Answer 3

如果用户实际上正在手动排序列表，那么有必要担心记录新顺序的时间复杂度为O(n)吗？无论如何，将列表显示给用户的时间复杂度都是O(n)。

- Gareth Rees

---

谢谢Gareth，我刚刚在更新我的问题，关于O(n)的复杂度有多大。然而，我已经提到最坏情况似乎不太可能发生，因此我最大的担忧是想找到一个解决看起来相当普遍的问题的算法。 - SystematicFrank

Answer 4

这并不是真正回答问题，但是...

由于你提到了“向数据添加位置字段”，我假设你的数据存储是关系型数据库，并且你的数据具有某种标识符。

因此，您可以通过将previous_data_id和next_data_id添加到您的数据中来实现双向链表。插入/移动/删除操作的时间复杂度为O(1)。

从数据库加载这样的集合相当容易：

• 获取每个项目并将其添加到以其ID为键的映射中。
• 对于每个项目，将其与其前一个和后一个项目连接起来。
• 从第一个项目（previous_data_id未定义）开始跟随链并将它们添加到列表中。

- Nicolas Repiquet

---

我正要发布一个答案，但你的答案本质上提供了相同的解决方案 - 一个双向链表结合一个字典/哈希表，其中值是列表中的节点。移动一个项目应该是O(1)，因为获取节点是O(1)操作，并且在列表中删除和重新插入节点也是O(1)。数据结构与通常用于实现LRU缓存的结构非常相似，但用于不同的目的。 - hatchet - done with SOverflow

我认为使用关系型数据库与否不会对问题产生太大影响。如果用户可以手动排序，那么无论是SQL还是NoSQL都必须存储这些用户输入。当然，我可以从一些具有排序容器的NoSQL存储中受益。然而，在第二段中，我立即提到我正在寻找那些没有排序容器的情况下的解决方案。一方面，我想避免将我的数据重新映射到中间结构的额外层。另一方面，我只对这个问题的算法挑战感兴趣。 - SystematicFrank