faster geometric average on ASCII

Question

Is it possible to speed up the following code, but without using external modules (NumPy, etc)? Just plain Python. Two lines of thought: speeding the computation in

chr(int(round( multiplOrds**(1.0/DLen), 0) ) )

or faster building of the desired structure. The aim is to find the geometric average of an ord() of an ASCII symbol and report it as a round value (symbol). The len(InDict) is anything above 1. The outcome of the example should be

KM<I

The code:

def GA():
    InStr="0204507890"
    InDict={
       0:"ABCDEFGHIJ",
       1:"KLMNOPQRST",
       2:"WXYZ#&/()?"
       }

    OutStr = ""

    DLen = len(InDict)
    for pos in zip(InStr, *InDict.values()):
        if pos[0]=="0":
            multiplOrds = 1
            for mul in (ord(char) for char in pos[1:] if char!="!"): multiplOrds*=mul
            OutStr+= chr(int(round( multiplOrds**(1.0/DLen), 0) ) )

    return OutStr

if __name__ == '__main__':
    import timeit
    print(timeit.timeit("GA()", setup="from __main__ import GA"))

Answer 1

I assume you are using python3.

Here is the fastest code I could get with provided information, GA_old is old function GA is optimized function. I moved input initialization to the global scope since it's not interesting to optimize initialization and I assume you get your input from other place and don't use the same input all the time.

So here is the code:

InStr="0204507890"
InDict={
   0:"ABCDEFGHIJ",
   1:"KLMNOPQRST",
   2:"WXYZ#&/()?"
}

def GA():
    OutStr = ""

    p = 1.0 / len(InDict)
    for pos,rest in zip(InStr, zip(*InDict.values())):
        if pos == "0":
            product = 1
            for char in rest:
                if char != '!':
                    product*= ord(char)
            OutStr += chr(int(round(product ** p)))
    return OutStr

def GA_old():

    OutStr = ""

    DLen = len(InDict)
    for pos in zip(InStr, *InDict.values()):
        if pos[0]=="0":
            multiplOrds = 1
            for mul in (ord(char) for char in pos[1:] if char!="!"): multiplOrds*=mul
            OutStr+= chr(int(round( multiplOrds**(1.0/DLen), 0) ) )
    return OutStr

if __name__ == '__main__':
    assert GA_old() == GA()
    import timeit
    print(timeit.timeit("GA()", setup="from __main__ import GA", number=100000))
    print(timeit.timeit("GA_old()", setup="from __main__ import GA_old", number=100000))

it produces following output on my machine (python 3.4.3):

 ⚡ python3 t.py 
0.6274565359999542
1.1968618339960813

Most of the speedup I got from following:

• don't use list comprehension here for mul in (ord(char) for char in pos[1:] if char!="!"):. Looks like python creates 2-level iterator and this is quite slower. Also embedding this comprehension into single loop with if improves readability IMO.
• (very surprisingly) removing second argument of round function speeds up function quite significantly. I can't explain this, it looks like minor performance bug in python.

But I think it could be optimized even more, but it will require knowledge about your real data (I guess you don't optimize this particular case that completes in fraction of second).

Some ideas:

• if your strings are long try not to append to them but use advise from other answers (bytearray or "".join(...))
• try to use cache for chr(int(round( multiplOrds**(1.0/DLen)))) (put already computed results to global dict and don't recompute value if it can be found in the dict).
• instead of calculating multiplOrds**(1.0/DLen) you can try to precompute table of ord(c) ** DLen for each possible character and try to search multiplOrds in this precomputed table.

None of this ideas will work good on input data that you posted since it's very small, but it may work good on bigger inputs.

Answer 2

A first thought:

Concatenating strings is slow as they are immutable, therefore each modification results in creating a new copied instance. That's why you should not do things like:

s = ""
for i in range(1000000):
    s += chr(65)

Each loop it will create a new string instance being one character larger than the previous, the old instance will remain until the Garbage Collector kicks in. Also allocating memory is slow.

Using a generator expression to store the partial strings and joining them together in the end is about twice as fast and shorter to code:

s = "".join(chr(65) for i in range(1000000))

Answer 3

Can't you use a lookup table or big switch statement with precalculated values? I'm not a python person, but this looks very messy. :)

Also I don't get what it is actually doing, so a few real examples (input->output) might help people to help you better, maybe even redisigning your whole algorithm, not only optimizing parts.

I tried on python fiddle: Is InDict always the same? Can the InStr be longer than InDict? Why do you only calculate something for 0-values?

Basically you seem to reduce every column of InDict to these numbers and then pick the one where the InStr is zero:

var ia = [ 75, 76, 77, 78, 58, 60, 65, 62, 63, 73 ]

var sa = [ "K", "L", "M", "N", ":", "<", "A", ">", "?", "I" ]

None of this makes sense to me, so i'm out for now, will check once you supply more information. Also, for what purpose are you writing the code?

And the fiddle thing gives me KM, not KM<I for your example? The < is fine, but it seems to break when the I is appended.

Another two ideas:

I think x**(1/n) is the n-th root of x, maybe there are faster functions for that if n is small.

Also since you are rounding the value anyway, you could replace it by a Taylor-sum and stop calculating as soon as the result is close enough.

And you could create thresholds for all the values, so you only have to go through the list and find the right value. So you just iterate once from 0 to maxX and calculate (x+0.5)**n, should be faster. Maybe do a check, how many values below/above are included and adjust the thresholds.

Answer 4

I prefer not to make a wild guess, so you can run your code under the profilers, especially line-by-line profiler: https://zapier.com/engineering/profiling-python-boss/

Also, when you need to store and concatenate a list of ASCII characters, it worst to look into using of bytearray instead of list or string for storing OutStr.

I noticed my changes in your code with comments:

def GA():
    InStr="0204507890"
    InDict={
       0:"ABCDEFGHIJ",
       1:"KLMNOPQRST",
       2:"WXYZ#&/()?"
    }
    OutStr = bytearray() # use bytearray instead of string

    DLen = len(InDict)
    for pos in zip(InStr, *InDict.values()):
        if pos[0]=="0":
            multiplOrds = 1
            for mul in (ord(char) for char in pos[1:] if char!="!"):     multiplOrds*=mul
            OutStr+= chr(int(round( multiplOrds**(1.0/DLen), 0) ) )

    return str(OutStr) # convert bytearray to string

Link to very interesting talk regarding usage of bytearray:

http://rhodesmill.org/brandon/talks/ (Oh, Come On. Who Needs Bytearrays?)