0

問題は、巨大なエクセルシートを扱えるデータ構造を考え出すことです（このままでは明らかにメインメモリに収まりません）

e が空のセルを表す Excel シートの一部として次を想像してください。

  A B C D ...

1 3 9 e e ...

2 e e e e ...

3 e e 5 e ...

4 e e e e ...

5 e e 6 e ...

したがって、データ構造により、Excel シートをメモリに保存できるようになり (Excel シートの値のみがメイン メモリに収まることがわかっています)、次の操作をサポートする必要があります。

getByColumn(Column col);- 特定の列のすべての値を返します。たとえば、列 C の場合は 5,6 です。

getByRow(Row row);- 特定の行のすべての値、たとえば 3 と 9 などを ROW 1 に与える

insertCell(Column col, Row row, int value);- セルの値を挿入または上書きします

getExcelSheet(FileName);- Excel シート全体を圧縮形式 (データ構造) で提供します。

このための考えられるデータ構造は何ですか? 面接の準備をしていますが、これは宿題ではありません。さまざまな人々からいくつかの洞察を得たいと思います。

感覚的に言うと、Excel シートが 1 テラバイトで、8 GB のメモリがあるとします。1 テラバイトの Excel シートには空のセルがたくさんありますが、値はさまざまなセル全体に広がっています

4

4 に答える 4

1

タスのコメントとマークの回答の詳細（+1）：

ウィキペディアが Dictionary Of Keys または DOK と呼んでいるもの (これは本質的に Jens の答えです) を使用すると、セル値を効率的に挿入できますが、正しくコメントしているように、getByRow と getByColumn はかなり遅くなります。

より良いオプションは、wikipedia が Coordinate List または COO と呼んでいるものです: トリプルのセット (rowindex、columnindex、value) です。実際には、これを 3 つの配列として格納することになるでしょう。挿入を高速化するには、並べ替えられたエントリと並べ替えられていないエントリのセットを保持し、並べ替えられていないセットに挿入します。並べ替えられていないエントリの数がしきい値 T (空でないセルの総数 K に依存する可能性があります) を超えるたびに、それらを並べ替えられたセットに並べ替えます。

それらをすべて行インデックスで並べ替え、インデックスを持つ別の配列を配列に保持して、列インデックスで並べ替えられたバージョンを提供する必要があります。

getByRow の場合、行インデックスでソートされた配列の正しいセクションを取得し、さらにソートされていないセットを検索します。

これはすべて、マトリックス内の空でないエントリごとにいくつかの単語を格納するのに十分なメモリがあることを前提としています。そうでない場合は、これをある種の外部メモリ アプローチと組み合わせる必要があります。

于 2012-10-01T16:53:07.347 に答える
1

セル座標を値にマッピングする Map/Dictionary を使用し、明示的に設定されていないものすべてに対して EMPTY_CELL のデフォルト値を返します。

それに基づいて目的のメソッドを実装します。

于 2012-10-01T05:20:44.310 に答える
1

巨大な Excel シートと呼ばれるものに対して広く使用されている用語である疎行列のトピックに関する広範な文献があります。文献は、データ構造と、それらを作成および変更するための適切なアルゴリズムの両方をカバーしています。ウィキペディアの記事は、調査の出発点として適しています。面接の準備をするのに十分なことを教えてくれるかもしれません。

于 2012-10-01T09:03:12.963 に答える
-2

この魔法の Excel シートを 2 次元配列に格納し、空のセルに null を格納することができます。データがそれに収まらない場合は、運が悪いと思います

于 2012-10-01T05:23:35.377 に答える