5
\$\begingroup\$

My mask translator is performing poorly in scenario where I have 30 masks and 10,000 ownerships. This is a bit field and similar to bit masks such as enum.IntFlag.

I though about creating a list with all combinations of masked values and names (1 - alex, 2 - ben, 3 - alex/ben, 4 - clark, 5,... sum from 1 to 30 = 465) and then doing a simple lookup rather than evaluating the function for each ownership item. What do you think about this approach?

def findbits(num,object):
  for i in range(128):
      if num & 1 << i:
          y = "{0}".format(i + 1)
          output.append([names[int(y)-1], object])

output = []
map = [['1','alex'],['2','ben'],['4','clark'],['8','dean'],['16','eric']]
mask = [row[0] for row in map] #['1', '2', '4', '8', '16']
names = [row[1] for row in map] #['alex', 'ben', 'clark', 'dean', 'eric']
ownership = [['radio','3'],['telly','31']]

for item in ownership:
  findbits(int(item[1]),item[0])

print(output) 
#[['alex', 'radio'], ['ben', 'radio'], ['alex', 'telly'], ['ben', 'telly'], ['clark', 'telly'], ['dean', 'telly'], ['eric', 'telly']]

In a nutshell: I have to find which names own which objects, that is to decompose masked number for each object (e.g. radio: 31 = 16 + 8 + 4 + 2 + 1) and look up values (names) for each sub-number (16 - eric, 8 - dean, ...).

And a large scale example:

import random
import string

def get_ownerships(nbr):
    for i in range(nbr):
        objects = ''.join(random.choice(string.ascii_letters) for m in range(4))
        ownership.append([objects,mask[i]])
    return ownership

def findbits(num,object):
  for i in range(int(num**0.5)+1): #roundup to nearest integer; this is crucia for performance. Shall be dependent on num, 
  #precisely the position of the highest subnumer. If num = 17, then 17 = 16 + 1 where 16 is 5th element (1 - 2 - 4 - 8 - 16), 
  #hence 5 elements = roundup(17^0.5). Could be improved though
      if num & 1 << i:
          y = "{0}".format(i + 1)
          output.append([names[int(y)-1], object])

ownership = []
mask = [random.randrange(1, 32767) for _ in range(1000)]
get_ownerships(1000)
output = []
map = [['1','al'],['2','be'],['4','cl'],['8','de'],['16','er'],['32','fa'],['64','ga'],['128','ha'],['256','ia'],['512','ja'],['1024','ka'],['2048','la'],['4096','ma'],['8192','na'],['16384','oa']]
mask = [row[0] for row in map] #['1', '2', '4', '8', '16']
names = [row[1] for row in map] #['alex', 'ben', 'clark', 'dean', 'eric']

for item in ownership:
  findbits(int(item[1]),item[0])
\$\endgroup\$
5
\$\begingroup\$

Code block 1

  • Please don't use variable names like object, i or y.
  • Standard indentation in Python is 4 spaces, not a mix between 2 and 4.
  • Mutating values out of a functions scope isn't best practice. This is because it leads to confusing code.
  • The following snippet is not needed. You can just use names[i].

    y = "{0}".format(i + 1)
    names[int(y)-1]
    
  • Rather than findbits I would make a function find_names. Which will return the names that can use the object.

  • Your bit mask, num & 1 << i, is good. But you can change it to use while num: to allow you to not waste any loops. Since the input you've provided us only goes to 1 << 4, there's not much point in looping all the way to 128. And so we can bitshift the other way.
def find_names(number, names):
    index = 0
    while number:
        if number & 1:
            yield names[index][1]
        number >>= 1
        index += 1


def main(map, ownership):
    output = []
    for obj, number in ownership:
        for name in find_names(int(number), map):
            output.append([name, obj])
    return output


if __name__ == '__main__':
    print(main(
        [['1','alex'],['2','ben'],['4','clark'],['8','dean'],['16','eric']],
        [['radio','3'],['telly','31']],
    ))

Both my solution and your solution are similar, however my solution bitshifts number downwards, where yours shifts i upwards. This means that you're constantly making 1 << i larger and comparing with number. This means on the first iteration 1 << i is \$1\$, in binary form, where on the third iteration it's \$100\$, in binary form.

Mine however works the opposite way checking the least significant bit, with number & 1. And so on the first iteration number would be something like \$10001001\$. Where on the third iteration it would be \$100010\$. This is as >> discards the least significant bit.

I find the following table to highlight the increase and decrease in size of the numbers to help. It's apparent that yours grows to match the bitlength of the original number, where mine shrinks until it reaches zero. The red highlights the bit that we're comparing with on each iteration.

$$ \begin{array}{l l r l} \text{iteration} & \text{matching bit} & \text{Yours - 1 << i} & \text{Mine - number} \\ 0 & 1000100\color{red}{1} & \color{red}{1} & 1000100\color{red}{1}\\ 1 & 100010\color{red}{0}1 & \color{red}{1}0 & 100010\color{red}{0} \\ 2 & 10001\color{red}{0}01 & \color{red}{1}00 & 10001\color{red}{0} \\ 3 & 1000\color{red}{1}001 & \color{red}{1}000 & 1000\color{red}{1} \\ 4 & 100\color{red}{0}1001 & \color{red}{1}0000 & 100\color{red}{0} \\ 5 & 10\color{red}{0}01001 & \color{red}{1}00000 & 10\color{red}{0} \\ 6 & 1\color{red}{0}001001 & \color{red}{1}000000 & 1\color{red}{0} \\ 7 & \color{red}{1}0001001 & \color{red}{1}0000000 & \color{red}{1} \\ \end{array} $$

Code block 2

  • We can transfer a lot of the changes from the above code block to the second.
  • I would split the objects comprehension over multiple lines, as I find it helps with readability.
  • The variable m is never used and so you can use the name _ to denote that it is never used.
  • I would move the mask iterator into get_ownerships and just generate one in the for. This allows you to generate both the name and the mask with ease.
import random
import string


def generate_ownerships(amount, limit):
    for _ in range(amount):
        object_name = ''.join(
            random.choice(string.ascii_letters)
            for _ in range(4)
        )
        mask = random.randrange(1, limit)
        yield [object_name, mask]


def find_names(number, names):
    index = 0
    while number:
        if number & 1:
            yield names[index][1]
        number >>= 1
        index += 1


def main(map, ownership):
    output = []
    for obj, number in ownership:
        for name in find_names(int(number), map):
            output.append([name, obj])
    return output


if __name__ == '__main__':
    main(
        [['1','al'],['2','be'],['4','cl'],['8','de'],['16','er'],['32','fa'],['64','ga'],['128','ha'],['256','ia'],['512','ja'],['1024','ka'],['2048','la'],['4096','ma'],['8192','na'],['16384','oa']],
        generate_ownerships(1000, 32767),
    )

Further comments

  • The first value in names is never used. As only names[index][1] is used. This means you can change your input so that you only specify the names.

    If you would still like to specify the value in any order, [['2', 'be'], ['1', 'al']], then you can normalize the names. This requires ordering the names by the first value.

  • Since this is tagged you may be able to get a performance increase if you use an LRU cache from functools. This will store the \$n\$ most recently used values to a function so you don't need to regenerate the output.

    This would require a small change to find_names to return an iterable rather than an iterator, and to only take hashables. For best performance it would only take number.

    It should be noted that this may not lead to a performance gain. The amount of performance gain you get may also change depending on the size of \$n\$ and so you should test the performance on your data with different values.

    If you have both space and time constraints then you can utilize the generalized birthday problem to find a rough number to limit the cache to. As it's 50% chance for hits at a fraction the size of the maximum input is a good way to save on both. If this is needed then I will leave it to you to implement.

import functools


def normalize_names(names):
    return [name for _, name in sorted(names, key=lambda i: int(i[0]))]


@functools.lru_cache(maxsize=None)
def find_names(number):
    output = ()
    index = 0
    while number:
        if number & 1:
            output += (index,)
        number >>= 1
        index += 1
    return output


def main(map, ownership):
    output = []
    for obj, number in ownership:
        for index in find_names(int(number)):
            output.append([map[index], obj])
    return output


if __name__ == '__main__':
    print(main(
        normalize_names(
            [['2','ben'],['1','alex'],['4','clark'],['8','dean'],['16','eric']],
        ),
        [['radio','3'],['telly','31']],
    ))
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank Peilonrayz for detailed answer, great food for thought. I will go through the code over the weekend, do some tests and come back (accept answer). \$\endgroup\$ – regresss Jan 23 at 19:10
  • \$\begingroup\$ I like the simplicity of your code. No need to hold in memory what is not needed. Will start practicing. Could you explain bit the while number part in find_names function (bitshifting)? \$\endgroup\$ – regresss Jan 23 at 20:05
  • \$\begingroup\$ @regresss In a bit / tomorrow sure. Also which bit the while number: if number & 1:? \$\endgroup\$ – Peilonrayz Jan 23 at 20:07
  • \$\begingroup\$ Yes, please also with number >>= 1. \$\endgroup\$ – regresss Jan 23 at 20:44
  • 1
    \$\begingroup\$ @regresss I have added some comments explaining how the bit-shifting work. \$\endgroup\$ – Peilonrayz Jan 24 at 15:44

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.