Здравствуйте, elmal, Вы писали:
Тё>>Честно говоря, я бы наверное задал встречный вопрос- у вас что, есть прецеденты? Ибо работать с говнокодерами я не нанимался. E>Есть прецеденты. Буквально несколько дней назад поймали дремавший 2 года баг в производительности. Который даже близко не связан ни с каким О, там с логгером проблемы были.
Не нужно некомпетентность в алгоритмах прикрывать ссылками на какой-то говнокод и неспособностью писать одновременно быстрый и расширяемый код.
E>И кстати о говнокоде. Именно максимально оптимизированный код (рассказываю, так как ты с таким не сталкивался, и не факт что столкнешься) — это с точки зрения человека лютый ужас. Он нечитаем совершенно, там бешенное количество коментов, там тронешь в одном месте, отвалится в другом или дичайшим образом просядет производительность.
Это было давно и неправда. Когда компиляторы были простыми, процессоры медленными, целые стеки протоколов писались на макросах, дабы простейшие операции инлайнились. Но даже в таком случае вот это "там тронешь в одном месте, отвалится в другом" уже никакого отношения к оптимизации не имело.
Здравствуйте, AleksandrN, Вы писали:
AN>>>Обходим дерево в файле-индексе, читаем каждую из исходного файла запись, соответствующую записи в файле-индексе и записываем её в новый файл. Тё>>Вы когда обходите дерево на диске, структура этого дерева определяет порядок обхода. Т.е. если вы представили исходный файл, как бинарное дерево- при его обходе вы получите ту же последовательность.
AN>>>Записи в новом файле окажутся отсортированными. Тё>>Нет.
AN>Пример: AN>Пусть в исходном файле поля, по которым производится сортировка имеют значения: AN>20, 12, 15, 23, 2, 43, 11, 35, 54, 1, 8, 14 AN>Читаем исходный файл стоим бинарное дерево: AN>читаем 20, дерева ешё нет, помещаем 20 в вершину; AN>читаем 12, в корне 20, значит 12 должно быть в левом поддереве, его нет, значит 12 будет левым потомком вершины AN>
AN> 20
AN> /
AN>12
AN>
AN>Читаем 15. Идём в левое поддерево — там 12, значит дальше идём вправо AN>
AN>Обход дерева слева направо даёт AN>1 2 8 11 12 14 15 20 23 35 43 54
1) Tree sort подразумевает работу в памяти. У вас 8гб памяти в системе (всего), и громадный файл на диске. Поэтому ваше решение не подходит. С тем же успехом можете запихать в std::map (TreeMap) файл 120гб, и потом проитерировать. Good luck with that.
2) Банальный heap sort по факту строит дерево на стеке, и использует меньше памяти. Не говоря про qsort.
Здравствуйте, Nuzhny, Вы писали:
N>Я как раз рассматриваю эту часть, как одну из самых важных. Что надо от кандидата? Чтобы он делал работу. Как узнать, что он сможет её делать? Узнать, как он справлялся ранее.
У бывших коллег в Б. опыт — покруче чем у меня, можно подумать я там вообще случайно оказался. А на ревью они ждали, чтобы я им выслал правильный ответ и они его вставили. Так какой смысл это читать и слушать басни Крылова?
N>Поэтому я стараюсь расспросить что, как и почему он использовал, если была математика, то про формулы мат. модели.
Я бы с удовольствием отложил свой детсад в сторонку и послушал про матмодели, посмотрел на формулы, которые он будет рисовать на доске. Но, к сожалению, таких не попадается, да и если придёт к нам (дал бы pass неглядя)- что ему у нас делать? Заскучает. Лучше в гугл наверное.
N>Иногда выясняется, что кандидат наук не может рассказать о том, что делал в кандидатской. Или как работает модуль, который он разрабатывал. Как бы он хорошо ни решал простые задачи, но зачем нужен поверхностный человек? Или какая разница, что человек никогда не использовал внешнюю сортировку, если он может разобраться с тонкостями сетевых протоколов?
Нам нужны хорошие люди. "тонкости сетевых протоколов"- это просто инфа про сетевые протоколы. Примерно как "номенклатура болтов и гаечных ключей для косилки комбайна Дон".
N>Кажется, что 1-2 задачек хватит.
Перевернуть порядок слов и внешнюю сортировку. Наверное. Трабла в том, что не могут перевернуть даже порядок букв.
Здравствуйте, landerhigh, Вы писали:
L>Это было давно и неправда. Когда компиляторы были простыми, процессоры медленными, целые стеки протоколов писались на макросах, дабы простейшие операции инлайнились. Но даже в таком случае вот это "там тронешь в одном месте, отвалится в другом" уже никакого отношения к оптимизации не имело.
Здесь не в компиляторах дело. В оптимизированном по максимуму коде уже не получится применять очень элегантные высокоуровневые решения. Уже забиваешь на иммутабельность, делаешь все in place. У тебя алгоритм заточен под конкретные данные, если вместо условно интов там будет строка или дробное число — приплыли, оптимизации не работают и все переписывать по другому. Начинаешь переиспользовать массивы и т.д. В случае многопоточности минимизируешь синхронизации, в идеале мечтаешь не блокировать. В результате получается весьма трудный для понимания код по сравнению с кодом в лоб. И в котором легко ошибиться. Кажется — вот нахрена так сделано, что это за фигня, это лишняя операция. Уберешь — код работает по другому. И какого то черта медленнее. Всегда есть баланс между скоростью и поддерживаемостью. Чем сильнее оптимизируешь, тем на большие тонкости приходится завязываться, тем более опасные практики приходится применять. Можно без опасных практик — но тогда ты не выжмешь ту скорость, что возможно достичь.
Тема не в теме просто потому, что никогда с таким не сталкивался на практике, он прочитал одну книжку и считает себя богом. А опыт мизерный. А прочитает ли он больше книжек когда нибудь — далеко не факт.
Здравствуйте, Тёмчик, Вы писали:
Тё>Вы понимаете теперь, для чего детсадовские задачки на интервью? Чтобы потом не выпадать в осадок от коллег.
Такие коллеги легко видны и без детсадовских задачек. В первые минуту разговора (а не экзамена). И хрен получится зубрежкой обмануть. При этом многие таланты твое собеседование пройдут путем зубрежки. Твой уровень тоже, если что, очень хорошо виден. Точнее отсутствие опыта видно невооруженным глазом. Потому то и нищебродишь даже в Австралии, по зарплате уступая россиянам.
Здравствуйте, elmal, Вы писали:
E>Здравствуйте, Тёмчик, Вы писали:
Тё>>Вы понимаете теперь, для чего детсадовские задачки на интервью? Чтобы потом не выпадать в осадок от коллег. E>Такие коллеги легко видны и без детсадовских задачек. В первые минуту разговора (а не экзамена). И хрен получится зубрежкой обмануть. При этом многие таланты твое собеседование пройдут путем зубрежки. Твой уровень тоже, если что, очень хорошо виден. Точнее отсутствие опыта видно невооруженным глазом. Потому то и нищебродишь даже в Австралии, по зарплате уступая россиянам.
Задачи на заваливание многие не решат. Если они не знают, как решаются эти задачи.
Здравствуйте, Тёмчик, Вы писали:
Тё>1) Tree sort подразумевает работу в памяти. У вас 8гб памяти в системе (всего), и громадный файл на диске. Поэтому ваше решение не подходит. С тем же успехом можете запихать в std::map (TreeMap) файл 120гб, и потом проитерировать. Good luck with that.
И прочитай ветку переписки ещё раз — в файле-индексе будут не записи из исходного файла, а значение, по которому будет проводиться сортировка и ссылка на позицию записи в исходном файле.
Как, по твоему, устроены индексы в СУБД?
Тё>2) Банальный heap sort по факту строит дерево на стеке, и использует меньше памяти. Не говоря про qsort.
Ты же сам написал, что файл 120 Гб, а памяти — 8 Гб. Может и не хватить для хранения всех нужных данных. Для сортировки кучей (heap sort), сначала нужно построить двоичную кучу. Почему ты думаешь, что такое дерево будет меньшего размера? Ты, в процессе сортировки, будешь записи в файле переставлять? И все JSON-записи у тебя одного размера будут?
Здравствуйте, Тёмчик, Вы писали:
C0x>>. Пройдя пару собеседований , ты уже можешь решить практически любую задачку из подобного списка. То есть они абсолютно бесполезны. Тё>Так ведь цель- не найти учёного-алгоритмиста, а просто программиста с зачатками интеллекта. Чтобы потом не появлялось в коде O(N!) на ровном месте.
Тема, тебе не один человек, и уже даже не намекая, прямым текстом говорят: таким способом ты не найдешь «просто программиста с зачатками интеллекта». Не, может случайно повезет, но системно — нет. Но вот ты упираешься, зачем тогда вопрос задавал?
У тебя будет полчаса, а с этими задачами ты их потратишь впустую. В общем советую тебе отказаться от проведения собеседования, сошлись на занятость, но не участвуй.
Здравствуйте, RussianFellow, Вы писали:
>>Тё3) Дан файл с integer values от 1 до 2^32-1, они не повторяются за исключением 1 дупликата. Нужно распечатать значение дупликата. Как это сделать? (код не нужен) >>Тё4) Дан файл с integer values от 0 до 1000000, без дупликатов, но значения в произвольном порядке. Как их вывести в другой файл в порядке возрастания?
Да, забыл добавить, что в обоих случаях можно использовать указатели на std::bitset (std::bitset<0xFFFFFFFF/8>* и std::bitset<1000000>* соответственно) если экзаменатор предполагает, что в записанных цифрах в файлах могут быть пропуски. (Других решений я не знаю.)
задача 3:
читаем число, записываем в i
проверяем, что по позиции i в bitset стоит 0. Если 0 — записываем 1. Если 1, то i — дубликат.
задача 4:
читаем число, записываем в i
по позиции i в bitset записываем 1.
после прочтения файла проходим по bitset с индексом k.
Если для k в bitset стоит 1, то выводим k в файл.
Здравствуйте, Тёмчик, Вы писали:
W>>А она вообще отработает, если поле по которому надо сортировать суммарно весит больше 8Гб? Тё>В этом случае, если элемент больше определенного порога, представить его как проекцию элемента на диске, с методом сравнения (не затягивая его целиком в память).
Рассмотрим файл с одинаковыми записями:
{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}
длина записи 7 байт
файл 140GB, значит нам нужно хранить 140 / 7 * 2^30 = 20 * 2^30 смещений. Каждое смещение минимум 35 бит. Удачи вам в пихивании 107 374 182 400 байтов в одну корзину размером 589 934 592 байт.
Здравствуйте, B0FEE664, Вы писали:
Тё>>В этом случае, если элемент больше определенного порога, представить его как проекцию элемента на диске, с методом сравнения (не затягивая его целиком в память).
BFE>Рассмотрим файл с одинаковыми записями: BFE>{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}{"I":1}{"I":1} BFE>длина записи 7 байт BFE>файл 140GB, значит нам нужно хранить 140 / 7 * 2^30 = 20 * 2^30 смещений. Каждое смещение минимум 35 бит. Удачи вам в пихивании 107 374 182 400 байтов в одну корзину размером 589 934 592 байт.
Вы правда не понимаете смысл bucket sort? Ведь в википедии разжёвано для третьеклассников.
Здравствуйте, Тёмчик, Вы писали:
Тё>Вы правда не понимаете смысл bucket sort?
Да.
Тё>Ведь в википедии разжёвано для третьеклассников.
Но я то не третьеклассник.
Если вам не сложно, расскажите, пожалуйста, как будет работать алгоритм bucket sort для файла размером 140GB состоящим из одинаковых записей {"I":1}, если мы пытаемся сортировать этот файл по полю "I"?
Вот вы взяли запись, распарсили значение, значение равно 1. Положили его в первую корзину. В корзине одна запись.
Взяли вторую запись, распарсили значение, значение равно 1. Положили его в первую корзину. В корзине две записи.
Взяли третью запись, распарсили значение, значение равно 1. Положили его в первую корзину. В корзине три записи.
...
Здравствуйте, B0FEE664, Вы писали:
BFE>Если вам не сложно, расскажите, пожалуйста, как будет работать алгоритм bucket sort для файла размером 140GB состоящим из одинаковых записей {"I":1}, если мы пытаемся сортировать этот файл по полю "I"?
BFE>Вот вы взяли запись, распарсили значение, значение равно 1. Положили его в первую корзину. В корзине одна запись. BFE>Взяли вторую запись, распарсили значение, значение равно 1. Положили его в первую корзину. В корзине две записи. BFE>Взяли третью запись, распарсили значение, значение равно 1. Положили его в первую корзину. В корзине три записи. BFE>...
BFE>Я правильно рассказываю начало работы алгоритма?
Затянули сколько влезло в 1 корзину, отсортировали любым библиотечным методом по вкусу в памяти (с comparator по сортируемому полю), выгрузили в выходной файл, запомнили смещение на начало следующей корзины. Затянули следующих в 2 корзину, отсортировали в памяти, выгрузили в выходной файл. Так пока весь входной файл не вычитан. Заключительный проход: создаем временный файл, создаём кольцевой буфер в памяти, создаём поле «смещение следующего элемента в выходном файле, берём fibonacci heap (PriorityQueue), (или если в C++ этого не завезли- std::map тоже сойдёт, но чуть медленнее), и считываем по 1 записи (смещение записи) + comparator на сортируемое поле, из каждой отсортированной корзины. Достаём 1 элемент из PriorityQueue (т.е. номер корзины и смещение элемента относительно начала корзины, и пытаемся скопировать в выходной файл, пока он не налезает на невытащенный элемент корзины 1, остаток в кольцевой буфер памяти, если туда не влезло- в временный файл. Дальше, из какой корзины элемент ушёл- из нее закидываем ещё элемент в PriorityQueue, и повторяем шаг с выгрузкой из PriorityQueue. Таким образом, в итоге выходной файл окажется отсортирован. Удаляем временный файл (если он в процессе потребовался и был создан).
Здравствуйте, Тёмчик, Вы писали:
Тё>Затянули сколько влезло в 1 корзину, отсортировали любым библиотечным методом по вкусу в памяти (с comparator по сортируемому полю), выгрузили в выходной файл, запомнили смещение на начало следующей корзины. Затянули следующих в 2 корзину, отсортировали в памяти, выгрузили в выходной файл....
Здравствуйте, B0FEE664, Вы писали:
BFE>Это не bucket sort. Это external merge sort.
Ок, был неправ- это external merge sort. Что мешало отписавшихся тут куче критикующих такой "слишком сложный" вопрос, решить эту задачку указанным методом? Вместо того, чтобы демонстрировать потуги с tree merge?
И ведь я даже не задал баянную knapsack problem- все предельно простое.
Здравствуйте, B0FEE664, Вы писали:
>>>Тё3) Дан файл с integer values от 1 до 2^32-1, они не повторяются за исключением 1 дупликата. Нужно распечатать значение дупликата. Как это сделать? (код не нужен) >>>Тё4) Дан файл с integer values от 0 до 1000000, без дупликатов, но значения в произвольном порядке. Как их вывести в другой файл в порядке возрастания?
BFE>Да, забыл добавить, что в обоих случаях можно использовать указатели на std::bitset (std::bitset<0xFFFFFFFF/8>* и std::bitset<1000000>* соответственно) если экзаменатор предполагает, что в записанных цифрах в файлах могут быть пропуски. (Других решений я не знаю.)
Какие нафиг указатели? BFE>задача 3: BFE>читаем число, записываем в i BFE>проверяем, что по позиции i в bitset стоит 0. Если 0 — записываем 1. Если 1, то i — дубликат.
BFE>задача 4: BFE>читаем число, записываем в i BFE>по позиции i в bitset записываем 1. BFE>после прочтения файла проходим по bitset с индексом k. BFE>Если для k в bitset стоит 1, то выводим k в файл.
Ппц вы правда работаете программистом? Написать цикл 0..1000000 не судьба?
Здравствуйте, Тёмчик, Вы писали:
BFE>>Да, забыл добавить, что в обоих случаях можно использовать указатели на std::bitset (std::bitset<0xFFFFFFFF/8>* и std::bitset<1000000>* соответственно) если экзаменатор предполагает, что в записанных цифрах в файлах могут быть пропуски. (Других решений я не знаю.) Тё>Какие нафиг указатели?
На стеке не поместятся.
Тё>Ппц вы правда работаете программистом?
Правда.
Тё>Написать цикл 0..1000000 не судьба?
В последовательности записанных чисел в файлах могут быть пропуски?
