这是一个稍微更有效的解决方案(对不起,它是 JavaScript)。关键是只存储一次长度,在您的代码中,每次长度增加一个“startLength [start] = 1 + cnt - start”时,您都会进行计算。
通过使用条件“if previous == 0 and r == 1”而不是“if previous == 1 and r == 1”。我减少了计算量,但我还必须在 for 循环之后添加一个“if r == 1”来捕获最终情况。
var test=[0,1,1,1,0,0,0,1,1,0,0,1,0];
function runs(arr) {
var result = {};
var start = 0;
var previous = 0;
var cnt = 0;
var r = 0;
for(; cnt<arr.length; cnt++) {
var r = arr[cnt];
if(r == 1 && previous == 0)
start = cnt;
if(r == 0 && previous == 1)
result[start] = cnt - start;
previous = r;
}
if(r == 1)
result[start] = cnt - start;
return result;
}
var result = runs(test);
for(var start in result)
console.log("start " + start + " length " + result[start]);
编辑 2这是一个 python 基准测试,显示使用 groupby 函数(目前是这个问题的最佳答案)要慢得多。
from itertools import groupby
from operator import itemgetter
import random
import time
lst = [ 1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0]
def makeList(size):
random.seed()
return [random.randint(0,1) for r in xrange(size)]
def runs1(lst, showOutput):
startLength = {}
for k,v in groupby(enumerate(lst),key=itemgetter(1)):
if k:
v = list(v)
startLength[v[0][0]] = v[-1][0] + 1 - v[0][0]
if showOutput == True:
for s,l in startLength.iteritems():
print s,l
def runs2(lst, showOutput):
previous = 0
cnt = 0
startLength = {}
for r in lst:
if previous == 0 and r == 1:
start = cnt
if previous == 1 and r == 0:
startLength[start] = cnt - start
previous = r
cnt += 1
if r == 1:
startLength[start] = cnt - start
if showOutput == True:
for s,l in startLength.iteritems():
print s,l
testList = makeList(10)
print "slow version"
runs1(testList, True)
print "fast version"
runs2(testList, True)
benchmarkList = makeList(10000)
start = time.time()
runs1(benchmarkList, False)
print "slow ", time.time() - start
start = time.time()
runs2(benchmarkList, False)
print "fast ", time.time() - start
start = time.time()
runs1(benchmarkList, False)
print "slow ", time.time() - start
start = time.time()
runs2(benchmarkList, False)
print "fast ", time.time() - start
start = time.time()
runs1(benchmarkList, False)
print "slow ", time.time() - start
start = time.time()
runs2(benchmarkList, False)
print "fast ", time.time() - start