确定2D阵列中最长连续值范围的最快方法

Question

问题

让我们假设我们正在使用大型数据集,为了简单起见,我们在这个问题中使用这个较小的数据集:

dataset = [["PLANT", 4,11],
           ["PLANT", 4,12],
           ["PLANT", 34,4],
           ["PLANT", 6,5],
           ["PLANT", 54,45],
           ["ANIMAL", 5,76],
           ["ANIMAL", 7,33],
           ["Animal", 11,1]]

并且我们想找出哪个列具有最长的连续值范围,哪个是最快的找出方法,哪个是最佳列？

天真的做法

我发现它很快就可以按每列分类

sortedDatasets = []
for i in range(1,len(dataset[0]):
    sortedDatasets.append(sorted(dataset,key=lambda x: x[i]))

但是这里出现了滞后的部分:我们可以从这里继续for loop为每个已排序的数据集做一个,并计算连续的元素但是当处理for loopspython时非常慢.

现在我的问题是:有没有比这种天真的方法更快的方法,甚至可能有这些2D容器的内置函数？

---

更新:

更准确地说,范围的含义可以通过这种伪算法来描述 - 这包括在以下情况下递增current value == next value:

if nextValue > current Value +1: 
     {reset counter} 
else: 
     {increment counter}

Answer 1

您可以使用合理的效率来完成此操作groupby.我会分阶段进行,所以你可以看看它是如何工作的.

from itertools import groupby

dataset = [
    ["PLANT", 4, 11],
    ["PLANT", 4, 12],
    ["PLANT", 34, 4],
    ["PLANT", 6, 5],
    ["PLANT", 54, 45],
    ["ANIMAL", 5, 76],
    ["ANIMAL", 7, 33],
    ["ANIMAL", 11, 1],
]

# Get numeric columns & sort them in-place
sorted_columns = [sorted(col) for col in zip(*dataset)[1:]]
print sorted_columns
print

# Check if tuple `t` consists of consecutive numbers
keyfunc = lambda t: t[1] == t[0] + 1

# Search for runs of consecutive numbers in each column
for col in sorted_columns:
    #Create tuples of adjacent pairs of numbers in this column
    pairs = zip(col, col[1:])
    print pairs
    for k,g in groupby(pairs, key=keyfunc):
        print k, list(g)
    print

产量

[[4, 4, 5, 6, 7, 11, 34, 54], [1, 4, 5, 11, 12, 33, 45, 76]]

[(4, 4), (4, 5), (5, 6), (6, 7), (7, 11), (11, 34), (34, 54)]
False [(4, 4)]
True [(4, 5), (5, 6), (6, 7)]
False [(7, 11), (11, 34), (34, 54)]

[(1, 4), (4, 5), (5, 11), (11, 12), (12, 33), (33, 45), (45, 76)]
False [(1, 4)]
True [(4, 5)]
False [(5, 11)]
True [(11, 12)]
False [(12, 33), (33, 45), (45, 76)]

现在,要攻击你的实际问题:

from itertools import groupby

dataset = [
    ["PLANT", 4, 11],
    ["PLANT", 4, 12],
    ["PLANT", 34, 4],
    ["PLANT", 6, 5],
    ["PLANT", 54, 45],
    ["ANIMAL", 5, 76],
    ["ANIMAL", 7, 33],
    ["ANIMAL", 11, 1],
]

# Get numeric columns & sort them in-place
sorted_columns = [sorted(col) for col in zip(*dataset)[1:]]

# Check if tuple `t` consists of consecutive numbers
keyfunc = lambda t: t[1] == t[0] + 1

#Search for the longest run of consecutive numbers in each column
runs = []
for i, col in enumerate(sorted_columns, 1):
    pairs = zip(col, col[1:])
    m = max(len(list(g)) for k,g in groupby(pairs, key=keyfunc) if k)
    runs.append((m, i))

print runs
#Print the highest run length found and the column it was found in
print max(runs)

产量

[(3, 1), (1, 2)]
(3, 1)

FWIW,这可以压缩成一行.它更高效,因为它使用了几个生成器表达式而不是列表推导,但它不是特别易读:

print max((max(len(list(g)) 
    for k,g in groupby(zip(col, col[1:]), key=lambda t: t[1] == t[0] + 1) if k), i)
        for i, col in enumerate((sorted(col) for col in zip(*dataset)[1:]), 1))

更新

我们可以通过做一些小的改动来处理你的新的连续序列定义.

首先,我们需要一个键函数,True如果排序列中相邻数字对之间的差异<= 1 ,则返回该函数.

def keyfunc(t):
    return t[1] - t[0] <= 1

而不是采用与该键函数匹配的序列的长度,我们现在做一些简单的算术来查看序列中值范围的大小.

def runlen(seq):
    return 1 + seq[-1][1] - seq[0][0]

把它们放在一起:

def keyfunc(t):
    return t[1] - t[0] <= 1

def runlen(seq):
    return 1 + seq[-1][1] - seq[0][0]

# Get numeric columns & sort them in-place
sorted_columns = [sorted(col) for col in zip(*dataset)[1:]]

#Search for the longest run of consecutive numbers in each column
runs = []
for i, col in enumerate(sorted_columns, 1):
    pairs = zip(col, col[1:])
    m = max(runlen(list(g)) for k,g in groupby(pairs, key=keyfunc) if k)
    runs.append((m, i))

print runs
#Print the highest run length found and the column it was found in
print max(runs)

更新2

如评论中所述,如果其arg是空序列则会max引发ValueError.处理它的一种简单方法是将max调用包装在一个try..except块中.如果异常很少发生,这是非常有效的,try..except实际上if...else当没有引发异常时比等效逻辑更快.所以我们可以这样做:

run = (runlen(list(g)) for k,g in groupby(pairs, key=keyfunc) if k)
try:
    m = max(run)
except ValueError:
    m = 0
runs.append((m, i))

但如果这种异常经常发生,最好使用另一种方法.

这是一个使用完全成熟的生成器函数的新版本,find_runs代替生成器表达式.在开始处理列数据之前find_runs简单地yield为零,因此max总是至少有一个值要处理.我已经内联runlen计算以节省额外函数调用的开销.这种重构还使得runs在列表理解中构建列表变得更容易.

from itertools import groupby

dataset = [
    ["PLANT", 4, 11, 3],
    ["PLANT", 4, 12, 5],
    ["PLANT", 34, 4, 7],
    ["PLANT", 6, 5, 9],
    ["PLANT", 54, 45, 11],
    ["ANIMAL", 5, 76, 13],
    ["ANIMAL", 7, 33, 15],
    ["ANIMAL", 11, 1, 17],
]

def keyfunc(t):
    return t[1] - t[0] <= 1

def find_runs(col):
    pairs = zip(col, col[1:])
    #This stops `max` from choking if we don't find any runs
    yield 0
    for k, g in groupby(pairs, key=keyfunc):
        if k:
            #Determine run length
            seq = list(g)
            yield 1 + seq[-1][1] - seq[0][0]

# Get numeric columns & sort them in-place
sorted_columns = [sorted(col) for col in zip(*dataset)[1:]]

#Search for the longest run of consecutive numbers in each column
runs = [(max(find_runs(col)), i) for i, col in enumerate(sorted_columns, 1)]
print runs

#Print the highest run length found and the column it was found in
print max(runs)

产量

[(4, 1), (2, 2), (0, 3)]
(4, 1)