6

每隔一段时间，我必须处理用户可以手动排序的元素列表。

在大多数情况下，我尝试依赖使用订单敏感容器的模型，但这并不总是可行的，而是求助于向我的数据添加位置字段。这个位置字段是一个双精度类型，因此我总是可以计算两个数字之间的位置。然而，这并不理想，因为我担心会遇到一个极端情况，即我没有足够的数值精度来继续在两个数字之间插入。

我对保持头寸数字的最佳方法存有疑问。第一个想法是遍历所有行并在每次插入后给它们一个整数，例如：

在 2 和 3 之间删除一行之后：

1   2   2.5   3   4    5

位置编号更新后：

1   2   3     4   5    6

当然，如果我有大量条目，那可能会变得很重。不是专门在内存中，而是将所有新值存储回磁盘/数据库。我通常使用某种类型的 ORM 和移动软件。更新所有代码将从磁盘中取出每个对象并将它们设置为脏，从而重新验证我的数据模型的所有相关验证规则。

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

我相信对于这些情况有一个标准算法，可以定期和持续地更新位置编号，或者只是其中一些。理想情况下，它应该是 O(log n)，在最坏情况和最好情况之间没有很大的时间差异。

老实说，我也认为任何必须用户/排序的东西，在最坏的情况下都不能增长到成为一个真正的问题。边缘情况似乎也极为罕见，如果我搜索推动边界数字的解决方案则更是如此。但是，我仍然相信这个问题有一个众所周知的标准解决方案，我不知道，我想了解它。

4

4 回答 4

4

第二次尝试。

考虑整个position值范围，比如 0 -> 1000

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

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

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

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

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

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

所以 ：

  • 大多数时候，添加一个节点不需要改变其他节点的位置。
  • 当需要平衡时，只会更改您的项目的一个子集。
  • 这是O(log n)！

编辑

算法解释

于 2012-12-14T09:16:02.753 回答
0

几天后没有有效的答案。这是我的理论：

这里真正的挑战是一个切实可行的解决方案。也许有一个数学上正确的解决方案，但是每天过去，似乎实现会非常复杂。一个好的解决方案不仅应该在数学上是正确的，而且还应该与问题的性质、遇到问题的机会低以及问题的轻微影响相平衡。就像用子弹杀死苍蝇一样无用，尽管非常有效。

我开始相信一个好的答案可能是：用正确的解决方案去地狱，让它像一行计算一样，并忍受两个元素排序可能失败的罕见情况。不值得增加复杂性并在这种挑剔的问题上投入时间或金钱，这种问题非常罕见，不会造成数据损坏，只是暂时的 UX 故障。

于 2012-12-17T16:07:25.953 回答
0

如果用户实际上是手动对列表进行排序，那么真的有必要担心花费 O( n ) 来记录新订单吗？在任何情况下，仅将列表显示给用户都是O( n )。

于 2012-12-14T08:12:22.370 回答
0

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

当您谈到“向您的数据添加位置字段”时，我假设您的数据存储是一个关系数据库，并且您的数据具有某种标识符。

所以也许你可以通过在你的数据中添加一个和来实现一个双向链表。因此插入/移动/删除操作是O(1)。previous_data_idnext_data_id

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

  • 获取每个项目并将它们添加到地图中，并以它们的 id 作为键。
  • 对于每个项目，将其与其上一个和下一个项目连接起来。
  • 从第一项（previous_data_id未定义）开始，跟随链并将它们添加到列表中。
于 2012-12-14T08:15:02.450 回答