时间戳

首页 > 解决方案 > 将丢失的数字序列转换为其范围的任何简单方法？

python - 将丢失的数字序列转换为其范围的任何简单方法？

问题描述

假设我有一个类似的列表：''' [1,2,3,4,9,10,11,20] ''' 我需要结果是这样的：''' [[4,9], [11,20]] ''' 我定义了一个函数，如下所示：

def get_range(lst):
i=0
seqrange=[]
for new in lst:
    a=[]
    start=new
    end=new
    if i==0:
        i=1
        old=new
    else:
        if new - old >1:
            a.append(old)
            a.append(new)
    old=new
    if len(a):
        seqrange.append(a)
return seqrange

还有其他更简单有效的方法吗？我需要在数百万范围内执行此操作。

标签： python

解决方案

您可以使用 numpy 数组和它们附带的diff函数。当你有数百万行时，Numpy比循环更有效。

顺便说一句： 为什么 numpy 数组这么快？因为它们是数据数组而不是指向数据的指针数组（这就是 Python 列表），因为它们将一大堆计算卸载到用 C 编写的后端，并且因为它们利用 SIMD 范例来运行单一I同时对多个数据进行指令。

现在回到手头的问题：

该diff函数为我们提供了数组连续元素之间的差异。非常方便，因为我们需要找到这个差异大于已知的threshold！

import numpy as np

threshold = 1
arr = np.array([1,2,3,4,9,10,11,20])

deltas = np.diff(arr)
# There's a gap wherever the delta is greater than our threshold
gaps = deltas > threshold 
gap_indices = np.argwhere(gaps)

gap_starts = arr[gap_indices]
gap_ends = arr[gap_indices + 1] 

# Finally, stack the two arrays horizontally
all_gaps = np.hstack((gap_starts, gap_ends))
print(all_gaps)
# Output: 
# [[ 4  9]
#  [11 20]]

您可以all_gaps像 2D 矩阵一样访问：例如，all_gaps[0, 1]会给您9。如果您确实需要将答案作为列表列表，只需将其转换为：

all_gaps_list = all_gaps.tolist()
print(all_gaps_list)
# Output: [[4, 9], [11, 20]]

将@happydave 的答案中的迭代方法的运行时间与 numpy 方法进行比较：

import random
import timeit

import numpy

def gaps1(arr, threshold):
    deltas = np.diff(arr)
    gaps = deltas > threshold 
    gap_indices = np.argwhere(gaps)
    gap_starts = arr[gap_indices]
    gap_ends = arr[gap_indices + 1] 
    all_gaps = np.hstack((gap_starts, gap_ends))
    return all_gaps

def gaps2(lst, thr):
    seqrange = []
    for i in range(len(lst)-1):
      if lst[i+1] - lst[i] > thr:
        seqrange.append([lst[i], lst[i+1]])
    return seqrange

test_list = [i for i in range(100000)]
for i in range(100):
    test_list.remove(random.randint(0, len(test_list) - 1))

test_arr = np.array(test_list)

# Make sure both give the same answer:
assert np.all(gaps1(test_arr, 1) == gaps2(test_list, 1))

t1 = timeit.timeit('gaps1(test_arr, 1)', setup='from __main__ import gaps1, test_arr', number=100)
t2 = timeit.timeit('gaps2(test_list, 1)', setup='from __main__ import gaps2, test_list', number=100)

print(f"t1 = {t1}s; t2 = {t2}s; Numpy gives ~{t2 // t1}x speedup")

在我的笔记本电脑上，这给出了：

t1 = 0.020834800001466647s; t2 = 1.2446780000027502s; Numpy gives ~59.0x speedup

我的话很快！

推荐阅读