LRU Cache

import functools
import time

# caching up to 12 different results
@functools.lru_cache(maxsize=12)
def slow_func(x):
    time.sleep(2)  # Simulate long computation
    return x

slow_func(1)  # ... waiting for 2 sec before getting result
slow_func(1)  # already cached - result returned instantaneously!

slow_func(3)  # ... waiting for 2 sec before getting result

Queues

• collections.deque (pronounced deck) is a double ended queue idea for stacks/queues
• queue.Queue is also a queue but intended for concurrent operations and multi-threaded programs, uses dequeue internally

Time Complexity

• lists:
  • growing beyond current size - everything must move - or inserting near the beginning.
  • Append and extend, are still amortized worst case O(1) O(k) respectively, but that's because of amortized. Individual action may still be O(n).
  • If you need to add/remove at both ends, consider using a collections.deque instead.
  • Delete and Insert are O(n) average and worst, since it is just as likely to be in the front half as back half ie. move n/2 on average.
• set:
  • similar to dict
  • x in s: O(1) average, O(n) worst
  • set difference s-t or s.difference(t) and in-place set difference s.difference_update(t) are different: The first one is O(len(s)) (for every element in s add it to the new set, if not in t). The second one is O(len(t)) (for every element in t remove it from s). So care must be taken as to which is preferred, depending on which one is the longest set and whether a new set is needed.

Collections

https://github.com/dabeaz-course/practical-python/blob/main/Notes/02_Working_with_data/05_Collections.md

• Counter

  from collections import Counter
  total_shares = Counter()
  for name, shares, price in portfolio:
      total_shares[name] += shares
  

• defaultdict (always get a default value when accessing)

from collections import defaultdict
holdings = defaultdict(list)
for name, shares, price in portfolio:
    holdings[name].append((shares, price))
holdings['IBM'] # [ (50, 91.1), (100, 45.23) ]

Objects

• use is for object equality, which uses id() the object reference
• be careful with shallow copies (ie. list of list of lists, will still hold reference to element lists)
  • b = copy.deepcopy(a)

Classes