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 performance 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']],
))
