算法效率 - 使用 Pandas 的数据处理效率（三个嵌套 for 循环）
Algorithm Efficiency - Data Processing Efficiency using Pandas (three nested for loops)
数据来自两个数据集，我需要检查第一个数据集中特定位置[=25]是否有单一时间事件 =]与第二个数据集中相同特定位置的时间范围重合，如果如果满足条件。我有一个要检查的 特定位置 的列表。
我的问题是第一个数据集包含大约 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 的初学者，所以我想知道我是否可以在不使用数据库或某些大数据解决方案的情况下以更有效的方式执行此操作。感谢大家的帮助！
下面的代码创建了两个数据框。然后根据 room_id 合并这些。如果 login_time 落在 start_time 和 end_time 之间，则创建附加列 flag 以识别每个 event_id。
导入库
import pandas as pd
import numpy as np
#import datetime
from datetime import datetime, timedelta
import hashlib
创建示例数据框
# Create dataframe - 1
room_id = abs(np.floor(np.random.randn(100)*100))
login_time = np.random.random() * timedelta(days=1)
temp1 = abs(np.floor(np.random.randn(100)*100))
df1 = pd.DataFrame({'room_id': room_id, 'login_time':login_time, 'temp1':temp1})
df1['login_time'] = df1.apply(lambda x: x['login_time'] + timedelta(hours=x['temp1']), axis=1)
del df1['temp1']
# Create dataframe - 2
room_id = abs(np.floor(np.random.randn(100)*100))
event_id = np.random.randn(100)*100
start_time = np.random.random() * timedelta(days=1)
temp2 = abs(np.floor(np.random.randn(100)*100))
temp3 = abs(np.floor(np.random.randn(100)*100))
df2 = pd.DataFrame({'room_id': room_id, 'event_id': event_id, 'start_time': start_time, 'temp2':temp2,'temp3':temp3})
df2['start_time'] = df2.apply(lambda x: x['start_time'] + timedelta(hours=x['temp2']), axis=1)
df2['end_time'] = df2.apply(lambda x: x['start_time'] + timedelta(hours=x['temp3']), axis=1)
df2['event_id'] = df2.apply(lambda x: hashlib.md5(str(x['event_id']).encode('utf-8')).hexdigest(), axis=1)
del df2['temp2']
del df2['temp3']
# Merge two dataframes
df = df1.merge(df2, on='room_id', how='inner')
df.head(2)
检查登录是否在开始和结束时间之间
注意：这里flag==1表示登录时间在起止时间之间
df['flag'] = np.where((df['login_time'] >= df['start_time']) & (df['end_time'] >= df['login_time']), 1, 0)
过滤掉所有带flag==0的事件，只保留flag==1
df = df[df['flag']==1]
df.head(5)
当您剥离 DataFrame 机制时，这是一个有点有趣的算法问题。要回答您的问题，YES 这可以做得更快。我将稍微重述一下您的问题，以便该解决方案可以更适用于更多人。重构它以适应您正在使用的数据结构应该不需要太多工作。
在开始之前，我想指出@NileshIngle 的代码可以为您的代码提供显着的速度提升（我还没有对任何东西进行基准测试），但是对于每种情况，时间复杂度仍然是二次方的，而不仅仅是在最坏的情况下。这个事实隐藏在他使用的各种 pandas 函数调用中，但代码总是每次都触及每个时间范围。鉴于您提到的数据集的大小，除非在非常特殊的情况下，否则这不太可能是您正在寻找的解决方案。
免责声明：我认为这个问题可以通过 最坏情况 复杂度 nlog(n)+mlog(m) 来解决，如果 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对应的时间段呢？由于结束时间 3 小于 4，我们失去了范围 (2,3)，并且我们不再获得任何时间范围。
我们将继续并应用该想法来创建一个基本的基于排序的算法，尝试将时间范围与时间相匹配。在您的应用程序中，只要您有对象引用，您实际上并不需要返回值的顺序相同，但我们将继续跟踪所有内容的原始位置。如果选择我会使用 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 分别是两个输入列表的长度。
数据来自两个数据集，我需要检查第一个数据集中特定位置[=25]是否有单一时间事件 =]与第二个数据集中相同特定位置的时间范围重合，如果如果满足条件。我有一个要检查的 特定位置 的列表。
我的问题是第一个数据集包含大约 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 的初学者，所以我想知道我是否可以在不使用数据库或某些大数据解决方案的情况下以更有效的方式执行此操作。感谢大家的帮助！
下面的代码创建了两个数据框。然后根据 room_id 合并这些。如果 login_time 落在 start_time 和 end_time 之间，则创建附加列 flag 以识别每个 event_id。
导入库
import pandas as pd
import numpy as np
#import datetime
from datetime import datetime, timedelta
import hashlib
创建示例数据框
# Create dataframe - 1
room_id = abs(np.floor(np.random.randn(100)*100))
login_time = np.random.random() * timedelta(days=1)
temp1 = abs(np.floor(np.random.randn(100)*100))
df1 = pd.DataFrame({'room_id': room_id, 'login_time':login_time, 'temp1':temp1})
df1['login_time'] = df1.apply(lambda x: x['login_time'] + timedelta(hours=x['temp1']), axis=1)
del df1['temp1']
# Create dataframe - 2
room_id = abs(np.floor(np.random.randn(100)*100))
event_id = np.random.randn(100)*100
start_time = np.random.random() * timedelta(days=1)
temp2 = abs(np.floor(np.random.randn(100)*100))
temp3 = abs(np.floor(np.random.randn(100)*100))
df2 = pd.DataFrame({'room_id': room_id, 'event_id': event_id, 'start_time': start_time, 'temp2':temp2,'temp3':temp3})
df2['start_time'] = df2.apply(lambda x: x['start_time'] + timedelta(hours=x['temp2']), axis=1)
df2['end_time'] = df2.apply(lambda x: x['start_time'] + timedelta(hours=x['temp3']), axis=1)
df2['event_id'] = df2.apply(lambda x: hashlib.md5(str(x['event_id']).encode('utf-8')).hexdigest(), axis=1)
del df2['temp2']
del df2['temp3']
# Merge two dataframes
df = df1.merge(df2, on='room_id', how='inner')
df.head(2)
检查登录是否在开始和结束时间之间
注意：这里flag==1表示登录时间在起止时间之间
df['flag'] = np.where((df['login_time'] >= df['start_time']) & (df['end_time'] >= df['login_time']), 1, 0)
过滤掉所有带flag==0的事件，只保留flag==1
df = df[df['flag']==1]
df.head(5)
当您剥离 DataFrame 机制时，这是一个有点有趣的算法问题。要回答您的问题，YES 这可以做得更快。我将稍微重述一下您的问题，以便该解决方案可以更适用于更多人。重构它以适应您正在使用的数据结构应该不需要太多工作。
在开始之前，我想指出@NileshIngle 的代码可以为您的代码提供显着的速度提升（我还没有对任何东西进行基准测试），但是对于每种情况，时间复杂度仍然是二次方的，而不仅仅是在最坏的情况下。这个事实隐藏在他使用的各种 pandas 函数调用中，但代码总是每次都触及每个时间范围。鉴于您提到的数据集的大小，除非在非常特殊的情况下，否则这不太可能是您正在寻找的解决方案。
免责声明：我认为这个问题可以通过 最坏情况 复杂度 nlog(n)+mlog(m) 来解决，如果 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对应的时间段呢？由于结束时间 3 小于 4，我们失去了范围 (2,3)，并且我们不再获得任何时间范围。
我们将继续并应用该想法来创建一个基本的基于排序的算法，尝试将时间范围与时间相匹配。在您的应用程序中，只要您有对象引用，您实际上并不需要返回值的顺序相同，但我们将继续跟踪所有内容的原始位置。如果选择我会使用 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 分别是两个输入列表的长度。