خريطة سلسلة إلى سلسلة موفرة للذاكرة في Python (أو C)

Question

أحتاج إلى بنية بيانات فعالة في الذاكرة لتخزين حوالي مليون زوج من المفاتيح والقيمة، حيث تكون المفاتيح عبارة عن سلاسل يبلغ حجمها حوالي 80 بايت، والقيم عبارة عن سلاسل يبلغ حجمها حوالي 200 بايت، ويبلغ إجمالي حجم المفتاح والقيمة حوالي 280 ميجابايت.أحتاج أيضًا إلى بحث فعال عن القيمة عن طريق المفتاح، ويفضل أن يكون ذلك باستخدام خريطة التجزئة.يجب أن يكون الحمل الزائد للذاكرة أقل ما يمكن، على سبيل المثال.بالنسبة إلى 280 ميجابايت من البيانات المفيدة، يجب ألا تستخدم بنية البيانات أكثر من 300 ميجابايت من الذاكرة الافتراضية (بما في ذلك malloc() النفقات العامة وكل شيء آخر).نمط الاستخدام هو كما يلي:نبدأ ببنية بيانات فارغة، ونملأها تدريجيًا، دون تغيير المفاتيح مطلقًا، وعدم تغيير طول القيم أبدًا.كميزة إضافية، قد تدعم بنية البيانات تغيير طول القيم، على حساب قيمة إضافية بنسبة 100% (بمعنى أنه بالنسبة لبايتات القيمة x، قد يتم إهدار x بايت مؤقتًا في مساحة المخزن المؤقت غير المستخدمة).

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

فقط لإثبات أن مثل هذا الحمل البسيط ممكن، قمت بإنشاء تصميم بسيط به معالجة مفتوحة, ، جدول التجزئة المكون من 1.25 مليون عنصر يحتوي على مؤشرات 4 بايت إلى كتل بيانات بحجم 1 ميجابايت، وكتل البيانات التي تحتوي على أطوال المفتاح والقيمة كما قاعدة 128 متغيرات.هذا التصميم له قيود مهمة:لا يسمح بإزالة الأزواج أو تغييرها دون إضاعة مساحة الذاكرة الخاصة بهم.وفقًا لحساباتي مع مليون زوج من المفاتيح ذات القيمة يبلغ كل منها 280 بايت، يكون الحمل أقل من 3.6% (10080000 بايت).الحدود المذكورة أعلاه أكثر سخاءً، فهي تسمح بـ 20.000.000 بايت من الحمل الزائد.

لقد وجدت للتو http://www.pytables.org/ ، والذي يوفر وصولاً سريعًا وتعبئة البيانات بكفاءة في الذاكرة.لا بد لي من فحصه عن كثب لمعرفة ما إذا كان يناسب احتياجاتي.

Answer 1

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

Answer 2

حسنًا، النهج البسيط.

استخدم قاموس بايثون لبنية البيانات.لقد ملأت قاموس بايثون بمليون زوج من المفاتيح ذات القيمة العشوائية حيث كان المفتاح 80 حرفًا والقيمة 200 حرفًا.لقد استغرق الأمر 360,844 كيلو بايت على جهاز الكمبيوتر الخاص بي، وهو ما لا يزيد عن 300 ميجا بايت خارج مواصفاتك، لكنني أقدمه كحل على أي حال لأنه لا يزال فعالاً في الذاكرة.

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

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

cPickle.dump(mydict, "myfile.pkl")

لإعادة تحميل القاموس الخاص بك:

mydict = cPickle.load("myfile.pkl")

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

Answer 3

ذكرت Martijn هذا في تعليق (لست متأكدًا من سبب تعليق الناس بالإجابات) ، لكنني أوافق: استخدم SQLite. يجب أن تجربها ومعرفة ما إذا كانت ستفي باحتياجاتك.

Answer 4

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

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

لذلك ، ها هو ما تفعله.

يمكنك إنشاء مجموعة من:

struct {
    char value[80];
    char *data;
} key;

وتبقي هذا الصفيف مرتبة.

إذا كنت قد تكرر المفاتيح ، فأنت بحاجة إلى:

struct link {
    char *data;
    link *next;
}

struct {
    char value[80];
    link *data;
} key;

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

ثم البحث هو بحث ثنائي بسيط. "الألم" في الحفاظ على مفاتيح هذه الصفيف وإدخال/حذف. إنه ليس مؤلمًا كما يبدو ، لكنه يوفر الكثير من الذاكرة ، خاصة على أنظمة 64 بت.

ما تريد تقليله هو عدد المؤشرات. المؤشرات باهظة الثمن عندما يكون لديك الكثير من الهياكل مليئة المؤشرات. على نظام 64 بت ، المؤشر هو 8 بايت. لذلك بالنسبة لمؤشر واحد ، هناك 8 ميغابايت من ميزانية ذاكرتك.

لذلك ، فإن النفقات في بناء المصفوفة ونسخها وضغطها (إذا كنت تعرف "سيكون لديك مليون صف ويمكنك الالتزام بذلك ، ثم malloc (1000000 * sizeof (مفتاح)) على الفور ، فسوف يوفر لك ذلك بعض النسخ أثناء التوسع).

لكن لا تخف من ذلك ، بمجرد أن ينطلق ، يكون الأداء جيدًا. وحدات المعالجة المركزية الحديثة هي في الواقع جيدة في نسخ 100 متر من الذاكرة حولها.

كما جانبا ، لقد فعلت شيئًا كهذا في جافا. على 64 بت JVM ، خريطة مع 25M إدخالات هي 2G من ذاكرة الوصول العشوائي. إن حلي (باستخدام تقنيات مماثلة لهذا) يحتوي على حوالي 600 متر). تستخدم Java مؤشرات أكثر من C ، لكن الفرضية هي نفسها.

Answer 5

هل حاولت استخداميل مباشر؟ معظم بياناتك في الأوتار ، وبالتالي فإن النفقات العامة قد تتناسب مع متطلباتك.

Answer 6

يمكنك استعمال ال sha1 من المفتاح بدلاً من المفتاح نفسه. إذا كانت المفاتيح فريدة من نوعها ، فعندئذ sha1 من المحتمل أن يكون تجزئة المفاتيح أيضًا. يوفر توفير الذاكرة لمحاولة الصرير تحت الحد الخاص بك.

from random import choice
from string import letters
from hashlib import sha1

def keygen(length):
    return "".join(choice(letters) for _ in xrange(length))

def gentestdata(n=1000*1000):
    # return dict((sha1(keygen(80)).digest(), keygen(200)) for _ in xrange(n))
    d = {}
    for _ in xrange(n):
        key = sha1(keygen(80)).digest()
        assert key not in d
        value = keygen(200)
        d[key] = value
    return d

if __name__ == '__main__':
    d = gentestdata()

على مربع Ubuntu الخاص بي ، يتصدر هذا عند 304 ميجابايت من الذاكرة:

2010-10-26 14:26:02 hbrown@hbrown-ubuntu-wks:~$ ps aux | grep python
[...]
hbrown   12082 78.2  7.5 307420 303128 pts/1   S+   14:20   4:47 python

قريب بما فيه الكفاية؟ إنه بيثون ، وليس جيم

---

لاحقًا: أيضًا ، إذا كانت بياناتك زائدة إلى حد ما ، يمكنك ذلك gzip القيم. إنه وقت مقابل مفاضلة الفضاء.

Answer 7

استخدام SQLite فكرة جيدة. يمكن للتنفيذ السريع معرفة ما إذا كنت كذلك سريع كفاية مع القليل من الجهد.

---

إذا حددت أن عليك أن تدحرج بنفسك ، فإنني أوصي بما يلي:

ما مدى جودة التنبؤ بعدد الأزواج ، أو الحد الأعلى لذلك؟
ما مدى جودة التنبؤ بحجم البيانات الكلي ، أو الحد الأعلى لذلك؟

تخصيص الساحة للسلاسل والعقد. (عادة ، كنت تعمل على قائمة الساحات ، لذلك لا يتعين عليك التنبؤ بالحجم الكلي).

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

ومع ذلك ، إذا كان عليك تشغيل أي عمليات CMP/نسخة إلخ.

• جميع العناصر محاذاة كلمة وحدة المعالجة المركزية
• جميع بايت وسادة هي (على سبيل المثال) 0
• يمكنك قراءة "ما وراء" نهاية السلسلة بأمان طالما أنك لا تعبر حدود وحدة المعالجة المركزية

---

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

---

منطقة الذاكرة

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

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

---

إذا كان عليك دعم "أحرف مضحكة" / Unicode ، فقم بتطبيع سلاسلك قبل تخزينها.

Answer 8

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

• http://docs.python.org/library/struct.html

Answer 9

يحتوي Apache Portable Runtime (AKA APR) على جدول تجزئة يعتمد على C. يمكنك رؤية الوثائق في http://apr.apache.org/docs/apr/0.9/group_أبريل_hash.html

مع Apr_hash_t كل ما تخزنه هو باطل*. لذلك يمنحك السيطرة الكاملة على القيم. لذلك إذا كنت تريد ، يمكنك تخزين المؤشر إلى كتلة بايت 100 بدلاً من الطول الفعلي للسلسلة.

Answer 10

يجب أن تكون جودي فعالة للذاكرة: http://judy.sourceforge.net/
(المعايير: http://www.nothings.org/computer/judy/, ، انظر "حجم بنية البيانات").
أنظر أيضا: http://www.dalkescientific.com/python/pyjudy.html

ايضا،

لمفاتيح الحجم الثابت هناك http://panthema.net/2007/stx-btree/ في C ++ (أنا متأكد من أنه مع أغلفة C مخصصة يمكن استخدامها من Cpython). إذا سمحت مجموعة البيانات ، فيمكنك تخزين مفاتيح طول المتغير في القيمة واستخدام تجزئة أو بادئة لمفتاح طول المتغير كمفتاح طول ثابت.

ينطبق نفس المنطق http://google-opensource.blogspot.ru/2013/01/c-containers-that-save-memory-and time.html و http://code.google.com/p/sparsehash/ -ISTEAD من استخدام سلسلة std :: الثقيلة كمفتاح ، استخدم مفتاح عدد صحيح 32 بت أو 64 بت ، مما يجعله بطريقة أو بأخرى من مفتاح طول المتغير الحقيقي.