允许对对象重新排序的算法，同时只需要更新恒定数量的对象位置

2024-04-25

我有一大堆对象，我希望根据它们的一个属性来保持顺序。

作为一个例子，我们假设一个对象可能看起来像：

var myObject = {
    id: 'c_1',
    position: 0 
}

有序集合的简单实现如下所示：

[{
    id: 'c_1',
    position: 0 
}, {
    id: 'c_2',
    position: 1
}, {
    id: 'c_3',
    position: 2 
}, {
    id: 'c_4',
    position: 3 
}, {
    id: 'c_5',
    position: 4 
}]

这是一个幼稚的实现的原因是，如果“c_4”希望在“c_1”和“c_2”之间移动，那么“c_2”、“c_3”、“c_4”和“c_5”的位置必须全部更新为容纳。这意味着，平均而言，对于对象数组的任何给定重新排序，N/2 + 1 个元素将受到影响。

我目前提出的解决方案并不那么幼稚，但也有其自身的缺陷。

我没有将每个元素直接相邻放置（即 0、1、2、3、4），而是在每个元素之间留下“足够大”的间隙：

[{
    id: 'c_1',
    position: 10000 
}, {
    id: 'c_2',
    position: 20000
}, {
    id: 'c_3',
    position: 30000 
}, {
    id: 'c_4',
    position: 40000 
}, {
    id: 'c_5',
    position: 50000
}]

现在，如果“c_4”希望在“c_1”和“c_2”之间移动，则其位置将设置为其两个提议的新邻居的中点。 “c_4”的位置为 15000，不需要影响其他元素。

不过，在足够大量的重新排序 (log(10000) = 13) 后，该解决方案开始崩溃，并且一旦遇到这种情况，就需要重新索引数组。

我想知道是否有另一种更优雅的解决方案来解决我的困境？

当我输入此内容时，我意识到我可以停止期望位置是整数，并允许它变成双精度数，这将允许任何两个给定元素之间有近乎无限数量的位置。也许这是正确的选择，但这实际上只是我的非幼稚实现的重新哈希。

这些是问题的步骤

数据的初始状态，包含重要索引的列表
更改列表中项目的索引
更新列表中所有项目的操作
数据的最终状态

至少有 3 种方法可以在客户端和服务器之间同步 #1 和 #4，我将在下面概述。请注意，我不会比较这三个选项的计算强度。听起来，处理速度不是您最关心的问题，而是带宽是。考虑到这一点，以下是三个选择：

方法一：发送最终状态

第一种方法是最明显的方法，也是您遇到问题的方法，是通过传递 #4 来更新服务器。随着您的列表变长，这将成为发送的相当大的有效负载。

Pros

#3 执行一次
它适用于最常见的 HTTP 动词，例如 POST
这是最明显的；很容易理解发生了什么

Cons

正如您所指出的，随着列表的增长，您通过线路发送的数据会变得非常大

方法二：仅发送更改

第二种选择将带宽降低到绝对最小值。为此，您可以通过线路传递#2 并在服务器上执行#3。这会重复该操作（我想您仍然希望在客户端上执行它，而不是等待服务器的响应），但将带宽使用保持在最低限度。

这可能如下所示：

{
  oldIndex: 2134
  newIndex: 54
}

这为服务器提供了执行 #3 和执行 #4 所需的一切。这很容易扩展到n通过创建按顺序执行的操作列表来进行操作，从而产生n更新中的对象。

Pros

带宽可能是最小的

Cons

客户端和服务端重复操作逻辑，不太DRY
服务器执行更多计算
它是专有的，不像第一种方法那样简单的 API 端点

方法三：JSONPatch

第三个选项是使用JSON 补丁规范 https://www.rfc-editor.org/rfc/rfc6902生成补丁发送到服务器。单个移动操作的 JSON 补丁产生n+1物体，其中n = Math.abs(oldIndex - newIndex).

例如，

给定初始数组

[a, b, c, d, e, f, g, h, i, j]

和操作

{
  oldIndex: 5
  newIndex: 2
}

上面的算法显示 JSONPatch 将有 5-2+1，即 4 个对象。这些对象是：

[
  {"op":"replace","path":"/5","value":"e"},
  {"op":"replace","path":"/4","value":"d"},
  {"op":"replace","path":"/3","value":"c"},
  {"op":"replace","path":"/2","value":"f"}
]

如果您选择使用 JSONPatch 我建议您使用类似的库JSON 补丁 https://github.com/Starcounter-Jack/JSON-Patch来处理它。

Pros:

处理的不仅仅是动作
没有库可以处理所有的边缘情况（我在 JSON-Patch 上有几个关于失败情况的未解决问题）

Cons:

比仅仅传递操作本身更多的带宽
潜在的更多计算
需要额外的库
取决于 HTTP PATCH 动词

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm