[ Поиск ] - [ Пользователи ] - [ Календарь ]
Полная Версия: Задачка про пхп
vital
ПРосто интеренсо кто как мыслит wink.gif
ВОбщем, есть файл размером 40GB.
Есть пхп под который выделено 4GB.
В файле записаны числа - по одному в каждой строке - в разнобой.
Фaйл нужно отсортировать по возрастанию.
Бд не юзать, линуховую команду sort не юзать.

Код можете не писать. ВАжна идея



Спустя 48 минут, 5 секунд (3.02.2012 - 16:59) m4a1fox написал(а):
vital
Какое конечное число? И еще вопрос, скажем вот так

1,2,3,5,6,8,7,9,4,0....

или

1,2,5,6,8,9,4,0....

То есть не все... некоторых нет?
Нужно больше информации...

Спустя 12 минут, 59 секунд (3.02.2012 - 17:12) sergeiss написал(а):
Еще вопросы:
- какой размерности числа, сколько знаков максимум?
- 4 ГБ - это для оперативной работы (промежуточных результатов) или для вывода данных?

Спустя 26 минут, 52 секунды (3.02.2012 - 17:39) killer8080 написал(а):
накидал вариант
Свернутый текст
set_time_limit(0);
ignore_user_abort(true);

$lines_limit = 10000000;
$file_src = 'bigfile.txt';

$temp_dir = 'temp_sort_dir/';
$temp_file = $temp_dir.'temp.txt';

if(!file_exists($temp_dir))
mkdir($temp_dir, 0755) or die("can't make temp direcory");
else
remove_files($temp_dir);

$f = @fopen($file_src, 'r') or die("can't open source file");

$i = 0;
$arr = array();
while(!feof($f)){
if($i++ < $lines_limit){
$arr []= trim(fgets($f, 1024));
}
else{
sort($arr, SORT_NUMERIC);
file_put_contents($temp_dir. $arr[0]. '.temp', implode("\r\n", $arr)."\r\n");
$arr = array();
$i = 0;
}
}

fclose($f);
unset($arr, $i);

if(!file_exists($temp_file))
unlink($temp_file);

$files = glob($temp.'*.temp');
foreach($files as $temp_file_i){
file_put_contents($temp_file, file_get_contents($temp_dir . $temp_file_i), FILE_APPEND);
}
unset($files, $temp_file_i);

if(filesize($temp_file) == filesize($file_src))
echo copy($temp_file, $file_src) ? 'success' : "can't copy temp file";
else
echo 'mismatch file sizes';

remove_files($temp_dir);

function remove_files($dir){
foreach(globe($dir.'*') as $file){
if(is_file($file))
unlink($file);
}
}

Спустя 1 час, 34 минуты, 34 секунды (3.02.2012 - 19:13) Zerstoren написал(а):
Т.к. у нас есть условие что это инты, то можно создать файлы в которых будут лежать диапазоны, по 2 гига на диапазон.

Проходим весь 40гб файл.

Разбираем все инты большими порциями, по 3.5 гб за раз (не забываем, сам язык тоже жрет оперативку)

Распихиваем все элементы по диапазонным файлам.

В случае если диапазонный файл выходит за пределы 2х гигов, мы разбиваем его на еще 2 файла.
И раскидываем значения по файлам.

Теперь каждый файл по очереди можем сортировать, чем сортировать - дело ваше. Хоть встроенными функциями, хоть сами пишите.

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

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

Склеиваем все вместе и profit!

Спустя 2 дня, 18 часов, 24 минуты, 23 секунды (6.02.2012 - 13:38) vital написал(а):
Цитата (m4a1fox @ 3.02.2012 - 15:59)
vital
Какое конечное число? И еще вопрос, скажем вот так

1,2,3,5,6,8,7,9,4,0....

или

1,2,5,6,8,9,4,0....

То есть не все... некоторых нет?
Нужно больше информации...

Все-равно абсолютно

Спустя 7 минут, 9 секунд (6.02.2012 - 13:45) vital написал(а):
Цитата (sergeiss @ 3.02.2012 - 16:12)
Еще вопросы:
- какой размерности числа, сколько знаков максимум?
- 4 ГБ - это для оперативной работы (промежуточных результатов) или для вывода данных?

4гб - мемори_лимит в пхп.ини
Числа - инты.

Спустя 2 минуты, 14 секунд (6.02.2012 - 13:47) vital написал(а):
Цитата (Zerstoren @ 3.02.2012 - 18:13)
Т.к. у нас есть условие что это инты, то можно создать файлы в которых будут лежать диапазоны, по 2 гига на диапазон.

Проходим весь 40гб файл.

Разбираем все инты большими порциями, по 3.5 гб за раз (не забываем, сам язык тоже жрет оперативку)

Распихиваем все элементы по диапазонным файлам.

В случае если диапазонный файл выходит за пределы 2х гигов, мы разбиваем его на еще 2 файла.
И раскидываем значения по файлам.

Теперь каждый файл по очереди можем сортировать, чем сортировать - дело ваше. Хоть встроенными функциями, хоть сами пишите.

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

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

Склеиваем все вместе и profit!

И как же записать все в один файл?) В склеивании есть свой подвох.

Спустя 3 часа, 25 минут, 24 секунды (6.02.2012 - 17:13) sergeiss написал(а):
Цитата (vital @ 6.02.2012 - 14:45)
Цитата (sergeiss @ 3.02.2012 - 16:12)
Еще вопросы:
- какой размерности числа, сколько знаков максимум?
- 4 ГБ - это для оперативной работы (промежуточных результатов) или для вывода данных?

4гб - мемори_лимит в пхп.ини
Числа - инты.

Еще раз повторю свой вопрос smile.gif Только уточню, что он был о том, что где эти 4ГБ выделены - на диске? Или там есть много места, достаточно для любой работы? По начальному вопросу можно так понять, что это на диске выделено 4 ГБ. Потому я и спросил. Потому что если на диске 4ГБ, а файл 40 ГБ, то задача нерешаема. Если в оперативке 4 ГБ - то это другой вопрос совсем.

По твоему ответу МОЖНО ПРЕДПОЛОЖИТЬ, что на диске мы имеем столько места, сколько нам надо. Плюс к этому я допускаю (хотя об этом не сказано!!!), что многие числа могут повторяться, некоторые по много раз. Или там нет повторов? Это тоже может повлиять на алгоритм работы.

ОК, бум думать... Особенно, когда ты ответишь на ВСЕ вопросы, в т.ч. и заданные ранее. Потому что иначе это не полное ТЗ получается smile.gif

PS. В частности, какое максимальное число возможно в перечне? - существенный вопрос.

Спустя 58 минут, 28 секунд (6.02.2012 - 18:11) vital написал(а):
Цитата (sergeiss @ 6.02.2012 - 16:13)
Цитата (vital @ 6.02.2012 - 14:45)
Цитата (sergeiss @ 3.02.2012 - 16:12)
Еще вопросы:
- какой размерности числа, сколько знаков максимум?
- 4 ГБ - это для оперативной работы (промежуточных результатов) или для вывода данных?

4гб - мемори_лимит в пхп.ини
Числа - инты.

Еще раз повторю свой вопрос smile.gif Только уточню, что он был о том, что где эти 4ГБ выделены - на диске? Или там есть много места, достаточно для любой работы? По начальному вопросу можно так понять, что это на диске выделено 4 ГБ. Потому я и спросил. Потому что если на диске 4ГБ, а файл 40 ГБ, то задача нерешаема. Если в оперативке 4 ГБ - то это другой вопрос совсем.

По твоему ответу МОЖНО ПРЕДПОЛОЖИТЬ, что на диске мы имеем столько места, сколько нам надо. Плюс к этому я допускаю (хотя об этом не сказано!!!), что многие числа могут повторяться, некоторые по много раз. Или там нет повторов? Это тоже может повлиять на алгоритм работы.

ОК, бум думать... Особенно, когда ты ответишь на ВСЕ вопросы, в т.ч. и заданные ранее. Потому что иначе это не полное ТЗ получается smile.gif

PS. В частности, какое максимальное число возможно в перечне? - существенный вопрос.

Числа. Инты. ЛЮБЫЕ, к-е вмещаются в диапазон INTEGER типа пхп. В любом порядке, 1 число в строке. Одинаковые могут быть. Их просто расположить один за одним - как в любой сортировке массива.

4гб - мемори_лимит в пхп.ини.
Место на винчестере - бесконечно.

Спустя 23 минуты, 39 секунд (6.02.2012 - 18:35) Zerstoren написал(а):
>>> И как же записать все в один файл?) В склеивании есть свой подвох.

В до записывании его не будет)

Спустя 38 минут, 13 секунд (6.02.2012 - 19:13) sergeiss написал(а):
Цитата (vital @ 6.02.2012 - 19:11)
Числа. Инты. ЛЮБЫЕ, к-е вмещаются в диапазон INTEGER типа пхп. В любом порядке, 1 число в строке. Одинаковые могут быть. Их просто расположить один за одним - как в любой сортировке массива.

4гб - мемори_лимит в пхп.ини.
Место на винчестере - бесконечно.

Вот. Это уже понятнее smile.gif

Тогда получаем... Что Zerstoren уже описал алгоритм очень даже хорошо. Разве что только "диапазонные" файлы нужно делать не по 2ГБ, а поменьше. Иначе они потом не загрузятся в оперативку 4 ГБ.
И в "склеивании" нету никакого подвоха. Если только ты считаешь "подвохом" возможное отсутствтие в конце файла знака "конец строки" smile.gif Тогда да - будет подвох. Но только он, других не видать.

Спустя 10 минут, 51 секунда (6.02.2012 - 19:24) Zerstoren написал(а):
Цитата (sergeiss @ 6.02.2012 - 16:13)
Цитата (vital @ 6.02.2012 - 19:11)
Числа. Инты. ЛЮБЫЕ, к-е вмещаются в диапазон INTEGER типа пхп. В любом порядке, 1 число в строке. Одинаковые могут быть. Их просто расположить один за одним - как в любой сортировке массива.

4гб - мемори_лимит в пхп.ини.
Место на винчестере - бесконечно.

Вот. Это уже понятнее smile.gif

Тогда получаем... Что Zerstoren уже описал алгоритм очень даже хорошо. Разве что только "диапазонные" файлы нужно делать не по 2ГБ, а поменьше. Иначе они потом не загрузятся в оперативку 4 ГБ.
И в "склеивании" нету никакого подвоха. Если только ты считаешь "подвохом" возможное отсутствтие в конце файла знака "конец строки" smile.gif Тогда да - будет подвох. Но только он, других не видать.

В сенсе "знака в конце строки"?
Ты имеешь ввиду конец файла?
Или обычный \n ?


_____________
"Нужно быть готовым прислушиваться к тем, кто может тебя чему-нибудь научить. Иначе ты никогда не вырастешь."

Откровенно я никому ниразу не нагрубил. А дать подзатыльник зарвавшемуся юнцу, так это и ему на пользу, и мне в удовольствие. © AllesKlar
Быстрый ответ:

 Графические смайлики |  Показывать подпись
Здесь расположена полная версия этой страницы.
Invision Power Board © 2001-2024 Invision Power Services, Inc.