ropes for lists in python

blist provides a rope data structure for general lists in python.

I just found a nifty list replacement for python: blist

These are much the same as ropes with the added niceness that you can use them in python anywhere you would normally use a list. As a taste of how fast they are, here is some ways to do a sorted list:

from blist import * import bisect class SortedList(blist): br = bisect.bisect_right def insort(self, v): self.insert(self.br(self, v), v) from itertools import tee,izip def pairwise(iterable): "s -> (s0,s1), (s1,s2), (s2, s3), ..." a, b = tee(iterable) try: b.next() except StopIteration: pass return izip(a, b) if __name__ == "__main__": import random,time n = 10000 random.seed(0) start = time.clock() for it in range(10): s = SortedList() for v in range(n): s.insort(random.randint(0,2**30)) stop = time.clock() print (stop - start) s = SortedList() for i in range(n): s.insort(random.randint(0,2**30)) assert(all(x<=y for x,y in pairwise(s))) random.seed(0) start = time.clock() for i in range(10): l = list() for i in range(n): bisect.insort(l, random.randint(0,2**30)) stop = time.clock() print (stop - start) # let's compare heapq import heapq random.seed(0) start = time.clock() for i in range(10): l = list() for i in range(n): heapq.heappush(l, random.randint(0,2**30)) for i in range(n): heapq.heappop(l) stop = time.clock() print (stop - start)

Surprisingly enough, the blist is only 2* slower than the heap, the list is faster for small lists, but around 10000 elements it starts to lose, quadratically. So if you want a sorted list at random points in an algorithm, this is a good option. (alternatively, if you want just the smallest and largest elements, consider a minmax heap)




[æ]