Bryan;
My own version also timed out.
And now I can tell: it's incredibly SLOW.
Nevertheless it would be interesting to compare
speed of my code against yours. I can't do it myself
because my Python is of 2.3.4 version.
Just uncomment "your" part.
import bisect
def oops(w,a,b):
for m in w:
j=bisect.bisect_left(a,m)
a.insert(j,m)
b.insert(j,max(b[:j]+[0])+1)
def n00m(n,w):
a,b=[],[]
oops(w,a,b)
v=map(lambda x: -x, w[::-1])
c,d=[],[]
oops(v,c,d)
e=map(sum, zip(b, d[::-1]))
mx=max(e)
f=[]
for i in xrange(n):
if e[i]==mx:
f.append(i+1)
print len(f)
def one_way(seq):
n = len(seq)
dominators = [n + 1] * (n * 1)
score = [None] * n
end = 0
for (i, x) in enumerate(seq):
low, high = 0, end
while high - low > 10:
mid = (low + high) >> 1
if dominators[mid] < x:
low = mid + 1
else:
high = mid + 1
while dominators[low] < x:
low += 1
dominators[low] = x
score[i] = low
end = max(end, low + 1)
return score
def supernumbers(seq):
forscore = one_way(seq)
opposite = [len(seq) - x for x in reversed(seq)]
backscore = reversed(one_way(opposite))
score = map(sum, zip(forscore, backscore))
winner = max(score + [0])
return sorted([seq[i] for i in range(len(seq)) if score[i] ==
winner])
def b_olson(sequence):
supers = supernumbers(sequence)
print len(supers)
import random, time
n=50000
w=range(1,n+1)
random.shuffle(w)
t=time.time()
n00m(n,w)
print 'n00m:',time.time()-t
"""
t=time.time()
b_olson(w)
print 'b_olson:',time.time()-t
"""
--
http://mail.python.org/mailman/listinfo/python-list
