3

私たちのチームは、モバイルプラットフォーム用のテーブルウィジェットの実装に取り​​組んでいます（アプリケーションの1つは、MS Excelのようなモバイルオフィスです）。

テーブルデータを格納するためのデータ構造を最適化する必要があります（単純な2次元配列が使用されます）。

テーブルデータを保存するための最適なデータ構造を提案してください。以下は、データ構造の要件の一部です。

  • テーブルのサイズは最大2^32 x 2^32です。
  • テーブルセルの大部分は空です（つまり、テーブルはまばらです）。したがって、空のセルのデータを保存しないことが望ましいです。
  • データ構造のインターフェースは、行と列の挿入/削除をサポートする必要があります。
  • データ構造は、空でないセルを順方向および逆方向に反復できるようにする必要があります。
  • テーブルのセルを結合できます（つまり、1つのセルが複数の行や列にまたがることができます）。
4

2 に答える 2

2

行/列の挿入/削除の問題についてさらに考えた後、有望に見えるものを思いつきました。

最初に、少なくとも 1 つの空でないセルを持つ、すべての水平インデックスとすべての垂直インデックスを含む 2 つの並べ替えられたデータ構造 (検索ツリーなど) を作成して維持します。

このテーブルの場合:

 ABCDE
1
2*
3 %  #
4
5   $

あなたが持っているでしょう：

  1. A、B、D、E - 水平インデックスを使用
  2. 2,3,5 - 垂直インデックスを使用

これらの A、B、D、E、2、3、5 インデックス値を、前述の 2 つの構造のある種のノード内に格納して、メモリ内のノードのアドレスを知って何かをリンクできるようにします (ここでも、ツリー ノードは完全に適合します)。 ）。

各セル (空でない) には、その場所を説明するインデックス ノードへのリンクのペアがあります (ノードへのリンク/参照を示すために & を使用しています)。

  • *: &2,&A
  • %: &3,&B
  • #: &3,&E
  • $: &5,&D

テーブルを定義するにはこれで十分です。

では、行/列の挿入をどのように処理するのでしょうか? 新しい行/列インデックスをそれぞれの (水平または垂直) インデックス データ構造に挿入し、その後 (= 右または下) にインデックス値を更新します。次に、この新しい行/列 (存在する場合) に新しいセルを追加し、それらを適切なインデックス ノードにリンクします。

たとえば、行 3 と行 4 の間に行を挿入し、@ を含むセルを 4C (新しい行) に追加します。

 ABCDE
1
2*
3 %  #
4  @   <- new row 4
5      <- used to be row 4
6   $  <- used to be row 5

インデックス構造は次のようになります。

  1. A,B,C(new),D,E - 横方向のインデックスを使用
  2. 2,3,4(新規),6(以前は 5) - 垂直インデックスを使用

セルは、次のようにインデックス ノードにリンクされます。

  • *: &2,&A - 前と同じ
  • %: &3,&B - 前と同じ
  • #: &3,&E - 前と同じ
  • @: &4,&C - 新しいインデックス ノード 4 および C にリンクする新しいセル
  • $: &6,&D - 以前は &5,&D

しかし、$ セルを見てください。以前と同じ 2 つの物理ノードを指していますが、垂直/行ノードにインデックス 5 ではなくインデックス 6 が含まれているだけです。

$ セルの下に 100 個のセル ノードがある場合、たとえば空でない 5 行のみを占めている場合、100 ではなく、行/垂直インデックス データ構造の 5 つのインデックスのみを更新する必要があります。

同様の方法で行と列を削除できます。

さて、これを便利にするには、すべてのセルをその座標で見つけられるようにする必要もあります。

そのために、すべてのキーがインデックス ノードのアドレスの組み合わせであり、値がセル データ (またはセル データ自体) の場所である、別の並べ替えられたデータ構造 (これもおそらく検索ツリー) を作成できます。

これで、セル 3B に到達したい場合は、インデックス データ構造で 3 と B のノードを見つけ、それらのアドレス &3 と &B を取得し、それらを &3*2 32 +&B に結合し、それを検索キーとして使用します。先ほど定義した 3 番目のデータ構造の % セル。(注: 2 32は、実際にはビット単位の 2 ポインター サイズであり、システムによって異なる場合があります。)

他のセルに何が起こっても、% セルのインデックスが 3B から別のものに変わっても、% のセル リンクのアドレス &3 と &B は変わりません。

これに基づいて反復を簡単に開発できます。

マージも実行可能なはずですが、私はそれに集中していません。

于 2012-10-24T11:14:58.570 に答える
0

Excel の場合と同様に、キーと値のペアを保存することをお勧めします。たとえば、Excel ドキュメントに A ～ AA などの列があり、1 ～ 256000 行などがあるとします。キーと値のペアのような日付を持つ値を格納するだけです。

例えば：

someKeyValueStore = new KeyValueStore();

someData = new Cell(A1,"SomeValue");

someOtherData = new Cell(C2,"SomeOtherValue");

someKeyValueStore.AddKeyValuePair(someData);
someKeyValueStore.AddKeyValuePair(someOtherData);

この場合、空のセルを気にする必要はまったくありません。空でないものにアクセスできます。もちろん、特定のキーに値があるかどうかを簡単に確認できるように、コレクション内のキーを追跡したいと思うでしょう。しかし、それは本質的にそれを処理する最も簡単な方法です。

于 2012-10-24T08:25:58.130 に答える