1

項目 (ディレクトリ内のファイルと考えてください) のリストがあり、これらの項目の順序はユーザーによって任意に管理されます。ユーザーは、アイテムを他のアイテムの間に挿入したり、アイテムを削除したり、移動したりできます。

特定のアイテムが挿入または移動されたときに、他のアイテムの順序付けプロパティが影響を受けないように、順序付けを各アイテムのプロパティとして保存する最良の方法は何ですか? これらのオブジェクトはデータベースに保存されます。

理想的な実装では、無限の数の挿入/再注文をサポートできます。

このアプローチの限界を特定するために私が使用しているテストは次のとおりです。

x、y、z の 3 つのアイテムを使用して、左側のアイテムを繰り返し、他の 2 つのアイテムの間に配置します。次に、右側のオブジェクトを取り、他の 2 つの間に配置します。なんらかの制約に違反するまで続行します。

他の人の参考のために、私が試したいくつかのアルゴリズムを含めました。

4

5 に答える 5

4

1.1。小数、倍精度

順序を 10 進数として格納します。順序が x と y の 2 つのアイテムの間に を挿入するには、その順序を x/2+y/2 として計算します。

制限:

精度、またはパフォーマンス。double を使用すると、分母が大きくなりすぎると、 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) の値を指定します (これは他の 2 つの数値の間にあることが簡単に示されます)。

制限:

精度またはオーバーフロー。

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: 説得力があり、現実的で、証明された、より複雑にする理由が見つかるまでは、IT をシンプルに保ちます。

したがって、DOM が既にそれを行っている場合に、独自の order プロパティを維持するのは余分で不必要なコードとメンテナンスであると私は主張します。DOM に順序を維持させて、必要なときにいつでも現在の順序付けの脳死状態の単純なシーケンス番号のセットを動的に生成できるようにしないのはなぜですか? CPU は、必要なときや変更されたときに、すべてのアイテムの新しいシーケンス番号を生成するのに十分高速です。そして、この新しい順序をサーバーに保存したい場合は、シーケンス全体をサーバーに送信するだけです。

これらの分割シーケンスの 1 つを実装して、何も番号を付け直すことなく常により多くのオブジェクトを挿入できるようにすると、大量のコードが必要になり、バグが発生する可能性が高くなります。そのレベルの複雑さが本当に必要であることが証明されるまで、そこに行くべきではありません.

于 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 に答える