خوارزمية لدمج الملفات الكبيرة

Question

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

يمكن أن تكون هذه الملفات كبيرة نسبيًا، كما هو الحال في 500000 حدث أو أكثر في سجل واحد، لذا فإن قراءة محتويات السجلات بالكامل في حدث بسيط [] ليس ممكنًا.

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

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

Answer 1

1. اقرأ السطر الأول من كل ملف من ملفات السجل

2. حلقة

   أ.ابحث عن السطر "الأقدم".

   ب.أدخل السطر "الأقدم" في ملف السجل الرئيسي

   ج.اقرأ السطر التالي من الملف الذي يحتوي على السطر الأقدم

يمكنك التحقق من التكرارات بين b وc، مع تقديم المؤشر لكل ملف من هذه الملفات.

Answer 2

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

إليك مثال في لغة بايثون، لكنه يصنع كودًا زائفًا جيدًا أيضًا:

def merge_files(files, key_func):
    # Populate the current array with the first line from each file
    current = [file.readline() for file in files]
    while len(current) > 0:
        # Find and return the row with the lowest key according to key_func
        min_idx = min(range(len(files)), key=lambda x: return key_func(current[x]))
        yield current[min_idx]
        new_line = files[min_idx].readline()
        if not new_line:
            # EOF, remove this file from consideration
            del current[min_idx]
            del files[min_idx]
        else:
            current[min_idx] = new_line

Answer 3

شوف هذا الرابط: http://www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

• استخدم الكومة (استنادًا إلى مصفوفة).سيكون عدد العناصر في هذه الكومة/المصفوفة مساوياً لعدد ملفات السجل لديك.

• اقرأ السجلات الأولى من جميع الملفات وأدخلها في الكومة الخاصة بك.

• تكرار حتى (لا مزيد من السجلات في أي من الملفات)

      > remove the max element from the heap
      > write it to the output
      > read the next record from the file to which the (previous) max element belonged
          if there are no more records in that file
              remove it from file list
              continue
      > if it's not the same as the (previous) max element, add it to the heap

الآن لديك جميع الأحداث الخاصة بك في ملف سجل واحد، وقد تم فرزها، وليس هناك تكرارات.التعقيد الزمني للخوارزمية هو (n log k) حيث n هو العدد الإجمالي للسجلات وk هو عدد ملفات السجل.

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

Answer 4

كنا بحاجة إلى دمج عدة ملفات سجل بترتيب زمني تحتوي على أسطر متعددة لكل إدخال سجل واحد (تقوم تطبيقات Java بذلك غالبًا - آثار المكدس الخاصة بها هي نفسها).قررت تنفيذ البرنامج النصي البسيط Shell + Perl.ويغطي مهامنا.إذا كنت مهتمًا بذلك - اتبع الرابط http://code.google.com/p/logmerge/

Answer 5

قراءة سطر واحد فقط في كل مرة من كلا الملفين المصدر.قارن السطور واكتب الخط الأقدم في ملف الإخراج (وتقدم إلى السطر التالي).قم بذلك حتى تصل إلى نهاية كلا الملفين وتقوم بدمج الملفات.

وتأكد من إزالة التكرارات :)

أعتقد أن هذا الرمز في C# قد يوضح النهج:

        StringReader fileStream1;
        StringReader fileStream2;
        Event eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
        Event eventCursorFile2 = Event.Parse(fileStream2.ReadLine());

        while !(fileStream1.EOF && fileStream2.EOF)
        {
            if (eventCursorFile1.TimeStamp < eventCursorFile2.TimeStamp)
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
            }
            else if (eventCursorFile1.TimeStamp == eventCursorFile2.TimeStamp)
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
                eventCursorFile2 = Event.Parse(fileStream2.ReadLine());
            }
            else
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile2 = Event.Parse(fileStream2.ReadLine());
            }  
        }

حالة الاستراحة ليست صحيحة تمامًا لأن هذه مجرد حالة سريعة وغير قذرة، ولكن يجب أن تبدو متشابهة..

Answer 6

أو يمكنك استعارة أداة دمج السجلات من Awstats وهي أداة إحصائيات موقع ويب مفتوحة المصدر.

logresolvemerge.pl هو برنامج نصي Perl يمكنه دمج ملفات سجل متعددة:يمكنك حتى استخدام سلاسل رسائل متعددة لدمج ملفات السجل (يجب أن يكون لديك Perl 5.8 للاستخدام متعدد الخيوط).لماذا لا تحاول استخدام أداة متاحة بسهولة بدلاً من إنشاء واحدة؟