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

~40 из предположения, что один и тот же пользователь не делает запросы 1 раз в секунду, иначе целая строка. Я не уверен, что это верное предположение, а имя юзера ~20 символов. Все равно я твой подход совершенно не понимаю, честно.

А задача на какую должность?

http://company.yandex.ru/job/vacancies/dev_browser.xml

Уточняющий вопрос: последние строчки,

[XYXYXYXYXYXYXY][ZKZKZKZKZKZKZKKZ][LLLLL]
[XYZKXYZKXYZKXYZKXYZKXYZKXYZKXYZK][LLLLL]

это уже на диске?

к слову, подозреваю, что я последнюю фазу сортировки бы за 3 часа не написал :) и сначала бы сделал халявный вариант.

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

один и тот же пользователь не делает запросы 1 раз в секунду, иначе целая строка

У меня сомнения что это логи доступа. Больше похоже на дату регистрации и id.

Все равно я твой подход совершенно не понимаю, честно.

Мы берём частичный индекс чтобы он влез в память и сортируем им.

Потом вторым прогоном исправляем то что не отсортировалось.

Благо я пока не сишнек, алгоритм ниже можно зафигачить хоть на перле/питоне/руби :)

http://www.daniweb.com/software-development/cpp/threads/430160/how-to-sort-th...

If your sort key is short, you can loop to
 1a) remember line position (ftell)
 1b) read line
 1c) extract the key
 put both key & position in a structure array
 Now sort the structure
 Read each line from the the line position (fseek) and write the sorted file.

I used this technique and it was quite fast, even with reading the file twice.

Это о чём пишет true_admin.

1c) extract the key

Не подойдет: size(key)==size(line)

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

Т.е. да, на последнем этапе это сортировка пузырьком. Можно более продвинутую эвристику, но тут уже можно багов наплодить. А так алгоритм такой: находим неотсортированный блок данных, выгружаем в память, сортируем, вгружаем обратно. В блок данных входит всё что имеет одинаковый префикс, поэтому найти его не проблема.

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

То есть в худшем случае - O(n^2)

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

Грубое описание алгоритма: 1). mmap-им начало первого и второго блока в память, выделяем место под рабочую зону и будущий результат. 1). сравниваем X0 и Y0, меньшее кладем в зону результата, сдвигаем соотв указатель. Если нужно переложить Y0, то если X0 помещается, то кладем его вместо Y0, иначе в рабочую зону. 2). делаем тоже самое для следующего элемента итого у нас получаются следующие зоны: [Q(сортированный список)][A(1-ый-список)][B(перемещенный-1ый-список)][C(2ой-список] ++ [D (рабочая область)]

где Q A B C D сортированы, q<b<d<a<c.

Как-то так, в целом тут или читать статью надо или писать, но нужно работать.

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

Сливать можно не по два, а умнее, вести отсортированный список текущих элементов каждого файла, тогда за один проход все файлы сливаются тратя O(кол-во файлов) памяти, но тут алгоритм будет хитрый, возможны баги, за 3 часа в нервной обстановке делать бы не стал.

Там over 200 млн данных которые были сгенерены миллионами рандомных юзеров. Откуда там худший случай?

Ну а так спорить бессмысленно, можно подобрать такой датасет где то что я предлагаю вообще никогда не досчитается. Это мне напоминает hash collision attack типа такого: http://mail.python.org/pipermail/python-dev/2011-December/115116.html

Ну или суровый метод - ставим 64-битный линукс, накатываем свопа over 9000 и сортируем std::sort-ом :) Если бы строки были фиксированной длины, можно было бы вообще за-mmap-ить и in-place отсортировать :)

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

Сливать можно не по два, а умнее, вести отсортированный список текущих элементов каждого файла, тогда за один проход все файлы сливаются тратя O(кол-во файлов) памяти, но тут алгоритм будет хитрый, возможны баги, за 3 часа в нервной обстановке делать бы не стал.

по 2 это практически самое умное, т.к. в этом случае будет выстроено сбалансированное бинарное дерево слияний, особенно если блоков 2^N.

Если поймешь хацельную нотацию, то вот:

mergeList = head .go 
  where
    go [] = []
    go [x] = [x]
    go (a:b:[]) = a `merge` b
    go (a:b:c) = go (merge a b: go c)

Предполагается что 512 Мб без свопа. Закончилась память - лови Out of Memory exception

по 2 это практически самое умное, т.к. в этом случае будет выстроено сбалансированное бинарное дерево слияний, особенно если блоков 2^N.

Дерево слияний не обязательно должно быть бинарное. Если по 2, то будет log2_N итераций, пока не получится конечный результат. Если все сразу сливать в 1, то за 1 итерацию уложимся.

Стоимость merge sort против других алгоритмов: http://en.wikipedia.org/wiki/Timsort#Performance

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

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

не в этом вопрос: я могу писать в новый файл или нет?

Да. Разрешено все, что не запрещено)

merge sort на ява и на scala (ниже в комментах):

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

P.S. Зачем давать такие задачи, когда их уже решили другие? :)

сложность итераций сможешь посчитать? + если дело должно быть inplace, то сложность будет слишком большой.

Не, Trie не подойдет. Т.к. в худшем будет N^average_length по памяти. Т.е. где-то N^20, где N - размер алфавита. Подошел бы если было много одинаковых префиксов, а поскольку это условие не известно из описания задачи, то может быть пролет.

тут вопрос в разрешенности использования доп дисковой памяти, плюс 1-2 можно сделать inplace, без создания кучи файлов :)

Т.к. в худшем будет N^average_length

Да нет же. Необязательно всё имя пихать в дерево. Достаточно нескольких первых символов и каждый отдельный файлик уже с лихвой поместится в память!

Грубое описание алгоритма ...

Если я правильно понял (а это не очень просто в таких ситуациях), то это описание merge.

Если так, то это не inplace, т.к. рабочая зона растёт линейно.

inplace_merge c O(n^2) - это тупо сортировка вставками, (ну, понятно, что интереса не представляет).

inplace_merge c O(n log n) - красивый метод с применением «разделяй и властвуй.» Дано: вектор, содержащий 2 упорядоченные последовательности; индексы начала, конца, середины - известны.

1) Выбирается средний по позиции элемент в первой последовательности.

2) Во второй делением пополам ищется этот же элемент (или самый близкий).

3) Кусок между серединами циклически сдвигается таким образом, что вместо двух упорядоченных последовательностей получаем 4 упорядоченные последовательности:

(упрощенный пример)
[12445689ACCDF0125699BBDF] =>
6, 6 =>
[1244560125689ACCDF99BBDF]

4) Две пары упорядоченных векторов рекурсивно сливаются. На маленьких размерностях - выход из рекурсии - swap.

Ну, понятно, что если всё это добро на диске, то получим O(n log n) io операций.

inplace_merge c O(n) - очень красивая тема, но довольно объемная в описании.

tl;dr, но может кому-то интересно...

А, ясно. Только не понятно как мержить потом все деревья, чтобы памяти хватило.

тогда:

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

2). сохраняем отступы начала строк

3). сортируем qsort-ом индексы

4). выделяем новый кусок памяти в который поместится остортированный файл

5). складываем в него данные в соответсвии с отсортированными индексами.

6). записываем отсортарованныей данные назад, сохраняем отступ на отсортированные данные, и конец данных.

7). повторяем с п.1 до тех пор пока ещё есть данные в файле

8). мержим данные в новый файл

8.1) находим минимальную первую строку, кладем в новый файл, инкрементируем отступ.

PROFIT

https://github.com/abudnik/extsort

тут вопрос в разрешенности использования доп дисковой памяти, плюс 1-2 можно сделать inplace, без создания кучи файлов :)

В задаче этого не оговорено. Понятно, что надо использовать либо создание файлов, либо 100500 раз перечитывать файл. И тот и другой вариант имеет свои плюсы и недостатки.

Та-Да) Только написал это за 7 часов в сумме

Если так, то это не inplace, т.к. рабочая зона растёт линейно.

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

inplace_merge c O(n log n) - красивый метод с применением «разделяй и властвуй.» Дано: вектор, содержащий 2 упорядоченные последовательности; индексы начала, конца, середины - известны.

а никакой ссылки на статью нет, на досуге почитать?

кто написал, что написал? Если про меня, то я это решение предложил с 2-ой минуты чтения топика, а дальше извращался с мыслями про inplace, в предположении, что диск трогать нельзя :). За сколько бы я написал - хз, наверное за 3 часа бы не успел, тем более на плюсах, тем более на чужом рабочем месте (а если без доступа к man интернету, то совсем бы плохо было).

Никак. Из-за дерева ты уже отсортировал всё на макроуровне. Тупо пишешь файлики друг за другом

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

Ок, если будет время и желание, напиши свое решение, будем меряться пиписьками (мой external mergesort 4гига за 10 минут сортирует) :)

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

Я так пробовал, когда игрался с merge_sort. При такой эвристике - получится O(n^2), что было на первый взгляд неожиданно )))

а никакой ссылки на статью нет, на досуге почитать?

Вроде как общее место; я сначала придумал сам, потом посмотрел в плюсах, понял, что не учёл один момент, и потом долго думал как сделать O(n) inplace_merge (уже прочитал, что это возможно).

/usr/include/c++/4.7/bits/stl_algo.h::__merge_without_buffer

Там много ещё интересного в этом файле. Кстати std::inplace_merge несмотря на своё название сначала пытается выделить какую-нибудь память (пропорциональную N), слить в неё, а уж после неудачи вызывает Ъ inplace_merge!

O(N) inplace_merge я так и не придумал, но решение очень красивое.

А памяти сколько требует?

https://github.com/abudnik/extsort

натравил на http://norvig.com/big.txt, результат:

sorting finished...

real	0m9.043s
user	0m6.192s
sys	0m0.212s
~$ du -h big.txt
6,2M	big.txt
~$ du -h out.txt
257M	out.txt

мало того, что содержимое размножило до 257Мб, так еще и внутри ничего и не отсортировано

~$ 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;
	
	char buf[ BUF_SIZE ];
	while( fgets( buf, BUF_SIZE, in ) )
	{
		uint32_t new_offset = ftell( in );
		
		auto pos = std::lower_bound( 
			lines.begin(), lines.end(), offset,
			[&]( uint32_t a, uint32_t b ) { int c = strcmp( getline( a, buf0 ), getline( b, buf1 ) ); return c ? c < 0 : a < b; } );

		lines.insert( pos, offset );
		fseek( in, offset = new_offset, SEEK_SET );
	}
	
	FILE* out = fopen( argv[ 2 ], "wt" );
	for( uint32_t pos : lines )
	{
		getline( pos, buf0 );
		fwrite( buf0, strlen( buf0 ), 1, out );
	}
	
	fclose( out );
}

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

real	0m1.857s
user	0m0.692s
sys	0m1.164s
~$ du -h big.txt
6,2M	big.txt
~$ du -h out.txt
6,2M	out.txt
~$ wc -l out.txt 
128457 out.txt
~$ wc -l big.txt 
128457 big.txt

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

П.С. хотя проигрывает наверняка из-за мусора в конце выхлопа

256 + 32 Мб. По «ps aux|grep sort» не более 360 Мб.

Входной должен называться input.txt, а на выходе размножило, но посортировало (там в начале пустые строки) - отсортированные данные в конце.
Я уверен, что это не единственный баг.

Входной должен называться input.txt

я в коде изменил на big.txt

а на выходе размножило, но посортировало

неа

попробуй big.txt увеличить до нескольких Гб :)

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

Я бы фильтровал строки по первому символу и сохранял бы каждое отфильтрованое значение в файл с таким же именем. Далее, если, допустим, файл имеет размер больше 100МБ например, то делил бы его по второй букве и т.д. пока не будет файлов размером больше 100МБ. Потом отсортировал бы каждый файл и объеденил бы по порядку.

Для этого потребуется только лишь ещё 8ГБ свободного места на диске под файлы.