Написать сортировку файла за 3 часа (брутал-собес)

Написать сортировку файла.

Что в твоём понимании сортеровка файла?

superuser@yandex.ru 2010-12-02T13:30:12 11245
vasya@gmail.com 2011-03-25T00:00:02 88765
superuser@yandex.ru 2010-12-02T13:40:15 11244

Я не вижу тут utf-8, а так же что за даты, что за идентифакторы - авось у тебя там бигнумы.

У вас в распоряжении есть 512 Мб памяти.

С чего это? Почему ваши распоряжения всегда бреданосны.

Прежде чем приступить к реализации, расскажите, пожалуйста, детали алгоритма, который вы будете реализовывать.

Ну я не вижу вменяемого условия и объяснений зачем тут что-то сортировать.

~$ g++ -std=c++11 -Ofast 1.cpp && time ./a.out big.txt out.txt

real	7m30.397s
user	1m29.692s
sys	5m55.180s
~$ du -h big.txt
873M	big.txt
~$ cat 1.cpp
#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <vector>

#define BUF_SIZE 65536
FILE* in;
	
const char* getline( uint32_t pos, char* buf )
{
	fseek( in, pos, SEEK_SET );
	return fgets( buf, BUF_SIZE, in );
}

int main( int argc, char** argv )
{
	in = fopen( argv[ 1 ], "rb" );
	
	char	              buf0[ BUF_SIZE ];
	char	              buf1[ BUF_SIZE ];
	uint32_t              offset = 0;
	std::vector<uint32_t> lines;
	
	while( fgets( buf0, BUF_SIZE, in ) )
	{
		lines.push_back( offset );
		offset = ftell( in );
	}
	
	std::sort( lines.begin(), lines.end(), [&]( uint32_t a, uint32_t b ) { int c = strcmp( getline( a, buf0 ), getline( b, buf1 ) ); return c ? c < 0 : a < b; } );
	
	FILE* out = fopen( argv[ 2 ], "wt" );
	for( uint32_t pos : lines )
	{
		getline( pos, buf0 );
		fwrite( buf0, strlen( buf0 ), 1, out );
	}
	
	fclose( out );
}

а если «в распоряжении есть 512 Мб памяти» подразумевает лимит только на программу, а в наличие есть еще и disk cache, то банальный std::sort рулит и педалит

вот тебе рекурсивное описание алгоритма на функциональном бредоязыке.

start(file_in) ->
  r(file_in, 0).

r(file_to_be_sorted, row) ->
  file_to_be_sorted.length > 100MB? 
    true->
      foreach(file: filter_and_return_list_of_files_and_then_delete_source(file_to_be_sorted, row)) {r(file, row+1)};
    false->
      system("sort file_to_be_sorted > tmp && mv tmp file_to_be_sorted")
  end,
  system("cat `ls|sort` > .output.txt && rm * && mv .output.txt output.txt").

filter_and_return_list_of_files_and_then_delete_source(source, row) ->
  dict <symbol, file> ret,
  foreach (line: source.lines()) {dict.find(line.symbol(row)).writeln(line)},
  delete source,
  return ret.values.

Только он файл источника тоже удаляет.

ЕМНИП это у них типовая задача при приеме на работу. Всем ЛОР-ом туда что ли пойдем?;-)

Реально? Мне жалко тех, кто там работает.

Вот тебе пример «решения» «задач». Ниукого не возникло вопроса: «зачем?», «почему?» и т.п.

Все пишут байду ради байды, не понимая нахрена и как пишут.

http://www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

А если количество строк изначально больше квадрата количества строк помещающихся в памяти? Когда первые строки из всех отсортированных файлов не влезут в память.

бля, началось

лор, не ведись на это, умоляю

создаем древообразную структуру, где ветки - буквы алфавита. читаем строку с файла и запоминаем номер строки в древе на определенной позиции.

А ну да, пусть лучше анскиллед и дальше думает, что 1-127 - это utf8. Да, да, нахрен - это утф8. Есть что сказать?

Вот когда такие анскиллед подходят к делу и получается попец.

Им нужен utf-8 на уровне ЯП - они этм кичатся и прочее, а выходит попец.

А вы дальше пишите сортировку хренпойми чего, и 1-127 обзывайте утф8 - а я пока поржу.

я уже упоминал в треде про это. но никто не исключает хостинга почт где-то на «провайдер-почты.рф», не правда ли?

Я не читал тред - извини.

Тогда там не будет @yandex.ru, а мыло будет хранится как имя до авкружочке.

Тогда хранить их в утф тоже дебилизм, ибо есть ещё 127.

Даже тут:

superuser@yandex.ru 2010-12-02T13:30:12 11245 == superuser + id(байта 2 хватит) + дата в пределах 100лет - это ещё 4байта + идентификатор 4-8байт.

Итого 9+2+4+4 = 19/23 - уже в раза меньше, чем вес строки.

А если ещё хитрее сделать строка+offset от начала файла, а потом раскидывать их по пуллам(допустим как говорили пацаны выше a-z) - это будет 1+sizeof(str)+4 - т.е. в данном случае это 14байт на строку, что уже меньше 1/3 от сайзфоа файла.

Т.е. реально можно с 1/3 от длинны файла написать достаточно быструю сортировку. Для утф8 уже максимум за 1/6, если за пределами ascii.

Если хранить это всё во вменяемом формате, а не щит как сейчас и говорить зачем там идентификаторы( с вероятность 99% их можно выкинуть нахрен).

Вобщем задачка для щитстеров от щитстверов - тотальный анскиллед, а решения пацанов просто щитстизм.

Два чая мне за это.

Это ЛОР. Тут могут предложить только стопку царской водки и бутерброд с рыбой фугу.

// виноват, да. Это tazhate'у предназначалось.

Это у тебя такое домашнее задание для допуска к собеседованию? А ты думаешь, что в Яндексе не читают лор? :)

в распоряжении есть 512 Мб памяти

Это значит, что оперативки всего 512M. Твоя программа работать не будет.

Это значит, что оперативки всего 512M. Твоя программа работать не будет.

будет, еще и останется памяти свободной

1 лови правильное решение не использующее ни байта дополнительной памяти ( платя за это правом переписывать input.txt)

1. читаем 8-9 кусков по 512МБ(по факту чутка меньшье поэтому и получается 9 - а вообще для красоты куски пусть будут по 128M)

итак читаем кусок 128M ( полных строк сортируем в памяти любым nlongn - и перезаписываем ровно в тоже место откуда читали(можно конечно и тут(если разрешено по условиям) перевести все три поля в этолоные(мыло малыми), время как целое , id как целое(уточнить если вообще для id ограничения на макс значение или это по сути бигинт) - отсортировать вывести разделяя по пробелы между полями ( в этом случае мы можем получить кучу пробельных в конце - но эт уже..))

2.

по завершению 1 этапа имеем 32 куска - теперь мерджем через память и пишим . так до 8 кусков по полгига.

3. вот тут небольшое затруднение - исползуем восьми путевое слияние - т.е читаем из каждой из 8 частей по скажем 32(т.е у нас всего 64 таких куска)меговые куски .... - короче см кнута сортировка на месте с конст. памятью.

У тебя файл в кеш не влезет, ты будешь бегать по диску, тормозить будет аццки. В общем, это далеко не оптимальное решение.

прочитал некоторое число строк - это прочитал определёное число байт у которого на конце перевод строки

отсортировал в памяти - и записал по тому же смещению тоже число байт.

думаю всю решение это сортировка скажем 256М кусков в памяти. по смешению кратном 256M = это типо подготовительный этам

а затем эдак 16 последовательных «пузырьков»(где в качестве элеменарного действия над двумя соседними элементами размера в четверть гб есть их мердж в памяти и запись младшей части) - тогда 16? от 1 до 16,от 15 до 1 от 2 до 15 ....

отвечай тред сразу @ читай не

У тебя файл в кеш не влезет, ты будешь бегать по диску, тормозить будет аццки.

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

У меня встречный вопрос: какой мудофил хранит такие данные в текстовом файле? У них в яндексе про индексированные БД ещё не слышали? Оказываю консалтинговые услуги, дорого, пускай пишут в личку.

Вроде бы на третьей странице стало можно.

ээээ сколько есть места под «temp» в файловой системе если не меньше 4 ГБ то

1. этап - упорядочиваем полулиговые 8 кусков в памяти любимым nlogn. 2. 8->4->2->1 то биш 3 прохода мерджсорта

итого 4 прохода прочитано/записано на файловую систему 16 гигов размер дополнительно использованой памяти 8? гб.

Данные могут быть разнородными и их может быть петабайты. Ты про map/reduce что-нибудь слышал? Могу оказать тебе консалтинговые услуги, дорого, пиши в личку.

а чё?

И петабайты разнородных данных они держат в текстовыйх файлах, которые надо периодически сортировать? Дивно.

Ты седьмой кто врывается итт с merge(quick). Или восьмой, уже не сосчитать.

В данном случае нет разницы между бинарными и текстовым, но с текстом проще работать из скриптов на перле и питоне. Почитай про hadoop streaming, например.

Ваш вариант, сударь, уже подробно обсудили, причём, в намного более внятной и конкретной форме, с асимптотикой и возможными деталями. «Разбить, отсортировать в ОЗУ и смерджить» предложили, если мне не изменяет память в 3 или 4 комментарии.

Я уж молчу, что сабжевая решается с помощью sort -S 512M. Предоставлю исходные тексты GNU coreutils, гарантия, дорого.

И что? Задача нужна, чтобы отсеять тех кто не читал Кнута или не может сам придумать алгоритм, а также тех, кто не в состоянии написать пару десятков строк кода. На Си это пишется за 15 минут, 3 часа — очень хороший запас.

Я о том, что такие данные надо сразу складывать в подходящее хранилище, а не сортировать текстовые файлы. Если вакансия связана с big data, то ок, пускай бы задавали вопросы о map-reduce, структурах данных для хранилищах и т. д. А сабжевая задача вообще о чём?

Отсеивать надо тех, кто кидается писать свой велосипед на С, не потрудившись даже выяснить, что задача давно решена.

http://www.catb.org/~esr/writings/unix-koans/ten-thousand.html

ну если в одну школу/универ ходили - одно и тоже решение и приходит на ум.

как обычно - пока можем в памяти - как не можем слияние на лентах

если же офигенно прокачан скил на третьем тому кнута то сразу реализуем сортировку на ленте с буфером в 1/8 этой ленты .

ты поднял мне веки

Это же просто задача, она не может быть поводом для недовольства. Кто может ее решить во всех деталях, очевидно способен решить и другие задачи такого класса. А что мир неидеален, это надо просто принять.

Я уж молчу, что сабжевая решается с помощью sort -S 512M. Предоставлю исходные тексты GNU coreutils, гарантия, дорого.

Два кофе этому господину.

И что? Теорема Пифагора тоже давно доказана, зачем её еще раз доказывать в школе? Специалисты, которые вызубрили 100500 рецептов на все случаи жизни, но не умеют сами мыслить наверно где-то требуются, но видимо не на вакансии на которую ходил устраиваться топикстартер.

Вроде бы на третьей странице стало можно

ну значит тогда очевиден подходящий алгоритм сортировки :)

Слияние... на лентах... А что если порезать и склеить, это ведь и буфера не надо!?

Если в целой фирме не нашлось ни единого человека, способного придумать разумную задачу, то это тревожный симптом. Дальше что, задачки про канализационные люки и про монетку в блендере?

Почему сабжевая задача не разумная? Приведи пример разумной задачи.

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

Как я уже говорил в мыле максимум символов 30 - первы символ нам не нужен, в среднем 4бита на символ в самом ущербанском представлении + 4байта на оффсет от начала файла.

Строка «superuser@yandex.ru 2010-12-02T13:40:15 11244» из почти 50байт в ascii превращается в 8байт(4бита на символ, выкидывая первый).

Дальше ты эти представления записываешь в a-z пуллы, потом сортируешь каждый пулл и записываешь во второй файл(читая строку с таким-то оффетом из первого файла и пишешь во второй).

Если тебе не нравится рандомное чтение по 50байт 4гигигового файла - ты можешь сделать индексацию - это ещё 4байта на елемент, чтобы читать последовательно.

И того в среднем можно реально уложится в 1/4 файла.

А то, что вы предлогаете - есть банальный, тормазящий щит.

У тебя получилась немасштабируемая ересь, да еще и преждевременная оптимизация с игрой на битах и байтах. Сложные вещи в highload обычно не живут :)

Ты до места с хаффманом еще не дочитал видимо. Вот там реально можно выжать и 3-4 байта вместо 8-ми.

А если еще и битовый поток сжимать, то на 512 метрах можно хоть два таких файла за раз сортить.

А она не должна быть масштабируемой - для этого есть sort из кореутилс.

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

И это не предждевременная оптимизация - это не оптимизация - это запил реальной задачи. Если тебе нужно универсальное щитство, то так и пиши в задаче - я пройду мимо.

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

Поэтому аргументы не относятся к делу и является обычным деревенскоинтерпрайзным шаблоном.

Для вакансии разработчика Яндекс.Браузера? Учитывая, что Яндекс.Браузер не нужен, разумную задачу придумать сложно, лол.

Но какое вообще отношение к браузера имеет сортировка больших данных? Там могут быть задачи про сокеты и протоколы, про DOM и деревья в целом, про многопроцессные вычисления. Вообще-то из реальной работы берутся задачи для собеседований. Просто их реальная работа - перепиливание логотипа, вхреначивание яндекс.зондов и сборка инсталлеров под венду. Че-то, видать, на собеседовании об этом говорить стесняются.

Ты не запилишь вменяемого хафмана без констекста - тебе надо будет глядеть файлец, либо ты зафейлишь с шансом 50%.

Плюс хафман намного тормазнее, да и не нужен тут.

В хайлоадах люди ничего не сортируют, никаких текстовых файликов в таком ущербанском «формате» не хранят

Тебя обманули.

И это не предждевременная оптимизация - это не оптимизация - это запил реальной задачи.

Только с указанными ограничениями, если что-то сдвинуть, то твое решение вдруг перестанет работать.

Если тебе нужно универсальное щитство, то так и пиши в задаче - я пройду мимо.

Щитство это то что делаешь ты. Если вдруг завтра размер данных превысил критический размер и система встала раком, то ты будешь просыпаться ночью и всё срочно переписывать на «универсальное щитство»?

ваша реализация будет в 20раз сложнее моей.

Вранье.