I'm attempting optimize and figure out why for input n a function I wrote f(n) appears to never finish executing when n > 26.
TL;DR I need to figure out how to find the complexity of various python instructions that involve concatenating an empty string and dictionary lookups all within a while loop. The rest appears to be O(1) or negligible. Read below for proof that I've RTFM'd extensively and need help grasping this
f(n) returns a random alphabetical string of length n:
def func(n, prefix=None): if prefix is None: empty = "" else: empty = prefix while (len(empty) < n): c = padder[random.randint(0,len(padder) -1)] if empty.find(c) == -1: str = empty+c empty = str return empty
I disassemble the Python bytecode
>>>dis.dis(func(8)) 0 BREAK_LOOP 1 POP_BLOCK 2 PRINT_NEWLINE 3 INPLACE_POWER 4 RETURN_VALUE 5 PRINT_ITEM 6 <69> 7 IMPORT_STAR
However, when n > 26 it hangs. Why is the following is faster? (note: replace x with desired length of string)
print(''.join(random.choice(string.ascii_uppercase) for i in range(x)))
When I disassemble it like above, it appears to execute in O(n).
So far, I came to the conclusion that I should break down each operation, find their complexities, and that would determine why it hangs at n > 26. I found a cheatsheet for the time complexity of common python operations
However, it doesnt cover SETUP_LOOP, LOAD_CONST vs LOAD_FAST, etc. and other python instructions
Can someone please explain why my first script is slower than the second and at least point me to some good reference material? I google dork'd
intext:"python" intext:"time complexity" intext:"instruction"
Which was light on a cheatsheet. I found a good explanation but it was somewhat hard to follow