2

我正在编写一个程序，它需要我创建一个包含一百万条记录的数组。数组索引是唯一的 id（0-million 代表唯一的产品 id）。首先，所有元素都初始化为零。它们根据销售的产品而增加。

然而，这种方法具有很高的空间复杂度（4 * 百万字节）。后来我看到只有某些产品需要频繁更新。那么有什么方法可以减少内存使用并跟踪所有产品？

4

4 回答 4

1

This sounds more like a situation for table in a database than an in-memory array to me. If your use case allows for it, I'd use a database instead.

Otherwise, if in your use case:

  1. a significant fraction of the products will eventually be used,
  2. RAM is limited,
  3. external storage (disk, serial memory) is available,
  4. average access performance comparable to RAM speeds is required, and
  5. increased worst case access time is acceptable,

then you could try some sort of caching scheme (lru maybe?). This will use more code space, somewhat increase your average access time, and more significantly increase your worst case access time.

If a large fraction of the products will not just be infrequently, but never used, then you should look into @fatrock92's suggestion of a hash table.

于 2012-09-02T17:04:08.923 回答
1

如果您不需要频繁更新，则可以将所有结果存储在一个文件中。每当您更新任何条目时，您都可以创建一个临时文件，其中包含所有其他条目以及更新的条目。之后，您可以使用更改临时文件的名称rename(temp,new);。

虽然，一百万条记录的数组不需要那么多内存（只需 4 兆字节）。因此，您的方法是最好和最简单的方法。

最好的方法（算法）是制作一个哈希表来存储所有条目。但是，如果您不是 C 方面的专家，那么制作哈希表对您来说可能是个问题。

于 2012-09-02T16:58:06.310 回答
0

You can use link list, so whenever you need you can add or update elements in your list.
Also you can hold last time access in each node so you'd able to remove the nodes that has not been used lately.

于 2012-09-02T17:09:13.423 回答
0

最好为数组使用动态分配内存。使用 malloc 或 realloc 可以为您提供更好的内存分配方式 我想您知道如何使用 malloc 和 realloc

于 2012-09-02T16:59:55.483 回答