1

我有一个项目列表（想想目录中的文件），其中这些项目的顺序由用户任意管理。用户可以在其他项目之间插入项目、删除项目以及移动它们。

将排序存储为每个项目的属性的最佳方法是什么，以便在插入或移动特定项目时，其他项目的排序属性不受影响？这些对象将存储在数据库中。

理想的实现将能够支持无限数量的插入/重新排序。

我用来确定该方法局限性的测试如下：

有 3 个项目 x,y,z，重复取左边的项目，放在另外两个之间；然后把右边的物体放在另外两个之间；继续前进，直到违反某些约束。

为了其他人的参考，我已经包含了一些我尝试过的算法。

4

5 回答 5

4

1.1。小数，双精度

将订单存储为小数。要在具有 x 和 y 顺序的两个项目之间插入一个，请将其顺序计算为 x/2+y/2。

限制：

精度或性能。使用双打，当分母变得太大时，我们最终得到 x/2+y/2==x 。在 Javascript 中，它只能处理 25 次随机播放。

function doubles(x,y,z) {
    for (var i = 0; i < 10000000; i++) {
    //x,y,z
    //x->v1: y,v1,z
    //z->v2: y,v2,v1
      var v1 = y/2 + z/2
      var v2 = y/2 + v1/2
      x = y
      y = v2
      z = v1

      if (x == y) {
        console.log(i)
        break
      }
    }
}

>doubles(1, 1.5, 2)
>25

1.2. 小数，BigDecimal

与上面相同，但使用来自https://github.com/iriscouch/bigdecimal.js的 BigDecimal 。在我的测试中，性能迅速下降，无法使用。对于其他框架来说，它可能是一个不错的选择，但对于客户端 JavaScript 则不然。

我把那个实现扔掉了，再也没有了。

2.1。分数

将订单存储为（分子，分母）整数元组。要在 xN/xD 和 yN/yD 之间插入一个项目，请给它一个 (xN+yN)/(xD+yD) 的值（可以很容易地显示在其他两个数字之间）。

限制：

精度或溢出。

function fractions(xN, xD, yN, yD, zN, zD){
    for (var i = 0; i < 10000000; i++) {
    //x,y,z
    //x->v1: y,v1,z
    //z->v2: y,v2,v1

      var v1N = yN + zN, v1D = yD + zD
      var v2N = yN + v1N, v2D = yD + v1D

      xN = yN, xD=yD

      yN = v2N, yD=v2D

      zN = v1N, zd=v1D

      if (!isFinite(xN) || !isFinite(xD)) { // overflow
        console.log(i)
        break
      }
      if (xN/xD == yN/yD) { //precision
        console.log(i)
        break
      }
    }
}

>fractions(1,1,3,2,2,1)
>737

2.2. GCD 减少的分数

与上面相同，但使用最大公分母算法减少分数：

function gcd(x, y) {
    if(!isFinite(x) || !isFinite(y)) {
        return NaN
    }
    while (y != 0) {
        var z = x % y;
        x = y;
        y = z;
    }
    return x;
}

function fractionsGCD(xN, xD, yN, yD, zN, zD) {
    for (var i = 0; i < 10000000; i++) {
    //x,y,z
    //x->v1: y,v1,z
    //z->v2: y,v2,v1

      var v1N = yN + zN, v1D = yD + zD
      var v2N = yN + v1N, v2D = yD + v1D

      var v1gcd=gcd(v1N, v1D)
      var v2gcd=gcd(v2N, v2D)

      xN = yN, xD = yD
      yN = v2N/v2gcd, yD=v2D/v2gcd
      zN = v1N/v1gcd, zd=v1D/v1gcd

      if (!isFinite(xN) || !isFinite(xD)) { // overflow
        console.log(i)
        break
      }
      if (xN/xD == yN/yD) { //precision
        console.log(i)
        break
      }
    }
}

>fractionsGCD(1,1,3,2,2,1)
>6795

3. 字母

使用字母顺序。这个想法是从一个字母表开始（例如，[32..126] 的 ascii 可打印范围），然后增长字符串。因此，（'O' 是我们范围的中间），在“a”和“c”之间插入，使用“b”，在“a”和“b”之间插入，使用“aO”，等等。

限制：

字符串会变得太长以至于不适合数据库。

function middle(low, high) {
    for(var i = 0; i < high.length; i++) {
        if (i == low.length) {
            //aa vs aaf
            lowcode=32
            hicode = high.charCodeAt(i)

            return low +  String.fromCharCode( (hicode - lowcode) / 2)
        }

        lowcode = low.charCodeAt(i)
        hicode = high.charCodeAt(i)

        if(lowcode==hicode) {
            continue
        }
        else if(hicode - lowcode == 1) {
            // aa vs ab
            return low + 'O';
        } else {
            // aa vs aq
            return low.slice(0,i) + String.fromCharCode(lowcode + (hicode - lowcode) / 2)
        }
    }
}

function alpha(x,y,z, N) {
    for (var i = 0; i < 10000; i++) {
    //x,y,z
    //x->v1: y,v1,z
    //z->v2: y,v2,v1
        var v1 = middle(y, z)
        var v2 = middle(y, v1)
        x = y
        y = v2
        z = v1

        if(x.length > N) {
            console.log(i)
            break
        }
    }
}

>alpha('?', 'O', '_', 256)
1023
>alpha('?', 'O', '_', 512)
2047
于 2013-01-17T00:35:01.153 回答
2

也许我错过了一些基本的东西，我承认我对 javascript 知之甚少，但你肯定可以实现一个双向链表来处理这个问题吗？然后重新排序 a,b,c,d,e,f,g,h 以在 d 和 e 之间插入 X，您只需取消链接 d->e，链接 d->X，然后链接 X->e 等等。

因为在上述任何情况下，要么您将耗尽精度（并且您的无限排序丢失），要么您最终会得到非常长的排序标识符并且没有内存:)

于 2013-01-17T00:50:04.607 回答
1

软件公理#1：保持简单，直到你找到一个令人信服的、真实的和经过验证的理由让它变得更复杂。

因此，我认为当 DOM 已经为您执行此操作时，维护您自己的 order 属性是额外且不必要的代码和维护。为什么不让 DOM 保持顺序，您可以在需要时为当前顺序动态生成一组脑残的简单序列号？CPU 的速度非常快，可以在您需要或任何时间更改时为所有项目生成新的序列号。而且，如果你想在服务器上保存这个新的排序，只需将整个序列发送到服务器。

实现这些拆分序列之一，以便您始终可以插入更多对象而无需重新编号任何内容，这将需要大量代码和大量出现错误的机会。在证明您确实需要这种复杂程度之前，您不应该去那里。

于 2013-01-17T00:44:10.700 回答
0

将项目存储在数组中，并用于splice()插入和删除元素。

或者这是因为您对链表答案做出的评论而不能接受？

于 2013-01-17T01:05:16.800 回答
0

您要解决的问题可能是插入排序，它具有 O(n^2) 的简单实现。但是有一些方法可以改进它。假设有一个与每个元素关联的顺序变量。您可以巧妙地分配这些订单，变量之间的差距很大，并获得摊销 O(n*log(n)) 机制。看看（插入排序是 nlogn）

于 2013-01-17T01:27:00.963 回答