Jerry tiene razón, si solo le preocupa Ctrl-C, puede ignorar SIGINT por períodos cada vez. Si quiere ser una prueba contra la muerte del proceso en general, necesita algún tipo de diario mínimo. Para intercambiar dos elementos:
1) Agregue un registro a una estructura de control al final del archivo o en un archivo separado, indicando los dos elementos del archivo que va a intercambiar, A y B.
2) Copie A en el espacio reutilizable, registre que ya lo hizo, enjuague.
3) Copia de B en A, entonces grabar en el espacio de desecho que se ha hecho, al ras
4) Copiar en el espacio de desecho sobre B.
5) Retire el registro.
Este es O (1) espacio adicional para todos los propósitos prácticos, por lo que todavía cuenta como en el lugar en la mayoría de las definiciones. En teoría, registrar un índice es O (log n) si n puede ser arbitrariamente grande: en realidad es un log n muy pequeño, y el hardware razonable/tiempo de ejecución lo limita a 64.
En todos los casos cuando digo " flush ", me refiero a comprometer los cambios" lo suficiente ". A veces, su operación de descarga básica solo vacía búferes dentro del proceso, pero en realidad no sincroniza el medio físico, ya que no vacía los búferes a través de los niveles de hardware/dispositivo de OS/dispositivo. Eso es suficiente cuando lo único que te preocupa es la muerte por proceso, pero si te preocupan los medios de transporte abruptos, entonces tienes que pasar por alto el controlador. Si estaba preocupado por un corte de energía, tendría que sincronizar el hardware, pero no es así. Con un UPS o si cree que los cortes de energía son tan raros que no le importa perder datos, está bien.
Al inicio, verifique el espacio libre para cualquier registro de "intercambio en curso".Si encuentra uno, determine cuánto ha avanzado y complete el intercambio desde allí para que los datos vuelvan a estar en buen estado. Luego comience su clasificación de nuevo.
Obviamente, hay un problema de rendimiento aquí, ya que está haciendo el doble de escritura de registros que antes, y las descargas/sincronizaciones pueden ser sorprendentemente caras. En la práctica, su ordenación en el lugar puede tener algunas operaciones compuestas de elementos en movimiento, que implican muchos intercambios, pero que puede optimizar para evitar que cada elemento llegue al espacio cero. Simplemente debe asegurarse de que antes de sobrescribir cualquier dato, tenga una copia segura en algún lugar y un registro de dónde debe ir esa copia para que su archivo vuelva a un estado donde contenga exactamente una copia de cada elemento.
Jerry también tiene razón en que la clasificación real en el lugar es demasiado difícil y lenta para la mayoría de los propósitos prácticos. Si puede ahorrar una fracción lineal del tamaño del archivo original como espacio cero, lo tendrá mucho mejor con un tipo de fusión.
De acuerdo con su aclaración, no necesitaría ninguna operación de lavado incluso con un ordenamiento in situ. Necesita espacio cero en la memoria que funciona de la misma manera, y que su manejador SIGINT puede acceder para obtener los datos seguros antes de salir, en lugar de restaurar al iniciar después de una salida anormal, y necesita acceder a esa memoria de forma segura para señales (lo que técnicamente significa usar un sig_atomic_t
para marcar qué cambios se han realizado). Aun así, probablemente estés mejor con un mergesort que con un tipo real.
Creo que tienes que preguntar ¿Qué es más importante? Espacio, o si el proceso debe ser interrumpido.Si necesita asegurarse de que el archivo no está dañado, deberá hacer un seguimiento de su progreso y estados previos de alguna manera, esto ocupará más espacio que el archivo. –
Para estar seguro. Haga una copia y clasifique la copia. No puedo imaginar que el sistema de archivos tenga problemas con otro 40GB –
@Martin: su imaginación no funciona como lo hace la mía. En mi disco principal actualmente tengo 36.4GB gratis. –