6

ときどき、ユーザーが手動で並べ替えることができる要素のリストを処理する必要があります。

ほとんどの場合、順序に依存するコンテナーを使用するモデルに依存しようとしますが、これが常に可能であるとは限らず、データに位置フィールドを追加する必要があります。この位置フィールドは double 型であるため、常に 2 つの数値間の位置を計算できます。ただし、これは理想的ではありません。これは、2 つの数値の間に挿入を続けるのに十分な数値精度がないエッジ ケースに到達することを懸念しているためです。

ポジション番号を維持するための最善の方法について疑問があります。最初の考えは、すべての行をトラバースし、挿入ごとにラウンド番号を与えることです。次のようにします。

2 と 3 の間の行を削除した直後:

1   2   2.5   3   4    5

位置番号の更新後:

1   2   3     4   5    6

もちろん、エントリ数が多いと重くなる可能性があります。特にメモリ内ではなく、すべての新しい値をディスク/データベースに保存します。私は通常、ある種の ORM とモバイル ソフトウェアを扱っています。すべてのコードを更新すると、すべてのオブジェクトがディスクから取り出され、ダーティとして設定され、データ モデルの関連するすべての検証ルールが再検証されます。

2 つの位置の間の数値を計算するのに十分な精度が得られなくなるまで待つこともできます。ただし、同じ操作に同じ時間を必要としないため、ユーザー エクスペリエンスは低下します。

これらのケースには、位置番号を定期的かつ一貫して更新する標準アルゴリズム、またはそれらの一部だけがあると思います。理想的には、最悪のケースと最良のケースの間に大きな時間差がなく、O(log n) である必要があります。

正直なところ、ユーザー/ソートする必要があるものは、最悪の場合に実際の問題になるほど大きくなることはないと思います。エッジケースも非常にまれであるように思われ、境界番号をプッシュするソリューションを検索するとなおさらです。ただし、この問題には、私が気付いていない標準的なよく知られた解決策があると今でも信じており、それについて学びたいと思っています。

4

4 に答える 4

4

2 回目の試行。

position0 -> 1000 など、値の全範囲を考慮してください。

最初に挿入する項目の位置は 500 にする必要があります。リストは次のようになります。

(0) -> 500 -> (1000).

最初の位置に別のアイテムを挿入すると、次のようになります。

(0) -> 250 -> 500 -> (1000).

最初の位置にアイテムを挿入し続けると、問題が発生します。範囲が均等にバランスが取れておらず、... 待って...バランスが取れていますか? 二分木問題みたいじゃないですか!?

基本的に、リストを二分木として保存します。ノードを挿入するときは、周囲のノードに従って位置を割り当てます。ツリーのバランスが崩れると、ノードを回転させてバランスを取り直し、回転したノードの位置を再計算します。

そう ：

  • ほとんどの場合、ノードを追加しても他のノードの位置を変更する必要はありません。
  • バランス調整が必要な場合、アイテムのサブセットのみが変更されます。
  • O(log n)です！

編集

アルゴリズムの説明

于 2012-12-14T09:16:02.753 に答える
0

有効な答えがない数日後。これは私の理論です：

ここでの本当の課題は、実際的な解決策です。数学的に正しい解決策があるかもしれませんが、毎日のように、実装は非常に複雑になるようです。優れたソリューションは、数学的に正しいだけでなく、問題の性質、問題に遭遇する可能性が低いこと、およびその小さな意味とのバランスが取れている必要があります。非常に効果的ですが、弾丸でハエを殺すのはどれほど役に立たないかのように。

私は良い答えが得られると信じ始めています.正しい解決策で地獄に行き、1行の計算のように残して、2つの要素のソートが失敗する可能性があるまれなケースに対処してください. データに損傷を与えず、一時的な UX の不具合だけを引き起こす非常にまれな細かい問題に、複雑さを増して時間やお金を投資する価値はありません。

于 2012-12-17T16:07:25.953 に答える
0

ユーザーが実際にリストを手動でソートしている場合、新しい順序を記録するためにO( n ) を取得することについて心配する必要は本当にありますか? いずれにせよ、リストをユーザーに表示するためだけにO( n ) です。

于 2012-12-14T08:12:22.370 に答える
0

これは実際には質問に答えませんが...

「データに位置フィールドを追加する」と話したように、データ ストアはリレーショナル データベースであり、データには何らかの識別子があると思います。

そのため、データにandを追加することで、双方向リンク リストを実装できるかもしれません。したがって、挿入/移動/削除操作はO(1)です。previous_data_idnext_data_id

このようなコレクションをデータベースからロードするのはかなり簡単です:

  • 各アイテムを取得し、ID をキーとしてマップに追加します。
  • 各項目について、それを前の項目と次の項目に接続します。
  • 最初の項目 ( は未定義) から始めてprevious_data_id、チェーンをたどってリストに追加します。
于 2012-12-14T08:15:02.450 に答える