algorithm - 使用 order 属性重新排序对象

Question

考虑具有 order 属性的对象。对象将根据此属性进行排序。

给定以下限制和操作，您将如何分配 order 属性？

操作(按重要性排序)

push(object):在索引 0 处插入对象。

swap(indexN, indexM):将索引 N 处的对象与索引 M 处的对象交换。

remove(object):删除对象。其余元素必须保持相同的顺序。

insert(object):按给定顺序插入对象。

限制

更改对象的 order 属性代价高昂。应尽量减少更改。

order 可以是整数或 float ，具体取决于实现的要求。

如果 order 保持唯一，则 insert 操作必须包含一种方法来修复 order(如果它已经存在)，并进行尽可能少的更改尽可能。可以假定，如果插入的对象与现有对象具有相同的 order，则有另一个标准来确定哪个先出现。

如果 order 允许重复，则操作 swap 必须包括一种方法来修复交换元素的 order 如果它们具有相同的值，再次尽可能少地进行更改。惩罚操作 insert 是首选。

很可能这个问题已经有了名称和已知的解决方案，但我第一眼找不到。

Answer 1

使用 float 排序

对于 push，为对象分配一个顺序，该顺序等于现在位于索引 1 处的对象的顺序减去 1 (list[0].order = list[1].order - 1)

对于swap，交换两个对象的顺序(temp = list[i]; list[i] = list[j]; list[j] = list[i]; temp = list[i].order; list[i].order = list[j].order; list[j].order = temp);如果这可能会引入一致性问题，那么理想情况下，您可以在元素上放置一个 transit 标志，以指示它们的顺序正在被修改，或者在最坏的情况下锁定对象直到它们一致

对于 remove，什么都不做 - 列表中的对象仍然是有序的，您只是在序列中引入了一个间隙，这应该不是问题

insert 是唯一有问题的。如果您在索引 i 处插入一个元素，那么它的顺序等于索引 i-1 和 i+ 处元素顺序的平均值1 (list[i].order = (list[i-1].order + list[i+1].order)/2)。验证此新订单不等于索引 i-1 或 i+1 处的订单(list[i].order != list[i- 1].order && list[i].order != list[i+1].order) - 这表明您已经达到机器 epsilon。当这种情况发生时(这种情况应该很少发生)你有两个选择:

1. 硬着头皮对整个列表重新排序，即在索引 0 处分配一个 0 的顺序，在索引 1 处分配一个 1 的顺序，...一个 的顺序>n 在索引 n 处。
2. 在本地重新订购以尽量降低成本。将相邻元素重新排序为 list[i-1].order = (list[i-2].order + list[i-1].order)/2 和 list[i+ 1].order = (list[i+2].order + list[i+1].order)/2 重新排序之前 list[i] = (list[i-1] + list[ i+1])/2，再次验证您在 [i-1] 和 [i+1] 重新排序时未达到机器 epsilon - 如果您已达到机器 epsilon，例如[i-1]，然后首先将 [i-2] 重新排序为 list[i-2].order = (list[i-3].order + list[i-2].order)/2，然后重新排序 [i-1]。如果 [i-2] 重新排序命中机器 epsilon，则首先重新排序 [i-3]，依此类推。 (如果到达列表的末尾，则只需减少元素 [0] 的顺序或增加元素 [n] 的顺序。)如您所见，在最坏的情况下，级联重新排序的代价更高而不是简单地硬着头皮重新排序整个列表；但是，重新排序很可能会保留在本地。一个好的折衷办法是，如果级联次数太多(对于“太多”的合理值)，则进行完整的重新排序。