Interruptible en place algorithme de tri

StackOverflow https://stackoverflow.com/questions/3658921

Question

Je dois écrire un programme de tri en C et ce serait bien si le fichier pourrait être triée en place pour économiser de l'espace disque. Les données sont précieuses, donc je dois faire en sorte que si le processus est interrompu (ctrl-c) le fichier est pas corrompu. Je peux vous garantir le cordon d'alimentation sur la machine ne sera pas yanked.

Détails supplémentaires: fichier ~ 40 Go, les enregistrements sont 128 bits, la machine est de 64 bits, OS est POSIX

Les conseils sur la réalisation de celui-ci, ou des notes en général?

Merci!

Pour clarifier: Je pense que l'utilisateur voudra ctrl-c le processus. Dans ce cas, je veux sortir avec élégance et faire en sorte que les données sont en sécurité. Donc, cette question concerne la gestion des interruptions et le choix d'un algorithme de tri qui peut conclure rapidement la demande.

Suivi (2 ans plus tard): Juste pour la postérité, je l'ai installé le gestionnaire de SIGINT et il a très bien fonctionné. Cela ne me protège pas contre une panne de courant, mais qui est un risque que je peux gérer. Code https://code.google.com/p/ pawnsbfs / source / browse / trunk / hsort.c et

Autres conseils

le droit de Jerry, si elle est juste Ctrl-C vous êtes inquiet, vous pouvez ignorer SIGINT pendant des périodes à la fois. Si vous voulez être la preuve contre la mort de processus en général, vous avez besoin d'une sorte de journalisé minimale. Pour échanger deux éléments:

1) ajouter un enregistrement à une structure de commande à la fin du fichier ou dans un fichier séparé, ce qui indique que deux éléments du fichier, vous allez échange, a et b.

2) Copie A à l'espace de travail, record que vous avez fait, rincer.

3) Copie B sur A, puis enregistrer dans l'espace de travail que vous avez fait, rincer

4) Copie de l'espace scratch sur B.

5) Retirez le disque.

est O (1) espace supplémentaire à toutes fins pratiques, donc encore compte comme en place dans la plupart des définitions. En théorie, l'enregistrement d'un index est O (log n) si n peut être arbitrairement grand. En réalité, il est un très petit journal n, et les limites du matériel / durée raisonnable au-dessus de 64

Dans tous les cas, quand je dis « flush », je veux dire valider les modifications « assez loin ». Parfois, votre opération de rinçage de base uniquement des tampons dans débusque le processus, mais il ne fait pas synchroniser le support physique, car il ne chasse d'eau des tampons tout au long du pilote OS / périphérique / niveaux de matériel. C'est suffisant quand tout ce que vous êtes inquiet au sujet est la mort de processus, mais si vous êtes inquiet au sujet des médias démontages abrupts alors vous auriez à ras passé le conducteur. Si vous inquiet au sujet de panne de courant, vous auriez à synchroniser le matériel, mais vous n'êtes pas. Avec un onduleur ou si vous pensez les coupures d'électricité sont si rares ne vous dérange pas de perdre des données, qui est très bien.

Au démarrage, vérifiez l'espace de travail pour tous les enregistrements « swap en cours ». Si vous trouvez un, le travail jusqu'à quel point vous avez obtenu et procéder à l'échange à partir de là pour obtenir le retour de données dans un état sonore. Puis commencez votre genre encore.

Il est évident qu'il ya un problème de performance ici, puisque vous faites deux fois plus écrit des dossiers comme avant, et vidages / synchronisations peuvent être étonnamment coûteux. En pratique, votre genre en place pourrait avoir des opérations composé moving-choses, impliquant de nombreux échanges, mais vous pouvez optimiser pour éviter tout élément frappant l'espace zéro. Il vous suffit de vous assurer que avant de modifier les données, vous avez une copie de un endroit sûr et un dossier où cette copie doit aller afin d'obtenir votre dossier à un état où il contient exactement une copie de chaque élément.

Jerry aussi droit que le tri vrai en place est trop lent et difficile pour la plupart des raisons pratiques. Si vous pouvez épargner une fraction linéaire de la taille du fichier d'origine que l'espace de travail, vous aurez un temps beaucoup mieux avec une sorte de fusion.

Sur la base de ces précisions, vous auriez pas besoin d'opérations de chasse, même avec une sorte en place. Vous avez besoin de gratter l'espace dans la mémoire qui fonctionne de la même manière, et que votre accès gestionnaire SIGINT de boîte afin d'obtenir le coffre-fort de données avant sortir, plutôt que de la restauration au démarrage après un sortie anormale, et vous avez besoin d'accès que la mémoire d'une manière de signaux de sécurité (ce qui signifie techniquement à l'aide d'un sig_atomic_t pour signaler que des modifications ont été apportées). Même si, vous êtes probablement mieux avec un mergesort qu'un véritable genre en place.

La partie de protection contre ctrl-c est assez facile. signal(SIGINT, SIG_IGN);

En ce qui concerne le tri lui-même va, une fusion fonctionne généralement bien pour sorte de tri externe. L'idée de base est de lire autant d'enregistrements en mémoire que vous pouvez, les trier, puis les écrire de nouveau sur le disque. De loin la meilleure façon de gérer est d'écrire chaque exécution d'un fichier séparé sur le disque. Ensuite, vous fusionnez ceux qui reviennent ensemble - lire le premier enregistrement de chaque passage en mémoire, et d'écrire le plus petit de ceux sur le fichier d'origine; lire un autre record de la course qui a fourni cet enregistrement, et répéter jusqu'à ce que fait. La dernière phase est la seule fois que vous modifiez le fichier d'origine, il est donc le seul moment où vous avez vraiment besoin pour assurer contre les interruptions et autres.

Une autre possibilité est d'utiliser une sorte de sélection. Le mauvais point est que le tri s'est assez lent. Le bon point est qu'il est assez facile d'écrire pour survivre presque rien, sans utiliser beaucoup d'espace supplémentaire. L'idée générale est assez simple: trouver le dossier le plus petit dans le fichier et swap dans la première place. Ensuite, trouver le plus petit compte rendu de ce qui reste et swap dans la deuxième place, et ainsi de suite jusqu'à fait. Le bon point est que la journalisation est trivial: avant de faire un échange, vous enregistrez les valeurs des deux dossiers que vous allez échanger. Étant donné que les pistes de tri du premier enregistrement à la dernière, la seule autre chose que vous devez suivre est le nombre d'enregistrements déjà triés à un moment donné.

Utilisation sorte tas, et empêcher des interruptions (par exemple des signaux de blocage) pendant chaque opération d'échange.

Sauvegarde tout ce que vous envisagez de changer. Le plantez un drapeau qui marque une sorte de succès. Si tout est OK alors garder le résultat, sinon restaurer la sauvegarde.

En supposant un système d'exploitation 64 bits (vous avez dit qu'il est une machine 64 bits, mais pourrait encore être en cours d'exécution OS 32 bits), vous pouvez utiliser mmap pour mapper le fichier à un tableau puis utilisez qsort sur le tableau.

Ajouter un gestionnaire pour SIGINT à msync d'appel et munmap pour permettre l'application de répondre à Ctrl-C sans perdre de données.

Non affilié à StackOverflow
scroll top