像这样的代码
def IsEven(n):
if n%2==0:
return "Is even"
else:
return "Is odd"
可以转换为如下函数
def isEven(n):
return ["Is even","Is odd"][n%2==0]
问题是这样的代码:
def intervalsToOutput(n):
intervals=[(x1,x2), (x3,x4), (x5,x6), ... (xn,xn+1)]
if x1<=n<=x2:
return "in first interval"
elif x3<=n<=x4:
return "in second interval"
elif x5<=n<=x6:
return "in third interval"
...
elif xn<=n<=xn+1:
return "in last interval"
... can be replaced efficiently with a function like this:
(assuming the intervals (xi,xi+1) are not overlapping, and are sorted by xi)
def intervalsToOutput(n):
intervals=[(x1,x2), (x3,x4), (x5,x6), ... (xn,xn+1)]
answer=["in first interval","in second interval","in third interval",...,"in last interval"]
return answer[index of (n in Interval)]
我做的最好的(looking for speed)是
def intervalsToOutput(n):
intervals=[(x1,x2), (x3,x4), (x5,x6), ... (xn,xn+1)]
answer=["in first interval","in second interval","in third interval",...,"in last interval"]
import bisect as bisect
return answer[bisect.bisect_left(intervals, (n, )) - 1]# -1 because it is a zero based list
What bisect_left does is to find the position of n in intervals (in O(log(n)) time) by comparing (n,) with (xn,xn+1)
But the purpose of bisect is to find the insertion place, so it fails for any n which is x_{i+1}<n<=x_{j}
... (x_i, x_{i+1}), (x_j, x_{j+1}) ...
[x_i______x_i+1] fails on this interval x_j [________x_j+1]
EDIT:
#generate intervals and answers
import random
min=0
max=20
numIntervals=6
def Intervals(min,max,n):
randInts = random.sample(range(min, max), n * 2)
randInts.sort()
return [(x1,x2) for x1,x2 in zip(randInts[::2], randInts[1::2])]
intervals=Intervals(min,max,numIntervals)
answer=[f"In {n}th interval" for n in range(len(intervals))]
#Implement solution
import intervaltree
tree = intervaltree.IntervalTree()
[tree.addi(i[0],i[1],a) for i,a in zip(intervals,answer)]
def intervalsToOutput(x):
answer=tree.at(x)
if len(answer)>0:
return answer.pop().data
return "value not found"
print(intervals)
[print(f"{x} is ",intervalsToOutput(x)) for x in random.sample(range(min,max),numIntervals)]