خوارزمية الفرز في مكانها

Question

أحتاج إلى كتابة برنامج فرز في C وسيكون من الرائع أن يتم فرز الملف في مكانه لحفظ مساحة القرص. البيانات ذات قيمة ، لذلك أحتاج إلى التأكد من أنه إذا تم مقاطعة العملية (CTRL-C) ، فإن الملف غير تالف. يمكنني أن أضمن لن يتم انتزاع سلك الطاقة على الجهاز.

تفاصيل إضافية: الملف ~ 40 جيجابايت ، والسجلات 128 بت ، وآلة 64 بت ، ونظام التشغيل هو posix

أي تلميحات على إنجاز هذا ، أو ملاحظات بشكل عام؟

شكرًا!

للتوضيح: أتوقع أن يرغب المستخدم في CTRL-C العملية. في هذه الحالة ، أريد الخروج بأمان والتأكد من أن البيانات آمنة. لذا فإن هذا السؤال يدور حول التعامل مع المقاطعات واختيار خوارزمية فرز يمكن أن تختتم بسرعة إذا تم طلبها.

المتابعة (بعد عامين): فقط للأجيال القادمة ، لقد قمت بتثبيت معالج Sigint وعمل بشكل رائع. هذا لا يحميني من انقطاع التيار الكهربائي ، لكن هذا خطر يمكنني التعامل معه. رمز في https://code.google.com/p/pawnsbfs/source/browse/trunk/hsort.c و https://code.google.com/p/pawnsbfs/source/browse/trunk/qsort.c

Answer 1

تثبيت معالج ل SIGINT هذا فقط يضع علامة "يجب أن تخرج قريبًا".

في النوع الخاص بك ، تحقق من العلم بعد كل مبادلة من سجلين (أو بعد كل مقايضات N). إذا تم تعيين العلم ، فإن الإنقاذ.

Answer 2

جيري على حق ، إذا كان الأمر مجرد Ctrl-C أنت قلق بشأنه ، فيمكنك تجاهل Sigint لفترات في كل مرة. إذا كنت تريد أن تكون دليلاً على موت العملية بشكل عام ، فأنت بحاجة إلى نوع من الحد الأدنى من المجلات. من أجل مبادلة عنصرين:

1) أضف سجلًا إلى بنية تحكم في نهاية الملف أو في ملف منفصل ، مما يشير إلى عنصرين من الملف الذي ستقوم بتبديله ، A و B.

2) انسخ A إلى مساحة الصفر ، سجل أنك قمت بذلك ، تدفق.

3) نسخ B على A ، ثم سجل في مساحة الخدش التي قمت بذلك ، تدفق

4) نسخ من مساحة الصفر فوق B.

5) إزالة السجل.

هذا هو (1) مساحة إضافية لجميع الأغراض العملية ، لذلك لا يزال يعتبر في مكان في معظم التعريفات. من الناحية النظرية ، يكون تسجيل الفهرس هو O (log n) إذا كان n يمكن أن يكون كبيرًا بشكل تعسفي: في الواقع هو سجل صغير جدًا ، وحدود وقت تشغيل / تشغيل معقول في 64.

في جميع الحالات عندما أقول "Flush" ، أعني ارتكاب التغييرات "بما يكفي". في بعض الأحيان ، تقوم عملية التدفق الأساسية بتطهير المخازن المؤقتة فقط داخل العملية ، لكنها لا تتم مزامنة الوسيلة الفعلية بالفعل ، لأنها لا تتخلص من المخازن المؤقتة على طول مستويات برنامج التشغيل/الجهاز/الأجهزة. هذا يكفي عندما يكون كل ما تشعر بالقلق هو الموت ، ولكن إذا كنت قلقًا بشأن تفكيك الوسائط المفاجئة ، فعليك أن تتغلب على السائق. إذا كنت قلقًا بشأن انقطاع التيار الكهربائي ، فيجب عليك مزامنة الأجهزة ، لكنك لست كذلك. مع UPS أو إذا كنت تعتقد أن تخفيضات الطاقة نادرة جدًا ، فأنت لا تمانع في فقدان البيانات ، فلا بأس بذلك.

عند بدء التشغيل ، تحقق من مساحة الخدش للحصول على أي سجلات "مبادلة في التقدم". إذا وجدت واحدة ، فابحث عن مدى وصولك إلى المبادلة وإكمالها من هناك لإعادة البيانات إلى حالة الصوت. ثم ابدأ الفرز مرة أخرى.

من الواضح أن هناك مشكلة في الأداء هنا ، نظرًا لأنك تقوم بضعف كتابة السجلات كما كان من قبل ، وقد تكون المزامنة/المزامنة مكلفة بشكل مذهل. في الممارسة العملية ، قد يكون للفرز الموجود في مكانك بعض عمليات النقل المتحركة المركبة ، والتي تتضمن العديد من المقايضات ، ولكن يمكنك تحسينها لتجنب كل عنصر يضرب مساحة الخدش. عليك فقط التأكد من أنه قبل الكتابة فوق أي بيانات ، لديك نسخة منها آمنة في مكان ما وتسجيل المكان الذي يجب أن تذهب إليه هذه النسخة من أجل إعادة ملفك إلى حالة تحتوي على نسخة واحدة تمامًا من كل عنصر.

جيري أيضًا على حق أن الفرز الحقيقي في مكانه صعب للغاية وبطيء لأغراض معظم. إذا تمكنت من تجنيب بعض الكسر الخطي من حجم الملف الأصلي كمساحة للخدش ، فستكون لديك وقت أفضل بكثير منه مع نوع دمج.

بناءً على التوضيح الخاص بك ، لن تحتاج إلى أي عمليات تدفق حتى مع وجود نوع في المكان. تحتاج إلى مساحة خدش في الذاكرة التي تعمل بنفس الطريقة ، ويمكن أن يصل معالج sigint الخاص بك من أجل الحصول على آمنة للبيانات قبل الخروج ، بدلاً من الاستعادة عند بدء التشغيل بعد، بعدما مخرج غير طبيعي ، وتحتاج إلى الوصول إلى تلك الذاكرة بطريقة آمنة للإشارة (والتي تعني من الناحية الفنية استخدام أ sig_atomic_t إلى العلم الذي تم إجراء التغييرات). ومع ذلك ، من المحتمل أن تكون أفضل حالًا مع دمج من النوع الحقيقي.

Answer 3

إن الجزء للحماية من CTRL-C سهل جدًا: signal(SIGINT, SIG_IGN);.

بقدر ما يذهب الفرز نفسه ، فإن نوع الدمج يعمل بشكل عام للفرز الخارجي. الفكرة الأساسية هي قراءة أكبر عدد ممكن من السجلات في الذاكرة ، وفرزها ، ثم اكتبها مرة أخرى إلى القرص. إلى حد بعيد أسهل طريقة للتعامل مع هذا هو كتابة كل تشغيل إلى ملف منفصل على القرص. ثم تقوم بدمج هؤلاء معًا - اقرأ السجل الأول من كل تشغيل في الذاكرة ، وتكتب أصغر من هؤلاء إلى الملف الأصلي ؛ اقرأ سجلًا آخر من المدى الذي قدم هذا السجل ، وكرر حتى القيام به. المرحلة الأخيرة هي المرة الوحيدة التي تقوم فيها بتعديل الملف الأصلي ، لذلك فهي المرة الوحيدة التي تحتاج فيها حقًا إلى التأكد من الانقطاعات وما شابه.

احتمال آخر هو استخدام نوع التحديد. النقطة السيئة هي أن الفرز نفسه بطيء للغاية. النقطة الجيدة هي أنه من السهل جدًا كتابتها للبقاء على قيد الحياة تقريبًا ، دون استخدام مساحة إضافية. الفكرة العامة بسيطة للغاية: ابحث عن أصغر سجل في الملف ، وقم بتبديل ذلك في المكان الأول. ثم ابحث عن أصغر سجل لما تبقى ، وقم بتبديل ذلك في المركز الثاني ، وهكذا حتى القيام به. النقطة الجيدة في ذلك هي أن اليومية تافهة: قبل إجراء مبادلة ، تقوم بتسجيل قيم السجلين اللذين ستقوم بهما. نظرًا لأن النوع الذي يتم تشغيله من السجل الأول إلى الأخير ، فإن الشيء الآخر الوحيد الذي تحتاج إلى تتبعه هو عدد السجلات التي يتم فرزها بالفعل في أي وقت معين.

Answer 4

استخدم نوع الكومة ، ومنع الانقطاعات (مثل إشارات كتلة) أثناء كل عملية مبادلة.

Answer 5

النسخ الاحتياطي كل ما تخطط لتغييره. وضع العلم الذي يمثل نوعًا ناجحًا. إذا كان كل شيء على ما يرام ، فاحتفظ بالنتيجة ، وإلا استعادة النسخ الاحتياطي.

Answer 6

على افتراض نظام التشغيل 64 بت (قلت إنه جهاز 64 بت ولكن يمكن أن يدير 32 بت OS) ، يمكنك استخدام MMAP لرسم خريطة الملف إلى صفيف ثم استخدام QSort على الصفيف.

أضف معالجًا لـ Sigint للاتصال بـ MSYNC و MUNMAP للسماح للتطبيق بالرد على CTRL-C دون فقدان البيانات.