algorithm - Jira 的新故事 Lexorank 算法

Question

我希望创建一个大型项目列表，以便轻松插入新项目并轻松更改项目在该列表中的位置。更新项目的位置时，我想更改尽可能少的有关项目顺序的字段。

经过一些研究，我发现 Jira 的 Lexorank 算法满足了所有这些需求。 Jira 中的每个故事都有一个“排名字段”，其中包含一个由 3 部分组成的字符串:<bucket>|<rank>:<sub-rank> . (我不知道这些部分是否有实际名称，为了方便引用，我就这样调用它们)

有效排名字段的示例:

• 0|vmis7l:hl4
• 0|i000w8:
• 0|003fhy:zzzzzzzzzzzw68bj

在0|vmis7l:hl4上方拖动卡片时, 新卡将获得排名 0|vmis7l:hl2 ，这意味着只需要更新这张新卡的排名字段，而整个列表始终可以在此排名字段上排序。这相当聪明，我无法想象 Lexorank 是唯一使用它的算法。

1. 子排名中使用的这种排序方法有名称吗？

我的问题与在 Jira 中创建新卡片有关。每张新卡都以一个空的子排名开始，并且始终选择排名，使新卡位于列表的底部。我创建了一堆新故事只是为了看看等级会如何变化，而且等级似乎总是增加 8(以 base-36 为单位)。

1. 有没有人更具体地知道新卡的等级是如何产生的？为什么增加 8？

我只能想象一段时间后(2.7 亿张卡片)没有更多的排名生成，系统需要重新计算所有卡片的排名字段以为额外的排名腾出空间。

1. 是否有其他触发器需要重新计算所有排名字段？
2. 我想桶在这次重新计算中发挥了作用。我想知道怎么做？

Answer 1

1. 我们在这里讨论的是一种特殊的索引。这不是排序；它只是准备项目以某种顺序结束，以防有人碰巧对它们进行排序(通过任何排序算法)。我知道这种索引的变体已经在图书馆中使用了几十年，也许几个世纪，以确保属于一起但没有共同标题的书籍最终在书架上并排放置，但我从未听说过一个名字

2. 选择 8 可能是明智的折衷方案，甚至可能是通过分析典型用例。考虑一下:如果您选择一个小的增量，e。 G。 1，那么所有的门票都会有像 [a, b, c, …] 这样的排名。如果您以正确的顺序创建大量门票(最多 26 张)，这将非常好，因为这样您的排名字段就会保持很小(一个字母)。但是一旦你在另外两张票之间移动一张票，你就必须添加一个字母:[a, b] 加上它们之间的新票:[a, an, b] 。如果你希望有很多，你最好在行列之间留出空隙:[a, i, q, …]，那么额外的票也可以得到一个字母:[ a, e, i, q, …]。但是当然，如​​果你现在一开始就以正确的顺序创建很多票，你很快就会用完字母:[a, i, q, y, z, za, zi, zq, …]。 8 可能是一个很好的值，它允许门票之间有足够的差距，而不会过早增加对许多字母的需求。请记住，其他情况(可能不是手动创建的 Jira 票证)可能会使其他值更合理。

3. 你是对的，等级字段会不时重新计算，Lexorank 称之为“平衡”。基本上，平衡发生在以下三种情况之一:①排名用尽(达到最大值)，②排名是由于用户对票的重新排名太近([a, b, i] 并且在 a 和 b 之间应该有一些东西)，并且 ③ 在管理页面中手动触发平衡。 (实际上，根据介绍，Lexorank 允许最多三个字母排列，所以“靠得太近”可以是 aaa 和 aab 之类的东西，但想法是一样的.)

4. rank 的 部分在平衡过程中增加了，所以杂乱的 [0|a, 0|an, 0|b] 可以变成漂亮干净的 [1|a, 1|i, 1|q] 再次。 brownbag presentation about Lexorank (如评论中@dandoen 所链接)提到了 的循环使用，因此不是恒定递增 (0→1→2→3→…)，而是以 3 为模增加 2，因此它会返回在 2 之后变为 0 (0→1→2→0→…)。比较排名时，排序算法可以考虑 0 比 2“更大”(承认它不会是纯粹的字典顺序)。如果现在平衡算法向后工作(首先重新排序最后一张票)，这将始终保持排序顺序不变。 (这只是一个方面，这就是为什么我保持简短的解释，但如果这很有趣，请询问，我会详细说明。)

旁注:Lexorank 还跟踪排名的最小值和最大值。对于算法本身的功能，这不是必需的。