SHARE
TWEET

Untitled

a guest Jan 24th, 2020 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def do_insertions_simple(l, insertions):
  2.     r = list(l)
  3.     for i, x in insertions:
  4.         r.insert(i, x)
  5.     return r
  6.  
  7.  
  8. def do_insertions_fast(l, insertions):
  9.     result = []
  10.     extended = 0
  11.     for appended, (idx, val) in enumerate(insertions):
  12.         if idx > len(result):
  13.             result.extend(l[extended : idx - appended])
  14.             extended += idx - appended - extended
  15.         result.append(val)
  16.     result.extend(l[extended:])
  17.     return result
  18.  
  19.  
  20. from random import randint
  21.  
  22. l = list(range(1_000_000))
  23. insertions = [(randint(0, len(l)), "x") for _ in range(10_000)]
  24. insertions.sort()
  25. r1 = do_insertions_simple(l, insertions)
  26. r2 = do_insertions_fast(l, insertions)
  27. assert r1 == r2
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top