خوارزمية بنية البيانات في C#

Question

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

س.لدي جهاز به ذاكرة وصول عشوائي (RAM) سعة 512 ميجابايت / 1 جيجابايت ويجب علي فرز ملف (XML، أو أي ملف) بحجم 4 جيجابايت.كيف سأستمر؟ماذا سيكون هيكل البيانات، وما هي خوارزمية الفرز التي سأستخدمها وكيف؟

هل تعتقد أنه يمكن تحقيقه؟إذا كانت الإجابة بنعم، فهل يمكنك التوضيح؟

شكرا لك مقدما!

Answer 1

وهنا مثال واحد من محاكاة الذاكرة الظاهرية على C #

المصدر: http://msdn.microsoft. كوم / EN-US / مكتبة / aa288465 (VS.71) .aspx اتصال

// indexer.cs
// arguments: indexer.txt
using System;
using System.IO;

// Class to provide access to a large file
// as if it were a byte array.
public class FileByteArray
{
    Stream stream;      // Holds the underlying stream
                        // used to access the file.
// Create a new FileByteArray encapsulating a particular file.
    public FileByteArray(string fileName)
    {
        stream = new FileStream(fileName, FileMode.Open);
    }

    // Close the stream. This should be the last thing done
    // when you are finished.
    public void Close()
    {
        stream.Close();
        stream = null;
    }

    // Indexer to provide read/write access to the file.
    public byte this[long index]   // long is a 64-bit integer
    {
        // Read one byte at offset index and return it.
        get 
        {
            byte[] buffer = new byte[1];
            stream.Seek(index, SeekOrigin.Begin);
            stream.Read(buffer, 0, 1);
            return buffer[0];
        }
        // Write one byte at offset index and return it.
        set 
        {
            byte[] buffer = new byte[1] {value};
            stream.Seek(index, SeekOrigin.Begin);
            stream.Write(buffer, 0, 1);
        }
    }

    // Get the total length of the file.
    public long Length 
    {
        get 
        {
            return stream.Seek(0, SeekOrigin.End);
        }
    }
}

// Demonstrate the FileByteArray class.
// Reverses the bytes in a file.
public class Reverse 
{
    public static void Main(String[] args) 
    {
        // Check for arguments.
        if (args.Length == 0)
        {
            Console.WriteLine("indexer <filename>");
            return;
        }

        FileByteArray file = new FileByteArray(args[0]);
        long len = file.Length;

        // Swap bytes in the file to reverse it.
        for (long i = 0; i < len / 2; ++i) 
        {
            byte t;

            // Note that indexing the "file" variable invokes the
            // indexer on the FileByteStream class, which reads
            // and writes the bytes in the file.
            t = file[i];
            file[i] = file[len - i - 1];
            file[len - i - 1] = t;
        }

        file.Close();
    } 
}

استخدم رمز أعلاه للفة الطبقة مجموعة الخاصة بك. ثم مجرد استخدام أي مجموعة خوارزمية الفرز.

Answer 2

قد تكون الإجابة التي قد يريدها القائم بإجراء المقابلة هي كيفية إدارة فرز مجموعة البيانات بكفاءة والتي تتجاوز ذاكرة النظام. القسم التالي مأخوذ من ويكيبيديا:

أنماط استخدام الذاكرة وفرز الفهرس

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

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

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

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

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

Answer 3

استخدم فرق تسد .

وهنا يكمن شبة الكود:

function sortFile(file)
    if fileTooBigForMemory(file)
       pair<firstHalfOfFile, secondHalfOfFile> = breakIntoTwoHalves()
       sortFile(firstHalfOfFile)
       sortFile(secondHalfOfFile)
    else
       sortCharactersInFile(file)
    endif

    MergeTwoHalvesInOrder(firstHalfOfFile, secondHalfOfFile)
end

واثنين من الخوارزميات المعروفة التي تقع في لفرق تسد الفئة هي دمج النوع و خوارزمية سريعة نوعا . لذلك يمكن أن استخدامها للتنفيذ.

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

class File {
    private char[] characters;
    //methods to access and mutate 'characters'
}

Answer 4

وهناك وظيفة لطيفة على غيدو فان روسوم <لأ href = "http://neopythonic.blogspot.com/2008/10/sorting-million-32-bit-integers-in-2mb.html" يختلط = "نوفولو noreferrer"> بلوق التي لديها ما توحي. حذار من أن الرمز هو في بيثون.

Answer 5

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

Answer 6

وأود أن استخدام دمج متعددة الاتجاهات. هناك كتاب ممتاز يسمى <لأ href = "http://books.google.com/books؟id=2F74jyPl48EC&dq=managing+gigabytes&printsec=frontcover&source=bn&hl=en&ei=RIvuSfWnHN6rtge3ncnMDw&sa=X&oi=book_result&ct=result&resnum=4#PPR6،M1 "يختلط =" noreferrer نوفولو "> إدارة غيغابايت التي تظهر عدة طرق مختلفة للقيام بذلك. يذهبون أيضا إلى انعكاس على أساس فرز الملفات التي هي أكبر من الذاكرة الفعلية. ننظر حولنا الصفحة 240 لخوارزمية مفصلة جدا على الفرز من خلال قطع على القرص.

وظيفة أعلاه هو الصحيح في ذلك يمكنك تقسيم الملف وفرز كل جزء.

ويقول لديك ملف 4GB وتريد فقط لتحميل بحد اقصى 512MB. وهذا يعني أنك بحاجة إلى تقسيم الملف إلى 8 قطع الحد الأدنى. إذا كنت غير متأكد من كيفية النفقات العامة خارج بكثير النوع الخاص بك هو الذهاب للاستخدام، حتى أنك قد يتضاعف هذا العدد لتكون آمنة إلى 16 قطع.

ثم يتم فرز

وملفات 16 في وقت واحد ليكون في أمر مضمونة. حتى الآن لديك قطعة 0-15 الملفات التي تم فرزها كما.

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

ولقد استخدمت هذا النظام في C # لفرز مجموعات كبيرة من الكلمات غير المرغوبة من رسائل البريد الإلكتروني. النظام الأصلي حاجة كل منهم لتحميل إلى ذاكرة الوصول العشوائي من أجل فرزها وبناء قاموس لتهم غير المرغوبة. مرة واحدة نما ملف أكثر من 2 GB من ذاكرة في هياكل والتي تتطلب 6 + GB من ذاكرة الوصول العشوائي، والاستيلاء على 24 ساعة لفرز بسبب الترحيل وVM. النظام الجديد باستخدام شونكينغ فوق فرز الملف بأكمله في أقل من 40 دقيقة. وكان ذلك تسريع مثير للإعجاب لمثل هذا التغيير بسيط.

ولقد لعبت مع مختلف الخيارات الحمل (1/4 ذاكرة النظام في قطعة، الخ). واتضح أن لحالنا كان الخيار الأفضل حوالي 1/10 ذاكرة النظام. ثم كان ويندوز ذاكرة كافية خلفها لملف لائق I / O التخزين المؤقت للتعويض عن زيادة حركة المرور الملف. وكان الجهاز يقم استجابة للغاية على العمليات الأخرى التي تعمل على ذلك.

ونعم، أنا كثيرا ما أود أن أسأل هذه الأنواع من الأسئلة في المقابلات كذلك. فقط لمعرفة ما إذا كان يمكن للناس أن يفكر خارج منطقة الجزاء. ماذا تفعل عندما لا يمكنك فقط استخدام .Sort () على القائمة؟

Answer 7

ومجرد محاكاة الذاكرة الظاهرية، تفرط في مشغل مؤشر مجموعة، []

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