Теперь это уже не важно :)

Для вакансии разработчика Яндекс.Браузера?

«хорошее знание С++ и STL;» «знание классических алгоритмов и структур данных;»

Задача подходит.

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

Вранье от человека, который Яндекс.Браузер не видел.

Рано забанили. По-моему, в данном топике было всё в пределах допустимого.

У меня ничего не встанет, а вот щитство, которое написали щитстверы до меня - да.

Вот как вы любите аргументы, аля «завтраповолжшебству он превысит размер», которые работают лишь в вашем мире, где 1вменяемый человек на сотню ушлёпков. И то этот человек далеко не скиллед.

Канечно со среднем уровнем «днище поддонное» вы ничего вменяемого не запилите и для вас будут существовать такие аргументы.

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

Я запилил как анскиллед лишь потому, что авдруг станет 100гигов, а вдруг 1тб. А если станет 1тб - ты будешь тысячу лет ждать свою сортировку? Тотальная термальная стадия интерпрайза головного мозга.

Кто меня забанил, хоть выйди покажися, либо напишите мне имя этого отца. Лор должен знать своих гереов.

Ну не знаю. Ладно бы в срач врываться со щитами, но в ламповый дневной тред про сортировку — это ж кем надо быть. Все правильно сделали.

Вот как вы любите аргументы, аля «завтраповолжшебству он превысит размер», которые работают лишь в вашем мире, где 1вменяемый человек на сотню ушлёпков. И то этот человек далеко не скиллед.

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

А если станет 1тб - ты будешь тысячу лет ждать свою сортировку?

Почему тыщу? Предложенный алгоритм линеен и отлично масштабируется. 1тб для него это семечки.

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

А ну да. Как 5лет назад http отдавалка на сишке выдавала 100тонн r/s на ведре - так и отдаёт, но вы всё время изобретаете что-то новое и я в вас так верю. У вас растут какие-то нагрузки, какие-то новые данные. Откуда они берутся?

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

У вас тысячи проблем, какие-то текстовые файлы - которые хранят дату текстом - ну да, хайлоад нахрен.

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

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

Вы всё дальше и дальше от перфоманса вашего железа, хотя вы должны приближаться к нему. Где прогресс? А его нет - лишь жалкие оправдания и бесполезности.

Почему тыщу? Предложенный алгоритм линеен и отлично масштабируется. 1тб для него это семечки.

Не смеши мои тапки - там до ленейности как до луны пешком. И да, один пункт этой линейности даже не 1/100 от моей реальной линейности.

Если не ошибаюсь, тут у кого-то на 4г около 10 минут ушло. Кот представлен.

Откуда они берутся?

Интернет растет, число пользователей растет, данных генерируется всё больше и больше.

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

Вот именно, тысячи проблем и вместо того чтобы их решать ты придумываешь как упаковать один конкретный текстовый файл. Зачем это делать, если проблему можно решить проще?

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

Естественно, всё учитывается, поэтому твое решение не подходит, так как оно сложное, одноразовое, не масштабируемое.

И да, один пункт этой линейности даже не 1/100 от моей реальной линейности.

У тебя n*log(n), а с учетом влезания рано или поздно в swap, получается всё совсем печально, о какой линейности может идти речь?

Перечитал тред - ничего не нашел - один щит.

Ну тогда ладно.

Интересная задача. Кто знает правильный подход скажите, три часа на написание (если на написание, а не саму сортировку) - это к чести Яндекса или нет?

Моё решение, наверно самое тупое в треде, притом не факт, что успеющее отработать за вменяемое время, но потребляющее памяти около надобной на 3-5 строк, такое: подсчет строк исходника, создание равного по размеру выходного файла, запись первой строки из исходника в середину выходного, дальнейшее попеременное сравнение считанной строки с головой/хвостом выходного двигаясь к центру до нахождения позиции, затем сдвиг всей головы или хвоста на одну строку ближе к началу/концу файла, для освобождения места под запись только что определившейся, ну и так по новой, со всеми.

O(n^2). Учитывая, что n порядка 80 млн, как ты думаешь, когда закончится выполнение?

Может у Яндекса диски быстрей оперативки и процы звери...

Если нет, тогда 16 отсортированных временных файлов-массивов по 256М. Загрузка, слияние с сортировкой, выгрузка одного из. Загрузка, слияние с сортировкой другого... В памяти храним самые младшие+старшие строки (граници массивов), по ним выбираем файлы на слияние. Как-то так, хз, может и так не отсортирует.

Кстати, обратите внимание, как закукарекал наш петушек. Нарочитые нелепые ошибки исчезли, осталась обычная безграмотность. По последним постам, где он изливает свою боль, видно, что чувак не молодой, наверное ему лет под 40. Си «программист». Писал всю жизнь под микроконтроллеры, дрочил байты, а теперь никому не нужен вместе со своими «оптимизациями». Даже базовых навыков нет: это стало очевидно после его говномакроса foreach, который течёт как решето. Понимания алгоритмической сложности - нет; зачем она, если в контроллере 2К пзу и несколько портов? Теперь оказался на помойке жизни и пытается чесать своё пошатанное ЧСВ унылым троллингом на лоре. Жалкое, но поучительное зрелище.

А ведь он в прошлом был лиспанутым.

ни одного программиста на моём лоре... впрочем, неудивительно

Проверяемые заданием скилы:

1. Способность узнать алгоритм по задаче — внешняя сортировка. Для этого и просят сначала сказать что ты собираешься делать — чтобы время на тебя зря не тратить.

2. Опыт реализации конкретного алгоритма — выдумывать велосипед по ходу пьесы — за три часа сложно успеть.

3. Способность писать рабочий код.

// анон, который когда-то давно работал в яндексе

Тупые хантеры не умеют поставить задачу. Вот потому яндекс и не гугль.

Кто меня забанил, хоть выйди покажися, либо напишите мне имя этого отца.

Блокирован 12.06.2013 23:20:45, модератором mono по причине: Систематическое нарушение правил

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

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

в google docs-е и то только на первых собеседованиях.

Т.е. предназначение задания — отсеять дебилов?

К этому этапу подходят совсем немногие, а после него не остаётся почти никого.

Жизнь сурова и несправедлива, да.

Жизнь сурова и несправедлива, да.

а после него не остаётся почти никого.

Да нет, вполне справедлива, получается.

Это было лет 7-8 назад. С тех пор что-то могло измениться.

Но не их дурацкое расположение в дефолтном городе.

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

real	0m20.492s
user	0m11.800s
sys	0m1.152s
~$ du -h big.txt
873M	big.txt
~$ du -h out.txt
873M	out.txt
~$ wc -l out.txt 
18112437 out.txt
~$ wc -l big.txt 
18112437 big.txt
~$ cat 1.cpp
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <vector>
using namespace std;

#define BUF_SIZE 360 * 1024 * 1024
#define LINE_MAX_SIZE 65536
	
struct chunk
{
	chunk( FILE* f ) : f_( f ) { line_ = (char*) malloc( LINE_MAX_SIZE ); }
	bool pop_line( void ) { return fgets( line_, LINE_MAX_SIZE, f_ ); }
	
	FILE*	f_;
	char*	line_;
};

int main( int argc, char** argv )
{
	char*	 buf	= (char*) malloc( BUF_SIZE );
	char*	 end	= buf + BUF_SIZE - LINE_MAX_SIZE;
	FILE*	 in	= fopen( argv[ 1 ], "rb" );
	char*	 line   = buf;
	
	vector<chunk>	chunks;
	vector<char*>	lines;
	
	auto add_chunk = [&]()
	{
		std::sort( lines.begin(), lines.end(), [&]( char* a, char* b ) { return strcmp( a, b ) < 0; } );

		char fname[] = "/tmp/sortA";
		fname[ 9 ] = 'A' + chunks.size();

		FILE* out = fopen( fname, "wb+" );
		for( char* s : lines )
			fwrite( s, strlen( s ), 1, out );

		chunks.push_back( out );
		fseek( out, 0, SEEK_SET );
		line = buf;
		lines.clear();
	};
	
	while( fgets( line, LINE_MAX_SIZE, in ) )
	{
		lines.push_back( line );
		line  += strlen( line ) + 1;
	
		if( line >= end || lines.size() >= 8000000 )
			add_chunk();
	}
	
	if( lines.size() )
		add_chunk();
	
	FILE* out = fopen( argv[ 2 ], "wt" );
	for( chunk& c : chunks ) c.pop_line();
	
	while( chunks.size() )
	{
		std::sort( chunks.begin(), chunks.end(), []( const chunk& a, const chunk& b ) { return strcmp( a.line_, b.line_ ) > 0; } );
		fwrite( chunks.back().line_, strlen( chunks.back().line_ ), 1, out );
		
		if( !chunks.back().pop_line() )
			chunks.pop_back();
	}
	
	fclose( out );
}

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

А просто засунуть в базу построить индекс и проселектить низя ?

очевидно тут не хватает:

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

-- посоветуйте простую считалку трафика

-- негр, читающий вывод tcpdump

char fname[] = «/tmp/sortA»;

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

кстати еще раз насчет ТЗ - «сортирует файл», опять же надо уточнить как именно, будет ли 9 (в конце строки) перед 10 или наоборот, т.е. сортировка зачем делается - для поиска одной записи или диапазона + выхлоп, подозреваю, что второе, но надо ж выписывать это все

О, они до сих пор сортируют...
Мне практически такую же задачу давали у них, которую я с треском провалил.

Задачку про random4 из random2 не давали?)

int random4() { return rand2() << 1 | rand2(); }

sudo cast procoder99

Зачем кастовать себя?

Я не верю, что он хоть что-то писал. По мне чувак молодой, лет 13. Прочитал про C в ксакепе.

Я фигею, кто-то ещё и код тут начал писать. Я бы меньше чем за 200$ не сел, хотя и не программист, лол

Долго втыкал, при чем тут собес (социальное обеспечение). У ТСа дислексия.

а вопрос в чем?

Вот этот мужик знает как это сделать http://neopythonic.blogspot.co.uk/2008/10/sorting-million-32-bit-integers-in-...

Написать ф-ию, которая равновероятно и случайно выдает числа от 0 до 3, имея ф-ию rand2 - которая случайно возвращает 0 или 1.

Иди лучше выспись, лингвист-анон.

Ты больной. Тебе поможет только эвтаназия.

даже в этом критерии анон из прошлогоЯндЭкса показал свою низко...

не поняв устойчивого анохронизма «сортировка на лентах» имени Кнута

ээээ?

чё правда чтоли?

т.е такой простатой эффективно срезать?? тем более на сях

не так конечно красиво битно

return rand2()?2+rand2():rand2() :)

Кто бы уберёг хрупкую психику одного анона от заглядывания в «прощай самооценка» Кнута, разложив на пальцах как, что и сколько тасовать по методу великого «на лентах», при заданных в ОП условиях...

Я че-то не понял, а где лиспохаскелисты с решением «за пять минут и в три строчки»? Уже пять страниц, а ни одного решения не представили. Только кукарекать и могут, а как доходит дело до практики — позорно сливаются.

Я че-то не понял, а где лиспохаскелисты с решением «за пять минут и в три строчки»?

Да пожалуйста:

(sort-it)

Это eDSL на Лиспе. Остальное легкотня и не стоит драгоценного времени лиспера.

дык выше вообщето по ссылкам есть всё.

а если конкретно из кнута то ссылки из вот этой задачи:

задача 5.5.3 (37 бальная) на стр 424 второго издания

ну и решение на странице 746 даёт решение Прата и несколько ссылок на мохнатые публикации

но вообще выше уже дали хорошую ссылку и вроде даже тут на пальцах обьяснили как сливать два разноразмерных последовательности на месте используя если есть свободную память (т.е вроде прям непосредственные цитаты из тимсорта в части адаптивности )

Учитывая что операция получения случайного числа операция не тривиальная, и, как правило, довольно трудоёмкая можно сделать вывод, что ваше решение, которое использует 3 вызова функции random2 вместо 2х, как предложено выше, бесспорно лучше!