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

Question

من فضلك، قم بتقديم أمثلة التعليمات البرمجية باللغة التي تختارها.

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

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

Answer 1

فرز مليون عدد صحيح 32 بت في 2 ميجابايت من ذاكرة الوصول العشوائي باستخدام Python بقلم جويدو فان روسوم

Answer 2

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

Answer 3

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

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

Answer 4

تحتاج إلى توفير مزيد من المعلومات.ما هي مساحة التخزين الإضافية المتوفرة؟أين من المفترض أن تخزن النتيجة؟

وإلا فإن الجواب الأكثر عمومية:1.قم بتحميل النصف الأول من البيانات في الذاكرة (2 ميجابايت)، وقم بفرزها بأي طريقة، ثم قم بإخراجها إلى ملف.2.قم بتحميل النصف الثاني من البيانات في الذاكرة (2 ميجابايت)، وقم بفرزها بأي طريقة، واحتفظ بها في الذاكرة.3.استخدم خوارزمية الدمج لدمج النصفين المصنفين وإخراج مجموعة البيانات المصنفة الكاملة إلى ملف.

Answer 5

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

Answer 6

نوع البطولة المزدوجة مع دمج متعدد المراحل

#!/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 7

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

Answer 8

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

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

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

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

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

Answer 9

كما ذكر الأشخاص أعلاه، اكتب int بحجم 32 بت و4 ميجابايت.

لتناسب أكبر قدر ممكن من "الرقم" في أقل مساحة ممكنة باستخدام الأنواع int وshort وchar في C++.يمكن أن تكون ماهرًا (لكن لديك كودًا قذرًا غريبًا) عن طريق القيام بعدة أنواع من عمليات الإرسال لحشو الأشياء في كل مكان.

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

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

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

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

قد ترغب في تحديد أين يبدأ وينتهي قسم char، وأين يبدأ وينتهي القسم القصير، وأين يبدأ وينتهي قسم int.

Answer 10

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