Jira用于新故事的Lexorank算法

Question

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

经过一些研究,我发现Jira的Lexorank算法满足了所有这些需求.Jira中的每个故事都有一个'rank-field',其中包含一个由3个部分组成的字符串:<bucket>|<rank>:<sub-rank>.(我不知道这些部分是否有实际名称,为了便于参考,这就是我所说的)

有效等级字段的示例:

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

当拖动上面的卡时0|vmis7l:hl4,新卡将接收排名0|vmis7l:hl2,这意味着只需要更新该新卡的排名字段,而整个列表总是可以在该排名字段上排序.这是相当聪明的,我无法想象Lexorank是唯一使用它的算法.

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

我的问题与在Jira中创建新卡片有关.每张新卡都以空的子排名开头,并且总是选择排名,使得新卡位于列表的底部.我创建了一堆新故事只是为了看看排名会如何变化,而且排名总是增加8(基数为36).

2. 有没有人更具体地知道如何生成新卡的排名？为什么它增加8？

我只能想象,经过一段时间(2.7亿张牌)后,没有更多的牌可以产生,系统需要重新计算所有牌的等级字段,以便为更多的牌位腾出空间.

3. 还有其他需要重新计算所有等级字段的触发器吗？
4. 我认为桶在这次重新计算中发挥了作用.我想知道怎么样？

Answer 1

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

2. 8 可能是明智地选择作为折衷方案，甚至可能是通过分析典型用例。考虑一下：如果您选择一个小的增量，例如 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. <bucket> 部分的等级在平衡过程中增加，所以一个凌乱的[0|a, 0|an, 0|b]可以[1|a, 1|i, 1|q]再次变得干净整洁。关于 Lexorank的brownbag 演示（如@dandoen 在评论中所链接）提到了<buckets> 的循环使用，因此不是恒定增量（0?1?2?3?...），而是以模3 增加2，所以它会在 2 (0?1?2?0?...) 之后变回 0。在比较排名时，排序算法可以考虑 0 “大于” 2（承认它不会纯粹是按字典顺序排列的）。如果现在平衡算法向后工作（首先重新排序最后一张票），这将始终保持排序顺序不变。（这只是一个侧面，这就是为什么我保持简短的解释，但如果这很有趣，请询问，我会详细说明。）

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