قم بتخزين الأرقام باعتدال

في الآونة الأخيرة ، ظهرت مشكلة في أحد المشاريع: هناك مجموعة من المجموعات (Set) ، والتي يجب تخزينها بشكل فعال في ذاكرة الوصول العشوائي. لأن هناك مجموعات كثيرة ، ولكن القليل من الذاكرة. وعلينا أن نفعل شيئًا حيال ذلك.



بما أن اللغة التي كُتب بها كل هذا هي C # ، أي الفروق الدقيقة. أي أن HashSet <int> القياسي ينفق 16 بايت لتخزين رقم واحد ، كما يؤثر عامل التعبئة. هناك تطبيقات أكثر فاعلية (سأكتب عنها يومًا ما) ، ولكن من ناحية أخرى ، يمكنك تخزين المصفوفات بغباء ، 4 بايت لكل رقم (تحتاج إلى تخزين ints) ، وهو أمر فعال للغاية. ولكن هل يمكن تقليلها أكثر؟



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



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



ستحتوي المقالة على العديد من الأحرف والأرقام وليس صورة واحدة (باستثناء قطة معبأة على KDPV).

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



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



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

لذلك ، لدينا بيانات أساسية - مجموعة من ints ، 4 بايت (32 بت) لكل رقم. سوف نبني على هذا المؤشر.



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

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

فصل الأرقام بالحجم

حل بسيط لتبدأ به: يمكن تخزين الأرقام من 0 إلى 255 باستخدام 1 بايت لكل رقم ، حتى 65536 مع اثنين ، وحتى 16777216 بثلاثة. ومن هنا جاء الحل الأول:



نقوم بإنشاء 4 مصفوفات ، في إحداها نقوم بتخزين الأرقام بمقدار 1 بايت ، وفي الأخرى بمقدار 2 ، والثالث بمقدار 3 ، وماذا في الرابع ، أقترح تخمينه بمفردنا.



تصفيق ، ونحن بالفعل ننقذ. لكن لماذا البقاء حيث كنت؟ دعونا نستخدم 32 مصفوفة! وقم بتخزين الأرقام بمقدار 1 ، 2 ... بت. لقد أصبح أكثر اقتصادا.



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



ما هو هذا المقطع؟ بالإضافة إلى ذلك ، سوف يلتهم 32 مصفوفة 1 كيلوبايت من الذاكرة فقط لأنفسهم. ما يجب فعله حيال ذلك؟ وكل شيء بسيط: سنخزن هذه المصفوفات الـ 32 في مصفوفة واحدة!



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



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



لقد توصلنا للتو إلى صورة نقطية . لا تقلق كثيرًا وتخزن أرقامًا من 0 إلى 255 بهذه الطريقة - يوجد رقم - 1 ، لا - 0. وتنفق 32 بايت على هذا (8 بت في بايت * 32 = 256). بطبيعة الحال ، مع كل قيمة جديدة ، تبدأ فعالية البطاقة في الانخفاض. أولئك. لتخزين جميع ints ، نحتاج إلى 536870912 بايت ... إنه كثير جدًا. لذلك متى تتوقف: عند 256 ، عند 16 ، عند 65536 - يعتمد على البيانات. فليكن 256. أحب هذا الرقم ، إنه جميل.



أولئك. نقوم بتخزين أول 256 رقمًا باستخدام صورة نقطية ، ثم نقوم بتخزين طول الأرقام بطول معين بالبتات والأرقام نفسها.



لكن انظر إلى ما يحدث: تتطلب الأرقام من 0 إلى 511 9 بتات لتخزينها. في الوقت نفسه ، نحن أرقام من 0 إلى 255 - لقد حفظنا بالفعل. أولئك. في نطاق 9 بت لا يمكن العثور على الرقم 12. 256 فقط وأكثر. فلماذا تقوم بتخزينها في 9 بتات ، إذا كان بإمكانك تخزين رقم من 0 إلى 255 ثم إضافة 256 المفقودة في رأسك. تم حفظ بت واحد آخر! وبطبيعة الحال ، سيكون كل نطاق تالٍ أيضًا اقتصاديًا بمقدار 1 بت. نحن رائعون!



ماذا يمكنك أن تفعل أيضا؟ ويمكنك إلقاء نظرة على البيانات. إذا كانت كثيفة جدًا (1،2،3،5،6) ، فلا يمكنك تخزين الأرقام نفسها ، ولكن لا يمكنك تخزين الأرقام غير الموجودة (4). أولئك. بدلاً من تخزين 5 أرقام شرطية ، سنقوم بتخزين رقم واحد. قاعدة بسيطة: لدينا أكثر من النصف - نحتفظ بما لا وجود له ، وإلا العكس. أين تخزن؟ وبشكل مطول! انظر: لتخزين الأرقام بطول 10 بتات ، نحتاج إلى 11 بت (لأن من 0 إلى 1024 ضمناً). ولكن في الوقت نفسه ، يمكن دفع القيم في 11 بت في عام 2048 ، ونستخدم فقط 1025. لذلك سنخزن: الطول الموجب - نقوم بتخزين الأرقام. سلبي - نقوم بتخزين ما هو ليس كذلك. أقترح إجراء حساب مفصل للقارئ نفسه باعتباره تمرينًا مستقلاً (لأنني لست متأكدًا من أن كل شيء سوف يتناسب معًا ، لذلك سأتظاهر بأنه ضروري).



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



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

نحن نفكر في النظام

نظرة. لدينا مجموعة. ماذا لديه على عكس الكثيرين؟ ولديه: ترتيب العناصر. هذه معلومات إضافية ، ولم نستخدمها بعد. ماذا يمكنك ان تفعل حيال هذا؟



ولا يمكنك تخزين العناصر نفسها ، ولكن الاختلاف بينها:



1،2،3،4،8 => 1،1،1،1،4



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



بالإضافة إلى ذلك ، حسب حالة المشكلة ، تختلف جميع العناصر ، أي لا يزال بإمكاننا طرح واحد من الفرق لحفظ البتات:



1،2،3،4،8 => 1،1،1،1،4 => 1،0،0،0،3



هذا ليس صعبًا ، فلماذا و لا.



ولكن المشكلة قد خرجت الآن. لان الآن لا يمكننا تخزين الأرقام بشكل مستقل ، ولكن بنفس الترتيب فقط ، فإن الطريقة التي تحتوي على مصفوفة وأطوال لم تعد مناسبة. من الضروري الخروج بشيء آخر لأن يجب تخزين جميع الأرقام بالترتيب.



قم بتخزين طول الرقم بالبت قبل الرقم نفسه.



ليس خيارًا سيئًا. يأخذ الرقم من 1 إلى 32 بت ، أي للطول نحتاج 5 بتات ، ثم الرقم نفسه. للراحة ، يمكنك قطع الحالات القصوى (حسنًا ، لماذا سنحفظ هناك؟ بنسات!) ، أو العكس ، قم بتمييزها بشكل منفصل - على سبيل المثال ، إذا كان الطول 0 ، فهذا يعني الرقم 0 ، إذا كان الطول 1 هو رقم - 1 ، إذا كان الطول 2 ، ثم 2 التالي رقم البت 2،3،4،5 (نعلم بالفعل أنه يمكننا التحول إلى شيء لا يمكن أن يكون) ، إلخ.



أو هل يمكن تخزين طول الرقم في الرقم نفسه؟



كمية متغيرة الطول



بغض النظر عن كوننا أول من طرح هذا السؤال ، فهناك حل قياسي. تستخدم لتخزين السلاسل في UTF-8 والعديد من الأماكن الأخرى. المعنى بسيط.

إذا كان الرقم من 0 إلى 127 ضمناً ، فإننا نقوم بتخزينه في 1 بايت (على الرغم من أننا استخدمنا 7 بت فقط). إذا كان هناك المزيد ، فقم بتعيين البت الثامن على 1 واستخدم البايت التالي بنفس الطريقة (7 بتات ، مفقودة - مربع الاختيار والتالي). أولئك. سيتم تخزين الأرقام الصغيرة في بايت واحد ، وأكثر من ذلك بقليل - في اثنين ، وهكذا حتى 5.



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

استخدام القيم كعلامات

دعنا نتخطى كل المنطق ونقرر على الفور. سنقوم بتخزينه على النحو التالي:

• سيتم تخزين الأرقام من 0 إلى 252 في بايت واحد. إذا كان أكثر من ذلك:
• إذا كان الرقم من 252 إلى 252 + 256 = 508 ، فقم بتعيين القيمة 252 ، وفي البايت التالي يكون الرقم 252 (نعم ، نحن نعرف بالفعل كيفية تبديل القيم)
• إذا كان من 252 + 256 إلى 252 + 256 + 65536 ، فقم بتعيين 253 واستخدم البايتين التاليين لتخزين الرقم نفسه - فرق غير ضروري
• إذا كان من 252 + 256 + 65536 إلى 252 + 256 + 65536 + 16777216 ، ضع 254 و 3 بايت
• خلاف ذلك - 255 و 4 بايت.

هل هذه طريقة جيدة؟ كل شيء نسبي. في بايت واحد يمكننا دفع القيم حتى 252 ، بينما في VLQ فقط تصل إلى 127 ، ولكن فقط 508 في 2 بايت ، و 16383 بالفعل في VLQ. الطريقة جيدة إذا كانت أرقامك كثيفة بدرجة كافية ، وهنا سنفوز. لكن الشيء الجيد في هذه الطريقة هو أنه يمكن تعديلها لنطاقات مختلفة. على سبيل المثال ، إذا علمنا أن معظم الأرقام تتراوح من 10000 إلى 50000 ، فيمكننا دائمًا تخزينها في 2 بايت ، ولكن إذا ظهر عدد كبير ، فسنكتب 65535 ونستخدم 4 بالفعل. في الواقع ، نقوم بتحسين تخزين النطاق المطلوب بتكلفة التخزين غير الفعال غير ضروري.

خاتمة

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



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



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



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



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