减少C#应用程序的内存占用

Question

我正在开发一款需要处理大约400万个英语句子的C#应用程序。所有这些句子都被存储在一棵树中，其中树中的每个节点都是一个类，具有以下字段：

class TreeNode
{
    protected string word;
    protected Dictionary<string, TreeNode> children;
}

我的问题是，当应用程序达到第2000000个句子时，它将使用完所有RAM（我有2 GB RAM）。因此，它只能处理一半的句子，然后速度显着减慢。

我该怎么做来尝试减少应用程序的内存占用？

编辑：让我更详细地解释一下我的应用程序。所以我大约有300,000个英文句子，并且对于每个句子，我正在生成更多的子句，例如：

示例： 句子：“足球是一项非常流行的运动” 我需要的子句：

1. 足球是一项非常流行的运动
2. 是一项非常流行的运动
3. 一项非常流行的运动
4. 非常流行的运动
5. 流行的运动
6. 运动

每个句子都按单词存储在树中。因此，考虑上面的示例，我有一个TreeNode类，它的word字段为“足球”，孩子列表具有单词“是”的TreeNode。is节点的子节点是a节点。“a”节点的子节点是“very”节点。我需要逐字存储句子，因为我需要能够搜索以示例开始的所有句子：“Football is”。

因此，基本上对于句子中的每个单词，我都会创建一个新的（子句）。这就是最终产生4,000,000个不同句子的原因。将数据存储在数据库中不是选项，因为应用程序需要一次性处理整个结构。如果我必须将所有数据写入数据库，它还将进一步减慢流程。

谢谢

- PB_MLT

---

补充马克的评论，为什么不将其存储在数据库中，并让它管理内存分页？注意：抱歉马克，我似乎编辑了你的评论而不是添加新评论。我能还原吗？ - Mitch Wheat

你真的需要一次性将所有句子都存储在内存中吗？ - jason

你为什么要将它们存储为树形结构？你的应用程序的目的是什么？ - Hamish Grubijan

children 字典中是否只包含一个项目（例如您的示例中的“is”）？那么为什么需要一个字典呢？ - Dirk Vollmar

@Spi1988 - 感谢您抽出时间提供反馈，说明这对网站来说非常有用，考虑到未来可能会访问此问题的人。干杯。 - Marc Gravell

Answer 1

你使用的是什么作为键？你从哪里获取数据？如果这些是单词（不是完整的句子），我想知道你是否有很多重复的键（具有相同基本值的不同string实例），在这种情况下，您可以受益于实现本地interners以重用值（并让瞬态副本被垃圾回收）。

public sealed class StringCache {
    private readonly Dictionary<string,string> values
        = new Dictionary<string,string>(StringComparer.Ordinal);
    public string this[string value] {
        get {
            string cached;
            if (!values.TryGetValue(value, out cached)) {
                values.Add(value, value);
                cached = value;
            }
            return cached;
        }
    }
}

在构建树时实例化它，当您认为值很可能重复时使用：

StringCache cache = new StringCache(); // re-use this instance while building
                                       // your tree
...
string s = ... // whatever (from reading your input)
s = cache[s];

- Marc Gravell

---

毫无疑问，这将减少内存需求。实际上，它们的数量远远不到400万个单词 - 更接近于10万个。对它们进行字符串驻留处理将会产生巨大的影响。 - LBushkin

@Marc：你不使用string.Intern()的原因是什么？ - Mitch Wheat

@Marc：我想我刚刚发现原因了！内存可能直到CLR终止才被释放... - Mitch Wheat

@Mitch - 的确；这里的意图是允许数据在受控的时间/批次内共享，而不是整个过程。 - Marc Gravell

@Cameron - 嗯，我猜测你可以把引用分类为轻量级模式，但最终它是对象重用。 - Marc Gravell

我实现了你的解决方案，内存使用情况得到了很大改善。在采用你的方法之前，当系统完成整个过程的三分之一时，它会填满我的2GB RAM。现在，整个过程只使用了约200MB的RAM。这个收益是巨大的，因为我有很多重复的字符串。感谢你们的帮助。 - PB_MLT

Answer 2

字典类型本身会消耗大量内存。您考虑过使用List<KeyValuePair<string, TreeNode>>吗？泛型List每个实例使用的内存比泛型Dictionary少得多。

当然，使用List而不是Dictionary的限制是您无法通过字符串自动索引。这将是时间和空间之间的明显折衷。如果列表很短，甚至可能比字典更快（大约10个键的线性搜索通常比哈希表搜索更快）。即使至少大多数列表都很短，它仍然可能是一个很大的改进（例如，如果95%的列表有10个或更少的项，而其他5%的最大项可能为100个）。

您甚至可以使用Collection<KeyValuePair<string, TreeNode>>，它使用的内存比List<T>还要少。

- Eilon

---

所以... 为此有一个 HybridDictionary。它开始作为一个列表，然后变成字典。 - Hamish Grubijan

是的，有HybridDictionary，但即使它也有一些额外的成本。 HybridDictionary最初使用约32字节的内存，Dictionary<K,V>约44，List<T>约16，Collection<T>约8。（这不包括CLR开销，并假定为32位。） - Eilon

我会先尝试使用HybridDictionary，因为如果可能的话，我想保留字符串索引。 - PB_MLT

Answer 3

你能将每个单词映射到一个整数吗？这样你就会有一个包含唯一英语单词的整数到字符串的映射，以及一个包含句子的树形结构，如下所示：

class TreeNode
{
    protected int word;
    protected Dictionary<int, TreeNode> children;
}

Dictionary<string, int> _AllWords;

现在，_AllWords 集合不适合根据关键字查找单词。你可能需要一个多关键字列表，可以根据关键字和值进行快速查找。 CodeProject 上有一篇文章介绍了这个方法。

- Igor Zevaka

---

请注意，在x86上，这实际上与我提供的“内部建议”相同，但无需在int键和字符串值之间进行额外的查找。相反，每个int本身就是引用。 - Marc Gravell

Answer 4

需要考虑的一些要点。

1. 在初始化Dictionary<,>时，传入所需的最大项数。这将使其在启动时分配足够的桶。默认情况下，初始化为0个桶，相当于3（质数）。一旦添加更多项，字典必须重新初始化并将所有项复制到新的更大存储中。如果您的程序从不空闲，则GC不会收集旧字典。
2. 通过编码字符串，可以节省空间。字符串在内存中每个字符使用两个字节。借助一些辅助函数，您的类可能如下所示：

    class TreeNode
    {
        protected byte[] word;
        protected Dictionary<byte[], TreeNode> children;

        public string Word
        {
            get { return Encoding.UTF8.GetString(word); }
            set { word = Encoding.UTF8.GetBytes(value); }
        }

        public TreeNode GetChildByKey( string key )
        {
            TreeNode node;
            if(children.TryGetValue( Encoding.UTF8.GetBytes(key), out node  ))
            {
                return node;
            }
            return null;
        }
    }

[编辑] 我忘了您还需要一个新的 byte[] 键比较器。

var children = new Dictonary<string,TreeNode>(new ByteArrayComparer);

public class ByteArrayComparer : IEqualityComparer<byte[]>
{
    public bool Equals(byte[] x, byte[] y)
    {
        if (x.Length != y.Length)
            return false;

        for (int i = 0; i < x.Length; i++)
        {
            if (x[i] != y[i])
                return false;
        }

        return true;
    }

    public int GetHashCode(byte[] a)
    {
        return a[0] | (int)a[1] << 8 | (int)a[2] << 16 | (int)a[3] << 24;
    }
}

- Mikael Svenson

---

仅为完整性而言 - 编码可能在这里有一席之地，因为问题涉及到"英语句子"，但对于某些文化来说，这实际上可能会导致字符串使用的内存翻倍。 - Marc Gravell

这是一个很好的观察，我实际上没有考虑过。我习惯于使用西方字符集工作。在进行编码之前，测试并查看是否有帮助。使用可变字节结构可能也会有所帮助，特别是如果字符串较长。但在采用压缩方式之前，您应该重新考虑整个问题。 - Mikael Svenson

Answer 5

如果你的需求是性能，并且你感觉需要将所有单词存储在内存中，那么我建议你使用字符串数组来包含所有单词。然后将所有索引存储到排序的二叉树中。

- Rizon

Answer 6

为了减少内存占用，您应该寻找顺序数据缓存。

它可以通过您使用的集合来减少内存占用。（集合项必须标记为[Serializable]）

您甚至可以通过传递deleteOnClose:false参数使集合变为永久性的。

示例

using (var c = SequentialDataCache<TreeNode>.Initialize(deleteOnClose: false))
        {
            //add items to collection
            for (int i = 0; i < 1000; i++)
            {
                var treeNode = new TreeNode()
                                   {
                                       Word = string.Format("Word{0}", i),
                                       Children = new Dictionary<string, TreeNode>()
                                   };
                for (int j = 0; j < 100; j++)
                {
                    var child = new TreeNode() { Word = string.Format("Word{0}", j) };
                    treeNode.Children.Add(string.Format("key{0}{1}", i, j), child);
                }
                c.Add(treeNode);
            }

            //assert query
            Assert.AreEqual("Word0", c[0].Word);
            Assert.AreEqual("Word1", c[0].Children["key01"].Word);
            Assert.AreEqual("Word100", c[100].Word);
        }

和TreeNode相关...

    [Serializable]
    class TreeNode
    {
        private string word;
        private Dictionary<string, TreeNode> children;

        public string Word
        {
            get { return word; }
            set { word = value; }
        }

        public Dictionary<string, TreeNode> Children
        {
            get { return children; }
            set { children = value; }
        }
    }

- csizo

Answer 7

对于你的情况来说，这可能有些过度设计，但你可以将节点存储在磁盘文件中，并使用B-Tree实现来最大化IO性能。这是大多数数据库内部使用的方法，因为数据量太大无法全部存储在内存中。

- Ash

Answer 8

好问题，有些很棒的答案。我学到了很多。StringCache的想法值得研究。

我想回应“我不能使用数据库，因为我需要全部在内存中”的观点。在许多情况下，数据库实际上是最好的解决方案。

考虑到一个强大的SQL数据库引擎（我是MSSQL的人）：

• 可以容纳更多的数据--磁盘的大小而不是内存或交换空间的大小。（SQL数据库还可以利用另一台机器上的内存和磁盘，从而增加可用的占地面积，但要权衡网络延迟。）
• 对数据进行索引以便快速检索
• 动态缓存最常用的数据，并在内存压力指示时释放较少使用的数据。
• 使用由大型团队开发并调整以适应各种情况的存储、检索和缓存算法。

动态缓存对于这个解决方案集可能会带来巨大的好处。假设你的语料库只包含“正常”的句子，那么单词分布将不会是均匀的。最常见的单词将被访问多个数量级，比最不常见的单词多得多。很可能常用的单词将在早期被添加到字典中，并因此在数据库中靠近一起存储。一个好的SQL引擎将在内存中缓存最常用的块，自然而然地支持你所描述的搜索。

混合解决方案可能看起来像这样：

• 带有适当索引的表

  create table myWords (wordKey int identity, word varchar(50))
  create unique index iword 
    on myWords(word)  -- 用于添加和检索
  create unique index iwordKey 
    on myWords(wordKey) -- 用于将键映射回单词
  

• 用于添加/查找单词的存储过程。存储过程方便地返回一个整数。

  create procedure addWord (@word varchar(50))
  as
  begin
    declare @wordKey int, @rows int
    insert myWords (word)
      select @word
      where not exists (select 1 from myWords where word = @word)
    select @wordKey = @@identity, @rows = @@rowcount
    if @rows = 0
    begin
      select @wordKey = wordKey
        from myWords
        where word = @word
    end
    return @wordKey
  end
  

• 应用程序将单词添加到数据库中，仅使用wordKey值在内存中构建树。

• 搜索匹配句子将从查询获取所涉及单词的wordKey值开始，然后分析树，收集构建完整句子所需的wordKeys，并最终使用第二个查询检索这些单词。

您可以在构建数据库时稍微牺牲一点速度，以进一步优化缓存最常用单词的效益。

1. 向表中添加一个字段（usageCount int）。插入时将其设置为1，更新时递增。
2. 仅使用单词索引，从语料库中填充字典表。
3. 在usageCount上添加聚集索引（降序），这将重新组织以使最常用的单词靠近一起。（也许再次删除它——工作已经完成。）
4. 构建您的树。

即使您的语料库在未来增长，单词频率也不太可能改变到足以影响效率。

- Bruce

Answer 9

你唯一可以“显著”减少内存使用的方法是不将句子保存在内存中。

你想要实现什么？为什么要构建树？如果你正在计数某些东西，请在读取它们时计数并丢弃字符串。如果你正在构建图表（即分析句子和/或单词之间的关系），请尝试枚举句子和单词，以便它们可以通过该ID成为唯一/键。在内存中使用该ID。

希望这可以帮助到你。

- tgiphil

---

我很高兴地报告，确实有方法可以显著减少内存使用。 - Marc Gravell