15

ゴール

可能な限り最小限のデータを使用して、静的リストをある順序から別の順序に並べ替える方法を説明するデータをエンコードする方法は?

助けになるアルゴリズムやコンピュータ サイエンスの用語があると感じていますが、今のところ、この問題に固執しすぎて、それを他の方法で見ることができません。

背景の動機

私は、すべての通信が断続的な信じられないほど高価な衛星接続を介して行われる遠隔地に展開されるプログラムを持っています。少し誇張されていますが、データ コストは 1 キロバイトあたり 1 ドルに近く、1 日に数回しか発生しません。

一日の始まりに、ユーザーはアイテムのリストを与えられ、フィールドに出て何かをしますが、最終結果は多かれ少なかれ同じアイテムのリストが異なる順序でソートされます。他にもデータはありますが、この問題にとって重要ではありません。

現在、発生したすべての動きの記録を送り返し、それらを順番に再生しています。ユーザーがシステムに慣れてくると、ムーブ レコードのリストは、すべてのアイテム自体を送り返すだけのサイズに近づき始めており、多くの場合、いくつかのムーブの組み合わせによって前のムーブが元に戻されます。

仮定

  • 開始リストと終了リストは、まったく同じアイテムのセットで構成されています
  • 各アイテムには一意の ID (32 ビット整数) があります
  • 各項目には固有のソート順 (32 ビット整数) があります。
  • ユーザーは、数百から千以上のアイテムのリストを持っています
  • 通常、ユーザーは 1 日に約 100 個のアイテムを再注文します。
  • リスト内の新しい位置にアイテムを移動すると、順序の変更を検出できます
  • 一部の「移動」は前の移動を元に戻す場合があります
  • 最適解を求めるための計算リソースは安価/無制限
  • 転送時間は高価です
  • リスト全体を送り返すよりも、変更データを送り返す方がコストがかからない

最も単純なデータ構造

この問題を解決するために、次のデータ構造が利用可能であると仮定します。

  • ListItem
    • item_id
    • sort_order
  • MoveRecord
    • item_a_id
    • new_a_position

リストの例を次に示します。各リストの項目は同じです。変更されたアイテムはほんのわずかですが、すべてのアイテム ID に新しい並べ替え順序があるため、新しい item_id/sort_order_id ペアを送り返すことはできません。

**List 1: Original List**    **List 2: Re-ordered List**    
order - id                    order - id
     1. 10                         1. 90
     2. 20                         2. 30
     3. 30                         3. 40
     4. 40                         4. 50
     5. 50                         5. 60
     6. 60                         6. 10
     7. 70                         7. 80
     8. 80                         8. 70
     9. 90                         9. 20

可能な限り最小限のデータ量を使用して、リスト 1 の順序をリスト 2 の順序に変換するために必要な変更をエンコードするにはどうすればよいですか?

好奇心として、最適な解決策があることを証明することは可能ですか?

アップデート

同僚は、「スワップ」は正しい考え方ではないかもしれないと指摘しました。リストの一番上または一番下にアイテムを送信することもできます。これは、交換というより移動です。スワップは、2 つの移動の組み合わせになります。

ポインタをありがとう。これまでのところ、保証された最適なソリューションは見当たりません。さらに、問題が少し変わっただけです。

1 つの方法で最良の結果が得られることを証明できない場合は、すべての方法を使用して解決策を見つけ、使用した方法を示す小さなヘッダーを付けてその解決策を返信します。ただし、解決策を提案し続けてください。この質問を私の調査で更新します。

みんな、ありがとう！

4

8 に答える 8

2

アルゴリズム部分:

リストの並べ替えは順列と呼ばれます。各順列は一連のループに分割でき、N 要素の各ループには (N - 1) スワップが必要です。例えば

1、2、3、4、5、6 --> 3、2、4、1、6、5

これは、1 - 4 - 3 (2 回のスワップが必要) 2 - 2 (0 回のスワップ) 5 - 6 (1 回のスワップ) に分割できます。

解決策を見つけるには、間違った位置にある要素を選択して、その場所に配置するだけです。

詳細部分:

もちろん、より小さなデータ型、RLE、その他のエンコード アルゴリズムなどを使用することもできます。

非常に理論的ですが、非実用的な部分です。

N 個の数値のシーケンスのすべての順列は、辞書式に並べることができ、シーケンスを表すには 0 から (N! - 1) までの 1 つの数値で十分です。したがって、理論的には最良の答えは、順列のインデックスを計算し、それを転送し、そのインデックスで順列を再作成することです。

于 2009-10-14T23:10:28.653 に答える
1

スワップを分析して何かが得られるかどうかはわかりません。あなたが言うように、それらは互いに元に戻すことができ、混乱を招く結果につながります。

最良の選択肢は、並べ替えられたリストで、元のリストに対して並べ替えられていないそのリストのセグメントを特定することだと思います。たとえそれらが新しい場所から始まったとしてもです。あなたの例では、これは 30 から 60 までのセグメントです。したがって、一種のランレングス エンコーディングで、位置と長さを記述するセグメント マップを送り返します。

繰り返しますが、サンプルデータを使用します:順序付けられた開始インデックス、長さのリスト:

{ (9, 1) , (3, 4) , (1, 1) , (8, 1) , (7, 1) , (2, 1) }

あなたが送り返すことができる最小量の情報のようです。データの圧縮率は、共通に保持されるセグメントの数とサイズによって異なります。

（編集）実際には、スワップの数が少ない場合、スワップリストが短くなるデータセットがいくつかあると思います。しかし、おそらく、ランレングス エンコーディングのほうが優れているカットオーバー ポイントがいくつかあるでしょう。その場合、両方を計算し、小さい方を選択します。

于 2009-10-14T18:09:26.037 に答える
1

必要なのは、リストをソートするために必要な順列です。これを取得するには、0 から n までのインデックスのリストを作成し、対応するインデックスで項目を比較するカスタム比較関数を使用してそのリストを並べ替えます。たとえば、Python では次のようになります。

perm = sorted(range(len(l)), key=lambda x:l[x])

次に、接続を介して「perm」を送信し、それを使用してソートされたリストを取得できます。

for x in perm:
  print perm[x]

さらなる最適化として、ほとんどの要素が変更されない場合、順列は高度に圧縮可能になります。通常の圧縮を使用するか、差のような変換を使用します (たとえば、各要素を絶対値ではなく、前の要素との差として保存します)。先頭に移動し、長さのエンコードを実行します。

于 2009-10-14T18:11:45.923 に答える
0

Peterが言うように、各整数のサイズを最小化するのが理想的ですが、実際には、アイテムの数に制限を設けることなくそれを行うことができます。可変バイトエンコーディングは、必要なバイト数のみを使用して整数のシーケンスを圧縮する方法です。これを行う最も一般的な方法は、各バイトの1ビットを予約して、そのバイトが現在のリスト項目の最後のバイトであるかどうかを示すことです。

最初にデルタエンコーディングを使用すると便利な場合があります。ここに、整数自体ではなく、整数間の差を格納します。つまり、可変バイトを使用すると、より適切に圧縮されます。もちろん、格納されている整数（おそらく、変更されているアイテムのID）を最初にソートする必要がありますが、それはあなたにとって問題ではないようです。

于 2009-10-17T11:41:37.897 に答える
0

ネットワークを介して送信されるデータのすべてのビットを最小限に抑えようとしている場合、どのようにデータを送信していますか? たとえば、何らかの形で圧縮していますか？アイテムが数千しかない場合、並べ替え順序に 32 ビットの数値を使用するのはおそらくやり過ぎです。16 ビットでは、$$$ の半分で 65000 アイテムを取得できます。固有 ID についても同様です。

于 2009-10-14T18:23:10.870 に答える
0

Zobrist ハッシュを使用して、前の注文に戻るケースを特定することで簡単に解決できる場合があります。つまり、各スワップの後、到達した順列に基づいてハッシュを計算します。各ハッシュは、その特定の順列についてこれまでに見つかったスワップの最短シーケンスにマップされます。

これは、ちょっとした探索的検索で簡単に拡張できます。Zobist ハッシュは、ゲーム ツリー検索を最適化する方法として発明されました。

もちろん、スワップの数に厳密な下限を設定するのは簡単です。必要な場所にないアイテムの数です。ただし、その下限が実際に達成可能かどうかは、より難しい問題です。

于 2009-10-14T18:08:50.633 に答える
0

データ構造を無視する別の可能な解決策...

変更された項目の ID/インデックスのセット (完全にランダムなまばらなサブセットの場合は、それらをリストするだけです) と、そのサブセットの並べ替えを説明する順列番号を送信します。順列数には大きな整数表現が必要です。サイズは log(n!) に比例する必要があります。ここで、n は変更された項目の数です。

もちろん、順列番号は順列配列から定義されますが、この詳細はデコード時に回避できます。秘訣は、正しい最初の項目を最初のスロットにスワップしたら、配列の末尾に正しい新しい順列番号を導出できるように、順列番号をエンコードすることです。

あれは...

while not empty(indexes)
  item-to-swap := permutation-no remainder len(indexes)
  permutation-no := permutation-no div len(indexes)
  if item-to-swap != 0 : swap slot[indexes[0]], slot[indexes[item-to-swap]]
  indexes := tail(indexes)

開始時にすべてのアイテムを変更する必要がある場合でも、!= 0 チェックが必要です。アイテムは、ループの早い段階で正しい位置に上向きにスワップされている可能性があります。

これは、スワップの数を最適化しようとするものではありません。アイテムは、正しい位置に下向きにスワップされる前に、上向きに数回スワップされる場合があります。とはいえ、順列数はおそらく配列のランダム順列の最適空間表現です。順列が完全な配列の小さなサブセットにのみ影響することを考えると、そのサブセットに小さい順列番号を使用することは非常に理にかなっています。

于 2009-10-14T18:37:05.753 に答える
0

仮定して：

  • フィールド デバイスとベース システムの両方で、元のデータと最終データのコピーを保持できます。
  • スワップについて話すとき、リスト内の 2 つの項目が互いに交換されることを意味します。

あなたの最善の解決策はおそらく次のとおりです。

実行したすべてのスワップのリストを保持するのではなく、1 日の終わりに開始データと終了データを比較し、その変更を行うために必要なスワップを生成します。これは、一連のスワップがいくつかの変更を「元に戻す」ために変更されていないだけであっても、リスト内の変更されていない場所を無視します。データが次の形式をとっている場合、a,b,a,b,...whereaは、同じ順序で残す次の要素bのインデックスを示し、それを交換するアイテムのインデックスを示します。

シフトではなくスワップのみを行っているため、30、40、および 50 が同じ順序でわずかに異なる場所にあるサンプル データのようなデータになることはほとんどありません。スワップの数は、リスト内の元の項目の数の 1/4 から 1/10 の間になるため、通常、元のデータと同じ順序と同じ場所に大量のデータが存在することになります。次のスワップが行われたとします。

1 <-> 9
4 <-> 2
5 <-> 2

結果のリストは次のようになります。

 1. 90                   
 2. 50                  
 3. 30                      
 4. 20                       
 5. 40                      
 6. 60                       
 7. 70                       
 8. 80                       
 9. 10

したがって、変更データは次のように表すことができます。

 1,9,2,4,4,5

これは 6 つの値だけであり、16 ビットの数値として表すことができます (最初のリストに 16,000 を超える項目がないことを前提としています)。したがって、各「有効な」スワップは、単一の 32 ビット数で表すことができます。そして、実際のスワップの数は通常、元のリストのサイズの 1/5 から 1/2 になるため、元のリストのデータの 10% から 20% の間のデータをネットワーク経由で送信することになります (またはそれ以下)。 「有効な」スワップの数は、それらのスワップの一部が互いに取り消される場合、さらに少なくなる可能性があります)。

于 2009-10-14T20:06:44.873 に答える