8
\$\begingroup\$

I have a dictionary whose values may contain keys that are already in the dictionary. What we are actually talking about are parameters. Sometimes a parameter is defined by a number plus another parameter, etc.

It looks something like this:

paramDict = {'ad': '2*dmcg/factor*(xw/factor)',
'dmcg': 2.05e-07,
'dxwn_3vna': 10.0,
'factor': 1,
'xw': '0+dxwn_3vna'}

If there is another parameter in the value it is of type string, otherwise it is an int or a float. After the replacing I want the value to be a float.

The code I wrote to solve this problem is this:

    for _ in range(10):
        for key, value in paramDict.items():
            if type(value) is str:
                matchList = re.findall('[a-z]\w*', value)
                matchList = [match for match in matchList if match != 'e']
                for match in matchList:
                    param = paramDict[match]
                    paramDict[key] = value.replace(match, str(param))
                try:
                    paramDict[key] = eval(paramDict[key])
                except:
                    pass

It works as far as I can tell, but it just doesn't feel right to just repeat the whole process a finite number of times and hope that all the strings have been replaced. Is there a safer way?

\$\endgroup\$
2
\$\begingroup\$

It took me some time (the question challenged me), but after playing with some (stupidly :) ) over-complicated approaches I came up with this pretty straightforward solution. It does not even require high-end libraries

I do not think it needs explanation, but if you have questions - I will gladly answer them

EDITED:

It occurred to me that the original version did not handle the case when some of the expressions cannot be evaluated. Well, that may be easily rectified.

def eval_dict(paramDict):
    evaluated_post_cnt = 0 # Total number of converted from previous loop
    result = {}
    while True:
        for var_name, value in paramDict.iteritems():
            if not var_name in result:
                try:
                    exec('{} = {}'.format(var_name, value))
                    result[var_name] = locals()[var_name]
                except NameError:
                    pass
        all_evaluated_num = len(result) 
        if all_evaluated_num == len(paramDict):
            # All values converted
            return result
        if evaluated_post_cnt == all_evaluated_num:
            # No new keys converted in a loop - dead end
            raise Exception('Cannot convert some keys')
        evaluated_post_cnt = all_evaluated_num

OK, here's the "magic":

exec - (not recommended by purists) attempts to execute strings as a Python command lines, so if the sting is, e.g

'xw =0+dxwn_3vna'

the execution will fail with NameError exception if dxwn_3vna has not been evaluated yet - or it will assign value 10.0 to variable with the name xw - as regular assignment statement. Assigned variable is added to local variable set - which may be accessed with function locals() - returns dictionary. So, if the code succeeds in evaluating values - they are replaced in your dictionary.

That simplifies the code, because I do not have to replace variable names within strings with values - if all variables in this string

2*dmcg/factor*(xw/factor)

are already defined, then this string may be executed

'ad = 2*dmcg/factor*(xw/factor)'

Is it clear now?

\$\endgroup\$
  • \$\begingroup\$ thank you very much for your answer :) although i must admit i am thoroughly puzzled... so i tried running your code and what i understand is the first time it runs through the dictionary all the Parameters that already have a numeric value get added to evaluated_keys and somehow to locals. but then during the second run through it magically computes the remaining Parameters. could you please further explain the magic that happens in the lines exec('{} = {}'.format(var_name, value)) and paramDict[var_name] = locals()[var_name]? \$\endgroup\$ – moringana Feb 12 '15 at 14:03
  • \$\begingroup\$ oh and also, I am using python 2.6, so I already had to add numbers in the {} braces for .format, i dont know if this also affects your code in some other way! \$\endgroup\$ – moringana Feb 12 '15 at 14:06
  • 1
    \$\begingroup\$ @moringana,you may use '%s = %s' % (var_name, str(value)) then \$\endgroup\$ – volcano Feb 12 '15 at 14:12
  • \$\begingroup\$ yes I like it but i don't really understand it, so could you please answer my question that i asked in my first comment? \$\endgroup\$ – moringana Feb 12 '15 at 14:58
  • \$\begingroup\$ aha okay, much clearer now thank you :) that is a cool approach \$\endgroup\$ – moringana Feb 12 '15 at 16:16
6
\$\begingroup\$

Well what you want there is evaluating expressions while keeping track of dependencies, so you should definitely not implement it via regular expressions and hoping that running it ten times is enough.

The best way in Python would probably be using the ast module to parse and figure out the referenced variables, then calculate dependencies and evaluate the parsed expressions via compile and eval while passing in the referenced variables in the local parameter.

That way you make sure that the expressions are actually valid, you can use Python expressions and you can (and should) also detect cycles in the specification.

Below is a sketch how to do that, not saying that is the best code, please edit or comment with improvements, I couldn't find a good example while searching.

import ast, _ast

params = {
    'ad': '2*dmcg/factor*(xw/factor)',
    'dmcg': 2.05e-07,
    'dxwn_3vna': 10.0,
    'factor': 1,
    'xw': '0+dxwn_3vna',
    'foo': 'bar',
    'bar': 'foo'
}

parsed = {}

for key, value in params.iteritems():
    parsed[key] = value

    if type(value) in (str, unicode):
        parsed[key] = ast.parse(value, mode="eval")

evaluated = {key: value for key, value in parsed.iteritems()}

So at this point the evaluated dictionary is mostly a copy of the params, except that expressions have been parsed.

def referenced(code):
    return [node.id for node in ast.walk(code) if "id" in node._fields]

referenced returns a list with the names of referenced variables in the expression.

evaluating = []

def resolve(key, value):
    if key in evaluating:
        raise Exception("Loop while evaluating {}".format(key))

    if type(value) is not _ast.Expression:
        evaluated[key] = value
        return value

    evaluating.append(key)

    locals = {name: resolve(name, evaluated[name]) for name in referenced(value)}

    result = eval(compile(value, "<unknown>", "eval"), globals(), locals)

    evaluated[key] = result

    evaluating.pop()

    return result

resolve evaluates the expression recursively but also keeps track of the stack (in evaluating), so it can detect cycles by looking up the current variable. It also assigns the results immediately, so in further invocations it will return early (the not _ast.Expression case).

for key, value in parsed.iteritems():
    try:
        resolve(key, value)
    except Exception as exception:
        print ("Error while evaluating {}: {}".format(key, exception))

print(evaluated)

Lastly, iterate over all entries and try to evaluate them.

\$\endgroup\$
  • \$\begingroup\$ Thank you very much for your answer! This seems a lot more complex than my try (I've been learning Python for three weeks now), so I will first have to look into abstract syntax trees and such... When I feel like I've gotten my head around it I will get back to you :) \$\endgroup\$ – moringana Feb 12 '15 at 8:02
  • \$\begingroup\$ Yeah well, in that case this answer is overkill. If you were to use your original approach in a production setting you would run into issues though, which is why I wanted to highlight that. E.g. your solution, or @volcano's will work, but corner cases remain, which would come haunt you later on. \$\endgroup\$ – ferada Feb 12 '15 at 10:39
  • \$\begingroup\$ well the goal is indeed to make it as reliable as possible, but maybe for my case my or volcano's solution is already sufficient, I will have to check. I have already found a fault in my solution though... thank you for your answer though, I am always pleased to learn about new methods and modules! \$\endgroup\$ – moringana Feb 12 '15 at 13:28
3
\$\begingroup\$

A slightly more robust technique than volcano's, but still less-so than ferada's, is to capture the evaluation in a fake "scope" and avoid messing with strings:

paramDict[var_name] = eval(value, {}, paramDict)

This keeps locals clean.

However, you don't want to start with everything available to eval since you'll never get a NameError that way. Instead, build a dictionary as you go.

What might even be better is abusing eval's locals argument with a lazy cached evaluation strategy:

# from UserDict import UserDict on Python 2
from collections import UserDict

class StringScope(UserDict):
    def __getitem__(self, name):
        expr = self.data[name]

        if isinstance(expr, str):
            expr = self.data[name] = eval(expr, {}, self)

        return expr

scope = StringScope(paramDict)

That's it: scope will now lazily evaluate its values as they are requested. If you want eager evaluation, just do

scope = dict(StringScope(paramDict))

instead. This will automatically do walking of the dependency chain, too, so is technically more efficient algorithmically.

\$\endgroup\$
  • \$\begingroup\$ I have read up on Python OOP and am making Progress in understanding your code, however, when I try to run it I get TypeError: Error when calling the metaclass bases module.__init__() takes at most 2 arguments (3 given) right in the class StringScope(UserDict):line. Do you have an idea about what could be the problem here? (I am using Python 2.6 and had to already change from collections Import UserDict to Import UserDict ) \$\endgroup\$ – moringana Feb 16 '15 at 11:11
  • \$\begingroup\$ okay found the error, I need to write from UserDict import UserDict \$\endgroup\$ – moringana Feb 16 '15 at 13:05
  • 1
    \$\begingroup\$ @moringana There's already a comment on that (# from UserDict import UserDict on Python 2). \$\endgroup\$ – Veedrac Feb 16 '15 at 16:32
  • \$\begingroup\$ sorry for bothering you again, but could you explain why there are two equal signs in the line ` expr = self.data[name] = eval(expr, {}, self)`? And also, shouldn't we need to create an instance of the StringScope class before using it? \$\endgroup\$ – moringana Feb 23 '15 at 14:01
  • \$\begingroup\$ The two equals signs sets both the values. So a = b = 0 sets a = 0 and b = 0. // I am constructing an instance of the StringScope class (StringScope(paramDict)). The implicit __getitem__ calls do the magic to make things work from there. \$\endgroup\$ – Veedrac Feb 23 '15 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.