2

我正在研究 C++ 并使用 multimap 来存储数据。

 struct data
 {
      char* value1;
      char* value2;

      data(char* _value1, char* _value2)
      {
           int len1 = strlen(_value1);
           value1 = new char[len1+1];
           strcpy(value1,_value1);

           int len2 = strlen(_value2);
           value2 = new char[len2+2];
           strcpy(value2,_value2);
      }
      ~data()
      {
           delete[] value1;
           delete[] value2;
      }
 }

 struct ltstr
 {
     bool operator()(const char* s1, const char* s2) const
     {
          return strcmp(s1, s2) < 0;
     }
 };


 multimap <char*, data*, ltstr> m;

样本输入：

  Key               Value
  ABCD123456        Data_Mining Indent Test Fast Might Must Favor List Myself Janki Jyoti Sepal Petal Catel Katlina Katrina Tesing Must Motor blah blah.
  ABCD123456        Datfassaa_Minifasfngf Indesfsant Tfdasest Fast Might Must Favor List My\\fsad\\\self Jfasfsa Katrifasdna Tesinfasfg Must Motor blah blah.
  tretD152456       fasdfa fasfsaDfasdfsafata_Mafsfining Infdsdent Tdfsest Fast Might Must Favor List Myself Janki

输入中有 2700 万个条目。输入大小 = 14GB

但我注意到内存消耗达到 56 GB。我可以知道如何减少内存大小吗？

4

6 回答 6

4

如果您无法减少实际存储的数据量，您可能想尝试使用开销较小的不同容器（map 和 multimap 有很多），或者找到一种方法只保留部分数据记忆。

您可能想看看这些库：

于 2013-02-15T16:38:13.800 回答
3

一种可能性是使用 astd::map<char *, std::vector<data> >而不是 multimap。在多重映射中，您将密钥字符串存储在每个条目中。使用地图，您将只有一个密钥字符串的副本，并附有多个data项目。

于 2013-02-15T17:02:13.717 回答
2

第一个优化是存储data对象而不是指针

std::multimap <char*, data, ltstr> m;

因为 usingdata*为分配增加了额外的内存开销。

另一种是使用池分配器/内存池来减少动态内存分配的占用空间。

如果您有许多相同的密钥字符串，您也可以改进它，如果您可以重复使用这些密钥。

于 2013-02-15T16:47:15.960 回答
2

我仍然不完全确定这里发生了什么，但似乎内存开销至少是问题的一部分。但是，总体内存消耗大约是结构所需的 4 倍data。如果有 27M 条记录占用 14GB，则每条记录大约有 500 字节，但占用的空间为 56GB。对我来说，这表明存储的数据比我们这里显示的要多，或者至少有一些数据被存储了不止一次。

而且“堆存储的额外数据”并没有真正为我做。在 linux 中，内存分配至少需要大约 32 个字节的数据。16 字节的开销，而自己分配的内存占用了 16 字节的倍数。

因此，对于data *存储在 multimap 中的一条记录，我们需要：

 16 bytes of header for the memory allocation
 8 bytes for pointer of `value1`
 8 bytes for pointer of `value2`
 16 bytes of header for the string in value1
 16 bytes of header for the string in value2
 8 bytes (on average) "size rounding" for string in value 1
 8 bytes (on average) "size rounding" for string in value 2

 ?? bytes from the file. (X)

 80 + X bytes total.

然后我们char *在多图中：

 16 bytes of header for the memory allocation. 
 8 bytes of rounding on average. 

 ?? bytes from the file. (Y)

 24 + Y bytes total.

多重映射的每个节点都有两个指针（我假设它是某种二叉树）：

 16 bytes of header for the memory allocation of the node. 
 8 bytes of pointer to "left"
 8 bytes of pointer to "right"

 32 bytes total.

因此，这使得文件中的每个条目产生 136 个字节的“开销”。对于 2700 万条记录，也就是刚刚超过 4GB。

正如我所说，该文件每个条目包含 500 个字节，因此为 14GB。

总共有 18GB。

所以，在某个地方，有些东西要么泄漏，要么数学错误。我在这里的计算可能不正确，但即使上面的所有内容都占用了我计算出的两倍空间，仍然有 20GB 下落不明。

我们当然可以做一些事情来节省内存：

1）不要在data. 先计算两个长度，分配一块内存，然后紧接着存储字符串：

  data(char* _value1, char* _value2)
  {
       int len1 = strlen(_value1);
       int len2 = strlen(_value2);
       value1 = new char[len1 + len2 +2];
       strcpy(value1,_value1);

       value2 = value1 + len1 + 1; 
       strcpy(value2,_value2);
  }

这将平均为每个条目节省 24 个字节。我们可以通过巧妙地一次性为数据、value1 和 value2 分配内存来节省更多。但这可能有点“太聪明了”。

2) 分配一大块data物品，一次分发一个，也会有所帮助。为此，我们需要一个空的构造函数和一个“setvalues”方法：

struct data
{
    ...
    data() {};
    ... 
    set_values(char* _value1, char* _value2)
    {
         int len1 = strlen(_value1);
         int len2 = strlen(_value2);
         value1 = new char[len1 + len2 +2];
         strcpy(value1,_value1);

         value2 = value1 + len1 + 1; 
         strcpy(value2,_value2);
    }
}

std::string v1[100], v2[100], key[100];

for(i = 0; i < 100; i++)
{
    if (!read_line_from_file(key[i], v1[i], v2[i]))
    {
        break;
    }
}    

data* data_block = new data[i]; 

for(j = 0; j < i; j++)
{
    data_block[j].setValues[v1[j].c_str(), v2[j].c_str());
    m.insert(key[i].c_str(), &data_block[j]);
}

同样，这不会节省大量内存，但每个 16 字节区域可以节省一些内存。以上当然不是完整的代码，更多的是“如何完成的说明”。

3）我仍然不确定多重映射中的“键”来自哪里，但是如果键是 value1 和 value2 条目之一，那么您可以重用其中一个，而不是存储另一个副本[假设是这样目前完成]。

如果这不是一个真实的答案，我很抱歉，但我确实相信这是一个答案，即“在某个地方，在你对你正在做的事情的解释中，有些东西是下落不明的”。

了解您的程序中进行了哪些分配肯定会有所帮助。

于 2013-02-16T07:46:33.323 回答
2

在没有看到一些数据的情况下，有几件事可以提高项目的内存使用率。

首先，正如 Olaf 建议的那样，将数据对象存储在 multimap 中，而不是指向它的指针。不过，我不建议为您的数据结构使用池，与直接将其存储在地图中相比，它只会使事情复杂化而不会节省内存。

不过，您可以做的是为您的地图分配std::pair<char*, data>对象的专用分配器。这可以节省一些开销和堆碎片。

接下来，您应该关注的主要事情是尝试摆脱char*数据中的两个指针。有 14 个演出的数据，必须有一些重叠。根据它是什么数据，您可以以不同的方式存储它。

例如，如果数据是名称或关键字，那么将它们存储在中央哈希中是有意义的。是的，有更复杂的解决方案，如上面建议的 DAWG，但我认为应该首先尝试简单的解决方案。

通过简单地将其存储在 a 中std::set<std::string>并将迭代器存储到其中，您可以压缩所有重复项，从而节省大量数据。这假设您不删除字符串。删除字符串需要你做一些引用计数，所以你会使用类似std::map<std::string, unsinged long>. 我建议您编写一个继承自 / 包含此哈希的类，而不是将引用计数逻辑放入您的数据类中。

但是，如果您存储的数据没有太多重叠，例如因为它是二进制数据，那么我建议您将其存储在 a std::stringor中std::vector<char>。原因是因为现在您可以摆脱数据结构中的逻辑，甚至可以将其替换为std::pair.

我还假设您的密钥不是您存储在数据结构中的指针之一。如果是，请务必摆脱它并在您的多图中使用 的first属性std::pair。

根据您存储的数据类型，可能会进一步改进。

因此，如果有很多可能不适用于您的数据的假设，您可能只有这样：

typedef std::set<std:string> StringMap;
typedef StringMap::const_iterator StringRef;
typedef std::multimap<StringRef, std::pair<StringRef, StringRef>> DataMap;
于 2013-02-15T17:30:49.430 回答
2

我怀疑您正在泄漏或不必要地复制密钥中的内存。关键char *字符串从何而来，你如何管理它们的记忆？

如果它们与数据对象中的字符串相同，请考虑使用 amultiset<data *, ltdata>而不是 a multimap。

如果有很多重复字符串，请考虑在 a 中合并字符串set<char *,ltstr>以消除重复。

于 2013-02-15T17:31:00.457 回答