1

我有以下输入：

  • 公差水平 T
  • 数字数量 N
  • N个数字

任务是在这 N 个数字中找到最长的周期，使它们在容差范围内。更准确地说，给定子字符串的左右边界l和r两个不同的元素a1，并且a2在这两个边界之间，它必须保持|a1 - a1| <= T. 我怎样才能有效地做到这一点？我的做法是：

def getLength(T, N, numbers):

    max_length = 1

    for i in range(0, N-1):
        start = numbers[i]
        numlist = [start]

        for j in range(i+1, N):
            end = numbers[j]
            numlist.append(end)

            if (max(numlist) - min(numlist)) > T:
                break

            if (j-i+1) > max_length:
                max_length = j-i+1

    return max_length

编辑：说清楚。该代码按预期工作。但是，它的效率不够高。我想更有效地做到这一点。

4

1 回答 1

0

首先，我不确定您的代码是否符合您在问题中描述的内容。其次，处理 12,000 个随机数只需要不到一秒的时间。

无论如何，它可以通过不调用min()并max()在numlist每次添加新元素时加速。相反，您可以使用几条if语句更新当前的最小和最大变量。

这里的代码显示正在完成，以及我为计时性能编写的一个简单框架：

def getLength(T, N, numbers):
    max_length = 1

    for i in range(N-1):
        start = numbers[i]
        numlist = [start]
        min_numlist = max_numlist = start  # Added variables.

        for j in range(i+1, N):
            end = numbers[j]
            numlist.append(end)

# Inefficient - replaced.
#            if (max(numlist) - min(numlist)) > T:
#                break

            # Update extremities.
            if end > max_numlist:
                max_numlist = end
            if end < min_numlist:
                min_numlist = end

            if max_numlist-min_numlist > T:
                break

            if j-i+1 > max_length:
                max_length = j-i+1

    return max_length


if __name__ == '__main__':
    import random
    import time

    random.seed(42)  # Use hardcoded seed to get same numbers each time run.
    T = 100
    N = 12000
    numbers = [random.randrange(1000) for _ in range(N)]
    starttime = time.time()
    max_length = getLength(T, N, numbers)
    stoptime = time.time()
    print('max length: {}'.format(max_length))
    print('processing {:,d} elements took {:.5f} secs'.format(N, stoptime-starttime))
于 2017-11-07T02:38:48.433 回答