3

我在一次采访中被问到以下问题，我无法解决任何对此的指示将非常有帮助。

我有 100 个文件，每个文件大小为 10 MB，每个文件的内容都是一些字符串映射到整数值。

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 的树。我们将这两棵树保存到磁盘中。为了跟踪我们的树，我们保留了一组树及其名称/位置以及它们的第一个和最后一个属性的名称。从现在开始，对于文件 N 中的每一行，我们使用我们的列表来定位合适的树以将其插入，将该树加载到内存中，并执行必要的操作。我们继续这个过程，直到我们到达终点。

使用这种方法，加载到内存中的最大数据量将不超过 25 mb。总是有一个文件N被加载（10mb），一个树加载（最多10mb）和一个树的数组/列表（希望不会超过5mb）。

稍微严谨一点的算法：

  1. 初始化一个已排序的二叉树B，其条目是一个(key, value)元组，根据条目的属性进行排序，key并具有name, size, first_key, last_key其中name一些任意唯一字符串和size字节大小的属性。

  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 回答