Прерывистый алгоритм сортировки на месте

Ответ 1

Установите обработчик для SIGINT, который просто устанавливает флаг "process should exit soon".

В своем роде проверьте флаг после каждого свопа двух записей (или после каждого N свопов). Если флаг установлен, выйдите из него.

Ответ 2

Джерри правильно, если это просто Ctrl-C, о котором вы беспокоитесь, вы можете игнорировать SIGINT за периоды за раз. Если вы хотите быть доказательством против смерти процесса в целом, вам нужен какой-то минимальный журнал. Чтобы поменять два элемента:

1) Добавьте запись в структуру управления в конце файла или в отдельный файл, указав, какие два элемента файла вы собираетесь менять, A и B.

2) Скопируйте A на место царапины, запишите, что вы сделали это, заподлицо.

3) Скопируйте B над A, а затем запишите в пространство царапин, которое вы сделали, сбросьте

4) Скопируйте с места царапины над B.

5) Удалите запись.

Это O (1) дополнительное пространство для всех практических целей, поэтому оно по-прежнему считается на месте в большинстве определений. Теоретически запись индекса равна O (log n), если n может быть сколь угодно большим: на самом деле это очень маленький log n, а разумное время аппаратного/рабочего времени ограничивает его выше на 64.

Во всех случаях, когда я говорю "flush", я имею в виду фиксацию изменений "достаточно далеко". Иногда ваша базовая операция флеша только очищает буферы внутри процесса, но фактически не синхронизирует физический носитель, поскольку он не очищает буферы полностью через драйверы/аппаратные уровни OS/device. Этого достаточно, когда все, о чем вы беспокоитесь, - это смерть процесса, но если вас беспокоит резкое разборки СМИ, вам придется скрыться за водителем. Если вас беспокоит отказ от питания, вам придется синхронизировать аппаратное обеспечение, но это не так. С ИБП или если вы считаете, что отключения питания настолько редки, что вы не против потери данных, это прекрасно.

При запуске проверьте место царапины для любых записей "swap-in-progress". Если вы найдете его, выясните, как далеко вы добрались, и завершите обмен оттуда, чтобы вернуть данные в состояние звука. Затем снова начните сортировку.

Очевидно, что здесь проблема с производительностью, так как вы делаете в два раза больше записей записей, как и раньше, а flushes/syncs могут быть невероятно дорогими. На практике ваш вид на месте может иметь некоторые сложные операции с движущимися элементами, включающие множество свопов, но которые вы можете оптимизировать, чтобы каждый элемент не попадал на место царапины. Вам просто нужно убедиться, что перед перезаписью каких-либо данных у вас есть где-то ее копия и запись о том, куда должна идти эта копия, чтобы вернуть файл в состояние, в котором содержится ровно одна копия каждого элемента.

Основываясь на ваших разъяснениях, вам не нужны никакие операции с флеш файлами даже с помощью сортировки на месте. Вам нужно иметь место с нуля в памяти, которое работает одинаково и что ваш обработчик SIGINT может получить доступ, чтобы обеспечить безопасность данных перед выходом, а не восстанавливать при запуске после аномального выхода, и вам нужно получить доступ к этой памяти в сигнальной системе, (что технически означает использование sig_atomic_t, чтобы отметить, какие изменения были сделаны). Тем не менее, вы, вероятно, лучше со слиянием, чем с истинным видом на месте.

Ответ 3

Часть для защиты от ctrl-c довольно проста: signal(SIGINT, SIG_IGN);.

Что касается самой сортировки, то сортировка слияния обычно хорошо подходит для внешней сортировки. Основная идея состоит в том, чтобы прочитать как можно больше записей в памяти, отсортировать их, а затем записать их обратно на диск. Самым простым способом справиться с этим является запись каждого прогона в отдельный файл на диске. Затем вы объедините их обратно - прочитайте первую запись из каждого запуска в память и напишите наименьшее из них в исходный файл; прочитайте еще одну запись из прогона, которая предоставила эту запись, и повторите до конца. Последняя фаза - это единственный раз, когда вы изменяете исходный файл, так что это единственный раз, когда вам действительно нужно заверить от перерывов и т.д.

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

Ответ 4

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

Ответ 5

Резервное копирование, что бы вы ни планировали изменить. Поместите флаг, который отмечает успешный вид. Если все в порядке, сохраните результат, в противном случае восстановите резервную копию.

Ответ 6

Предполагая, что 64-разрядная ОС (вы сказали, что это 64-битная машина, но все еще может работать под 32-разрядной ОС), вы можете использовать mmap для сопоставления файла с массивом, а затем использовать qsort для массива.

Добавьте обработчик для SIGINT для вызова msync и munmap, чтобы приложение могло реагировать на Ctrl-C без потери данных.