A slow slow function. Any ideas ?

[edy_sze]

Hey Guys

I've got a Python function that is slowing the efficiency of my program down and was wondering if anyone could give me some pointers on how I could make this function more efficient ?

The function is used for converting a integer to a base 16 number.

def IntToNBytes(integer, n):
    tmphex = hex(integer)[2:]
    while len(tmphex)<2*n:
        tmphex = '0'+tmphex
    tmpbyte = []
    j = 0
    for i in range(n):
        tmpbyte.append(int(tmphex[j], 16)*16+int(tmphex[j+1], 16))
        j = j+2
    return tmpbyte

[jice]

def IntToNBytes(integer, n):
    while len(tmphex)<2*n:
        tmphex = '0'+tmphex

You should NOT do this. Adding characters to strings like this is very slow.
You should use a list instead (eventually, if you need a string a the end, you can join it (''.join(mylist)) :

def IntToNBytes(integer, n):
    tmphex = list(hex(integer)[2:])
    while len(tmphex)<2*n:
        tmphex.insert(0,'0')
    tmpbyte = []
    j = 0
    for i in range(n):
        tmpbyte.append(int(tmphex[j], 16)*16+int(tmphex[j+1], 16))
        j = j+2
    return tmpbyte

[woooee]

And you should perhaps leave it as a list to avoid any string slicing later. You can also use list comprehension to prepend the zeros which will be faster. This is only an example, since I'm not sure what is going on.

def IntToNBytes(integer, n):
    tmphex = hex(integer)[2:]
    tmphex_list = [ 0 for x in range(2*n - len(tmphex))]
    tmphex_list.extend(list(tmphex))
    tmpbyte = []
    j = 0
    for i in range(n):
        tmpbyte.append(int(tmphex_list[j], 16)*16+int(tmphex_list[j+1], 16))
        j = j+2
    return tmpbyte

Finally, you only want to convert a number once. If it appears in the string many times (as zero does), you are converting it many times. Try using a dictionary to store the value the first time it is encountered. It may or may not be faster than the calcs. Since this is a function, and you are probably calling it several times, return and pass the accumulated dictionary each time. Again, this is just a rough guess of what I think you are doing.

def IntToNBytes(integer, n, hex_dic):
    tmphex = hex(integer)[2:]
    tmphex_list = [ 0 for x in range(2*n - len(tmphex))]
    tmphex_list.extend(list(tmphex))
    tmpbyte = []
    j = 0
    for i in range(n):
        for current in [tmphex_list[j], tmphex_list[j+1]]:
            if current not in hex_dic:
                hex_dic[current] = int(current, 16)
        tmpbyte.append(hex_dic[tmphex_list[j]*16+hex_dic[tmphex_list[j+1])
        j = j+2
    return tmpbyte, hex_dic

[vegaseat]

You can test this sort of thing with module timeit ...

import timeit

stmt1 = "x = '0' + 'ff12'"
print( "%s took %0.3f micro-seconds" % (stmt1, timeit.Timer(stmt1).timeit()) )

stmt2 = "x = ['ff12'].insert(0, '0')"
print( "%s took %0.3f micro-seconds" % (stmt2, timeit.Timer(stmt2).timeit()) )

"""my result -->
x = '0' + 'ff12' took 0.073 micro-seconds
x = ['ff12'].insert(0, '0') took 1.902 micro-seconds
"""

[jice]

Does this mean that it is no longer slower to concatenate a string than to build a list and join it at the end (or is it that i should hage say list = + list ) ?

[woooee]

Using list insert may indeed be slower that string concatenate, since every item after the inserted one has to be moved. This is why I chose to create at list of zeroes first and then extend it using the hex value. It depends on the length of the string or list, of course. These times are going to be longer because functions are called. And timeit extends the execution time considerably.

import timeit
 
n = 500
def test_extend():
   test_list = [ 0 for x in range(n)]
   test_list.extend('ff12')

def test_insert():
   x = ["ff12"]
   for ctr in range(n):
      x.insert(0, '0')

def test_string():
   x = 'ff12'
   for ctr in range(n):
      x = '0' + x

print( "test_extend took %0.3f micro-seconds" % (timeit.Timer(test_extend).timeit()) ) 

print( "test_insert took %0.3f micro-seconds" % (timeit.Timer(test_insert).timeit()) ) 

print( "test_string took %0.3f micro-seconds" % (timeit.Timer(test_string).timeit()) )
 
"""
##--- insert 5 zeroes
test_extend took 3.241 micro-seconds
test_insert took 3.174 micro-seconds
test_string took 1.683 micro-seconds

##-------  insert 500 zeroes
test_extend took 46.459 micro-seconds
test_insert took 330.859 micro-seconds
test_string took 117.718 micro-seconds
"""

[vegaseat]

Thanks woooee!
I also found out that Python3 (Python26?) did away with the setup statement required with Python25.

[edy_sze]

Cheers Guys ..... I tried not using append string .... made it faster !