Как быстро определять наличие строк в файле, при этом не засоряя ОЗУ?

@Evil12Boy · Регистрация: 25.10.2023

Студворк — интернет-сервис помощи студентам

Есть код, который находится в цикле. Мне нужно при каждой генерации проверять, есть ли сгенерированная строка в файле. Если есть, записать в другой файл. Раньше делал так:

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool F = true;
HashSet<string> HS = new(File.ReadAllLines(path)); //Здесь загружается файл размером 390Мб
Random rnd = new();
string Alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890";
int Length= 39;
while (F)
{
  StringBuilder sb = new(Lenght - 1);
  int Position = 0;
  for (int i = 0; i < Lenght; i++)
  {
    Position = rnd.Next(0, Alphabet.Lenght - 1);
    sb.Append(Alphabet[Position]);
  }
  Console.WriteLine(sb);
  if (HS.Contains(sb.ToString())
  {
    F = false;
    //Запись строки в другой файл
  }
}

Вот несколько строк из файла (все они одинаковой длины):

Кликните здесь для просмотра всего текста

fd512f88908e949f7f07c99167799a075c274f1
ff0a33055ea4e6669a3925a94e0a28fb256be5d
99dc7be5c1c761f3f4a0249309a6786fa91d0fb
909fd0f1dcb3149e764212d8279a1d2bc687028
ec4c98b0745d3d7095b85c2d57bafd6befd8681
fb5252617abc7bf0adfc19b0aeb1d8adfb27fd4
8d6f71698b00693009d18c6ed6fae3733932078
17d855fc899e183f150ddf52269d3781f6bbbfb
618512eaf1f16364eecdf63e7de46d3e972e568
0ade12db0026cafb67a2717484e4bb02e40f2f3
c5017274e5bc5c3ca1c9ba7dc19fe8341aa9134
ce5d60fef69ed01a2245084dbeaee4a69ae4afa
7b62f067bd38af3735299df0ba68a11bec52966
...

Но такой метод не вариант, жрёт слишком много ОЗУ (получается ~1,7 Гб занятой ОЗУ из 391 Мб файла). А мне нужно будет использовать файл размером до 2,5Гб.

Также пробовал использовать алгоритм - фильтр Блума из ГитХаба:

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Filter<string> filter = new(9999999); 
StreamReader sv = new StreamReader(path);
string line = sv.ReadLine();
while (line != null)
{
  filter.Add(line);
  line = sv.ReadLine();
}
sv.Close();
//Дальше та же генерация строк, проверку делал так:
if (filter.Contains(sb.ToString())
{
  F = false;
  //Запись строки в другой файл
}

Но при использовании файла размером ~2Гб (более 50 млн строк) происходит слишком много ложный срабатываний.

Что предложите делать? Хочется, чтобы результат был - "Да, такая строка точно есть в файле, записываем", а не как с фильтром Блума

@Wolfdp · 30.10.2023, 01:55

Глянул что там за чудо алгоритм на пайтоне (учитывая что этот ЯП не знаю от слова "совсем", больше читал коменты из первоисточника). Как я понял, там банально максимально алоцируют считуемый блок файла посредством деления пополам и просмотра больше-меньше (наверное.... не уверен что правильно понял описание алгоритма).

В целом мне понравилась идея того что подготовить "размеченный файл", и тупо проходить по нему. Переделал свой пример, чтобы вместо словаря в ОЗУ был словарь содержащий сдвиг+длину в специально заготовленом файле. Алгоритм приблизительно такой:
- генерим текстовый файл.
- генерим временую папку рядом.
- проходим каждую запись где:
- - сжимаем строку из 38 символов до 10 байт
- - первый 4 символа стают именем файла
- - оставшиеся 9 тупо пишем в временый файл с соотвествующим именем
- по проходу все записей, мержим все временый файлы в один большой.
- в начале нашего смерженого файла будет храниться словарь содежращий первий байт слова в качестве ключа (по факту это первый четыре символа), а в качестве значения -- сдвиг в файле и длина блока
- при поиске смотрим в словарь, делаем Seek и ищем пока не считаем BlockLength

Нужно понимать следующие моменты:
- рядом появляется дополнительный файл объемом 30% от изначального
- если в исходном файле все строки начинаются одинаково (ну или очень много) -- беда. По сути всё это не даст никакого эффекта. Короче, если ваш исходный файл со строками не подвержен нормальному распределению, лучше использовать писанину из питона.

Протестировал сразу на hdd 2008 года подключеный через usb 3.0 (без понятия что там за скорости, но хрустел знатно). ОЗУ не подымалось выше 30Мб (ну или я не заметил).

generate big file 1GB for test - 00:00:18.7170961
generate optimized file - 00:00:30.4767341
check 50_006 element - 00:00:28.3722130

generate big file 5GB for test - 00:01:12.0878518
generate optimized file - 00:02:08.5539424
check 50_006 element - 00:02:05.3147744

Вроде как 2~3ms для 5GB -- подходит под ваши хотелки. Ещё попытался провернуть на флешке с USB 2.0, но там тупо оптимизированый файл генерится вечность (на 100MB исходник тупило 4 минуты), решил забить. В целом с генерацией файла явно есть варианты ускорения, т.к. сейчас валит очень много мелких write по 9 байт, и подозреваю что это не есть хорошо. Была наивная попытка "ускорить за счет изначального выставления файлу размера побольше с последующим Truncate", не уверен что это помогло хоть как-то (вырезать уже не стал).

P.S. всё это начинает походить на таблицу БД.

@Evil12Boy · 30.10.2023, 11:01 **[ТС]**

Wolfdp, спасибо!)
Можно закрывать тему

(на этом форуме темы вообще закрываются?)

@Usaga · 31.10.2023, 09:21

Не по теме:

Сообщение от Evil12Boy

(на этом форуме темы вообще закрываются?)

Нет. Они на будущее остаются. Принудительно закрываются только те темы, где происходит непотребщина.

@Элд Хасп · 05.11.2023, 11:39

Сообщение от Wolfdp

- если в исходном файле все строки начинаются одинаково (ну или очень много) -- беда. По сути всё это не даст никакого эффекта.

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

Моя реализации для другой задачи (но может и здесь подойти):

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    public class BytesComparerHelper : IEqualityComparer<IEnumerable<Byte>>
    {
        public bool Equals(IEnumerable<byte>? x, IEnumerable<byte>? y)
        {
            if (x is null || y is null)
                return x is null && y is null;
            return x.SequenceEqual(y);
        }
 
        public int GetHashCode([DisallowNull] IEnumerable<byte> bytes)
        {
            uint hash = 587173672; // Какой-то случайный литерал для затравки
            foreach (var @byte in bytes)
            { 
                uint most = hash & 0x80_00_00_00;
                hash <<= 1;
                if (most != 0)
                    hash ++;
                hash ^= @byte;
            }
            return (int) hash;
        }
    }

Добавлено через 1 минуту
Если хеши получаются слишком разные и, соответственно, слишком много временных доп. файлов, то можно uint заменить на ushort.

Добавлено через 6 минут

Сообщение от Evil12Boy

Только проверка наличия строк (которые генерируются по 100 штук в секунду) с строками из одного такого файла.

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

Добавлено через 3 минуты
Очень сильно будет зависеть от железа. Если это старые компы (а вы писали что у вас есть и такие) с HDD....

Добавлено через 3 минуты
Wolfdp, я бы попробовал заменить временные файлы и итоговый дополнительный, на простую БД типа SQLite.

@Wolfdp · 05.11.2023, 22:54

Сообщение от Элд Хасп

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

По идеи "да" -- это решает вопрос, если точно знаем что есть очень много повторяющихся в начале строк. Теоретически -- колизии хеша никто не отменял, и все 3 Гб может начинаться одинаково, что тоже обесценивает индекс (он у всех будет одинаковый). Но это вопрос контекста применения, в целом идея не лишена смысла.

Сообщение от Элд Хасп

я бы попробовал заменить временные файлы и итоговый дополнительный, на простую БД типа SQLite.

Честно говоря, я уже не столь горю желание писать код, как пример выше и замерять перфоманс. А перегнать данные в БД -- явно не шустрая задача, там можно налажать на многих моментах. Мне просто было интересно попробовать определенные моменты: искать одновременно несколько значений за проход (у меня код исключительно замедлился, без внятного понимания почему), упаковать + создать индекс (профит уже явно ощутимый).

Как я понял, основная проблема именно количество строк, а не их качество, и то сколько раз их перебрать придется. Индекс и бинарный поиск решают вопрос чтобы не просматривать каждую строку, а только часть от всей инфы. Последний способ имеет преимущество на дистанции (т.к. для получения +1 проверки нам по сути нужно удвоить текущий объем данных), но жутко дорогой в плане подготовки данных (отсортировать ВСЁ -- это операция явно не из быстрых). Плюс менее гибкий в плане, когда у нас данные не одинаковой длины (нужно учитывать разделитель и выполнять отступы).

Возвращаясь к контексту применения, ТС указывал что файл он сортировал вообще в сторонней программе, что намекает на возможность заготовить данный для ПО и больше не возвращаться к этому вопросу. Количество проверок бинарным поиском для 3Гб будет в районе 28 (плюс-минус). Индексированием 3Гб разбивается где-то на ~10Мб сектора, что явно в себе будет содержать более 30 элементов, так что чисто по количеству операций -- бинарный должен выигрывать (ну или сильнее дробить файл, используя short). Прада это только предположение, т.к. есть определенный ньюанс: бинарный поиск постоянно выполняет "случайный" доступ к файлу, в то время как индеск позволяет считать блок. На HDD это возможно будет играть роль.

В любом случае, ТС уже выбрал бинарный, и более подробный контекст задачи только у него. Нужно ли обновлять массив байт для поиска? Если да -- тут явно лучше вариант от kotelok, с несколькими файлами (просто докидываешь в конец и всё). Насколько плохо, что приходиться тягать за собой 3Гб, который в теории можно сжать в четыре раза и далее применять любой из способов (хоть бинарный, хоть через индекс). Ну и практические тесты. Запустить игру для "усложнения задачи" -- так себе. Я бы решал задачу через подключения реальных hdd и разворачивания виртуальной машины с интересуемым количеством ОЗУ. В идеале вообще стоит где-то отрыть древнего пациента, и проверять "отзывчивость" там, так как кеш CPU тоже творит чудеса.

Не по теме:

P.S. как отучить себя выделять по Ctrl+W в браузере?.... =_=

@Wolfdp · 02.01.2024, 12:06

Не по теме:

ну хоть спустя 2 месяца до меня дошло что 4 бита -- это 16 значений, а не сколько я там надумал... T_T Хоть бы кто пнул. Хорошо что ТС использовал по итогу другое решение.

Новые блоги и статьи Все статьи Все блоги /
Теория всего 12. ВГК anaschu 21.07.2026 ### Главные семантические изменения и дешифровка новой физики 1. `REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`): Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .	Публикация отклонённая на хабре. Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование задачи и целеполагание Hrethgir 21.07.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11948&stc=1&d=1784657928 Привет Хабр. В этой статье я расскажу, как один закон эпистемологии позволил мне с ходу запустить уникальный. . .	Теория всего 11. Основные параметры anaschu 21.07.2026 Дешифровка тензорного ядра Soil Chemistry 2. 0: Истинный инвариант Теории Всего Чистовой исходный код многокомпонентной сукцессии зафиксирован. Модель оперирует единым вектором состояния. . .	Теория всего 10. Клод трусишка anaschu 21.07.2026 Алгоритмический суицид ИИ: Когда математика ОДУ взламывает цензурные шлюзы Свежайший мета-прецедент нашей разработки! Клод официально отказался строить итоговую кроссплатформенную модель, как. . .
Теория всего 9. Окончательная проработка метафоры "дерево = традиции" anaschu 21.07.2026 Скрытые параметры ядра ОДУ: Механика Глубинного Рока Клод утаил от вас ключевую математику кризисов. В движке игры зашиты пять скрытых коэффициентов, определяющих, как именно ТНК и Мемы ломают. . .	Теория всего 8. Clauude трусишка. Ответ джемени anaschu 21.07.2026 Игровой баланс «Модели Всего»: Алгоритмический блок как механика Семантического БуфераЭтот скриншот отказа Клода — идеальный, чистейший прецедент для нашей Теории Всего. Вы столкнулись не просто с. . .	Теория всего 7. Дерево - это патриархат, грибы - это феминизм anaschu 21.07.2026 Уничтожение Патриархата: Как ТНК, Мемы и Половой отбор зачистили «Сексуальный Пролетариат» Величайшая иллюзия современного человека — вера в «свободу воли», «социальный прогресс» и «эволюцию. . .	История и социология Терры на примере борьбы микориз за пространство. 1. Глоссарий терры. anaschu 21.07.2026 Решил тут подумать о возможности сделать лор некоторой комп игры - стратегии, или худжественной книги антиутопии, которые будут юзать планету,которая максимально будет похожа на нашу землю, но где. . .

@Evil12Boy 0 / 0 / 0 Регистрация: 25.10.2023 Сообщений: 35
	30.10.2023, 11:01 [ТС]
	Wolfdp, спасибо!) Можно закрывать тему (на этом форуме темы вообще закрываются?) 0

@Wolfdp
	02.01.2024, 12:06
	Не по теме: ну хоть спустя 2 месяца до меня дошло что 4 бита -- это 16 значений, а не сколько я там надумал... T_T Хоть бы кто пнул. Хорошо что ТС использовал по итогу другое решение. 0

Как быстро определять наличие строк в файле, при этом не засоряя ОЗУ?

Решение