data-structures - 効率的なExcelのようなアプリを実装する方法

Question

効率的なExcelのようなアプリを実装する必要があります。次のようなデータ構造を探しています。

• 効率的な方法でデータを保存します（たとえば、未使用のセルにメモリを事前に割り当てたくありません）。
• ユーザーがセルの1つで数式を変更したときに、効率的な更新を許可する

何か案は？

ありがとう、李

Answer 1

この場合、あなたはオンライン辞書構造を探しています。これは、1つのデータ（この場合はセルを表す座標）を別のデータ（この場合はセルの内容または数式）に関連付けることができる構造のカテゴリです。「オンライン」形容詞は、辞書エントリをリアルタイムで追加、削除、または変更できることを意味します。

そのような構造はたくさんあります。いくつかのより一般的なものに名前を付けるために：ハッシュテーブル、バイナリツリー、スキップリスト、リンクリスト、さらには配列内のリスト。

もちろん、これらのいくつかは他のものより効率的です（実装とエントリの数によって異なります）。通常、私はこの種の問題にハッシュテーブルを使用します。

ただし、「この範囲内のすべてのセルを変更する」範囲クエリを実行する必要がある場合は、バイナリツリーまたはより複雑な空間構造を使用する方がよい場合がありますが、問題の単純な要件を考慮すると、おそらくそうではありません。