在Python中迭代巨大列表的子列表的有效方法

Question

所以我需要找到一种有效的方法来迭代 python 中的大列表。

给定：整数和数字数组（子列表的长度）

约束：数组最多 100K 个元素，元素在范围 (1,2**31) 内

任务：对于每个子列表，找到最大数和最小数之间的差异。打印出最大的差异。

Ex: [4,6,3,4,8,1,9], number = 3
As far as I understand I have to go through every sublist:

[4,6,3]  max - min = 6 - 3 = 3
[6,3,4]  3
[3,4,8]  5
[4,8,1]  7
[8,1,9]  8

final max = 8

所以我的解决方案是：

import time

def difference(arr, number): 
    maxDiff = 0
    i = 0
    while i+number != len(arr)+1:
        diff = max(arr[i:i+number]) - min(arr[i:i+number])

        if diff > maxDiff:
            maxDiff = diff

        i += 1

    print maxDiff


length = 2**31
arr = random.sample(xrange(length),100000)   #array wasn't given. My sample
t0 = time.clock()
difference(arr,3)
print 'It took :',time.clock() - t0

回答：

2147101251
It took : 5.174262

我也对 for 循环做了同样的事情，这导致了更糟糕的时间：

def difference(arr,d):
    maxDiff = 0
    if len(arr) == 0:
        maxDiff = 0
    elif len(arr) == 1:
        maxDiff = arr[0]
    else:
        i = 0
        while i + d != len(arr)+1:

            array = []
            for j in xrange(d):
                array.append(arr[i + j])

            diff = max(array) - min(array)

            if diff > maxDiff:
                maxDiff = diff

            i += 1
    print maxDiff

length = 2**31
arr = random.sample(xrange(length),100000)      #array wasn't given. My sample
t0 = time.clock()
difference(arr,1000)
print 'It took :',time.clock() - t0

回答：

2147331163
It took : 14.104639

我的挑战是将时间缩短到 2 秒。

最有效的方法是什么？

根据@rchang 和@gknicker 的回答和评论，我得到了改进。我想知道我还能做些什么吗？

def difference(arr,d):
    window = arr[:d]
    arrayLength = len(arr)
    maxArrayDiff = max(arr) - min(arr)

    maxDiff = 0

    while d < arrayLength:

        localMax = max(window)
        if localMax > maxDiff:
            diff = localMax - min(window)

            if diff == maxArrayDiff:
                return diff
                break
            elif diff > maxDiff:
                maxDiff = diff

        window.pop(0)
        window.append(arr[d])

        d += 1

    return maxDiff


#arr = [3,4,6,15,7,2,14,8,1,6,1,2,3,10,1]
length = 2**31
arr = random.sample(xrange(length),100000)
t0 = time.clock()
print difference(arr,1000)
print 'It took :',time.clock() - t0

回答：

2147274599
It took : 2.54171

不错。还有其他建议吗？

Answer 1

这是我解决这个问题的尝试。

我进行了大量的实验和测量，并得出以下结论：

1. subset_length对性能有重大影响。
2. numpymin/max 比内置函数快得多，但仅适用于大型数组，低于 50，内置函数更快。
3. 这具有以下效果：对于subset_length 来说
   • 低于 10 你的最新版本是最快的
   • 在 10 到 50 之间，我的算法的没有 numpy 的版本（尚未发布（尚未））是最快的
   • 50以上我的算法是最快的
   • 在 1000 时，该算法的性能比您的算法高出 100 倍

请注意，它array必须是 anumpy.array()并且subset_length必须是 3 或更多。

def difference_np(array, subset_length):
    assert subset_length > 2, "subset_length must be larger than 2"
    length = array.size
    total_diff = array.max()-array.min()

    current_min = array[:subset_length].min()
    current_max = array[:subset_length].max()
    max_diff = current_max - current_min
    max_diff_index = 0
    index = subset_length
    while index < length:
        i_new = index
        i_old = index-number
        index += 1     
        new = array[i_new]            
        old = array[i_old]

        # the idea here is to avoid calculating the
        #   min/max over the entire subset as much as possible,
        #   so we treat every edge case separately.
        if new < current_min:
            current_min = new
            if old == current_max:
                current_max = array[i_old+1:i_new-1].max()
        elif new > current_max:
            current_max = new
            if old == current_min:
                current_min = array[i_old+1:i_new-1].min()
        elif old == current_min:
            current_min = array[i_old+1:i_new].min()
        elif old == current_max:
            current_max = array[i_old+1:i_new].max()
        else:
            continue

        current_diff = current_max-current_min
        if current_diff > max_diff:
            max_diff = current_diff
            max_diff_index = i_old

        # shortcut-condition
        if max_diff == total_diff:
            print('shortcut at', (index-1)/(length-subset_length), '%' )
            break

    return max_diff, max_diff_index

我不确定快捷方式条件是否那么有效，因为它很少适用并且需要输入数组的两次完整迭代。

编辑

如果算法使用 ，则还存在其他改进空间list.pop(0)。由于list针对右侧操作进行了优化，list.pop(0)因此相对昂贵。存在collections.deque一种提供快速左侧弹出的替代方案：deque.popleft()。给整体速度带来了不小的提升。

numpy collections.deque这是我的算法的非基于版本：

def difference_deque(array, subset_length):
    assert subset_length > 1, "subset_length must be larger than 1"
    length = len(array)
    total_diff = max(array)-min(array)

    current_slice = collections.deque(array[:subset_length])
    current_min = min(current_slice)
    current_max = max(current_slice)
    max_diff = current_max - current_min
    max_diff_index = 0

    index = subset_length
    while index < length:
        i_new = index
        i_old = index-number
        index += 1     
        new = array[i_new]            
        old = current_slice.popleft()

        if new < current_min:
            current_min = new
            if old == current_max:
                current_max = max(current_slice)
            current_slice.append(new)
        elif new > current_max:
            current_max = new
            if old == current_min:
                current_min = min(current_slice)
            current_slice.append(new)
        elif old == current_min:
            current_slice.append(new)
            current_min = min(current_slice)
        elif old == current_max:
            current_slice.append(new)
            current_max = max(current_slice)
        else:
            current_slice.append(new)
            continue

        current_diff = current_max-current_min
        if current_diff > max_diff:
            max_diff = current_diff
            max_diff_index = i_old+1

        # shortcut-condition
        if max_diff == total_diff:
            print('shortcut at', (index-1)/(length-number), '%' )
            break

    return max_diff, max_diff_index

它稍微扭曲了运行时排名： - 最多 10 你的算法（带双端队列）是最好的 - 最多 100 我的算法（带双端队列）是最好的 - 超过 100 我的算法（带 numpy）是最好的