熊猫数据优化展望

Question

有什么最好的方法来处理熊猫的数据？我想遍历一个dataframe，并找到最近的下一个索引，它至少有+/-2的值差。例如: 100、99、102、98、103、103将创建一个新列，其中2、2、3、0、N/A、0表示找不到。

我的解决方案性能是n* log(n)。任何优秀的人都能给我一个更好的性能解决方案吗？

Answer 1

当所有元素都是整数时，可以在线性时间内这样做。下面的解决方案是复杂的，而且只对算法感兴趣(如果是这样的话)。由于它使用循环和数据结构，任何真正的实现都需要在C/C++/Cython中实现(否则，常数会非常高，以至于需要非常长的序列才能开始看到改进，尽管它是线性的)。

由于解决方案是复杂的，我将首先做一些简化的假设，然后说明如何消除它们。最初的假设是：

1. 需要的是找到下一个位置的索引，即2或更大。
2. 所有的整数都是不同的。

有了这些假设，就有可能使用一个众所周知的面试问题的变体(这很常见，我认为这是民间传说)。这样做的目的是保留数组中尚未找到下一个位置的位置的堆栈。在遍历元素和位置时，保持循环不变量：

• 堆栈中的索引正在增加。
• 堆栈不包含i，j位置，使ai +2 <= aj和i

这些不变量最初是很满足的，我将展示它们是如何维护的。

假设在迭代j中，堆栈的顶部是i:我会将其标记为<.，i> (堆栈位于右侧)。当aj >= ai + 2时，我们可以弹出堆栈并将I的下一个位置设置为j。当这种情况发生时，我们可以弹出堆栈，直到条件失败。但是，作为某一点，堆栈可以是<.，k，i>，其中包含ai +2> aj。对不变量的一些思考就足以看出，在这种情况下，如果堆栈中有一个元素需要弹出，那么它必须是k(如果它存在)。这是唯一需要检查的项目--最后一个项目之前的任何其他项目都不能是一个需要弹出的项目。所以，我们只需要检查k，如果有必要的话也要打开它。在迭代结束时，我们只需要推送j本身。

下面的代码是这样做的：

def plus2_detector(a, verbose=False):
    if verbose:
        print 'starting with', a
    remaining, out = [], [None] * len(a)
    for i, e in enumerate(a):
        if verbose:
            print 'it begin', i, e, remaining
        while remaining and e >= a[remaining[-1]] + 2:
            if verbose:
                print 'setting', i, remaining[-1], a[remaining[-1]]
            out[remaining[-1]] = i 
            del remaining[-1]
        if len(remaining) > 1 and e >= a[remaining[-2]] + 2:
            if verbose:
                print 'back setting', i, remaining[-2], a[remaining[-2]]
            out[remaining[-2]] = i 
            del remaining[-2]
        remaining.append(i) 
        if verbose:
            print 'it end', i, e, remaining
    return out

你可以运行它，例如，

>>> plus2_detector([1, 2, 3, 5, 4, -1, -2, 10, 9, 8, 7, 11], False)
[2, 3, 3, 7, 7, 7, 7, None, 11, 11, 11, None]

为了直观地感受它所做的事情，您可以在不同的(不同的整数！)上运行它！使用verbose=True，看看它能做什么。

现在要处理掉简化的问题。

第一个简化过程很简单:运行该算法的两个副本:一个检查>= 2，一个检查<= -2，然后组合结果。

第二个简化是比较棘手的。问题是，如果堆栈的顶部不需要弹出，我们可能需要搜索许多项目，看看是否需要弹出--这个潜在项不一定就在顶部下面。如果堆栈顶部的元素是相同的，则可能发生这种情况。

处理这个问题很乏味，但在概念上并没有那么困难。堆栈现在需要包含对等元素的连续未处理索引的整数列表。这意味着当您推送一个新索引时，您需要检查它是否继续运行。如果是，则将其追加到顶部的列表中；如果没有，则创建一个新的元组。现在，所有连续的等效未处理项都分组在一起(类似于itertools.groupby所做的事情)。

有一些技术上的复杂问题(当弹出倒数第二个列表时，我们可能需要结合顶部和新的倒数第二个元组)，但想法是一样的。

使用摊销分析的标准参数(每个元素被插入并弹出一次，非弹出操作是常量)，复杂性是线性的。

以下是查找+2或更高索引的一般情况的代码，但不限制元素是唯一的：

def general_plus2_detector(a, verbose=False):
    if verbose:
        print 'starting with', a
    remaining, out = [], [None] * len(a)
    for i, e in enumerate(a):
        if verbose:
            print 'it begin', i, '(', e, ')', remaining
        while remaining and e >= a[remaining[-1][0]] + 2:
            for j in remaining[-1]:
                if verbose:
                    print 'setting', j, '(', a[j], ') to', i, '(', a[i], ')'
                out[j] = i
            del remaining[-1]
        if len(remaining) > 1 and e >= a[remaining[-2][0]] + 2:
            for j in remaining[-2]:
                if verbose:
                    print 'back setting', j, '(', a[j], ') to', i, '(', a[i], ')'
                out[j] = i
            del remaining[-2]
            if len(remaining) > 1 and a[remaining[-2][0]] == a[remaining[-1][0]]:
                if verbose:
                    print 'joining', remaining[-2], remaining[-1]
                remaining[-1].extend(remaining[-2])
                del remaining[-2]
        if not remaining or a[remaining[-1][0]] != e:
            remaining.append([i]) 
        else:
            remaining[-1].append(i)
        if verbose:
            print 'it end', i, '(', e, ')', remaining
    return out

运行它显示：

a = [-1, -2, 3, 2, 2, 3, 2, 2, 4, 5, 4, 5, 2, 3, 4, 5, 5, 4, 4, 7]
>>> general_plus2_detector(a, False)
[2, 2, 9, 8, 8, 9, 8, 8, 19, 19, 19, 19, 14, 15, 19, 19, 19, 19, 19, None]