Я пока додумался до такого решения. Создать в MySQL таблицу с 2 колонками (id и str например). При этом на str сделать индекс уникальности. Из каждого файла считывать по нескольку строк, вставляя их через INSERT IGNORE в таблицу. Потом, когда в ней окажется всё содержимое файлов, делать
SELECT str FROM table ORDER BY str LIMIT 0,100
И результат записывать через fwrite порционно в итоговый файл. После записи все извлечённые строки удалять из БД и извлеать следующую сотню.
Как считаете, это нормальное решение? Или есть ещё какие-нибудь варианты?
И если решение на таком железе подходящее, то какой тип таблиц лучше использовать? MyISAM или InnoDB (склоняюсь в сторону последнего)
Спустя 1 час, 26 минут, 1 секунда (5.09.2010 - 16:30) Nord написал(а):
Мне кажется, использовать базу здесь лишнее. Я бы сделал так:
1) Сортируем каждый файл по отдельности
2) Потом берем два файла(можно и несколько сразу) - f1 и f2 - и сливаем их в один файл tmp1 как-то так:
4) Далее берем файлы tmp1 и f3, сливаем их в файл tmp2
5) Повторяем, пока остались неслитые файлы
1) Сортируем каждый файл по отдельности
2) Потом берем два файла(можно и несколько сразу) - f1 и f2 - и сливаем их в один файл tmp1 как-то так:
$f1 = fopen('f1.txt', 'rt');
$f2 = fopen('f2.txt', 'rt');
$tmp1 = fopen('tmp1.txt', 'wt');
$s1 = false;
$s2 = false;
while (!feof($f1) && !feof($f2)){
if ($s1 === false) $s1 = rtrim(fgets($f1));
if ($s2 === false) $s2 = rtrim(fgets($f2));
if ($s1 < $s2){
fwrite($tmp1, $s1 . "\n");
$s1 = false;
} elseif ($s1 > $s2){
fwrite($tmp1, $s2 . "\n");
$s2 = false;
} else {
fwrite($tmp1, $s1 . "\n");
$s1 = false;
$s2 = false;
}
}
// Дописываем остатки
if ($s1 !== false){
fwrite($tmp1, $s1 . "\n");
while (!feof($f1)) fwrite($tmp1, fread($f1, 1024));
}
if ($s2 !== false){
fwrite($tmp1, $s2 . "\n");
while (!feof($f2)) fwrite($tmp1, fread($f2, 1024));
}
4) Далее берем файлы tmp1 и f3, сливаем их в файл tmp2
5) Повторяем, пока остались неслитые файлы
Спустя 28 минут, 21 секунда (5.09.2010 - 16:58) Белый Тигр написал(а):
Но тогда сортировки всех строк относительно друг-друга не будет вообще 
А уникальность, если и реализовать, то лишь в пределах 1 файла.
А уникальность, если и реализовать, то лишь в пределах 1 файла. Спустя 5 минут, 54 секунды (5.09.2010 - 17:04) vasa_c написал(а):
| Цитата |
| Как считаете, это нормальное решение? |
Вполне нормальное решение учитывая хреновую изначальную задачу.
Только нафиг удалять строки?
Ну и вряд ли здесь нужна особая надёжность, поэтому InnoDB необязательна.
Спустя 55 секунд (5.09.2010 - 17:05) vasa_c написал(а):
id тоже нафиг. PRIMARY KEY (`str`) и всё
Спустя 1 час, 24 минуты, 46 секунд (5.09.2010 - 18:30) Белый Тигр написал(а):
Спасибо за советы. Действительно, с PRIMARY KEY я как-то не сообразил.
| Цитата |
| Ну и вряд ли здесь нужна особая надёжность, поэтому InnoDB необязательна. |
Здесь я скорее планирую получить не надёжность, а скорость. А удалять строки из таблицы за тем, чтоб запрос был всегда с лимитом 0, 100. А то ведь первое число будет расти, следовательно извлекаться при каждом запросе будет больше строк (из которых потом будет взято и отдано мне 100).
Спустя 2 минуты, 9 секунд (5.09.2010 - 18:32) olgatcpip написал(а):
хм...
| Цитата |
| Есть около 200 файлов, размером по 20-25мб, |
я ничего несмыслю в железе, но была у меня задачка где нужно было обработать несколько миллионов строк. Все делалось на хостинге, нормальном вроде..
Но выполнялось несколько часов + порой не хватало оперативной памяти.
Поэтому здесь мне хочется сказать только о том, что
1 - При работе составляй алгоритм так, чтобы память не засорялась старыми данными
2 - дай бог чтобы час работало, круто будет ! А то можешь столкнуться с акой проблемой как перезагрузка сервера.
3 - Прикручивая БД на первый взгляд избыточно, но с ней будет удобно.
4 - ТИ последнее.. Логи писать планируй, не знаю как тебе а они мне пол жизни спасли
Спустя 35 минут, 5 секунд (5.09.2010 - 19:07) Белый Тигр написал(а):
olgatcpip, большое спасибо за советы 
Завтра приступлю, опишу как закончу все выводы
Завтра приступлю, опишу как закончу все выводы Спустя 3 часа, 18 минут, 40 секунд (5.09.2010 - 22:26) Nord написал(а):
| Цитата |
| Но тогда сортировки всех строк относительно друг-друга не будет вообще А уникальность, если и реализовать, то лишь в пределах 1 файла. |
Ну почему же? Вот смотри:
Имеется 4 файла:
f1.txt f2.txt f3.txt f4.txt
-------- -------- -------- --------
2 4 5 5
5 9 6 4
77 11 7 1
3 3
9
Сортируем:
f1.txt f2.txt f3.txt f4.txt
-------- -------- -------- --------
2 3 5 1
3 4 6 4
5 9 7 5
9 11
77
Склеиваем f1.txt и f2.txt
f1.txt f2.txt tmp1.txt
-------- + -------- = ----------
2 2
3 3 3
4 4
5 5
9 9 9
11 11
77 77
Склеиваем tmp1.txt и f3.txt
tmp1.txt f3.txt tmp2.txt
---------- + -------- = ----------
2 2
3 3
4 4
5 5 5
6 6
7 7
9 9
11 11
77 77
Склеиваем tmp2.txt и f4.txt
tmp2.txt f4.txt result.txt
---------- + -------- = ------------
1 1
2 2
3 3
4 4 4
5 5 5
6 6
7 7
9 9
11 11
77 77
Или я неправильно понял задачу?
Спустя 21 минута, 13 секунд (5.09.2010 - 22:47) Белый Тигр написал(а):
А как вы удалите дубликаты не напрягая при этом оперативную память? Вот есть 2 файла. Нужно брать строку из первого и проводить поиск по второму. Следовательно, второй нужно полностью загрузить в оперативку, или же как-то страшно извращаться с побайтовым чтением до каждого \n. То же самое и с сортировкой - нужно полностью загрузить содержимое сортируемого файла, по кускам тут его не считаешь.
Спустя 12 часов, 31 минута, 45 секунд (6.09.2010 - 11:19) Nord написал(а):
| Цитата |
| А как вы удалите дубликаты не напрягая при этом оперативную память? Вот есть 2 файла. Нужно брать строку из первого и проводить поиск по второму. |
Именно поэтому сначала файлы нужно отсортировать(если есть дубликаты в пределах одного файла, то они удаляются тут же). А далее ничего искать не надо - смотрите код, написанный выше
В кратце:
Если строка из первого файла меньше, чем из второго, пишем ее, читаем следующую из первого файла, снова сравниваем со строкой из второго
Если строка из второго файла меньше, чем из первого, то пишем ее.
Если строки равны, то пишем одну из них
Добавлено:
По поводу сортировки файлов: есть специальные алгоритмы сортировки для файлов, где они не считываются полностью. Если нужно, я поищу в своих записях
Спустя 1 минута, 10 секунд (6.09.2010 - 11:20) linker написал(а):
Все давно уже придумано гугловцами, читайте про ReduceMap.
Спустя 1 час, 6 минут, 24 секунды (6.09.2010 - 12:26) Белый Тигр написал(а):
| Цитата |
| Все давно уже придумано гугловцами, читайте про ReduceMap. |
Почитал. Помоему как-то жестковато для такой простой задачи
| Цитата |
| Именно поэтому сначала файлы нужно отсортировать(если есть дубликаты в пределах одного файла, то они удаляются тут же). А далее ничего искать не надо - смотрите код, написанный выше В кратце: Если строка из первого файла меньше, чем из второго, пишем ее, читаем следующую из первого файла, снова сравниваем со строкой из второго Если строка из второго файла меньше, чем из первого, то пишем ее. Если строки равны, то пишем одну из них |
Спасибо за разъяснения. Хорошая идея. Только скорее всего время выполнения такого алгоритма будет очень долгим
С БД должно быть быстрее, мне кажется. Спустя 28 минут, 47 секунд (6.09.2010 - 12:55) linker написал(а):
Белый Тигр
Видимо не вчитывался. Почитайте, например, http://habrahabr.ru/blogs/algorithm/103467/
Видимо не вчитывался. Почитайте, например, http://habrahabr.ru/blogs/algorithm/103467/
Спустя 45 минут, 49 секунд (6.09.2010 - 13:41) Белый Тигр написал(а):
Спасибо. Тут уже понятнее