CODEWITHSUNDEEP
pythonoptimizationcompression
Infinity first
Infinity first

Reputation: 31

How to optimize the following python function to execute faster?

The following code is about semi fixed coding using mid-short. The encoding process works fine (takes 2 sec to execute). But decoding process takes about 16 seconds. I have mentioned only decoding process here. The code inside 'Main' block is just an example. Is there a way to make below code faster?

from math import ceil, floor, log2

def semi_fixed(stream, parent):

  code_len = ceil(log2(parent + 1))
  boundary = 2 ** code_len - parent - 1  # short_code_num
  # print('Code_len: ', code_len, 'Boundary: ', boundary)
  low = floor(parent / 2) - floor(boundary / 2)
  high = floor(parent / 2) + floor(boundary / 2) + 1
  if parent % 2 == 0:
     low -= 1
  bits = stream[-code_len+1::]  # First read short code from last
  data = int(str(bits), 2)

  if low >= data or data >= high:
     bits = stream[-code_len::]
     data = int(str(bits), 2)
  else:
     code_len -= 1   # To balance the length in recursive call
  return data, code_len



if __name__ == '__main__':
  encoded_data = '011010101011011110001010'
  decoded_data = [15]
  count = 0
  while len(decoded_data) <23:
    if decoded_data[count] == 0:
      decoded_data.append(0)
      decoded_data.append(0)
      count += 1
      continue
    else:
      node, bit_len = semi_fixed(encoded_data, decoded_data[count])
      decoded_data.append(node)
      decoded_data.append(decoded_data[count] - node)
      encoded_data = encoded_data[:-bit_len]
      print(encoded_data)
      count +=1
    print(decoded_data)

The semi fixed method read the encoded data from right side and decide the number of bits to decode. The process continues up to certain length. Here the length and first decoded data is hard coded. The result of above code is below (This one is just an example which takes less than a second):

01101010101101111000
[15, 10, 5]
0110101010110111
[15, 10, 5, 8, 2]
01101010101101
[15, 10, 5, 8, 2, 3, 2]
01101010101
[15, 10, 5, 8, 2, 3, 2, 5, 3]
0110101010
[15, 10, 5, 8, 2, 3, 2, 5, 3, 1, 1]
01101010
[15, 10, 5, 8, 2, 3, 2, 5, 3, 1, 1, 2, 1]
011010
[15, 10, 5, 8, 2, 3, 2, 5, 3, 1, 1, 2, 1, 2, 0]
0110
[15, 10, 5, 8, 2, 3, 2, 5, 3, 1, 1, 2, 1, 2, 0, 2, 3]
01
[15, 10, 5, 8, 2, 3, 2, 5, 3, 1, 1, 2, 1, 2, 0, 2, 3, 2, 1]
0
[15, 10, 5, 8, 2, 3, 2, 5, 3, 1, 1, 2, 1, 2, 0, 2, 3, 2, 1, 1, 0]

[15, 10, 5, 8, 2, 3, 2, 5, 3, 1, 1, 2, 1, 2, 0, 2, 3, 2, 1, 1, 0, 0, 1]

Upvotes: 2

Views: 124

Answers (2)

Infinity first
Infinity first

Reputation: 31

In the main function instead of slicing encoded_data on every iteration, I used indexing. The index tells the semi_fixed function where to start encoded_data for passing as argument. So, instead of using this:

  node, bit_len = semi_fixed(encoded_data, decoded_data[count])
  decoded_data.append(node)
  decoded_data.append(decoded_data[count] - node)
  encoded_data = encoded_data[:-bit_len]
  print(encoded_data)
  count +=1

I used the following:

node, bit_len = semi_fixed_decoder_QA(encoded_data[:-prev_bit_len], decoded_data[count])
decoded_data.append(node)
decoded_data.append(decoded_data[count] - node)
prev_bit_len += bit_len

Here, prev_bit_len is initialized to 1 and encoded_data is padded with an extra bit at right. This way I got almost same time for decoding as it was for encoding.

Upvotes: 1

Mark Adler
Mark Adler

Reputation: 112374

I can get a 30% speedup by using integer and bitwise operations:

  code_len = parent.bit_length()
  boundary = ((1 << code_len) - parent - 1) // 2  # short_code_num
  odd = parent & 1
  parent //= 2
  low = parent - boundary + odd - 1
  high = parent + boundary + 1

Not much yet, but something.

Upvotes: 1

Related Questions