numpy 在python中查找元组列表中的连续序列

9lowa7mx 于 2022-11-23 发布在 Python

关注(0)|答案(4)|浏览(173)

我正在努力解决以下问题：我想写一些小代码去同位素质谱数据。
为此，我比较了，如果两个信号之间的差等于质子的质量除以电荷态，到目前为止，这很容易。
我现在正在苦苦挣扎，寻找比两座山峰更串联的东西。
我把这个问题分解成一个元组列表，一个系列是n个元组，其中前一个元组的最后一个数字等于当前元组的第一个元组。
从这里：
[(1第10条第1款[第10条第1款]
对此：
[(1第10条：
简单订单将失败，因为可能存在跳跃（7--〉9）和中间信号（8，10）
下面是一些测试数据：

import numpy as np

proton = 1.0078250319 

data = [
 (632.3197631835938, 2244.3374),  #0
 (632.830322265625, 2938.797),    #1
 (634.3308715820312, 1567.1385),  #2
 (639.3309326171875, 80601.41),   #3
 (640.3339233398438, 23759.367),  #4
 (641.3328247070312, 4771.9946),  #5
 (641.8309326171875, 2735.902),   #6
 (642.3365478515625, 4600.567),   #7
 (642.84033203125, 1311.657),     #8
 (650.34521484375, 11952.237),    #9
 (650.5, 1),                      #10 
 (650.84228515625, 10757.939),    #11
 (651.350341796875, 6324.9023),   #12
 (651.8455200195312, 1398.8452),  #13
 (654.296875, 1695.3457)]         #14

mz, i = zip(*data)

mz = np.array(mz)
i = np.array(i)

arr = np.triu(mz - mz[:, np.newaxis])

charge = 2

所以实际上，在第一步，我只对mz值感兴趣，我从所有值中减去所有值，然后分离出上面的三角形。
为了计算，如果两个信号实际上在正确的质量数范围内，我使用以下代码：

>>> pairs = tuple(zip(*np.where(abs(arr - (proton / charge)) < 0.01)))
((0, 1), (5, 6), (6, 7), (7, 8), (9, 11), (11, 12), (12, 13))

现在，相应的信号已经一目了然：
峰1：0至1
峰2：5至8
峰3：9 - 13，无10。
因此，原则上，我希望将每个元组的第二个值与任何其他元组的第一个值进行比较，以确定后续序列。
我尝试的是将列表扁平化，去除重复项，并在这个1D列表中找到连续计数。但这失败了，因为发现了5 - 9的峰值。
我希望有一个矢量化的解决方案，因为这个计算是针对30000+光谱中的多个电荷状态的100 - 500个信号进行的。
我很确定，这个问题以前也有人问过，但一直没能找到合适的解决办法。
最后，使用这些序列检查相应峰的强度，将它们相加，并使用最大初始值来指定此处的脱同位素峰。
感谢基督教
另外，如果对已经存在的代码有一些建议，我很乐意学习。我对矢量化计算很陌生，通常写了大量的for循环，需要很长时间才能完成。

numpy

来源：https://stackoverflow.com/questions/74534622/find-consecutive-series-in-list-of-tuples-in-python

4条答案

按热度按时间

disho6za1#

在图论中，你的问题将是“如何找到图中所有不连通的子图？"。
因此，为什么不使用networkx这样的网络分析库呢？

import networkx as nx
# Your tuples become the edges of the graph.
edge = [(1,2), (2,3), (4,5), (7,9), (8,10), (9,11)]

# We create the graph
G = nx.Graph()
G.add_edges_from(edge)

# Use connected_components to detect the subgraphs.
d = list(nx.connected_components(G))

我们得到了预期的结果：

[{1, 2, 3}, {4, 5}, {7, 9, 11}, {8, 10}]

具有4个子图：

赞(0）回复(0）举报 2022-11-23

rbpvctlc2#

请尝试：

d = {}
pairs = [(1,2), (2,3), (4,5), (7,9), (8,10), (9,11)]
for t in pairs:
    if t[0] in d:
       d[t[0]].append(t[1])
       d[t[1]] = d.pop(t[0])
    else:
        d[t[1]] = list(t)
signals = tuple(tuple(v) for v in d.values())

这个问题的时间复杂度为O（n），所以这个问题的时间复杂度为O（n）。

赞(0）回复(0）举报 2022-11-23

wecizke33#

感谢所有的回应。
我真的很喜欢networkx的方法，但有趣的是，这比O（n）循环的解决方案要慢。我用我的原始数据和随机训练集进行了基准测试。在两种情况下，结果是相等的（这是前提条件），但O（n）的解决方案要快4到10倍。
下面是基准

networkx
size: 10
22.9 µs ± 1.92 µs per loop (mean ± std. dev. of 2 runs, 10 loops each)
size: 100
165 µs ± 4.59 µs per loop (mean ± std. dev. of 2 runs, 10 loops each)
size: 1000
2.08 ms ± 52.4 µs per loop (mean ± std. dev. of 2 runs, 10 loops each)
size: 10000
23.1 ms ± 499 µs per loop (mean ± std. dev. of 2 runs, 10 loops each)
size: 100000
350 ms ± 6.12 ms per loop (mean ± std. dev. of 2 runs, 10 loops each)
size: 1000000
4.82 s ± 120 ms per loop (mean ± std. dev. of 2 runs, 10 loops each)

loop
size: 10
3.31 µs ± 418 ns per loop (mean ± std. dev. of 2 runs, 10 loops each)
size: 100
35.3 µs ± 5.68 µs per loop (mean ± std. dev. of 2 runs, 10 loops each)
size: 1000
350 µs ± 22.2 µs per loop (mean ± std. dev. of 2 runs, 10 loops each)
size: 10000
3.95 ms ± 38.5 µs per loop (mean ± std. dev. of 2 runs, 10 loops each)
size: 100000
71.6 ms ± 278 µs per loop (mean ± std. dev. of 2 runs, 10 loops each)
size: 1000000
1.11 s ± 30.8 ms per loop (mean ± std. dev. of 2 runs, 10 loops each)

我认为在非常非常大的样本量下，NetworkX可能会表现得更好，但在我的场景中，小样本（〈1000个初始信号），但这通常是循环解决方案获胜。
这里是要复制的代码。

import numpy as np
import networkx as nx

def p1(edge):
    # from https://stackoverflow.com/a/74535322/14571316
    
    G = nx.Graph()
    G.add_edges_from(edge)

    # Use connected_components to detect the subgraphs.
    d = list(nx.connected_components(G)) 
    
    return d

def p2(pairs):
    # from https://stackoverflow.com/a/74535164/14571316 
    d = {}
    for t in pairs:
        if t[0] in d:
           d[t[0]].append(t[1])
           d[t[1]] = d.pop(t[0])
        else:
            d[t[1]] = list(t)
    signals = tuple(tuple(v) for v in d.values())
    
    return signals

print("networkx")
for size in [10, 100, 1000, 10000, 100000, 1000000]:
    print(f'size: {size}')
    l1 = np.random.randint(0, high=int(size/2), size=size)
    l2 = np.random.randint(0, high=int(size/2), size=size)
    pairs = tuple(zip(l1, l2))
    %timeit -n10 -r2 p1(pairs)
    
print("loop")
for size in [10, 100, 1000, 10000, 100000, 1000000]:
    print(f'size: {size}')
    l1 = np.random.randint(0, high=int(size/2), size=size)
    l2 = np.random.randint(0, high=int(size/2), size=size)
    pairs = tuple(zip(l1, l2))
    %timeit -n10 -r2 p2(pairs)

赞(0）回复(0）举报 2022-11-23

ddarikpa4#

时间复杂度O（n,,），是一个复杂度为O（n*n）的问题。

#!/usr/bin/env ipython
# --------------------
datain = [(1,2), (2,3), (4,5), (7,9), (8,10), (9,11)]
dataout = [];
# ---------------------------------------------------
for ii,val_a in enumerate(datain):
    appendval = set(val_a)
    for jj,val_b in enumerate(datain[ii+1:]):
        # -------------------------------------------
        if len(set(val_a).intersection(set(val_b)))>0:
            appendval = appendval.union(val_b)
            datain.remove(val_b)
        # -------------------------------------------
    dataout.append(tuple(appendval))
# ---------------------------------------------------

赞(0）回复(0）举报 2022-11-23

我来回答

numpy 在python中查找元组列表中的连续序列

4条答案

相关问题

热门标签

最新问答