Как уменьшить сложность времени при обходе условных данных?

Question

Я работаю со следующим Фреймом данных

Моя цель - предоставить каждому пользователю уникальный хэшированный идентификатор в месяц.

Итак, мой первый подход, очень простойбыло создать копию кадра данных, который преобразует даты только в месяцы, затем выбрать каждый раздел с уникальным идентификатором и уникальным месяцем и хэшировать его столбец id_user.

df_copy=df.copy()

# Set of {1..12} (number of the month)
months = pd.DatetimeIndex(df_copy["date"]).month.unique()
ordered_months = set(reversed(months))

# Set of all unique user's IDs
ids = df_copy["id_user"].unique()

# Transform YYYY-MM-DD to MM
df_copy["date"] = pd.DatetimeIndex(df_copy["date"]).month

# Dataframe of salts for hashing, unique salt per (id,month)
salt_table=pd.DataFrame(columns=ordered_months,index=ids)
salt_table.set_index(ids,inplace=True)

# Generate salt table
for i in ids:
    for j in ordered_months:
        # Generates unique b64 values
        salt_table[j][i]=os.urandom(256)

Так что это моя хеш-функция, берет шрифт, добавляет соль одинакового размера (различную для каждой уникальной пары (id, месяц)):

def hashme(passwd, salt):
    return hs.sha256(salt + passwd.encode()).hexdigest()

И, наконец, вычисляем этоФункция для каждого раздела выдаст что-то вроде

%%time
df_copy.sort_values(["id_user","date"])
salt_table.sort_index(inplace=True)
c=0
for i in ids:
    for j in ordered_months:
        partition = (df_copy["date"] == j) & (df_copy["id_user"]==i)
        df_copy.loc[partition,["id_user"]]=np.vectorize(hashme,otypes=[str])(df[partition]["id_user"],salt_table.ix[str(i),[j]])
    c+=1
    print("Progress .... ", c , " /4034" )
df["id_user"] = df_copy["id_user"]

Теперь это O (n * m) комплексный n, представляющий собой число идентификаторов, а m - количество месяцев. В этом случае это 4034 * 12 = 48408. Это заняло около 58 минут, чтобы вычислить, что слишком много для чего-то такого простого.

Я уверен, что есть лучший способ сделать это, у вас есть какие-либо предложения?

Answer 1

Почему это медленно?

При создании раздела вы перебираете все строки в df_copy.

partition = (df_copy["date"] == j) & (df_copy["id_user"]==i)

Эта операция примерно O(n*m), и вы выполните это n*m раз. Сложность, по крайней мере, вдвое больше, чем вы ожидаете.

Как мы можем сделать это быстрее?

Вероятно, вычисление хеша не такое медленное. Таким образом, кэширование хеша может не потребоваться.

def compute_hash(month, user_id):
    """ Your implementation goes here
    """
    pass

df["month"] = df["date"].transform(lambda x: x.month) 
df["hash"] = df.apply(lambda x: compute_hash(x["month"], x["user_id"], axis=1)

Если вам нужно будет кэшировать хэши. Я бы предложил использовать простой словарь.

month_user_cache = dict()
def cached_compute_hash(month, user_id):
    key = (month, user_id)
    if key not in month_user_cache :
        month_user_cache [key] = compute_hash(month, user_id)
    return month_user_cache[key]