How can you increase the speed of an algorithm that computes a usage streak?

Question

I have the following problem: I have data (table called 'answers') of a quiz application including the answered questions per user with the respective answering date (one answer per line), e.g.:

UserID	Time	Term	QuestionID	Answer
1	2019-12-28 18:25:15	Winter19	345	a
2	2019-12-29 20:15:13	Winter19	734	b

I would like to write an algorithm to determine whether a user has used the quiz application several days in a row (a so-called 'streak'). Therefore, I want to create a table ('appData') with the following information:

UserID	Term	HighestStreak
1	Winter19	7
2	Winter19	10

For this table I need to compute the variable 'HighestStreak'. I managed to do so with the following code:

for userid, term in zip(appData.userid, appData.term):
    final_streak = 1
    for i in answers[(answers.userid==userid) & (answers.term==term)].time.dt.date.unique():
        temp_streak = 1
        while i + pd.DateOffset(days=1) in answers[(answers.userid==userid) & (answers.term==term)].time.dt.date.unique():
            i += pd.DateOffset(days=1)
            temp_streak += 1
        if temp_streak > final_streak:
            final_streak = temp_streak
    appData.loc[(appData.userid==userid) & (appData.term==term), 'HighestStreak'] = final_streak

Unfortunately, running this code takes about 45 minutes. The table 'answers' has about 4,000 lines. Is there any structural 'mistake' in my code that makes it so slow or do processes like this take that amount of time?

Any help would be highly appreciated!

EDIT:

I managed to increase the speed from 45 minutes to 2 minutes with the following change:

I filtered the data to students who answered at least one answer first and set the streak to 0 for the rest (as the streak for 0 answers is 0 in every case):

appData.loc[appData.totAnswers==0, 'highestStreak'] = 0 
appDataActive = appData[appData.totAnswers!=0]

Furthermore I moved the filtered list out of the loop, so the algorithm does not need to filter twice, resulting in the following new code:

appData.loc[appData.totAnswers==0, 'highestStreak'] = 0 
appDataActive = appData[appData.totAnswers!=0]
for userid, term in zip(appData.userid, appData.term):
    activeDays = answers[(answers.userid==userid) & (answers.term==term)].time.dt.date.unique()
    final_streak = 1
    for day in activeDays:
        temp_streak = 1
        while day + pd.DateOffset(days=1) in activeDays:
            day += pd.DateOffset(days=1)
            temp_streak += 1
        if temp_streak > final_streak:
            final_streak = temp_streak
    appData.loc[(appData.userid==userid) & (appData.term==term), 'HighestStreak'] = final_streak

Of course, 2 minutes is much better than 45 minutes. But are there any more tips?

Answer 1

my attempt, which borrows some key ideas from the connected components problem; a fairly early problem when looking at graphs

first I create a random DataFrame with some user id's and some dates.

import datetime
import random

import pandas
import numpy

#generate basic dataframe of users and answer dates
def sample_data_frame():
    users = ['A' + str(x) for x in range(10000)] #generate user id
    date_range = pandas.Series(pandas.date_range(datetime.date.today() - datetime.timedelta(days=364) , datetime.date.today()),
                           name='date')
    users = pandas.Series(users, name='user')
    df = pandas.merge(date_range, users, how='cross')
    removals = numpy.random.randint(0, len(df), int(len(df)/4)) #remove random quarter of entries
    df.drop(removals, inplace=True)
    return df

def sample_data_frame_v2(): #pandas version <1.2
    users = ['A' + str(x) for x in range(10000)] #generate user id
    date_range = pandas.DataFrame(pandas.date_range(datetime.date.today() - datetime.timedelta(days=364) , datetime.date.today()), columns = ['date'])
    users = pandas.DataFrame(users, columns = ['user'])
    date_range['key'] = 1
    users['key'] = 1
    df = users.merge(date_range, on='key')
    df.drop(labels = 'key', axis = 1)
    removals = numpy.random.randint(0, len(df), int(len(df)/4)) #remove random quarter of entries
    df.drop(removals, inplace=True)
    return df

• put your DataFrame in sorted order, so that the next row is next answer day and then by user
• create two new columns from the row below containing the userid and the date of the row below
• if the user of row below is the same as the current row and the current date + 1 day is the same as the row below set the column result to false numerically known as 0, otherwise if it's a new streak set to True, which can be represented numerically as 1.
• cumulatively sum the results which will group your streaks
• finally count how many entries exist per group and find the max for each user

for 10k users over 364 days worth of answers my running time is about a 1 second

df = sample_data_frame()
df = df.sort_values(by=['user', 'date']).reset_index(drop = True)
df['shift_date'] = df['date'].shift()
df['shift_user'] = df['user'].shift()

df['result'] = ~((df['shift_date'] == df['date'] - datetime.timedelta(days=1)) & (df['shift_user'] == df['user']))
df['group'] = df['result'].cumsum()

summary = (df.groupby(by=['user', 'group']).count()['result'].max(level='user'))

summary.sort_values(ascending = False) #print user with highest streak