我有一个大型数组，可以重新排序并存储在NoSQL数据库(Firebase Realtime Database(中。我使用Ionic4离子重新排序组对它们进行排序。
我目前正在保存数据如下：
{
Data:
0:{
N1:'',
N2:'',
N3:false
},
1:{
N1:'',
N2:'',
N3:false
},
...
}
但是通过在开始时添加一个对象，我必须更新服务器中的完整数组。问题是，如果我有 1'000 个对象并在开始时添加 10 个新对象，我已经在服务器中写入了 10'000 个对象。
那么构建大型重新排序数组列表的最佳方法是什么？我的想法是使用 pushId，但我还没有找到问题不再存在的解决方案。在下面的代码中，您可以看到我的想法，但问题是一样的，一切都必须更新，并且很多 pushId 需要更多的内存......
{
Data:
[pushId]:{
P: 0, // Position at the array
N1:'',
N2:'',
N3:false
},
...
}
在插入/删除/移动列表项目时为列表项分配有序标签的问题众所周知，称为"联机列表标签"。 这是"订单维护问题"的严格版本，这里有一个维基百科页面：https://en.wikipedia.org/wiki/Order-maintenance_problem
你能做的最好的事情是每次插入摊销O(log N(重新标记，所以如果你有一个包含1000个对象的列表，并且你插入了10个东西，你将不得不更新大约100个项目——还不错。
实现这个界限并不难。 也许最简单的算法是本文中描述的第一个算法："用于维护列表中的顺序的两种简化算法"，作者是 Bender、Cole、Demaine 等，你可以在这里免费获得：https://erikdemaine.org/papers/DietzSleator_ESA2002/paper.pdf
对于最多 N 个项目的列表，它需要最多N 个可用键左右。 例如，您将对最多 232个项目使用 64 位整数。
这是一个简单的化身：
- 我们将为最多 232个项目分配 64 位标签
- 因此，对于标签的每个 k 位前缀(由高阶位组成(，有 2 个具有该前缀的64-k可用标签。
- 当我们在标签a和b之间插入项目时，我们可以在它们之间选择任何标签。 如果它们是相邻的，我们必须首先重新标记一些。
- 要重新标记，请找到密度足够低的最长前缀(使用的标签/可用标签(，并均匀地分隔具有该前缀的所有标签。
如果使用小于sqrt(m(标签，则具有m个可用标签的前缀的密度足够低。 那么，长度为k 的前缀具有足够低的密度，如果使用该前缀的32-k/2 标签少于 2 个。
请参阅链接的论文，以证明这提供了声称的摊销复杂性