Есть ли уловки, чтобы потреблять меньше памяти при работе с большим объемом памяти?

Question

У меня ограниченный объем оперативной памяти на моем сервере, но имеется большой объем данных, с которыми мне нужно работать в памяти в консольной программе. Существуют ли уловки, которые позволили бы мне получить тот же конечный результат, но без необходимости большого количества оперативной памяти

Для этого примера у меня есть 100 миллионов адресов электронной почты в списке строк. Мне нужно выяснить, существуют ли в нем какие-либо новые электронные письма, которые я сравниваю с этим. Если так, добавьте их. Если нет, не добавляйте их. Поэтому у нас всегда есть уникальный список электронных писем, без дубликатов.

100 миллионов электронных писем в этом примере требуют приблизительно 17 ГБ ОЗУ.

Есть ли какие-либо хитрости или советы, которые вы знаете, чтобы уменьшить объем ОЗУ, необходимый для того, чтобы, по крайней мере, иметь возможность "СУЩЕСТВУЕТ ЛИ В СБОРКЕ СПИСКА?" сравнение? - типы примеров, которые приходят на ум: например, другой тип коллекции или пользовательский программный инструмент третьей стороны, который сжимает данные в памяти, но вы все равно можете сортировать или сравнивать эти данные, или, возможно, файловая система базы данных, которая использует гораздо меньше памяти на том же объеме данных.

Я написал код, чтобы продемонстрировать, как это сделать обычным способом, при котором 17 ГБ ОЗУ расходуется.

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 электронных писем в коллекцию электронных писем, он будет просматривать еще 5 электронных писем в новом списке, добавляемом к нему. 2 будут добавлены, 3 не будут добавлены, поскольку они являются дубликатами уже в списке. общее количество заполненных писем в коллекции составляет 100 000 002. Это только для того, чтобы продемонстрировать, что моей конечной целью является возможность сравнения с существующей коллекцией, чтобы увидеть, является ли значение дубликатом или уже существует в этой коллекции, очень большой коллекции данных. Другая цель - снизить общее потребление ОЗУ с 17 ГБ до чего-то гораздо меньшего.

Answer 1

Вариант 1 Использование троичного дерева

Эта структура данных является эффективным способом хранения слов в памяти.Он очень сжат и быстр для поиска.

Вариант 2 Использование хэша в памяти и файла на диске

Храните только хэш каждого письма в памяти.Если вы попали в хеш-таблицу, посмотрите на диск.

Вариант 3 Используйте фильтр Блума и файл на диске

См. https://llimllib.github.io/bloomfilter-tutorial/

Answer 2

Похоже, вы подразумеваете, что у вас есть 100 миллионов адресов электронной почты, например, в текстовом файле.Я не вижу необходимости загружать весь файл в память и перебирать его;использовать потоковый ридер и читать его построчно.Для каждой строки проверьте, находится ли только что прочитанный адрес электронной почты в списке из 10, которые вы хотите импортировать, и, если он есть, удалите его из списка импорта

. В конце процесса вы уменьшите свой импорт.перечислите только те адреса, которых нет в огромном файле, и вы никогда не прочтете более одной строки за раз (ну, читатель кеширует небольшое количество килобайт)

Адаптировано из примера коллекции 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:\100million.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));  

Это быстрый и очень грязный пример, который не знает дела;он предназначен для простого объяснения концепции, а не производственного кода

Я работал над следующими предположениями:

У вас есть сервер с небольшим количеством оперативной памяти (например, 4 ГБ), и вынечасто (например, раз в 5 минут) добавлять небольшое количество адресов электронной почты (например, 10) в большой список из 100 миллионов адресов, не допуская дублирования новых адресов

Читать файл построчноСравните каждую строку со всеми 10 новыми адресами, удалите все, которые уже известны.В конце чтения файла, если у вас есть до N адресов, с которых вы начали, которых, как вы знаете, не существует в основном списке.

Я утверждаю, что ваше первоначальное утверждение «У меня есть большой объем данных, с которыми мне нужно работать в памяти», в этом случае возможно вместо этого работать на диске

Answer 3

Чтобы проверить, нет ли элемента в очень большом списке, вы можете использовать Фильтр Блума . Это обобщение хеш-таблицы, которая генерирует для каждой входной строки список хешей, которые хранятся в отличие от хеш-таблицы в нескольких сегментах. Таким образом, если у вас есть одна коллизия хеш-значений, она все равно может сработать, проверив другие хэши, если эта точная строка была когда-либо добавлена.

У вас все еще могут быть ложные срабатывания (filter.Contains ("xxxx") возвращает истину, хотя она никогда не добавлялась в список), но никогда не ложные отрицания.

Регулируя емкость, вы можете настроить частоту появления ошибок. Если ваш фильтр может жить с небольшим количеством ложных срабатываний, то этот должен быть хорошим.

Для примера посмотрите этот .

Я попробовал несколько попыток. Большинство реализаций используют ссылки в своем классе узлов, что невероятно неэффективно для памяти. Один из них на SO выглядит довольно неплохо: Как создать trie в c # . Этот спасает ок. 30% по сравнению с простым списком.

Помимо структур данных, я думаю, вам нужно взглянуть на общую цель. Я предполагаю, что ваши фактические данные не являются адресами электронной почты, потому что фильтр спама - это давно решенная проблема. Но чтобы поиграть с вашим примером, в ваших данных есть структура, которой вы можете воспользоваться. У вас есть большой список, состоящий из имени и домена. Первое, что нужно сделать, это разделить ваши данные на более мелкие файлы, которые содержат только почтовые адреса одного домена. Затем вы сортируете по имени и создаете индекс для каждого домена, где начальная позиция файла для каждой буквы хранится в его заголовке.

Когда приходит новое письмо, вы можете сначала выполнить быструю предварительную проверку с помощью фильтра Блума. Если он говорит, что он чистый, то вы закончили уже в 99,5% случаев. Почему 99,5%? Вы можете настроить свой фильтр Блума, чтобы иметь это свойство, рассчитав, сколько памяти вы хотите потратить, чтобы получить эту точность.

Это замечательно с точки зрения системы, потому что теперь вы можете сознательно принять решение о том, сколько ресурсов памяти / ЦП / диска вы хотите потратить на эту задачу.

Если у вас есть совпадение, вы можете открыть индексированный файл для этого домена, сразу перейти к отсортированным почтовым адресам и начать читать адреса, пока вы не нажмете плохого парня или не достигнете алфавитного порядка сортировки и не сможете прекратить чтение.

Если у вас есть больше доменов, знайте, как вы можете стать еще умнее. Поскольку вы знаете, что количество действительных отправителей для компании довольно ограничено, вы можете создать гораздо меньший проверенный белый список действительных отправителей. Если отправитель находится в белом списке, вы можете пропустить другие проверки уже.