3

面接で次の質問をされましたが、これに対する指針を解決できませんでした。非常に参考になります。

それぞれサイズが 10 MB のファイルが 100 個あります。各ファイルの内容は、整数値への文字列マッピングです。

string_key=整数値

 a=5
 ba=7
 cab=10 etc..

利用可能な物理 RAM スペースは 25 MB です。次のようにデータ構造をどのように設計しますか。

For any duplicate string_key, the integer values can be added
Display the string_key=integer value sorted in a alphabetical format

制約 :

All the entries of a file could be unique. All of the 10*1000MB of data could be unique string_key mapping to an integer value.

解決策 1 :

各ファイルを次々にロードしてハッシュマップに情報を格納しようと考えていましたが、このハッシュマップは非常に巨大であり、すべてのファイルに一意のデータが含まれていると RAM に十分なメモリがありません。

他のアイデアはありますか？

noSqldb の使用はオプションではありません。

4

1 に答える 1

2

これが私の突き刺しです。基本的には、一連の小さなバイナリ ツリーを使用して並べ替えられたデータを保持し、それらをその場で作成してディスクに保存してメモリを節約し、リンク リストを使用してツリー自体を並べ替えるというものです。

手を振るバージョン:

エントリのキーに基づいてアルファベット順に並べ替えられた二分木を作成します。各エントリにはキーと値があります。各ツリーには、属性として最初と最後のキーの名前があります。各ファイルを個別にロードし、行ごとにエントリをツリーに挿入すると、自動的にソートされます。ツリーのコンテンツのサイズが 10 mb に達すると、ツリーをそれぞれ 5 mb の 2 つのツリーに分割します。これら 2 つのツリーをディスクに保存します。ツリーを追跡するために、ツリーの配列とその名前/場所、および最初と最後の属性の名前を保持します。これ以降、fileN の各行について、リストを使用して適切なツリーを見つけて挿入し、そのツリーをメモリにロードして、必要な操作を実行します。最後に到達するまで、このプロセスを続けます。

この方法では、メモリにロードされるデータの最大量は 25 MB 以下になります。読み込まれる fileN (10mb)、読み込まれるツリー (最大 10mb)、およびツリーの配列/リスト (できれば 5mb を超えないこと) が常に存在します。

もう少し厳密なアルゴリズム:

  1. Bエントリがタプルで、エントリのプロパティに(key, value)基づいて並べ替えられ、任意の一意の文字列とバイト単位のサイズであるプロパティkeyを持つ、並べ替えられたバイナリ ツリーを初期化します。name, size, first_key, last_keynamesize

  2. エントリがエントリのプロパティに基づいて並べ替えられLた形式のタプルである、並べ替えられたリンク リストを初期化します。これは私たちの木のリストです。にタプルを追加します。(tree_name, first_key)first_key(B.name, B.first_key)L

  3. ファイルに名前が付けられていると仮定するfile1, file2, ..., file100と、たまたま python によく似た疑似コードで記述された次のアルゴリズムに進みます。(ここで使用する宣言されていない関数が自明であることを願っています)

    for i in [1..100]:
    f = open("file" + i)   # 10 mb into memory
    for line in file:
        (key, value) = separate_line(line)

        if key < B.first_key or key > B.last_key:
            B = find_correct_tree(L, key)

        if key.size + value.size + B.size > 10MB:
            (A, B) = B.split()     # supp A is assigned a random name and B keeps its name
            L.add(A.name, A.first_key)
            if key < B.first_key:
                save_to_disk(B)
                B = A      # 5 mb out of memory
            else:
                save_to_disk(A)

        B.add(key)
save_to_disk(B)

次に、リストを繰り返し処理し、関連する各ツリーを出力します。

    for (tree_name, _) in L:
        load_from_disk(tree_name).print_in_order()

これはやや不完全です。たとえば、これを機能させるには、変更Lのたびにリストを継続的に更新する必要があります。first_keyそして、これが数学的に 25 mb を使用することを厳密に証明していません。しかし、私の直感は、これがうまくいく可能性が高いことを教えてくれます. 並べ替えられたリンク リスト (ハッシュ テーブルなど) を保持するよりも、ツリーを並べ替えるより効率的な方法もおそらくあります。

于 2013-08-09T19:14:10.643 に答える