Когда вычислительная стоимость применения функции выпукла?

Question

Кажется, что много вещей, которые я делаю в Пандах, имеют выпуклые вычислительные затраты времени в количестве данных, которые у меня есть (например, 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)?

Answer 1

Для функций, имеющих большую, чем линейную, временную сложность. Сортировка, например, имеет сложность O(n log n).

gr_TILPS = TILPStemp.groupby('uniqueid') 

groupbysorts the keys by default, поэтому этот вызов имеет по крайней мере O(n log n) сложности. Вы можете включить сортировку выключить с помощью

gr_TILPS = TILPStemp.groupby('uniqueid', sort=False) 

---

В Панды 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.nuniqueshould be significantly faster.