على ذبابة محلل/ما قبل الجيل الفضاء/الوقت اعتبارات المقايضة

Question

هل الفوائد المتعلقة بالفضاء لاستخدام محلل سريع تفوق الفوائد المتعلقة بالوقت لجدول بحث تم إنشاؤه مسبقا?

---

نسخة طويلة:

أنا تأليف أداة مرجعية الكيمياء ، وأنا بما في ذلك ميزة من شأنها أن اسم الصيغ تلقائيا مطابقة لنمط معين;على سبيل المثال. C[n]H[2n+2] => [n]ane;أين [n] هو عدد صحيح ل لس;وفهرس في مجموعة من الأسماء على رس.(meth, eth, …)

بقدر ما أستطيع أن أرى ، وهذا يمكن تنفيذها في واحدة من طريقتين:

1. أنا قبل إنشاء مفتاح / قيمة قاموس البحث المزدوج من formula <=> name أزواج;إما عند بدء تشغيل التطبيق (بدء تشغيل أبطأ) ، أو قائمة ثابتة يتم نشرها مع التطبيق (تنزيل أبطأ).

2. يتم تقييم الصيغ على الطاير من قبل محلل بنيت خصيصا.

في النهج 1. الاسم = > يصبح البحث عن الصيغة أبسط بترتيب من حيث الحجم;لكن المولد ، ما لم أرغب في شحن عشرات الميجابايت من البيانات مع التطبيق ، يجب أن يكون له قيمة محددة مسبقا ومنخفضة إلى حد ما n.

ومما يزيد من تعقيد هذه حقيقة أن الصيغ يمكن أن يكون لها عدة مصطلحات;مثل C[n]H[2n+1]OC[n']H[2n'+1];ولكل من هذه ، وعدد من المباريات المحتملة يزيد هندسيا مع n.بالإضافة إلى ذلك ، فإن استخدام هذا النهج من شأنه أن يأكل ذاكرة الوصول العشوائي مثل عمل أي شخص.

النهج 2. يتيح لي دعم قيم كبيرة إلى حد ما من n باستخدام جدول بحث صغير إلى حد ما ، ولكن يجعل اسم => صيغة البحث إلى حد ما أكثر تعقيدا.بالمقارنة مع الجيل المسبق لملف الشحن مع التطبيق ، فإنه يتيح لي أيضا تصحيح الأخطاء في منطق التوليد دون الحاجة إلى شحن ملفات بيانات جديدة.

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

السؤال إذن ، هو:

1. هل هناك أي اعتبارات في المقايضة لقد فشلت في حساب ل, أو النهج التي لم أفكر?

2. هل فوائد استخدام محلل على ذبابة تبرر زيادة تعقيد التنفيذ?

Answer 1

يجب أن تذهب مع النهج الثاني.

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

التعبيرات العادية ليست قوية بما يكفي للتعامل مع ما تريد مباشرة.بدلا من ذلك عليك أن تفعل شيئا مثل:

m = re.match(r"C\[(\d+)\]H\[(\d+)]\]", formula)
if m:
    C_count, H_count = int(m.group(1)), int(m.group(2))
    match_size = len(m.group(0))
    if C_count*2+2 == H_count:
        replacement = alkane_lookup[C_count]
    elif C_count*2 == H_count:
        replacement = alkene_lookup[C_count]
    ...
    else:
        replacement = m.group(0)  # no replacement available

(بالإضافة إلى الكثير من الاحتمالات الأخرى)

ثم تضمين ذلك في حلقة التي تبدو مثل:

formula = "...."
new_formula = ""
while formula:
    match_size, replacement = find_replacement(formula)
    new_formula += replacement
    formula = formula[match_size:]

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

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