### listas esparsas implementadas com dicionários (start,length,dict)
### tpc: listas ordenadas com pesquisa binária

def empty():
    return (0,0,{})

def append(w,x):
    (start,nelem,dic)=w
    if x!=0:
        dic[start+nelem]=x
    return (start,nelem+1,dic)

def prepend(w,x):
    (start,nelem,dic)=w
    if x!=0:
        dic[start-1]=x
    return (start-1,nelem+1,dic)

def length(w):
    return w[1]

def val(w,i):
    (start,nelem,dic)=w
    if i>=nelem:
        print("erro")
    elif start+i in dic:
        return dic[start+i]
    else:
        return 0

def first(w):
    return val(w,0)
    
def last(w):
    return val(w,length(w)-1)
    
def nzpos(w):
    (start,nelem,dic)=w
    return [k-start for k in dic]

def most(w):
    (start,nelem,dic)=w
    if start+nelem-1 in dic:
        del dic[start+nelem-1]
    return (start,nelem-1,dic)

def rest(w):
    (start,nelem,dic)=w
    if start in dic:
        del dic[start]
    return (start+1,nelem-1,dic)

wesp=empty()
print([val(wesp,p) for p in range(length(wesp))])
wesp=append(wesp,5)
print([val(wesp,p) for p in range(length(wesp))])
wesp=append(wesp,0)
print([val(wesp,p) for p in range(length(wesp))])
wesp=prepend(wesp,0)
print([val(wesp,p) for p in range(length(wesp))])
wesp=prepend(wesp,3)
print([val(wesp,p) for p in range(length(wesp))])
wesp=prepend(wesp,0)
print([val(wesp,p) for p in range(length(wesp))])

[]
[5]
[5, 0]
[0, 5, 0]
[3, 0, 5, 0]
[0, 3, 0, 5, 0]

first(wesp)

0

last(wesp)

0

nzpos(wesp)

[3, 1]

wesp=most(wesp)
print([val(wesp,p) for p in range(length(wesp))])
print(wesp)

[0, 3, 0, 5]
(-3, 4, {0: 5, -2: 3})

wesp=rest(wesp)
print([val(wesp,p) for p in range(length(wesp))])

[3, 0, 5]

#########################

wesp=empty()
for i in range(1000000):
    wesp=append(wesp,i if i==500000 else 0)

%%time
soma=0
for p in nzpos(wesp):
    soma=soma+val(wesp,p)
print(soma)

500000
CPU times: user 344 µs, sys: 112 µs, total: 456 µs
Wall time: 405 µs

w=[]
for i in range(1000000):
    w.append(i if i==500000 else 0)

%%time
soma=0
for p in range(len(w)):
    soma=soma+w[p]
print(soma)

500000
CPU times: user 229 ms, sys: 6.85 ms, total: 236 ms
Wall time: 233 ms