Skip to main content
 首页 » 编程设计

python之什么时候应用凸函数的计算成本是

2024年10月25日15think

似乎我在 Pandas 中做的很多事情在我拥有的数据量上都有凸计算时间成本(例如,1 行需要 1 秒,2 行需要 2.2 秒,4 行需要 6 秒,等等) .

为什么计算成本不会随着我拥有的数据量线性增加?比如我写的这个函数:

def fractrips1brand(trip):  
    # Get number of transaction rows for THIS sepcific consumer 
    art = trip[trip.Item_Id.isin(insidegood)].Item_Id.nunique() 
    output = pd.Series({'numinsidegoods': art }) 
    return output 
 
 
gr_TILPS = TILPStemp.groupby('uniqueid') 
output = gr_TILPS.apply(fractrips1brand) 

似乎展示了这样的成本。

为什么不是O(n)?

请您参考如下方法:

函数具有大于线性的时间复杂度是很常见的。 例如,排序具有 O(n log n) 复杂性。

gr_TILPS = TILPStemp.groupby('uniqueid') 

groupby sorts the keys by default ,所以这个调用至少有 O(n log n) 复杂度。您可以使用

关闭排序
gr_TILPS = TILPStemp.groupby('uniqueid', sort=False) 

在 Pandas 0.15 及更早版本中,Series.nunique (source)调用 Series.value_counts (source)默认情况下也会对值进行排序。所以这是另一个复杂度为 O(n log n) 的函数调用。由于这个发生在 fractrips1brand 中,gr_TILPS.apply(fractrips1brand) 的总复杂度至少为 O(m n log n) 其中 m 是组数。

更新:在下一个 Pandas 版本(版本 0.16.0)中 Series.nunique should be significantly faster .