كيفية تحسين دمج الفرز؟

Question

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

Answer 1

يبدو أنك بحاجة فقط إلى دمج الأرقام الموجودة في ملفاتك ، وليس فرزها ، حيث يتم فرزها بالفعل في كل ملف. ال merge جزء من دمج الفرز هذا هو:

function merge(left,right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) ≤ first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append left to result
            break             
        else if length(right) > 0
            append right to result
            break
    end while
    return result

الآن يمكنك فقط قراءة أول 50 ميغابايت من الأرقام من كلا الملفين في مخازن المؤسقين ، وتطبيق خوارزمية الدمج ، ثم عندما يتم استنفاد أحد المخازن المؤقتة (جميع أرقامها التي تم تحليلها) ، اقرأ 50 ميجابايت أخرى من الملف المطلوب. ليست هناك حاجة لفرز أي شيء.

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

Answer 2

لماذا لا تستخدم المكتبة القياسية؟

#include <fstream>
#include <iterator>
#include <algorithm>

int main()
{
   std::ifstream in1("in1.txt");
   std::ifstream in2("in2.txt");
   std::ofstream ut("ut.txt");
   std::istream_iterator<int> in1_it(in1);
   std::istream_iterator<int> in2_it(in2);
   std::istream_iterator<int> in_end;
   std::ostream_iterator<int> ut_it(ut, "\n");

   std::merge(in1_it, in_end, in2_it, in_end, ut_it);
}

Answer 3

ربما تريد قراءة/الكتابة في أجزاء معقولة لتجنب النفقات العامة I/O. لذلك ربما استخدم ثلاثة مخازن المؤقتة ~ 30m ، input1 ، input2 والمخرجات.

استمر حتى يكون أحد المخازن المؤقتة الإدخال فارغة أو أن يكون المخزن المؤقت للإخراج ممتلئًا ، ثم قراءة/اكتب لإعادة ملء/تفريغ المخزن المؤقت الفارغ/الكامل.

وبهذه الطريقة تكتب/تقرأ أجزاء كبيرة من البيانات من القرص.

علاوة على ذلك ، تحتاج إلى بيانات I/O غير متزامنة لقراءة/كتابة البيانات أثناء قيامك بالتصنيف. ولكن هذا ربما يكون مبالغة.

Answer 4

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

double GetNumberFromFile(FILE file){
  if (feof(file)){
    return BIGBIGNUMBER;
  }
  else {
    return ReadADouble(file);
  }
}

double A = GetNumberFromFile(AFILE);
double B = GetNumberFromFile(BFILE);
while (A < BIGBIGNUMBER && B < BIGBIGNUMBER){
  if (A < B){
    write A;
    A = GetNumberFromFile(AFILE);
  }
  else if (B < A){
    write B;
    B = GetNumberFromFile(BFILE);
  }
  else {
    write A;
    write B; // or not, if you want to eliminate duplicates
    A = GetNumberFromFile(AFILE);
    B = GetNumberFromFile(BFILE);
  }
}
while (A < BIGBIGNUMBER){
    write A;
    A = GetNumberFromFile(AFILE);
}
while (B < BIGBIGNUMBER){
    write B;
    B = GetNumberFromFile(BFILE);
}

---

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

الفرق الوحيد بين النسخ وخوارزمية الدمج مثل لك هو قراءة ملفين ، وليس مركب واحد. في كلتا الحالتين ، فإن تسلسل الوقت الأساسي هو سلسلة من القراءات العازلة وتتخلل مع كمية صغيرة من عمل وحدة المعالجة المركزية. (من الممكن القيام به تداخل I/O ، بحيث يتم إجراء وحدة المعالجة المركزية في حين يحدث I/O ، لذلك هناك أساسًا لا التأخير بين المخزن المؤقت يقرأ ويكتب ، لكنه كان صفقة أكبر عندما كانت وحدات المعالجة المركزية أبطأ 1000 مرة.)

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

Answer 5

معيار. اقرأ القيمة بالقيمة وكتلة القراءة. تشعر الفرق! =)