Pop a list from beginning ? and memory saving...

[Jeff Epler]

I seem to recall a discussion, probably a few years ago by now, for a
list implementation that was efficient to grow or shrink from either
end.  I don't recall why it wasn't adopted.  I also can't find the
discussion. :(

I suspect that having unallocated space at both the front and the back
of the list, growing according to the same exponential curve when the
end is reached, would give this kind of behavior.  

The following isn't finished, but append, insert and pop seem to work
properly, and on my machine already beat the builtin list for at-front
operations at 10000 items (test 3/4) but lag in at-end operations (test
1/2):
    10000   test1   test2   test3   test4
    list    0.042   0.075   1.23    1.28
    delist  0.051   0.23    0.22    0.47

    100000  test1   test2   test3   test4
    list    0.48    0.92    151.2   127.6
    delist  0.56    2.46    5.45    9.31
(I didn't let a 1M-item test finish)

Jeff


def roundupsize(n):
    nbits = 0
    n2 = n >> 5
    while 1:
	n2 >>= 3
	nbits += 3
	if not n2: break
    return ((n>>nbits)+1)<<nbits

class delist(list):
    def __init__(self, data=[]):
	super(delist, self).__init__(data)
	self.start = 0
	self.__super = super(delist, self)

    def __growstart(self):
	l = len(self)
	nl = roundupsize(l)
	self[0:0] = [None] * (nl-l)
	self.start = self.start + nl-l

    def __len__(self):
	return self.__super.__len__() - self.start

    def pop(self, idx=None):
	if idx is None:
	    return self.__super.pop()
	if idx == 0:
	    ret = self[idx]
	    start = self.start
	    self[start] = None
	    self.start = start + 1
	    return ret
	else:
	    if idx > 0: idx = idx + len(self)
	    return self.__super.pop(idx + self.start)

    def __getitem__(self, idx):
	self.__super.__getitem__(idx + self.start)

    def insert(self, idx, item):
	if idx == 0:
	    if not self.start:
		self.__growstart()
	    self.start = self.start - 1
	    self[self.start] = item
	    return
	self.__super.insert(idx+self.start, item)

    def __repr__(self):
	return "<dlist +%d %s>" % (self.start, list(self[self.start:]))

def test():
    import time

    def test1(x):
	# Test speed of append
	assert not x
	for i in r:
	    x.append(i)
	assert len(x) == len(r)
	return x

    def test2(x):
	# Test speed of pop-from-end
	assert len(x) == len(r)
	for i in r:
	    x.pop()
	assert not x

    def test3(x):
	# test speed of insert-at-start
	assert not x
	for i in r:
	    x.insert(0, i)
#	    print x
	assert len(x) == len(r)
	return x

    def test4(x):
	# test speed of pop-from-start
	assert len(x) == len(r)
	for i in r:
	    x.pop(0)
	assert not x

    def run(f, arg):
	t0 = time.time()
	ret = f(arg)
	dt = time.time() - t0
	print "%s/%s/%d: %f" % (f.__name__, type(arg), len(r), dt)
	return ret

    for rr in (10000, 100000, 1000000):
	r = range(rr)
	for ll in list(), delist():
	    ll = run(test1, ll)
	    run(test2, ll)
	for ll in list(), delist():
	    ll = run(test3, ll)
	    run(test4, ll)

test()