python-2.7 - 在python中迭代巨大列表的子列表的有效方法

Question

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

给定:整数和数字数组(子列表的长度)

约束条件:数组最多 100K 个元素，元素在 range(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

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

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

subset_length 对性能有显着影响。

numpy min/max 比内置函数快得多，但仅适用于大型数组，例如 50 以下，内置函数更快。

这对子集长度的影响是

低于 10 你的最新版本是最快的

在 10 到 50 之间，我的算法版本没有 numpy(尚未发布(尚未发布))是最快的

超过 50 我的算法是最快的

在 1000 时，此算法的性能比您的算法高 100 倍

请注意 array 必须是 numpy.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)是最好的