2

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]
Infinity first
  • 31
  • 6
  • 1
    Concurrent Futures looks like a good place to start https://stackoverflow.com/questions/49358473/how-to-use-concurrent-futures-in-python – Carlo Aug 03 '21 at 16:31
  • @Infinity first - This _process takes about 16 seconds_ on what machine? Here it takes less than a hundredth of that, which is not a strong motivation for optimization. – Armali Aug 07 '21 at 14:31
  • @Armali, sorry about the confusion. For real problem it takes 16 seconds. The given example takes less than 1 second. I just gave an example to clarify how the code works. – Infinity first Aug 09 '21 at 01:48
  • More information about the real data would be helpful (if the encoded data is just a longer string - how long?; if there are multiple strings - how many?). – Armali Aug 09 '21 at 08:22
  • I can't make sense of this algorithm. Can you point to a comprehensive description or show the encoding method? – Armali Aug 09 '21 at 10:32
  • [Google]https://drive.google.com/file/d/11zc9ckcEvyKlzfy_KDQO7bmzHBuOCChX/view?usp=sharing. The paper is in this link which shows how to implement mid short coding (Page 4). – Infinity first Aug 10 '21 at 03:38
  • The encoded data is a list of strings. List length is up to 25 while string length is up to 5000. – Infinity first Aug 10 '21 at 11:27

2 Answers2

1

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.

Mark Adler
  • 101,978
  • 13
  • 118
  • 158
1

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.

Infinity first
  • 31
  • 6