Фільтрування рядків у різні файли

Інколи бувають завдання, коли потрібно взяти текстовий файл і розділити його на декілька враховуючи якусь умову. Коли в цьому файлі мало рядків і умова тільки одна – то звичайно це можна швидко зробити у звичайному блокноті. Складність появляється тоді, коли рядків декілька сотень тисяч, і умов яким повинен відповідати рядок також. У таких випадках мені зручно вирішувати завдання в програмі ZennoPoster.

Для прикладу можна поставити таку задачу – є текстовий файл, у якому є 1 000 000 рядків. У деяких рядках є символ @. Таких рядків приблизно 30%. Замовнику потрібно витягнути з нього всі рядки у яких є символ @ в інший файл, і видалити ці рядки з вхідного файла.

Замовник спочатку пробував вирішити це завдання самостійно. Він прив’язав текстовий файл до списку ZennoPoster. Потім перебирав його в циклі до того часу, поки не знаходив рядок який містить символ @. Знайшовши необхідний рядок він зберігав його в інший список, і видаляв рядок по номеру з вхідного списку. Після чого повторював ці дії знову і знову, до того часу, поки не пройде весь вхідний список.
Проте на практиці виявилось що час виконання цього завдання дуже великий. Замовник бачить проблему в тому, що файл містить багато рядків і вирішив пришвидшити виконання збільшивши кількість потоків потоків.

Проте, він скоріш за все нічого не знає про алгоритмічну складність. Замість того, щоб проводити перевірку умови 1 раз на 1 рядок, він перевіряв кожний рядок стільки раз скільки є рядків у вхідному списку за виключенням кількості рядків, які були видалені. Тобто 1 000 000 x (1 000 000 – 30%) = приблизно 660 000 000 000 разів. Тому не дивно, що час виконання був надзвичайно великим. Скоріш за все збільшення кількості потоків для вирішення цієї задачі не пришвидшило б її виконання, тому що крім самої проблеми з алгоритмом потоки завжди вставали б у чергу на зчитування і запис даних, а також була б проблема синхронізації контексту. Наприклад один потік провірив до 10 000 рядка, інший до 100 000 рядка. Потім коли було знайдено співпадіння – потік видалив би рядок – і в цей час інший потік продовжив би роботу зі списком, у якому уже зовсім інші дані (рядки змістились би у позиціях на видалений елемент).

Власне що потрібно знати, це те, що мінімально можлива кількість перевірок рядків така, як кількість рядків у списку. Тому потрібно прагнути сформулювати таку логіку, при якій 1 рядок береться на перевірку умови тільки один раз. Власне самий швидкий і правильний варіант, який підійде у більшості випадків – це просто у звичайному циклі брати рядки по черзі, перевіряти умову, після чого добавляти цей рядок у нові умовні списки good і bad. При цьому, список з вхідними рядками бажано не змінювати. Приклад коду, який вирішує цю задачу фільтрування вхідного списку на два інші по умові наявності символа @ в рядку може виглядати так:

var input = project.Lists["input"];
var good = project.Lists["good"];
var bad = project.Lists["bad"];

string pattern = "@";
string line = string.Empty;

for(int i=0;i<input.Count;i++) {
	if(input[i].Contains(pattern)) good.Add(input[i]);
	else bad.Add(input[i]);
}

Можна цю саму роботу виконати використовуючи Linq, при цьому можна перезаписувати файл з вхідними даними, наприклад рядками, у яких немає символа @. А список з результатами попередньо можна прив’язати до файла у якому ми хочемо бачити результат:

var input = project.Lists["input"].ToList();
var good = project.Lists["good"];

string pattern = "@";

var temp_good = input.Where(x=>x.Contains(pattern));
var temp_bad = input.Where(x=>!x.Contains(pattern));

project.Lists["input"].Clear();
project.Lists["input"].AddRange(temp_bad.ToList());

good.AddRange(temp_good.ToList());

Використання Linq може пришвидшити виконання, наприклад коли ми маємо справу не з однією провіркою, а з декількома. Діло в тому, що Linq працює з лінивими колекціями, які виконуються не зразу, а в останній момент, у моєму коді це відбувається при визові temp_good.ToList() і temp_bad.ToList(). Тобто якщо наступні рядки повинні виконатись тільки один раз при завершенні коду то це вже суттєво пришвидшить роботу (тому що не потрібно буде записувати файл декілька разів, і вся обробка буде виконуватись в оперативній пам’яті компьютера):

project.Lists["input"].Clear();
project.Lists["input"].AddRange(temp_bad.ToList());

Приклад коду, який виконує роботу фільтрації рядків по декількох файлах:

var input = project.Lists["input"].ToList();
var good = project.Lists["good"];

string[] patterns = new[]{"@1", "@2", "@3"};
var temp_input = input.Where(x=>!string.IsNullOrEmpty(x));

foreach(string pattern in patterns) {
string path = Path.Combine(project.Directory, string.Format("{0}.txt", pattern));
good.Bind(path);
good.Clear();

var temp_good = temp_input.Where(x=>x.Contains(pattern));
good.AddRange(temp_good.ToList());
temp_input = temp_input.Where(x=>!x.Contains(pattern));

}

project.Lists["input"].Clear();
project.Lists["input"].AddRange(temp_input.ToList());

Хочу зазначити, що способів вирішення задач може бути декілька, і їх приходиться змінювати в залежності від того, які дані ми подаємо на вхід, які саме дані ми хочемо одержати на виході і як саме ми хочемо користуватись рішенням (якщо завдання працювати тільки з одним паттерном – ми будуємо одну логіку роботи, якщо потрібно опрацювати декілька умов – логіка у нас також зміниться, якщо потрібно зберігати результат в файли, або коли зберігати немає необхідності). Тому коли є складнощі і важко самостійно розібратись – потрібно звертатись до людей які вже мали справу з вирішенням подібних задач. Але, якщо є достатньо вільного часу – то краще ознайомитись з поняттям алгоритмічної складності і приймати її до уваги при проектуванні автоматизації своїми сценаріями.