[Большой txt ~1 гб] как обработать?

Question

[delkov]

Доброго времени суток.
Имеется большой txt ~ 1гб, вида:
x y z text text
...

Надо собрать все повторения пары x y и просуммировать их z.
Ex:

1 2 5 тест тест
1 2 10 тест тест

После обработки:
1 2 15 тест

Код на matlab (очень долго):

fid = fopen(strcat('test.txt'));
T = textscan(fid, '%f %f %f %*[^\n]');

A = T{1};
B = T{2}; 
C = T{3};

A_2 = [];
B_2 = [];
C_2 = [];

while (~isempty(A))

	temp_A = A(1);
	temp_B = B(1);
	temp_C = C(1);
	total_sum = 0;
	I_A = find(A==temp_A);
	I_B = find(B==temp_B);
	I_AB = intersect(I_A, I_B);


	if (isempty(I_AB))
		total_sum = temp_C;
		A_2 = [A_2; temp_A];
		B_2 = [B_2; temp_B];
		C_2 = [C_2; total_sum];
		A(1) = []; 
		B(1) = [];
		C(1) = [];
	else
		for i=length(I_AB):-1:1
			total_sum = total_sum + C(I_AB(i));
			A(I_AB(i)) = [];
			B(I_AB(i)) = [];
			C(I_AB(i)) = [];
		end 
		A_2 = [A_2; temp_A];
		B_2 = [B_2; temp_B];
		C_2 = [C_2; total_sum];
	end 

end


data = [A_2 B_2 C_2]

dlmwrite('out.txt', data, 'delimiter','\t','precision',3)

Возможные пути решения
1) удалить в txt последние 2 столбца (ибо не используются)
2) загнать txt в sql -> обработать там.
3) возможно есть что-то для больших файлов у c++.
4) python?

Подскажите, уважаемые пользователи!
Спасибо.

Answer 1

[kazmiruk]

Прогоните файл утилитой sort (если используете linux). На выходе получите файл, который будет отсортирован. А дальше дело техники, файл в память грузить не надо. Читаете построчно и суммируете z. Как только поменялись x или y - обнуляем z и считаем для следующей пары.

Comments

[delkov]

Спасибо, сегодня опробую!

[Александр Титов]

В винде тоже sort есть.

[kazmiruk]

alex-t: о, честно - не знал, круто

Answer 2

[abcdefghijklmnopq]

функция API операционной системы для маппинга файлов на оперативную память как раз для этих целей подходит.

если есть возможность я бы все равно предварительно подрезал бы (два последних ненужных столбца), например, EmEditor хорошо работает с большими файлами.

Comments

[delkov]

Спасибо, про EmEditor не слышал ранее.

Answer 3

[Tuvan]

Если X и Y не слишком большие ,то можно сделать матрицу SUM[X][Y] += Z (аналог матрицы смежности в графах)

Comments

[delkov]

Не совсем понял, можно подробнее?

[Tuvan]

delkov: допустим у нас все таки X и Y не такие большие числа и мы можем создать матрицу размера N*M(что бы памяти хватило для хранения) , где N>=X, M>=Y (речь идет о максимальном значении X и Y),можно разок пробежаться по вашему файлу и найти эти максимальные значения,либо взять N и M заведомо больше чем максимальные X и Y. Создаем матрицу SUM[N][M] и заполняем ее нулями. Дальше читаем файл вытаскиваем из него наши x y z (можно на ходу парьсить или как вам угодно) и делаем SUM[x][y] +=z (то есть к ячейке x,y матрицы SUM прибавляем z) . Как в графах ,стоимость пути из x в y равен z.Теперь надо это вывести обратно в файл. Если конечные z всегда больше нуля , то просто бежим по матрице двумя циклами i,j и проверяем SUM[i][j]>0 ?, если да - значит есть путь из i->j стоимостью z < выводим это. 0 значит ,что пути нет (то есть таких "x" и "y" у нас не было и выводить их не нужно). Если же z может быть любым ,то нужно придумать число (назовем его INF) ,которое будет отличаться от любого z и заполнить матрицу этим числом. и перед выводом в файл проверять SUM[i][j]!=INF ? ,если да ,то выводим в файл

Answer 4

[AtomKrieg]

Если вам нужно делать это постоянно и скорость важна как воздух, то выбирайте С++. Вариант на c++ примерно такой:
1) Считать весь файл в память.
2) Распарсить каждую строчку (вручную, так как у встроенных функций есть оверхед)
3) Для подсчета суммы используем контейнер

map<pair<int, int>, int> result;
get_parse(val1, val2, val3);
result[std::make_pair(val1, val2)] += val3;

4) Пишем весь контейнер в память (ручной функцией), сохраняем на диск.

SQL будет точно самым медленным решением. Если хотите воспользоваться питоном, то используйте библиотеку Pandas (stackoverflow.com/questions/15570099/pandas-pivot-... или Numpy (но тогда без текстов, сами пример ищите)

Comments

[Oleg Shevelev]

Предположим у вас 8 гигабайт оперативной памяти и 100 гигабайтный файл. И делать это надо каждые пять минут...

[AtomKrieg]

Oleg Shevelev: Предположим я прочитал снова заголовок и увидел там 1ГБ. В чем смысл вашего комментария про 100 гигов?

[Oleg Shevelev]

AtomKrieg: человек учится, сейчас у него такая ситуация, а завтра другая. В общем увидел в совете антипаттерн который не плохо было бы дополнить вариантом когда в память не помещается.

Впрочем, следуя вашему алгоритму пользователю нужно от 1 до 2 гигабайт оперативной памяти для хранения:
- всего файла целиком
- результирующего массива
И этот вариант медленный, к тому же даже гигабайт на такую задачу - расточительство. Исключительно личное мнение, не более.

[MiiNiPaa]

Очень весело смотреть на предупреждения по поводу медленности стандартных функций рядом с использованием std::map которая проигрывает в большинстве случаев сортированному вектору. unordered_map смотрелась бы лучше, учитывая что сортировка ОПу не нужна.

[AtomKrieg]

MiiNiPaa: Ну тут надо проверять. О распределении данных ничего не известно.

[AtomKrieg]

MiiNiPaa: Мне в плане оригинальности ответ Tuvan понравился

Answer 5

[Oleg Shevelev]

1) удалить в txt последние 2 столбца (ибо не используются)
- если есть возможность не обрабатывать данные которые не нужны то так и нужно поступить.
2) загнать txt в sql -> обработать там.
- бессмысленное занятие
3) возможно есть что-то для больших файлов у c++.
- суть разбора больших файлов (1, 10, 100, 1000 гигабайт на файл и больше) в том что бы читать его чанками по несколько байт (размер выбирается исходя из задачи) и анализ файла в поточном виде (не загружать его весь в память).

Алгоритм:
1. читаете поточно по N байт
2. при нахождении \n считаете что началась новая строка
3. как только собрали строку - делаете с ней что хотите, в данном случае разбиваете по-пробельно (explode(" ", $str); пример из php, но не суть)
4. закидываете в некий результирующий массив третью ячейку в качестве значения и первые две ячейки в качестве ключа, если данные уже были то суммируете.

Конечно это не спасёт от величины результирующего массива равного количеству уникальных ключей (ячейки x y). Для этого применяют mapReduce, но для вашей задачи он избыточен.

Вариант как избавиться от большого результирующего массива:
1. алгоритм прежний
2. записываете значение в mysql или любую другую базу в виде

INSERT INTO result_table
SET
    key = ".$key.",
    value = ".$value."
ON DUPLICATE KEY UPDATE value = value + ".$value."

Где result_table.key PRIMARY KEY

Comments

[AtomKrieg]

И этот вариант медленный, к тому же SQL на такую задачу - расточительство.

[Oleg Shevelev]

AtomKrieg: с SQL я просто упростил. Давайте найдём самый быстрый вариант?:)

[Oleg Shevelev]

AtomKrieg: и при этом экономичный по памяти (читай подходит для овер-больших файлов)

[res2001]

Алгоритм 3 самый правильный и быстрый, имхо.

[delkov]

Спасибо!
Проциирую из смежной ветки:
Верно ли я понял: читать за раз 10 строк -- много выгодней чтения в цикле строку 10 раз (во втором случае обращение к диску идет единожды). Исходя из этого, чем больше за раз - тем выгодней, то разбиение должно выбираться из размера моей оперативной памяти (весь кусок при прочтении подгружается в нее?). Каков оптимус для 16 Гб?

[Oleg Shevelev]

res2001: вы про это?

3) возможно есть что-то для больших файлов у c++.
- суть разбора больших файлов (1, 10, 100, 1000 гигабайт на файл и больше) в том что бы читать его чанками по несколько байт (размер выбирается исходя из задачи) и анализ файла в поточном виде (не загружать его весь в память)...

Или про что-то ещё?

[Oleg Shevelev]

delkov: если вопрос был ко мне, то мне не совсем ясно что с чем сравнивается. Если в крадце, то:
1. читать данные всегда лучше 1 раз, при этом читать лучше кусками, хранение всех данных в памяти за раз не подразумевается
2. чем меньше накладных расходов, будь-то лишние проходы цикла по не контролируемому объёму данных или лишние данные в памяти при обработке, тем лучше
3. если на сервере 16 или N гигабайт оперативки это не значит что надо делать алгоритмы которые её активно утилизируют там где это не нужно, пример:
- кешировать горячие данные в памяти - хорошо
- читать файл целиком что бы потом сделать с ним что-то - плохо

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

Answer 6

[abcd0x00]

Я бы сначала разделил исходный файл на несколько разных файлов, где каждый файл хранит одинаковые x y.
Потом каждый из этих файлов по очереди превращал в одну строку и сбрасывал её в общий файл вывода.