Здравствуйте, B0FEE664, Вы писали:
BFE>>>Да, забыл добавить, что в обоих случаях можно использовать указатели на std::bitset (std::bitset<0xFFFFFFFF/8>* и std::bitset<1000000>* соответственно) если экзаменатор предполагает, что в записанных цифрах в файлах могут быть пропуски. (Других решений я не знаю.) Тё>>Какие нафиг указатели? BFE>На стеке не поместятся.
Какой нафиг стек? Использовать странички (выгружаемые на диск массивы байтов) не судьба?
Тё>>Ппц вы правда работаете программистом? BFE>Правда
В командах, где принято говорить о предыдущем опыте?
Тё>>Написать цикл 0..1000000 не судьба? BFE>В последовательности записанных чисел в файлах могут быть пропуски?
А как вы думаете? Всё же написано в условии.
Здравствуйте, Тёмчик, Вы писали:
BFE>>Это не bucket sort. Это external merge sort. Тё>Ок, был неправ- это external merge sort. Что мешало отписавшихся тут куче критикующих такой "слишком сложный" вопрос, решить эту задачку указанным методом? Вместо того, чтобы демонстрировать потуги с tree merge? И ведь я даже не задал баянную knapsack problem- все предельно простое.
Так ведь tree merge будет работать быстрее, если его построить на основе B-tree. Однако полное описание алгоритма займёт, наверное, час времени. Идея кратко: надо над pivots'ами из External distribution sort построить Би дерево, листами которого будут файлы хранящие смещение в основном файле, такого размера, что вместе со значениями поля влезали в 8 GB памяти. Эти листы-файлы следует записывать в несортированном виде, просто добавляя в конец смещение подходящие для данного листа. Вообще говоря такой индекс должен строится за один проход, но алгоритм очень нетривиальный. После этого каждый лист можно загрузить в память, отсортировать, после этого пройтись по основному файлу и скопировать записи по смещениям взятым из отсортированного листа в новый файл.
Так или иначе, ни тот, ни этот алгоритм не решает проблемы очень длинных ключей. Представьте, что у вас в файле всего 5 записей и значения ключевого поля каждой записи — это строки по длине превышающие 8 Gb.
Здравствуйте, Тёмчик, Вы писали:
BFE>>>>Да, забыл добавить, что в обоих случаях можно использовать указатели на std::bitset (std::bitset<0xFFFFFFFF/8>* и std::bitset<1000000>* соответственно) если экзаменатор предполагает, что в записанных цифрах в файлах могут быть пропуски. (Других решений я не знаю.) Тё>>>Какие нафиг указатели? BFE>>На стеке не поместятся. Тё>Какой нафиг стек?
Вызовов.
BFE>Использовать странички (выгружаемые на диск массивы байтов) не судьба?
А зачем?
Тё>>>Ппц вы правда работаете программистом? BFE>>Правда Тё>В командах, где принято говорить о предыдущем опыте?
Нет. По тестам я в 20% лучших из соискателей.
Тё>>>Написать цикл 0..1000000 не судьба? BFE>>В последовательности записанных чисел в файлах могут быть пропуски? Тё>А как вы думаете? Всё же написано в условии.
Дан файл с integer values от 0 до 1000000, без дупликатов, но значения в произвольном порядке.
Если файл содержит два числа: 2 и 3, например, то это файл integer values от 0 до 1000000, без дупликатов.
Здравствуйте, B0FEE664, Вы писали:
BFE>Здравствуйте, Тёмчик, Вы писали:
BFE>>>Это не bucket sort. Это external merge sort. Тё>>Ок, был неправ- это external merge sort. Что мешало отписавшихся тут куче критикующих такой "слишком сложный" вопрос, решить эту задачку указанным методом? Вместо того, чтобы демонстрировать потуги с tree merge? И ведь я даже не задал баянную knapsack problem- все предельно простое.
BFE>Так ведь tree merge будет работать быстрее, если его построить на основе B-tree. Однако полное описание алгоритма займёт, наверное, час времени. Идея кратко: надо над pivots'ами из BFE>External distribution sort построить Би дерево, листами которого будут файлы хранящие смещение в основном файле, такого размера, что вместе со значениями поля влезали в 8 GB памяти. Эти листы-файлы следует записывать в несортированном виде, просто добавляя в конец смещение подходящие для данного листа. Вообще говоря такой индекс должен строится за один проход, но алгоритм очень нетривиальный. После этого каждый лист можно загрузить в память, отсортировать, после этого пройтись по основному файлу и скопировать записи по смещениям взятым из отсортированного листа в новый файл.
Вы способны нагуглить информацию, но не способны её понять тем более, придумать корректное решение на ходу. Я вам расписал простое корректное решение (можете и с distribution sort предложить), но вы ничего не понимаете, упорно, из раза в раз.
Поэтому, когда бы я ни дорвался интервьюировать- я постараюсь им задавать такие вот задачки. Чтобы не пришлось потом в рабочее время как со столбом разговаривать.
BFE>Так или иначе, ни тот, ни этот алгоритм не решает проблемы очень длинных ключей. Представьте, что у вас в файле всего 5 записей и значения ключевого поля каждой записи — это строки по длине превышающие 8 Gb.
Здравствуйте, RussianFellow, Вы писали:
Тё>>1) школьная на рекурсию (не моя- не буду раскрывать) Тё>>2) перевернуть порядок слов (обсудили) Тё>>3) Дан файл с integer values от 1 до 2^32-1, они не повторяются за исключением 1 дупликата. Нужно распечатать значение дупликата. Как это сделать? (код не нужен) Тё>>4) Дан файл с integer values от 0 до 1000000, без дупликатов, но значения в произвольном порядке. Как их вывести в другой файл в порядке возрастания? Тё>>5) Дан файл из записей JSON размером 140GB, но у вас в системе всего 8GB памяти. Нужно вывести записи в другой файл, отсортированные по произвольному полю JSON. Как это сделать? (код не нужен). Тё>>6) Напишите код для разворота односвязного списка на доске. Тё>>7) Как узнать, есть ли loop в односвязном списке? Напишите код на доске.
Тё>>PS Спасибо, что указали на ошибку в условии (3).
RF>Я большинство из этих задач не решу!
Не переживай. Я, к примеру, даже прочитать их не смог.
-- Пользователи не приняли программу. Всех пришлось уничтожить. --
Здравствуйте, Тёмчик, Вы писали:
Тё>Вы способны нагуглить информацию, но не способны её понять тем более,
Вообще-то, использование B-Tree для решения подобных задач является общепринятым и широко известным.
Тё>придумать корректное решение на ходу.
Медленное решение я всегда могу предложить. Для любой решаемой задачи.
Тё>Я вам расписал простое корректное решение (можете и с distribution sort предложить), но вы ничего не понимаете, упорно, из раза в раз.
Если я ничего не понимаю, то как же я вам указал на правильное название?
Тё>Поэтому, когда бы я ни дорвался интервьюировать- я постараюсь им задавать такие вот задачки. Чтобы не пришлось потом в рабочее время как со столбом разговаривать.
Обычно на собеседованиях на алгоритмы хотят услышать о наилучшем решении, а вы хотите слышать только то, которое знаете.
И вообще, вы что, думаете, что решение с внешними корзинами является единственным и оптимальным? А вот и нет. Вот решение, которое намного проще, оптимальнее по памяти и пишется за один день максимум (если есть парсер Json и все ключи гарантированно влезают в память): читаем данные в память до лимита и записываем их в любую сортированную структуру. При достижении лимита (который меньше 8Gb), читаем ещё одну запись и добавляем её в структуру, после чего выкидываем из структуры максимальный (если сортируем по возрастанию) элемент. Процедуру повторяем до конца файла. Записываем полученные данные в файл. Сохраняем максимальный из имеющихся ключей, а остальную память освобождаем. Повторяем процедуру отсекая те данные, которые мы уже сохранили, используя для этого ключ с предыдущего шага. Менее, чем за 20 циклов мы получим отсортированную копию файла. Прошу заметить, что мы не создаём временные файлы, не тратим времени на их чтение и запись. Если время записи файла существенно превышает время чтения, то этот алгоритм обгонит external merge sort. Более того. его ещё можно оптимизировать если хранить кэш уже отсортированных смещений в разряженном массиве.
Здравствуйте, Тёмчик, Вы писали:
Тё>«предположительно» не подходит. Там простое в лоб решение, как можно не знать? https://en.m.wikipedia.org/wiki/Bucket_sort Тё>Размер корзины такой, чтобы поместился в память.
мдя... вообще, нужно отпарсить json потоковым парсером, выявить смешения начала — конца объекта, хранимого по сортируемому полю для всех записей.
построить в памяти структуру типа список записей:
{
сортируемое поле
смещение начала
смещение конца
}
отсортировать этот список чем хочешь. если этот список тоже не влазит в память (хотя это я думаю маловероятно), отсортировать внешней сортировкой.
все, задача решена. причем тут бакет сорт?
Здравствуйте, VladiCh, Вы писали:
VC>мдя... вообще, нужно отпарсить json потоковым парсером, выявить смешения начала — конца объекта, хранимого по сортируемому полю для всех записей. VC>построить в памяти структуру типа список записей: VC>{ VC> сортируемое поле VC> смещение начала VC> смещение конца VC>}
Вы просто Капитан Очевидность :facepaln: VC>отсортировать этот список чем хочешь. если этот список тоже не влазит в память (хотя это я думаю маловероятно), отсортировать внешней сортировкой.
Не влазит в память. VC>все, задача решена. причем тут бакет сорт?
Любая внешняя сортировка по вкусу.
