0

次の表を考えます。

|A|B|C|
|0|0|1|
|1|0|3|
|1|1|1|
|1|2|1|
|1|3|1|
|1|4|2|
|2|5|1|

A と B が与えられたときに C を決定できる、最も効率的なアルゴリズムとストレージ形式を考え出す必要があります。

                +-----------+
                |   BLACK   |
A = 0, B = 0 -> |    BOX    | -> 1
                +-----------+


                +-----------+
                |   BLACK   |
A = 1, B = 4 -> |    BOX    | -> 2
                +-----------+

アルゴリズムは、メモリと効率の間の適切なトレードオフを提供する必要があります。私の最初の試みは、A と B からハッシュを作成し、それをマップのキーとして使用することでした。

{
    "0.0": 1,
    "1.0": 3,
    "1.1": 1,
    "1.2": 1,
    "1.3": 1,
    "1.4": 2,
    "2.5": 1
}

しかし、それが最善のアプローチであるとは思えません(このようなマップに割り当てられたメモリと、このテーブルには数千の行が含まれる可能性があるため、ルックアップ時間に関して)。

誰かがより良い解決策を教えてもらえますか?

4

1 に答える 1

1

ハッシュ テーブルは、数千行であっても、これにアプローチするための完全に合理的な方法のように思えます。どの言語を使用していますか? あなたのテーブルの大きさと、最初の試みのパフォーマンスはどうでしたか?

データに使用できるパターンはありますか? A、B、C の可能な範囲は?

より多くのデータが必要です。

[これは回答ではなくコメントですが、コメントを投稿するには評判が不十分なようです。]

ネストされた配列のアイデアの例を含めるように更新します。

var table = [];

function add_entry (A, B, C) {
  if (!table[A])
    table[A] = []; // create if it doesn't already exist
  table[A][B] = C;
}

function retrieve_entry (A,B) {
  return table[A][B];
}

これにより、次のような構造が生成されます。

table = [
  [ 1 ],
  [ 3, 1, 1, 1, 2 ],
  [ undefined, undefined, undefined, undefined, undefined, 1 ]
];

標準の JavaScript 配列は、変装した単なるオブジェクトであり、まばらさを適切に処理します。A が変化しても B が一様に増加する部分を見逃したので (B は毎回ゼロから始まると思っていました)、型付き配列を使用する場合は、(型付き配列、オフセット) ペアを明示的に格納する必要があります。また、事前にサイズを計算する必要があります。これは少し厄介かもしれませんが、完全に実行できるはずです。B 値あたりの C 値の数に大きく依存して、より効率的であることが判明する場合とそうでない場合があります。

于 2013-05-16T08:13:05.317 に答える