cpython vs. pypy O(log n) vs. O(n^2)

gistfile1.txt

Time taken to insert elements into the specified data structures.
Left hand column is total number of elements, right hand side is total time.

Recall skiplist insert is O(log n) in average case, binary search insert is O(n) worst case.


python2.7:

Skiplist insert (implemented in pure python):
      10: 0.000175
     100: 0.001332
    1000: 0.016613
   10000: 0.187406
  100000: 2.358809
  200000: 5.275530
  300000: 8.458164

Binary search insert (using bisect.insort which is written in C):
      10: 0.000053
     100: 0.000295
    1000: 0.003061
   10000: 0.052480
  100000: 2.208176
  200000: 8.056014
  300000: 17.733418

pypy (bisect.insort is pure python so you see timings that you'd expect, pypy jit magic aside):
Skiplist insert (implemented in pure python):
      10: 0.000317
     100: 0.003895
    1000: 0.124335
   10000: 0.046035
  100000: 0.436781
  200000: 1.042915
  300000: 1.829222

Binary search insert (using bisect.insort):
      10: 0.000153
     100: 0.001310
    1000: 0.037063
   10000: 0.030436
  100000: 1.891885
  200000: 7.353198
  300000: 16.494077