هل يمكن أن يكون مترجم Python postfix (تدوين البولندية العكسي) أكثر كفاءة ودقيقة؟

Question

فيما يلي مترجم تدوين Python Postfix الذي يستخدم مكدسًا لتقييم التعبيرات. هل من الممكن جعل هذه الوظيفة أكثر كفاءة ودقيقة؟

#!/usr/bin/env python


import operator
import doctest


class Stack:
    """A stack is a collection, meaning that it is a data structure that 
    contains multiple elements.

    """

    def __init__(self):
        """Initialize a new empty stack."""
        self.items = []       

    def push(self, item):
        """Add a new item to the stack."""
        self.items.append(item)

    def pop(self):
        """Remove and return an item from the stack. The item 
        that is returned is always the last one that was added.

        """
        return self.items.pop()

    def is_empty(self):
        """Check whether the stack is empty."""
        return (self.items == [])


# Map supported arithmetic operators to their functions
ARITHMETIC_OPERATORS = {"+":"add", "-":"sub", "*":"mul", "/":"div", 
                        "%":"mod", "**":"pow", "//":"floordiv"}


def postfix(expression, stack=Stack(), operators=ARITHMETIC_OPERATORS):
    """Postfix is a mathematical notation wherein every operator follows all 
    of its operands. This function accepts a string as a postfix mathematical 
    notation and evaluates the expressions. 

    1. Starting at the beginning of the expression, get one term 
       (operator or operand) at a time.
       * If the term is an operand, push it on the stack.
       * If the term is an operator, pop two operands off the stack, 
         perform the operation on them, and push the result back on 
         the stack.

    2. When you get to the end of the expression, there should be exactly 
       one operand left on the stack. That operand is the result.

    See http://en.wikipedia.org/wiki/Reverse_Polish_notation

    >>> expression = "1 2 +"
    >>> postfix(expression)
    3
    >>> expression = "5 4 3 + *"
    >>> postfix(expression)
    35
    >>> expression = "3 4 5 * -"
    >>> postfix(expression)
    -17
    >>> expression = "5 1 2 + 4 * + 3 -"
    >>> postfix(expression, Stack(), ARITHMETIC_OPERATORS)
    14

    """
    if not isinstance(expression, str):
        return
    for val in expression.split(" "):
        if operators.has_key(val):
            method = getattr(operator, operators.get(val))
            # The user has not input sufficient values in the expression
            if len(stack.items) < 2:
                return
            first_out_one = stack.pop()
            first_out_two = stack.pop()
            operand = method(first_out_two, first_out_one)
            stack.push(operand)
        else:
            # Type check and force int
            try:
                operand = int(val)
                stack.push(operand)
            except ValueError:
                continue
    return stack.pop()


if __name__ == '__main__':
    doctest.testmod()

Answer 1

الاقتراحات العامة:

• تجنب اختبارات النوع غير الضروري ، والاعتماد على سلوك الاستثناء الافتراضي.
• has_key() تم إهماله منذ فترة طويلة لصالح in المشغل: استخدم ذلك بدلاً من ذلك.
• الملف الشخصي برنامجك ، قبل محاولة أي تحسين للأداء. للحصول على جولة تصميمي صفر من أي رمز معين ، ما عليك سوى تشغيل: python -m cProfile -s cumulative foo.py

نقاط محددة:

• list يجعل مكدسًا جيدًا خارج الصندوق. على وجه الخصوص ، يسمح لك بالاستخدام تدوين شريحة (الدورة التعليمية) لاستبدال pop/pop/append الرقص مع خطوة واحدة.
• ARITHMETIC_OPERATORS يمكن أن تشير إلى تطبيقات المشغل مباشرة ، بدون getattr عدم التوجيه.

وضع كل هذا معًا:

ARITHMETIC_OPERATORS = {
    '+':  operator.add, '-':  operator.sub,
    '*':  operator.mul, '/':  operator.div, '%':  operator.mod,
    '**': operator.pow, '//': operator.floordiv,
}

def postfix(expression, operators=ARITHMETIC_OPERATORS):
    stack = []
    for val in expression.split():
        if val in operators:
            f = operators[val]
            stack[-2:] = [f(*stack[-2:])]
        else:
            stack.append(int(val))
    return stack.pop()

Answer 2

يمكن استخدام القوائم مباشرة كمداخن:

>>> stack = []
>>> stack.append(3) # push
>>> stack.append(2)
>>> stack
[3, 2]
>>> stack.pop() # pop
2
>>> stack
[3]

يمكنك أيضًا وضع وظائف المشغل مباشرة في DICT arithmetic_operators:

ARITHMETIC_OPERATORS = {"+":operator.add,
                        "-":operator.sub,
                        "*":operator.mul,
                        "/":operator.div, 
                        "%":operator.mod,
                        "**":operator.pow,
                        "//":operator.floordiv}

ومن بعد

if operators.has_key(val):
    method = operators[val]

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

بالمناسبة ، باستخدام القوائم كمكدس إلى حد ما مشترك بيثون الاصطناعي.

Answer 3

يمكنك تعيين المشغلين مباشرة: {"+": operator.add, "-": operator.sub, ...}. هذا أبسط ، لا يحتاج إلى غير ضروري getattr كما يسمح بإضافة وظائف إضافية (دون اختراق وحدة المشغل). يمكنك أيضًا إسقاط بعض المتغيرات المؤقتة التي يتم استخدامها مرة واحدة فقط على أي حال:

rhs, lhs = stack.pop(), stack.pop()
stack.push(operators[val](lhs, rhs)).    

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

لكن دقيقة؟ هل يعطي نتائج خاطئة؟