2

シナリオ:

  • 写真のリスト
  • すべての写真には次のプロパティがあります
    • id
    • sequence_number
    • main_photo_bit
  • 最初の写真は にmain_photo_bit設定されてい1ます (他のすべては0)
  • 写真の順序はsequence_number(任意です)
  • メインの写真が必ずしも最低であるとは限りませんsequence_number（ソート前）

次の表を参照してください。

id, sequence_number, main_photo_bit
1   10               1             
2    5               0             
3   20               0

次に、シーケンス番号とメインの写真ビットを変更して順序を変更します。

ソート後の要件:

  • 最初のsequence_number写真の は変更されていません
  • 最初のsequence_number写真のが一番低いです
  • できるだけ変化を少なく

例:

例 #1 (2 番目の写真が最初の位置に移動):

id, sequence_number, main_photo_bit
2   10               1             
1   15               0             
3   20               0

これが起こったことです：

  • id 1: 新規sequence_numberおよびにmain_photo_bit設定0
  • id 2: 古い最初の写真 (id 2)sequence_numberにmain_photo_bit設定1
  • id 3: 何も起こらない

例 #2 (3 番目の写真から 1 番目の位置へ):

id, sequence_number, main_photo_bit
3   10               1             
1   20               0             
2   30               0

これが起こったことです：

  • id 1: 新しいsequence_number写真は最初の写真よりもmain_photo_bit大きい0
  • id 2:sequence_number新しく生成された秒より大きい新しいsequence_number
  • id 3: 古い最初の写真sequence_numberとにmain_photo_bit設定1

新しい注文を保存するために必要な手順を計算するための最良の方法は何ですか?

編集:
更新をできるだけ少なくしたい理由は、外部サービスと同期したいからです。これは非常にコストのかかる操作です。
私はすでにアルゴリズムの実用的なプロトタイプを手に入れましたが、いくつかのエッジケースで失敗します. したがって、パッチを適用する代わりに (これは機能する可能性がありますが、これまでよりもさらに複雑になります)、他の (より良い) 方法があるかどうかを知りたいです。
私のバージョン (要するに) では、写真を並べ替え ( を変更sequence_number)、 を交換しますmain_photo_bitが、すべてのシナリオを解決するには十分ではありません。

4

2 に答える 2

3

私が理解したことから、良い解決策は変更を最小限に抑えるだけでなく (更新はコストのかかる操作であるため)、将来の変更 を最小限に抑えることも試みます。dirty行を変更する必要があるかどうかを示すために、一時的なフィールドを追加することから始めます。

id, sequence_number, main_photo_bit, dirty
 1         10               1        false
 2          5               0        false
 3         20               0        false
 4         30               0        false
 5         31               0        false
 6         33               0        false

最初の行よりも小さい行がある場合はsequence_number、必ず変更する必要があります (より大きな数を取得するか、最初になるようにするため)。それらを次のようにマークしましょうdirty：

id, sequence_number, main_photo_bit, dirty
 2          5               0        true

(最初の が最も低いことが重要でない場合は、この手順をスキップしてくださいsequence_number)

結果にあるはずの写真のリストを見てみましょう（質問によると、どこからでもどこでも場所が変わったのは1枚の写真だけです）。太字の汚いもの：

[1, 2 , 3, 4, 5, 6] # 元の順序

[ 2 , 1 , 3, 4, 5, 6] # 例1: 2位から1位

[ 3 , 1 , 2 , 4, 5, 6] # 例 2: 3 位から 1 位

[1, 2 , 4, 3 , 5, 6] # 例 3: 3 位から 4 位

[1, 3 , 2 , 4, 5, 6] # 例 4: 3 位から 2 位

最初に行うことは、最初の要素の が最低であることを確認することですsequence_number。場所が変更されていない場合は、定義上変更されています。そうでない場合、古い最初のものはダーティとしてマークされ、main_photo_bitクリアされ、新しいものはそれらの値をそれ自体に受け取る必要があります。

この時点で、最初の要素には固定された が必要sequence_numberであり、すべてのダーティ要素の値は自由に変更できます (とにかく変更する必要があるため、有用な値に変更することをお勧めします)。続行する前に、ダーティな行を変更するだけで問題を解決できること、またはさらに多くの行もダーティにする必要があるかどうかを確認する必要があります。これは単純に、クリーンな行のすべてのペア間の間隔が、それらの間のダーティな行の数に適合するのに十分な大きさであるかどうかを判断する問題です。

[10, D, 20, 30, 31, 33]   # Original ordering (the first is dirty, but fixed)

[10, D, 20, 30, 31, 33]   # Example 1: 2nd to 1st place (ok: 10 < ? < 20)
[10, D, D, 30, 31, 33]    # Example 2: 3rd to 1st place (ok: 10 < ? < ? < 30)
[10, D, 30, D, 31, 33]    # Example 3: 3rd to 4th place (NOT OK: 30 < ? < 31)
  [10, D, 30, D, D, 33]   #   must mark 5th as dirty too (ok: 30 < ? < ? < 33)
[10, D, D, 30, 31, 33]    # Example 4: 3rd to 2nd place (ok)

sequence_numberこれで、ダーティな行に新しい s を割り当てるだけです。単純な解決策は、前のものをインクリメントすることですが、より良いアプローチは、それらをできるだけ等間隔に設定することです。sequence_numberこのようにすると、将来の並べ替えで必要な変更が少なくなる可能性が高くなります (つまり、例 3 のように、いくつかの が互いに近すぎて必要以上の行を更新しなければならないという問題を回避するため)。

[ 10 , 15 , 20, 30, 31, 33] # 例1: 2位から1位

[ 10 , 16 , 23 , 30, 31, 33 ] # 例 2: 3 位から 1 位

[10, 20 , 30, 31 , 32 , 33] # 例 3: 3 位から 4 位

[10, 16 , 23 , 30, 31, 33] # 例 4: 3 位から 2 位

ボーナス:本当にソリューションを限界まで押し上げたい場合は、計算を 2 回行います。例 3A を見てみましょう。ここでは、「3 位から 4 位」ではなく、「4 位から 3 位」として扱います (ソート結果は同じですが、変更が異なります)。

[1, 2 , 4 , 3, 5, 6] # 例 3A: 4 位から 3 位

[10, D, D, 20, 31, 33] # (ok: 10 < ? < ? < 20)

[10, 13 , 16 , 20, 31, 33] # 1 つ少ない変更

ほとんどの場合、それを行うことができます (例: 2 番目から 4 番目の位置 == 3 番目/4 番目から 2 番目/3 番目の位置)。

于 2012-10-26T08:09:33.160 に答える
1

シーケンス番号の代わりにリンク リストを使用します。次に、リスト内の任意の場所から画像を削除して、リスト内の任意の場所に再挿入できます。データベース ファイルの 3 行を変更するだけで済みます。メインの写真ビットは不要である必要があります。最初の写真は、それへのポインターを持たないことによって暗黙的に定義されます。

id      next
1       3
2       1
3

順序は次のとおりです。2、1、3

ユーザーは画像 3 を位置 1 に移動します。

id      next
1       
2       1
3       2

新しい順序は: 3, 2, 1

于 2012-11-01T10:13:44.757 に答える