algorithm مقارنة كيف يمكنك فرز 1 مليون عدد صحيح 32 بت في 2MB من ذاكرة الوصول العشوائي؟



ذاكرة الحاسوب وانواعها (8)

يرجى تقديم أمثلة الشفرة بلغة من اختيارك.

تحديث : لا توجد قيود على وحدة التخزين الخارجية.

مثال: يتم استقبال / إرسال إنتيجرز عبر الشبكة. هناك مساحة كافية على القرص المحلي للحصول على نتائج وسيطة.


Answer #1

1 مليون عدد صحيح 32 بت = 4 ميغابايت من الذاكرة.

يجب تصنيفها باستخدام بعض الخوارزميات التي تستخدم وحدة التخزين الخارجية. ميرجيسورت، على سبيل المثال.


Answer #2

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


Answer #3

وإليك حل صالح وممتع.

تحميل نصف الأرقام في الذاكرة. كومة فرزها في مكان وكتابة الإخراج إلى ملف. كرر للنصف الآخر. استخدم نوع خارجي (أساسا نوع دمج يأخذ الملف i / o في الاعتبار) لدمج الملفين.

جانبا: جعل كومة نوع أسرع في مواجهة بطيئة التخزين الخارجي:

  • بدء بناء كومة الذاكرة المؤقتة قبل أن تكون جميع الأعداد الصحيحة في الذاكرة.

  • بدء وضع الأعداد الصحيحة مرة أخرى في ملف الإخراج في حين كومة نوع لا يزال استخراج العناصر


Answer #4

لا يوجد مثال، لكن دلو سورت له تعقيدات منخفضة نسبيا ويسهل تنفيذه


Answer #5

المزدوج بطولة نوع مع بوليفاسد دمج

#!/usr/bin/env python
import random
from sort import Pickle, Polyphase


nrecords = 1000000
available_memory = 2000000 # number of bytes
    #NOTE: it doesn't count memory required by Python interpreter 

record_size = 24 # (20 + 4) number of bytes per element in a Python list
heap_size = available_memory / record_size 
p = Polyphase(compare=lambda x,y: cmp(y, x), # descending order
              file_maker=Pickle, 
              verbose=True,
              heap_size=heap_size,
              max_files=4 * (nrecords / heap_size + 1))

# put records
maxel = 1000000000
for _ in xrange(nrecords):
    p.put(random.randrange(maxel))

# get sorted records
last = maxel
for n, el in enumerate(p.get_all()):
    if el > last: # elements must be in descending order
        print "not sorted %d: %d %d" % (n, el ,last)
        break
    last = el

assert nrecords == (n + 1) # check all records read

Answer #6

كما الناس أعلاه ذكر نوع إنت من 32bit 4 ميغابايت.

لتناسب قدر "عدد" ممكن في أقل قدر ممكن من الفضاء ممكن باستخدام أنواع إنت، قصيرة وشار في C ++. هل يمكن أن يكون البقعة (ولكن لها كود القذرة الغريب) من خلال القيام عدة أنواع من الصب إلى الأشياء الأشياء في كل مكان.

هنا هو خارج حافة مقعد بلدي.

يتم تخزين أي شيء أقل من 2 ^ 8 (0 - 255) على شكل شار (1 بايت داتا تايب)

أي شيء أقل من 2 ^ 16 (256 - 65535) و> 2 ^ 8 يحصل على تخزين قصير (2 بايت نوع البيانات)

سيتم وضع بقية القيم في إنت. (4 بايت نوع البيانات)

ستحتاج إلى تحديد مكان بدء وبدء قسم شار، حيث يبدأ القسم القصير وينتهي، حيث يبدأ القسم إنت وينتهي.


Answer #7
  • أم، تخزين كل منهم في ملف.
  • ذاكرة خريطة الملف (قلت كان هناك فقط 2M من ذاكرة الوصول العشوائي؛ دعونا نفترض مساحة العنوان كبيرة بما فيه الكفاية لذاكرة خريطة ملف).
  • فرزها باستخدام ملف دعم مخزن كما لو كانت الذاكرة الحقيقية الآن!





google-moderator