您应该在愿望清单中添加一个更明智的约束:

O(log N)每件商品的最大空间(N为商品总数)

例如,链表解决方案坚持这一点 - 指针至少需要N个值,因此指针占用log N空间.如果你没有这个限制,Lasse Karlsen和tmyklebu已经提到的简单解决方案(不断增长的字符串)是解决你的问题的方法,但是每个操作的内存增加了一个字符(在最坏的情况下).你需要一些限制,这是一个明智的.

然后,听听答案:

不,没有这样的算法.

好吧,这是一个强烈的声明,并不容易听到,所以我想证明是必要的:)我试图弄清楚一般的证据,发表了一个关于计算机科学理论的问题,但一般的证据真的很难做到.假设我们更容易,我们将明确假设有两类解决方案:

绝对寻址 - 每个项的地址由一些绝对引用(整数,浮点数,字符串)指定

相对寻址 - 每个项目的地址相对于其他项目(例如链表,树等)指定

反驳绝对寻址算法的存在很容易.只取3个项目,A,B,C,然后继续移动前两个项目.您将很快用完移动元素的地址的可能组合,并将需要更多位.你将打破有限空间的约束.

反驳相对寻址的存在也很容易.对于非平凡的安排,当然存在一些其他项目所指的两个不同的位置.然后,如果您在这两个位置之间移动某个项目,则必须至少更改两个项目 - 引用旧位置的项目和引用新位置的项目.这违反了仅更改了一个项目的约束.

QED

不要被复杂性所吸引 - 它不起作用

现在,我们(和你)可以承认你想要的解决方案不存在,为什么你会变得复杂与复杂的解决方案,你的生命不工作？正如我们在上面证明的那样,它们无法工作.我想我们迷路了.这里的伙伴们花费了巨大的努力,最终得到了比最简单的解决方案更糟糕的过于复杂的解决方案:

Gene的有理数 - 在他的例子中它们增长4-6位,而不是最简单的算法所需的1位(如下所述).9/14有4 + 4 = 8位,19/21有5 + 5 = 10位,得到的数字65/84有7 + 7 = 14位!! 如果我们只看这些数字,我们会发现10/14或2/3是更好的解决方案.可以很容易地证明,不断增长的弦线解决方案是无与伦比的,见下文.

mhelvens的解决方案 - 在最坏的情况下,他将在每次操作后添加一个新的修正项目.这肯定会占用更多一点.

这些家伙非常聪明,但显然不能带来明智的东西.有人必须告诉他们 - 停止,没有解决方案,你所做的事情根本不可能比你害怕提供的最简单的解决方案更好:-)

回到原点,简单一点

现在,返回限制列表.你知道,其中一个必须被打破.仔细阅读清单并询问,哪一项最不痛苦？

1)违反内存约束

这很难被无限侵犯,因为你的空间有限......所以要时不时地违反管家的约束.

对此的解决方案是由tmyklebu提出并由Lasse Karlsen提到的解决方案 - 不断增长的字符串.只考虑0和1的二进制字符串.你有A,B和C项,并在A和B之间移动C.如果A和B之间没有空格,即它们看起来

A  xxx0 
B  xxx1

然后再为C添加一个位:

A  xxx0
C  xxx01
B  xxx1

在最坏的情况下,每次操作后都需要1位.您还可以处理字节,而不是位.然后在最坏的情况下,您将不得不为每8个操作添加一个字节.这都一样.而且,很容易看出这种解决方案无法打败.您必须添加至少一位,并且不能添加更少.换句话说,无论解决方案如何复杂,它都不可能比这更好.

优点:

每个项目有一个更新

可以比较任何两个元素,但速度慢

缺点:

随着字符串的增长,比较或排序将变得非常缓慢

有将是一个持家

2)违反一项修改后的约束

这导致了原始的链表解决方案.此外,还有很多平衡的树数据结构,如果你需要查找或比较项目(你没有提到),它们会更好.

这些可以修改3个项目,平衡树有时需要更多(当需要进行平衡操作时),但由于它是分摊的O(1),因此在长行操作中,每个操作的修改次数是不变的.在您的情况下,我只会在您需要查找或比较项目时使用树解决方案.否则,链表解决方案就会出现问题.抛出它只是因为它们需要3次操作而不是1次操作？来吧:)

优点:

最佳内存使用

快速生成有序列表(一次线性通过),无需排序

快速操作

没有家务

缺点:

不能轻易比较两个项目.可以轻松生成所有项目的顺序,但随机给出两个项目,比较它们将O(N)用于列表和O(log N)平衡树.

3个修改过的项目而不是1个(......让你知道这是多少"con")

3)违反"无管家"约束

这些是整数和浮点数的解决方案,最好由Lasse Karlsen在这里描述.此外,点1)的解决方案将落在这里:).Lasse已经提到了关键问题:

家政必须多久进行一次？

如果你将使用k-bit整数,那么从最佳状态开始,当项目在整数空间中均匀分布时k - log N,在最坏的情况下,每次操作都必须进行内务处理.然后,您可以使用更复杂的算法来限制"保持"的项目数量.

优点:

最佳内存使用

快速操作

可以比较任何两个元素

每个操作修改一个项目

缺点:

家政

结论 - 希望永远不会死

我认为最好的方法,以及这里的答案证明,决定哪一个约束是最不痛苦的,只是采取以前不赞成的简单解决方案之一.

但是,希望永远不会消亡.写这篇文章的时候,我意识到如果我们能够询问服务器的话,会有你想要的解决方案!当然取决于服务器的类型,但是经典的SQL服务器已经实现了树/链接列表 - 用于索引.服务器已经在执行"在树中移动此项之前"这样的操作了 !! 但服务器正在根据数据进行操作,而不是基于我们的请求.如果我们能够以某种方式要求服务器执行此操作而无需创建不正常的,无休止增长的数据,那将是您理想的解决方案!正如我所说,服务器已经做到了 - 解决方案非常接近,但到目前为止.如果你可以编写自己的服务器,你可以这样做:-)

我被这个问题着迷,所以我开始研究一个想法.不幸的是,它很复杂(你可能知道它会)并且我没有时间全力以赴.我以为我会分享我的进步.

它基于双向链表,但在每个移动的项目中都有额外的簿记信息.有一些聪明的技巧,我怀疑该集合中的每个n项都需要少于O(n)的额外空间,即使在最坏的情况下,但我没有证明这一点.它还需要额外的时间来确定视图顺序.

例如,采取以下初始配置:

A  (-,B|0)
B  (A,C|0)
C  (B,D|0)
D  (C,E|0)
E  (D,-|0)

从上到下的排序纯粹来自元数据,元数据由(predecessor,successor|timestamp)每个项目的一系列状态组成.

D在A和之间移动时,使用新的时间戳B将新状态推(A,B|1)送到序列的前面,通过递增共享计数器得到:

A  (-,B|0)
D  (A,B|1) (C,E|0)
B  (A,C|0)
C  (B,D|0)
E  (D,-|0)

正如你看到的,我们为了连接保留旧的信息C来E.

以下是从元数据中获取正确顺序的大致方法:

你保留一个指针A.

A同意它没有前任.所以插入A.它会引导你B.

B同意它想成为继任者A.所以插入B之后A.它会引导你C.

C同意它想成为继任者B.所以插入C之后B.它会引导你D.

D不同意.它希望成为继任者A.开始递归以插入它并找到真正的后继者:

D获胜,B因为它有一个更新的时间戳.插入D后A.它会引导你B.

B已经D是继任者了.回顾D过去的历史,这将引导您E.

E同意它希望成为D时间戳0的后继者E.所以回归.

所以继任者是E.插入E后C.它告诉你它没有继承者.你完蛋了.

这还不是一个算法,因为它并不涵盖所有情况.例如,当您向前移动项目而不是向后移动项目时.B在D和之间移动时E:

A  (-,B|0)
C  (B,D|0)
D  (C,E|0)
B  (D,E|1)(A,C|0)
E  (D,-|0)

'移动'操作是一样的.但是导出正确顺序的算法有点不同.从A它将进入B,能够C从它获得真正的继承者,但没有地方插入B自己.您可以保留它作为插入的候选者D,在那里它最终将匹配E该位置的特权的时间戳.

我在Plunker上编写了一些Angular.js代码,可以作为实现和测试该算法的起点.调用相关函数findNext.它没有做任何聪明的事情.

有一些优化可以减少元数据的数量.例如,当一个项目远离它最近放置的位置时,它的邻居仍然是自己联系的,你不必保留它的最新状态,但可以只替换它.并且可能存在这样的情况:您可以丢弃所有项目的足够旧状态(当您移动它时).

遗憾的是我没有时间完全解决这个问题.这是一个有趣的问题.

祝好运!

编辑:我觉得我需要澄清上述优化思路.首先,如果原始链接仍然存在,则无需推送新的历史记录配置.例如,从这里开始(D在A和之间移动B)很好:

A  (-,B|0)
D  (A,B|1) (C,E|0)
B  (A,C|0)
C  (B,D|0)
E  (D,-|0)

到这里(然后D在B和之间移动C):

A  (-,B|0)
B  (A,C|0)
D  (B,C|2) (C,E|0)
C  (B,D|0)
E  (D,-|0)

我们能够丢弃(A,B|1)配置,因为A并B仍通过自身连接.任何数量的"无关"运动都可以在不改变它的情况下进入.

其次,假设最终C和E移动相互远离,这样的(C,E|0)配置可以被丢弃下一次D移动.不过,要证明这一点比较棘手.

所有这些考虑,我相信这是一个很好的机会,列表需要较少比O(n+k)空间(n是列表中的项目数量,k是操作的次数),在最坏的情况; 特别是在一般情况下.

证明这一点的方法是为这种数据结构提出一个更简单的模型,很可能是基于图论.我再次感到遗憾的是,我没有时间研究这个问题.

@tmyklebu有答案,但他从来没有完全触及:你的问题的答案是"不",除非你愿意接受n-1位的最坏情况密钥长度来存储n个项目.

这意味着n个项目的总密钥存储量为O(n ^ 2).

有一个"对手"的信息理论论证说,无论你为n个项目的数据库选择分配键的方案,我总能得出一系列n项重新定位("将项目k移动到位置p" .")会强制你使用n-1位的密钥.或者通过扩展,如果我们从一个空数据库开始,并且你给我插入项目,我可以选择一系列插入位置,这将要求你至少使用第一个零位,一个用于第二个,等等. .

编辑

我之前有一个关于使用有理数字键的想法.但它比仅仅添加一位长度来分割相差一对的键之间的差距更为昂贵.所以我删除了它.

您还可以将选项3解释为将位置存储为无限长字符串.这样你就不会"用完小数点"或任何那种性质.给第一个项目,说'foo',位置1.递归地将你的宇宙划分为"少于foo的东西",它获得一个0前缀,以及"比foo更大的东西",它获得一个1前缀.

这在很多方面都很糟糕,特别是对象的位置可能需要尽可能多的位来表示对象的移动.