algorithm - 以最少的重新编号对项目进行排序

Question

我需要快速将重新排序的序列保存回我的项目的整数 sortOrder 列。

简单的逐一重新编号方法可能很慢 - 如果最后一项移到第一项，则所有 N 行都将被修改。多行更新语句会让数据库完成工作，但我想探索更智能的方法，比如使 sortOrder 浮点，除非我没有那个选项:(

我想象的解决方案将采用如下重新编号的列表:(100,200,1700,300,400...1600,1800,...) 并生成 (100,200,250,300,400...1600,1800,...)(通过修改本例中为一行)。乍一看似乎很简单，但我很难用代码表达它......

有人可以帮我解决这个逻辑吗？可能有相邻项目的序列需要移动才能适合新项目 - 我希望有人可能已经写好了？它必须比我现在拥有的更快，但仍然可读且易于理解/维护。

好的，回答后，回发我想出的结果代码(欢迎评论):

/**
 * Renumber list with minimal changes
 * 
 * Given a list of SortOrderNumbers in the 'new' sequence they are to be saved in, determine the
 * minimal set of changes (described by Change(i, newSortOrderNumber)) that can be saved that
 * results in a properly ordered sequence.
 * 
 * A simple answer would always be List(change<1,1>, change<2,2>, ...change<n,n>) which is of length N.
 * This method returns a set of changes no larger than N (often much smaller for simple moves).
 * 
 * @author Jim Pinkham
 * @param s
 * @return Set<Change>
 */
private Set<Change> renumber(int[] s) {
    Set<Change> ret = new HashSet<Change>();
    // pass1 goes from start forwards looking for decrease in numbering
    for (int i=1; i<s.length; i++) {
        // if predecessor of item is larger and it's large enough to renumber from start of list 
        if (s[i-1]>s[i] && s[i]>i) {                
            int beforeStart=0;
            int beforeIndex=-1;
            // go back towards start looking for anchor
            for (int j=i-2; j>=0; --j) {
                int diff = s[i]-s[j];
                if (diff>(i-j)) {
                    beforeIndex=j;
                    beforeStart=s[beforeIndex];
                    break;
                }
            }
        int diff = s[i]-beforeStart;
        int stepsToDiff=i-beforeIndex;
            int delta = diff/stepsToDiff;
            // renumber from start of list or anchor thru decrease
            int fixCnt=0;
            for (int j=beforeIndex+1; j<i; ++j) {
                s[j] = beforeStart + (delta*++fixCnt); 
                System.out.println("s["+j+"]="+s[j]);
                ret.add(new Change(j, s[j]));
            }
        }
    }
    // pass1 could leave some decreases in sequence  
    // pass2 goes from end back to start
    for (int i=s.length-1; i>0; i--) {
        // if predecessor of item is larger 
        if (s[i-1] > s[i]) {
            int afterIndex=s.length;
            int delta=DEFAULT_RENUMBER_GAP;
            // go back towards end looking for anchor               
            for (int j=i; j<s.length; ++j) {
                int diff = s[j]-s[i-1];
                if (diff>(j-(i-1))) {
                    afterIndex=j;
                    int afterEnd=s[afterIndex];
                    int stepsToDiff=afterIndex-(i-1);
                    int gap = afterEnd-s[i-1];
                    delta = gap/stepsToDiff;
                    break;
                }
            }
            // renumber from decrease thru anchor or end of list
            int fixCnt=0;
            for (int j=i; j<afterIndex; ++j) {
                s[j] = s[i-1] + (delta*++fixCnt); 
                System.out.println("s["+j+"]="+s[j]);
                ret.add(new Change(j, s[j]));                   
            }
        }
    }
    return ret;
}
class Change { 
    int i; 
    int sortOrder; 
    Change(int i, int sortOrder) { 
        this.i=i; this.sortOrder=sortOrder; 
    }
    public boolean equals(Change other) {
        return Integer.valueOf(i).equals(Integer.valueOf(other.i));
    }
    public int hashCode() {
        return Integer.valueOf(i).hashCode();
    }
}

Answer 1

I'd like to explore smarter ways, like making sortOrder floating point except I don't have that option

如果您发现用 float 来思考它更容易，为什么不把数字想象成定点数。

例如出于您的算法的目的，将 1000000 解释为 100.0000。您需要选择点位置，以便在给定(数组中的最大项目数+2)与整数大小的情况下可以容纳尽可能多的小数(或二进制)位。因此，假设最大条目数为 998，您需要在点之前保留 3 位数字，其余部分可用于“空缺”。

移动操作可以很简单，只需将其新排序编号设置为任一侧项目排序编号总和的一半，即将移动的项目插入其新邻居之间。使用 0 和 size(array)+1 作为最终情况。我再次假设您的 UI 可以记录用户完成的 Action - 不管我认为计算它们应该相当简单，并且可能会使用标准排序算法，只需重新定义“交换”。

因此，例如将数组中的最后一个移动到第一个(带虚数小数点):

1.00002.00003.00004.00005.0000

成为

1.00002.00003.00004.00000.5000 = (0.0000 + 1.0000)/2

给出排序顺序

0.50001.00002.00003.00004.0000

只改变一条记录，数组中的最后一条

将最后一个移动到第二个会这样做:

1.00002.00003.00004.00005.0000

成为

1.00002.00003.00004.00001.5000 = (1.0000+2.0000)/2

导致排序顺序为

1.00001.50002.00003.00004.0000

同样，只有一条记录发生了变化。

您仍然需要解决两个数字“之间”空间不足的情况，您最终会遇到这种情况。我认为这与算法无关。这将需要“交换”以重新编号更多条目以腾出更多空间。同样，无论算法如何，我认为您都不能排除必须对所有内容重新编号的情况，这种可能性很小。我还怀疑随着时间的推移，大量重新编号变得更有可能，无论你做什么 - 可用空间都会碎片化。然而，通过选择点的位置以提供尽可能多的空间，它应该是最佳的，即你尽可能推迟它。

为避免在不方便的时间进行更广泛的重新编号，建议在安静时期定期进行某种批量重新编号 - 基本上再次拉伸(stretch)间隙以为进一步的用户驱动排序腾出空间。同样，我认为无论您使用何种方法，您都可能需要它。

这只是一个草图，我认为它可能等同于任何其他方式，尽管它可能是一种更直观/可维护的思考方式，也是一种最大化扩展空间的方式。另外，如果您真的担心退化案例的性能不佳——从您的描述来看，您应该如此——我建议您在具有大量随机数据(无数据库)的测试工具中运行您使用的任何算法在很长一段时间内，看看它在实践中真正执行了多少次重新编号，尤其是看看它是否会随着长时间使用而退化。我怀疑任何算法都会这样。