باستخدام اللثغة (أو أوتوليسب) جيدا كيف هو أداء قوائم النقابي؟

Question

وأنا أفعل مشروع أوتوليسب الذي يستخدم الهياكل الجمعياتية طويلة للقيام التجهيز الهندسي الثقيل - لذلك أنا غريبة عن قائمة النقابي استخدام مكثف توقيت النتائج. كيف بسيط / مجمع هو التنفيذ؟ ويستخدم بعض بنية بيانات أو قائمة الطبيعية للأزواج منقط؟ وفيما أي تمديد لب شجرة أو شيء من هذا؟

Answer 1

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

Answer 2

ونقطة تحول بالنسبة SBCL على أجهزة x86 مؤخرا بين alists وhashtables الهوية القائمة على افتراض التوزيع حتى الوصول، وحوالي 30-40 العناصر.

Answer 3

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

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

Answer 4

وأنا لم تكن قد عملت مع أوتوليسب في حوالي 10 عاما، ولكن لم أجد أي مشكلات في الأداء الحقيقي مع قائمة جمعية التلاعب. وكتبت التعليمات البرمجية التي ستفعل قدر لا بأس به من قائمة جمعية التلاعب.

العمل في VBA أو ObjectARX قد يكون لها بعض الفوائد الأداء، ولكنك ربما تحتاج إلى تشغيل بعض التجارب المقارنة لمعرفة ما إذا كان من الأفضل حقا.

Answer 5

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