python - 算法效率——使用Pandas的数据处理效率(三个嵌套的for循环)

Question

数据来自两个数据集，我需要检查第一个数据集中在特定位置的单一时间事件是否与重合time range在第二个数据集中在相同的特定位置，如果满足条件，则将第二个集合的ID相应地附加到第一个集合中。我有一个要检查的特定位置列表。

我的问题是第一个数据集包含大约 500,000 行，第二个数据集包含大约 90,000 行。运行两个数据集需要很长时间，而且我的计算能力有限。

这是 Python 代码:

import datetime
import pandas as pd

def assign_tRangeID(singleEventDF, timeRangeDF):
    margin = datetime.timedelta(minutes=15)
    for i, single in singleEventDF.iterrows():
        for j, timeRange in timeRangeDF.iterrows():
           if timeRange['start_time']-margin <= single['singleEvent_time'] <= timeRange['end_time']
               singleEventDF.at[i, 'tRange_ID'] = timeRangeDF['ID']

for i, location in location_list.iterrows():
    single_subset = singleEvent['loc'].loc[[singleEvent['loc'] = location['loc']]
    tRange_subset = timeRange['loc'].loc[[timeRange['loc'] = location['loc']]
    assign_eventID(single_subset, tRange_subset)

我是 Python 的初学者，所以我想知道我是否可以在不使用数据库或某些大数据解决方案的情况下以更有效的方式执行此操作。感谢所有的帮助!

Answer 1

当您剥离 DataFrame 机制时，这是一个有点有趣的算法问题。要回答您的问题，是 这可以做得更快。我将稍微重述一下您的问题，以便该解决方案可以更适用于更多人。重构它以适应您正在使用的数据结构应该不需要太多工作。

在开始之前，我想指出@NileshIngle 的代码可以为您的代码提供显着的速度提升(我还没有对任何东西进行基准测试)，但是对于每种情况，时间复杂度仍然是二次方的，而不仅仅是在最坏的情况下。这个事实隐藏在他使用的各种 pandas 函数调用中，但代码总是每次都触及每个时间范围。鉴于您提到的数据集的大小，除非在非常特殊的情况下，否则这不太可能是您正在寻找的解决方案。

免责声明:如果 m 和 n 的大小是各自的输入。我的解决方案平均达到了这种复杂性，但在最坏的情况下却达不到。有人想想出更好的办法吗？

给定单个时间列表和时间范围列表，例如

single_times = [4, 5, 2, 3, -1]
time_ranges = [(1, 5), (10, 11), (2, 3)]

我们能否设计一个比 O(len(t)len(r)) 更快的算法，它为 t 中的每个元素输出 r 中每个匹配时间范围的索引>?对于这个问题(考虑到您的示例包含端点)，输出将是:

res = [[0], [0], [0, 2], [0, 2], []]

乍一看，问题似乎是对于 single_times 的每个元素，我们必须检查 time_ranges 的每个元素，导致大量的运行时间荒谬数据。对于我们想要合并两个列表的一般类型的数据，无法避免这种二次运行时间。然而，我们可以轻松地对这两个列表进行排序这一事实为我们提供了更好的计算范围。

探索这个想法，如果single_times按升序排序会发生什么？例如，如果我们知道 3 对应的时间范围是 [(1,5),(2,3)] 并且我们想知道4对应的时间范围？我们失去了 (2,3) 范围，因为结束时间 3 小于 4，我们不再获得任何时间范围.

我们将继续并应用该想法来创建一个基本的基于排序的算法，尝试将时间范围与时间相匹配。在您的应用程序中，只要您有对象引用，您实际上并不需要返回值的顺序相同，但我们将继续跟踪所有内容的原始位置。鉴于选择，我会使用 numpy 来提高效率和各种便利功能，但原始 Python 更具可移植性。

import itertools as it

def matching_times(single_times, time_ranges):
    single_index = sorted(xrange(len(single_times)), key=lambda i: single_times[i])
    single_times_sorted = [single_times[i] for i in single_index]
    time_ranges_sorted = sorted([(i, v[0], v[1]) for i, v in enumerate(time_ranges)], key=lambda w: w[1])

    m = 0  # keep track of min location in time_ranges_sorted
    res = [[]]

    # Find solutions for single_times_sorted[0]
    for i, w in enumerate(time_ranges_sorted):
        if w[1] > single_times_sorted[0]:
            break
        if w[2] >= single_times_sorted[0]:
            res[0].append(w)
            m = i+1

    for cur_time in it.islice(single_times_sorted, 1, len(single_times_sorted)):
        # Keep previous solutions that don't end too soon
        res.append([w for w in res[-1] if w[2]>=cur_time])

        # Strip extraneous information as soon as possible to preserve a semblance
        # of memory efficiency
        res[-2] = [w[0] for w in res[-2]]

        for i, w in enumerate(it.islice(time_ranges_sorted, m, len(time_ranges_sorted)), m):
            if w[1] > cur_time:
                break
            if w[2] >= cur_time:
                res[-1].append(w)
                m = i+1

    # Strip remaining extra information from solution
    res[-1] = [w[0] for w in res[-1]]

    # Re-sort result according to original locations in single_times
    return [v[1] for v in sorted(enumerate(res), key=lambda v: single_index[v[0]])]

然后非常简单地获得所需的解决方案:

res = matching_times(single_times, time_ranges); res
>>> [[0], [0], [0, 2], [0, 2], []]

这仍然具有最坏情况下的二次时间复杂度，但对于真实世界的数据，相对于时间范围的总数，每次可能没有很多匹配时间范围，预期运行时间将更接近 O( nlog(n)+mlog(m)) 其中 m 和 n 分别是两个输入列表的长度。