正文

做了codility网站上一题：CountBoundedSlices

IP云
IP云V管理员/4 阅读
09/08
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

在写上一随笔之前，在Codility网站上还做了一个道题（非Demo题）：CountBoundedSlices，得了60分（害臊呀）。今天又重新做了一下这个算法，性能提高了不少，但由于此题不是Demo题，不能重新在Codility网站测试了。

可以从http://codility.com/cert/view/certAWY5VP-D46CA7989XU4XEZT/details看到题目的详细信息。

这里把题目copy出来：

An integer K and a non-empty zero-indexed array A consisting of N integers are given.

A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called aslice of array A.

A bounded_slice is a slice in which the difference between the maximum and minimum values in the slice is less than or equal to K. More precisely it is a slice, such that max(A[P], A[P + 1], ..., A[Q]) − min(A[P], A[P + 1], ..., A[Q]) ≤ K.

The goal is to calculate the number of bounded_slices.

以下新做的算法及第一次做的算法贴在下面：

def solution(K, A):
# http://codility.com/cert/view/certAWY5VP-D46CA7989XU4XEZT/details
_ret_numer = 0
_count = len(A)
for _inx in range(_count):
_max_int = None
_min_int = None
for _inx2 in range(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2] if _max_int - _min_int <= K:
_ret_numer += 1
else:
break
return _ret_numerdef solution2(K, A): def sum_special(number, times):
return sum(range(number, number-times, -1))
_ret_numer = 0
_current_inx = 0 # current index
_loop_inx = _current_inx # loop index for array.
_minvalue_inx = _current_inx # index of min value for a loop break.
_maxvalue_inx = _current_inx # index of max value for a loop break.
_count = len(A) # array length
while _loop_inx < _count: # compare two values, get max
if A[_maxvalue_inx] < A[_loop_inx]:
_maxvalue_inx = _loop_inx
# compare two values, get min
if A[_minvalue_inx] > A[_loop_inx]:
_minvalue_inx = _loop_inx # break if meeting condition.
if A[_maxvalue_inx] - A[_minvalue_inx] > K:
_first_inx = None
_second_inx = None
if _minvalue_inx <= _maxvalue_inx:
_first_inx, _second_inx = _minvalue_inx, _maxvalue_inx
else:
_first_inx, _second_inx = _maxvalue_inx, _minvalue_inx _ret_numer += sum_special(_second_inx-_current_inx, _first_inx-_current_inx+1) _current_inx = _first_inx + 1 # move next to first_inx
_loop_inx = _current_inx
_minvalue_inx = _current_inx # index of min value for a loop break.
_maxvalue_inx = _current_inx # index of max value for a loop break
else:
_loop_inx += 1 # increment one
if _current_inx != _loop_inx:
_ret_numer += sum_special(_loop_inx-_current_inx, _loop_inx-_current_inx) return _ret_numer

关于新做的算法，虽然性能提高了很多，但我还是不是很满意，因为_loop_inx在每次满足K条件计算后还要重新回溯到_current_inx位置，按理说应该通过记录更多数据达到不需要回退，试了几次发现复杂度陡升。

列了测试case：

def test(K, A):
print K, len(A), A[:10]
import time
_start = time.time()
_value = solution(K, A)
_end = time.time()
print "solution result: time=%f, value=%d" % (_end-_start, _value)
_start = time.time()
_value2 = solution2(K, A)
_end = time.time()
print "solution2 result: time=%f, value=%d" % (_end-_start, _value2)
return _value == _value2def sample_test():
import random
N = random.randint(1,100000)
A = [random.randint(-1000000000,1000000000) for _ in xrange(N)]
K = random.randint(0,1000000000)
return test(K, A)def simulate_test(times=100):
_error_occur = False
print "simulate start..."
for _ in range(times):
if not sample_test():
_error_occur = True
break
if _error_occur:
print "occur error, please check it"
print "simulate complete"

以下是随机做100次，两次算法测试结果对比。可以看到两此算法得到time差距挺大的，如果codility网站测试，应该能够高于60分吧。

>>> simulate_test(times=)
simulate start...
[, -, , -, -, , , -, , -]
solution result: time=2.067000, value=
solution2 result: time=0.028000, value=
[, -, -, -, -, , -, -, -, -]
solution result: time=9.547000, value=
solution2 result: time=0.060000, value=
[-, , , -, -, -, , , , -]
solution result: time=25.332000, value=
solution2 result: time=0.104000, value=
[, , , , , , -, -, -, ]
solution result: time=0.013000, value=
solution2 result: time=0.002000, value=
[-, , , -, , -, , , -, -]
solution result: time=1.731000, value=
solution2 result: time=0.030000, value=
[-, , , , -, -, , , -, -]
solution result: time=29.778000, value=
solution2 result: time=0.124000, value=
[, -, -, -, -, , , -, -, -]
solution result: time=7.330000, value=
solution2 result: time=0.055000, value=
[, , -, , -, -, -, -, , ]
solution result: time=0.580000, value=
solution2 result: time=0.014000, value=
[-, -, , , -, -, -, , -, ]
solution result: time=0.011000, value=
solution2 result: time=0.002000, value=
[-, -, -, -, , -, , , , -]
solution result: time=1.124000, value=
solution2 result: time=0.026000, value=
[, , , -, -, , -, -, -, ]
solution result: time=7.352000, value=
solution2 result: time=0.053000, value=
[-, , -, -, , -, -, -, , ]
solution result: time=17.873000, value=
solution2 result: time=0.084000, value=
[, -, -, , , -, , -, -, ]
solution result: time=0.894000, value=
solution2 result: time=0.017000, value=
[-, -, -, , , -, , -, , -]
solution result: time=9.026000, value=
solution2 result: time=0.064000, value=
[, -, , -, -, , , , , ]
solution result: time=37.246000, value=
solution2 result: time=0.106000, value=
[-, , , -, , -, , , , ]
solution result: time=0.057000, value=
solution2 result: time=0.005000, value=
[, , -, -, , , -, -, -, -]
solution result: time=27.318000, value=
solution2 result: time=0.116000, value=
[-, , -, -, , -, , -, , ]
solution result: time=29.328000, value=
solution2 result: time=0.108000, value=
[, , , -, -, , -, -, , ]
solution result: time=4.457000, value=
solution2 result: time=0.044000, value=
[, -, , , -, , -, , -, ]
solution result: time=27.306000, value=
solution2 result: time=0.112000, value=
[, -, , -, -, -, -, , , -]
solution result: time=0.406000, value=
solution2 result: time=0.012000, value=
[-, -, -, , , , -, , , -]
solution result: time=16.640000, value=
solution2 result: time=0.094000, value=
[-, , -, , , , -, , , ]
solution result: time=0.816000, value=
solution2 result: time=0.019000, value=
[, -, , , , -, -, -, -, ]
solution result: time=0.104000, value=
solution2 result: time=0.007000, value=
[, , -, , , -, , , , -]
solution result: time=10.739000, value=
solution2 result: time=0.064000, value=
[, -, -, -, -, , , , , -]
solution result: time=43.970000, value=
solution2 result: time=0.121000, value=
[, -, -, , , , , , -, -]
solution result: time=26.614000, value=
solution2 result: time=0.114000, value=
[-, , -, , -, , , -, -, ]
solution result: time=40.215000, value=
solution2 result: time=0.116000, value=
[, , , -, , , , , , ]
solution result: time=13.974000, value=
solution2 result: time=0.075000, value=
[, -, -, -, , , , -, , -]
solution result: time=0.337000, value=
solution2 result: time=0.010000, value=
[-, -, -, , , , -, , , ]
solution result: time=1.821000, value=
solution2 result: time=0.029000, value=
[, , , -, , , , , , -]
solution result: time=23.379000, value=
solution2 result: time=0.098000, value=
[-, , , -, , , , , , ]
solution result: time=46.241000, value=
solution2 result: time=0.137000, value=
[, , , , -, -, , -, -, ]
solution result: time=19.033000, value=
solution2 result: time=0.096000, value=
[, -, , , -, , -, -, , ]
solution result: time=0.246000, value=
solution2 result: time=0.011000, value=
[, -, -, , , , , , , ]
solution result: time=25.029000, value=
solution2 result: time=0.093000, value=
[-, , , -, -, -, -, , -, ]
solution result: time=24.828000, value=
solution2 result: time=0.113000, value=
[-, , -, -, , -, -, -, -, ]
solution result: time=33.016000, value=
solution2 result: time=0.121000, value=
[, , , , , -, -, , -, ]
solution result: time=0.939000, value=
solution2 result: time=0.018000, value=
[, , -, , -, , , -, , -]
solution result: time=24.851000, value=
solution2 result: time=0.088000, value=
[, -, , , , , , , -, ]
solution result: time=4.077000, value=
solution2 result: time=0.038000, value=
[-, , , -, -, , , -, -, ]
solution result: time=1.293000, value=
solution2 result: time=0.025000, value=
[, -, -, , , -, , -, , ]
solution result: time=30.663000, value=
solution2 result: time=0.113000, value=
[, , , , -, -, -, -, , -]
solution result: time=1.144000, value=
solution2 result: time=0.024000, value=
[, -, , -, , -, -, , -, ]
solution result: time=2.057000, value=
solution2 result: time=0.030000, value=
[, , -, -, -, -, -, , , ]
solution result: time=15.251000, value=
solution2 result: time=0.076000, value=
[, , , , , -, -, -, , -]
solution result: time=1.286000, value=
solution2 result: time=0.026000, value=
[-, -, -, , , -, , , -, -]
solution result: time=0.239000, value=
solution2 result: time=0.009000, value=
[-, , , -, -, -, , -, , ]
solution result: time=0.073000, value=
solution2 result: time=0.009000, value=
[, -, -, -, , , -, , , -]
solution result: time=34.535000, value=
solution2 result: time=0.140000, value=
[, -, , , , -, , , -, -]
solution result: time=9.660000, value=
solution2 result: time=0.076000, value=
[-, , -, -, , , , -, , -]
solution result: time=11.874000, value=
solution2 result: time=0.073000, value=
[, -, -, , , -, , , -, -]
solution result: time=11.689000, value=
solution2 result: time=0.063000, value=
[, -, -, , , -, , , -, ]
solution result: time=20.965000, value=
solution2 result: time=0.088000, value=
[-, -, , -, -, , -, -, -, ]
solution result: time=3.483000, value=
solution2 result: time=0.040000, value=
[-, , , , -, , -, , , ]
solution result: time=12.949000, value=
solution2 result: time=0.077000, value=
[-, -, -, , , , -, , -, ]
solution result: time=12.332000, value=
solution2 result: time=0.077000, value=
[, -, -, -, , -, -, , , -]
solution result: time=17.879000, value=
solution2 result: time=0.087000, value=
[, -, -, -, -, -, -, , , -]
solution result: time=37.262000, value=
solution2 result: time=0.137000, value=
[-, , -, -, -, -, , -, -, -]
solution result: time=34.129000, value=
solution2 result: time=0.129000, value=
[, -, -, -, , , , , , ]
solution result: time=31.118000, value=
solution2 result: time=0.130000, value=
[-, , -, -, , , -, -, , ]
solution result: time=37.183000, value=
solution2 result: time=0.117000, value=
[-, , , , , -, -, -, , -]
solution result: time=15.267000, value=
solution2 result: time=0.080000, value=
[-, , , -, -, , -, -, , -]
solution result: time=16.971000, value=
solution2 result: time=0.076000, value=
[, -, , , , -, -, , , ]
solution result: time=26.181000, value=
solution2 result: time=0.109000, value=
[-, , , -, -, -, , -, , ]
solution result: time=10.175000, value=
solution2 result: time=0.063000, value=
[, -, , -, -, , , -, , ]
solution result: time=0.538000, value=
solution2 result: time=0.019000, value=
[-, -, -, , , -, -, , -, -]
solution result: time=0.004000, value=
solution2 result: time=0.001000, value=
[-, -, , -, -, -, -, -, , -]
solution result: time=13.853000, value=
solution2 result: time=0.064000, value=
[, , -, -, -, -, , , -, ]
solution result: time=19.379000, value=
solution2 result: time=0.108000, value=
[-, , -, -, , -, -, , -, ]
solution result: time=14.006000, value=
solution2 result: time=0.077000, value=
[-, , , , , , -, , , ]
solution result: time=33.683000, value=
solution2 result: time=0.119000, value=
[-, -, , -, -, -, , -, -, -]
solution result: time=13.952000, value=
solution2 result: time=0.086000, value=
[, , -, -, -, -, , , -, ]
solution result: time=7.784000, value=
solution2 result: time=0.060000, value=
[, -, , -, -, -, -, , , ]
solution result: time=39.554000, value=
solution2 result: time=0.118000, value=
[-, , -, , , , , -, -, ]
solution result: time=8.962000, value=
solution2 result: time=0.063000, value=
[-, , , , , , , , , ]
solution result: time=13.551000, value=
solution2 result: time=0.066000, value=
[-, , -, -, -, -, , -, -, ]
solution result: time=46.575000, value=
solution2 result: time=0.193000, value=
[-, -, , -, -, , , , , ]
solution result: time=17.800000, value=
solution2 result: time=0.096000, value=
[-, -, -, -, -, , -, -, -, ]
solution result: time=8.196000, value=
solution2 result: time=0.059000, value=
[-, , , , , -, , -, -, -]
solution result: time=1.367000, value=
solution2 result: time=0.026000, value=
[-, , -, -, , -, , -, , -]
solution result: time=34.445000, value=
solution2 result: time=0.104000, value=
[, , -, -, , -, -, -, -, ]
solution result: time=6.394000, value=
solution2 result: time=0.057000, value=
[-, -, -, , -, , -, -, , -]
solution result: time=0.540000, value=
solution2 result: time=0.015000, value=
[-, , , -, , , -, , -, -]
solution result: time=16.369000, value=
solution2 result: time=0.093000, value=
[, -, -, , -, -, , -, , -]
solution result: time=0.908000, value=
solution2 result: time=0.019000, value=
[-, , , -, , , -, , , ]
solution result: time=2.199000, value=
solution2 result: time=0.033000, value=
[-, -, -, -, , -, , -, -, -]
solution result: time=19.046000, value=
solution2 result: time=0.093000, value=
[, , -, -, -, , -, , -, ]
solution result: time=4.440000, value=
solution2 result: time=0.042000, value=
[-, , , , , , -, , -, -]
solution result: time=5.149000, value=
solution2 result: time=0.057000, value=
[, , , -, -, -, , , -, ]
solution result: time=20.987000, value=
solution2 result: time=0.089000, value=
[-, , -, , , , , , -, -]
solution result: time=0.585000, value=
solution2 result: time=0.017000, value=
[, -, , , -, -, , , -, ]
solution result: time=30.561000, value=
solution2 result: time=0.128000, value=
[, , -, , -, , , -, -, -]
solution result: time=44.342000, value=
solution2 result: time=0.119000, value=
[-, -, -, , -, , , , , ]
solution result: time=36.514000, value=
solution2 result: time=0.108000, value=
[-, , -, -, , , , , , -]
solution result: time=33.019000, value=
solution2 result: time=0.123000, value=
[, , , , -, , , , , -]
solution result: time=13.259000, value=
solution2 result: time=0.091000, value=
[, -, -, -, , , , -, , -]
solution result: time=33.030000, value=
solution2 result: time=0.116000, value=
[-, -, , -, , -, -, -, , ]
solution result: time=34.337000, value=
solution2 result: time=0.129000, value=
[-, , -, -, , -, -, , , -]
solution result: time=0.360000, value=
solution2 result: time=0.010000, value=
simulate complete
>>>