当需要处理大量内存集合时，有什么技巧可以减少内存消耗吗？

Question

我的服务器上的 RAM 数量有限，但我需要在控制台程序的内存中处理大量数据。有什么技巧可以让我仍然获得相同的最终结果，但不需要那么多 RAM

对于这个例子，我在一个字符串列表中有 1 亿个电子邮件地址。我需要查明我正在与之比较的任何新电子邮件是否已经存在于其中。如果是这样，请添加它们。如果没有，请不要添加它们。所以我们总是有一个唯一的电子邮件列表，没有重复。

此示例中的 1 亿封电子邮件需要大约 17GB 的 RAM。

您是否知道任何技巧或提示来减少至少仍然能够进行 "DOES IT EXIST IN THE LIST COLLECTION?" 比较所需的 RAM？ - 想到的示例类型：例如不同类型的集合，或自定义第 3 方引用的软件工具，它压缩内存中的数据但您仍然可以对该数据进行排序或比较，或者可能是基于文件的数据库系统使用相同数据量的内存要少得多。

我已经编写了代码来演示如何以导致消耗 17GB RAM 的正常方式执行此操作。

using System;
using System.Collections.Generic;
using System.Linq;

namespace NewProgram
{
    class Program
    {
        public static List<string> emails = new List<string>(); 

        public static void Main(string[] args)
        {
            LoadAllEmails();

            Console.WriteLine(emails.Count() + " total emails"); //100000000 total emails

            AddEmailsThatDontExistInMasterList(
                new List<string>()
                {
                "something@test.com", //does not already exist, so it will be added to list
                "testingfirst.testinglast"+ (1234567).ToString() + "@testingdomain.com", //should already exist, won't be added
                "testingfirst.testinglast"+ (3333335).ToString() + "@testingdomain.com", //should already exist, won't be added
                "something2@test.com", //does not already exist, so it will be added to list
                "testingfirst.testinglast"+ (8765432).ToString() + "@testingdomain.com", //should already exist, won't be added
                });

            Console.WriteLine(emails.Count() + " total emails after"); //100000002 total emails

            Console.ReadLine();
        }


        public static void LoadAllEmails()
        {
            for (int i = 0; i < 100000000; i++)  //100,000,000 emails = approximately 17GB of memory
            {
                emails.Add("testingfirst.testinglast" + i.ToString() + "@testingdomain.com");
            }
        }

        public static void AddEmailsThatDontExistInMasterList(List<string> newEmails)
        {
            foreach (string email in newEmails)
            {
                if (emails.Contains(email) == false)
                {
                    emails.Add(email);
                }
            }
        }
    }
}

将 100,000,000 封电子邮件添加到 "emails" 集合后，它会查看添加到其中的新列表中的另外 5 封电子邮件。将添加 2 个，不会添加 3 个，因为它们已经在列表中重复。完成后，集合中的电子邮件总数为 100,000,002 封。这只是为了证明我的最终目标是能够与现有集合进行比较，以查看某个值是否重复或已经存在于该集合中，这是一个非常大的数据集合。另一个目标是将总消耗的 RAM 从 17 GB 减少到更小的东西。

Answer 1

您似乎在暗示您在一个文本文件中有 1 亿个电子邮件地址。我看不到需要将整个文件加载到内存中并循环遍历它；使用流 reader 并逐行读取。对于每一行，检查刚刚读取的电子邮件地址是否在您要导入的 10 个列表中，如果是，则将其从导入列表中删除

在该过程结束时，您将把导入列表减少到仅包含那些不在大文件中的地址，并且您一次阅读的内容不会超过一行（好吧 reader将缓存少量千字节）

改编自 Microsoft 的示例集合：

https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/file-system/how-to-read-a-text-file-one-line-at-a-time

string line;  
string[] emailsToImport = "a@b.com c@d.com".Split();

// Read the file and process it line by line.  
System.IO.StreamReader file =   
  new System.IO.StreamReader(@"c:0million.txt");  
while((line = file.ReadLine()) != null)  
{  
    for(int i = 0; i < emailsToImport.Length; i++){
      if(emailsToImport[i] == line)
        emailsToImport[i] = null;
    }
}  

file.Close();  
System.Console.WriteLine("new emails remaining to import: {0} ", string.Join(",", emailsToImport));

这是一个快速且非常肮脏的示例，不区分大小写；它旨在作为概念的简单解释，而不是生产代码

我基于以下假设：

您的服务器内存容量较小（例如 4gb），并且您很少需要（例如每 5 分钟一次）将少量电子邮件地址（例如 10 个）添加到一个大列表中100M地址，确保新地址不重复

逐行读取文件，将每一行与所有 10 个新地址进行比较，删除任何已知的地址。在读取文件结束时，一旦你有多达 N 个你开始使用的地址，你知道它们不存在于主列表中。

我断言，在这种情况下，您的原始语句 "I have a large amount of data I need to work with in memory" 可以在磁盘上使用

Answer 2

选项 1 使用三叉树

这种数据结构是一种在内存中存储单词的有效方法。它高度压缩且搜索速度快。

选项 2 使用内存哈希和 on-disk 文件

在内存中只保留每封电子邮件的哈希值。如果你在哈希表中得到了命中，请查看磁盘。

选项 3 使用布隆过滤器和 on-disk 文件

见https://llimllib.github.io/bloomfilter-tutorial/

Answer 3

要检查某个项目是否不在非常大的列表中，您可以使用 Bloom Filter。它是散列 table 的泛化，它为每个输入字符串生成一个散列列表，与散列 table 不同，散列存储在多个存储桶中。因此，如果你有一个散列值冲突，它仍然可以通过检查其他散列来解决是否添加了那个确切的字符串。

你仍然可以有误报（filter.Contains("xxxx") return true 虽然它从未被添加到列表中）但永远不会误报。

通过调整容量可以配置错误率。如果您的过滤器可以承受较小的误报率，那么这个过滤器应该不错。

查看示例 this one。

我试了几次。大多数实现在它们的节点 class 中使用引用，这是难以置信的低内存效率。 SO 上的一个似乎还不错：How to create a trie in c#。这个节省了大约。与普通列表相比，减少 30%。

除了数据结构之外，我认为您还需要查看总体目标。我猜你的实际数据不是电子邮件地址，因为垃圾邮件过滤器是一个长期解决的问题。但是为了玩弄你的例子，你可以利用数据中的结构。您有一个包含名称和域的大列表。要做的第一件事是将您的数据拆分成更小的文件，这些文件只包含一个域的邮件地址。然后按名称排序并为每个域创建一个索引，其中每个字母的文件起始位置存储在其 header 中。

当收到新邮件时，您可以先使用 Bloom Filter 进行快速预检查。如果它说它是干净的，那么您已经完成了 99.5% 的所有情况。为什么是 99.5%？您可以通过计算要花费多少内存来获得此精度来配置您的 Bloom Filter 以获得此属性。

从系统的角度来看这很棒，因为您现在可以有意识地决定要为此任务花费多少 Memory/CPU/Disk 资源。

当你命中时，你可以打开该域的索引文件，直接跳转到排序的邮件地址并开始读取地址，直到你命中坏人或者你超过了字母排序顺序，你可以停止正在阅读。

如果你有更多的领域，你就知道如何变得更聪明。因为您知道公司的有效发件人数量非常有限，所以您可以创建一个小得多的有效发件人检查白名单。如果发件人在白名单上，您可以跳过其他检查。

当需要处理大量内存集合时，有什么技巧可以减少内存消耗吗？

Are there any tricks to consume less memory when needing to work with a large in memory collection?

c#

memory-management

out-of-memory