Вложенная (двойная) строка за строкой итерации Pandas DataFrame

Ответ 1

Я переписал решение, используя DataFrame.apply вместо DataFrame.apply, и в качестве оптимизации использовались массивы numpy, где это возможно. Я использовал frozenset потому что они неизменяемы и хешируются, и поэтому Series.unique работает правильно. Series.unique не работает на элементах set типов.

Кроме того, я нашел d.loc[list(x), 'STRIP'].nunique() будет немного быстрее, чем d.loc[list(x)].STRIP.nunique(). Я не уверен, почему, но я использовал более быстрое утверждение в приведенном ниже решении.

Алгоритм простого английского языка:

Для каждой строки создайте набор индексов ниже (или равно) индекса текущего индекса, чье Отклонение больше текущего Прибытия. В результате получается список наборов.

Возвращайте уникальные наборы, которые не являются подмножествами других множеств (и для второго алгоритма дополнительно фильтруют, что оба STRIP называются наборами)

(Обновление) 2-е улучшение:

1 небольшое улучшение выполняется путем опускания до уровня numpy и использования np.apply_along_axis вместо использования df.apply. Это возможно, поскольку PLANE всегда равна индексу df.values и мы можем получить доступ к базовой матрице с df.values

Я нашел значительное улучшение в понимании списка, которое возвращает максимальные подмножества

[list(x) for x in sets if ~np.any(sets > x)]

Вышеприведенная операция О (п ^ 2). На небольших наборах данных это очень быстро. Однако на больших наборах данных это утверждение становится шеей бутылки. Чтобы оптимизировать это, сначала отсортируйте sets и снова проведите по элементу, чтобы найти максимальные подмножества. После сортировки достаточно проверить, что elem [n] не является подмножеством elem [n + 1], чтобы определить, является ли elem [n] максимальным подмножеством. Процедура сортировки сравнивает два элемента с < операцией

Тайминги:

Хотя моя первоначальная реализация значительно улучшила производительность по сравнению с попыткой OP, алгоритм был экспоненциально упорядочен, как показано на следующей диаграмме.

Я представляю только тайминги для findMultiEvents, hal_2 & hal_5. Относительная производительность findSinglEvents, hal_1 & hal_3 аналогично сопоставима.

прокрутите ниже, чтобы увидеть код бенчмаркинга.

обратите внимание, что я прекратил бенчмаркинг findMumtiEvents & hal_2 раньше, когда стало очевидно, что они менее эффективны по экспоненциальному коэффициенту

Реализация

Улучшенная реализация:

def maximal_subsets(sets):
    sets.sort()
    maximal_sets = []
    s0 = frozenset()
    for s in sets[::-1]:
        if s0 > s or len(s) < 2:
            continue
        maximal_sets.append(list(s))
        s0 = s
    return maximal_sets

def maximal_subsets_2(sets, d):
    sets.sort()
    maximal_sets = []
    s0 = frozenset()
    for s in sets[::-1]:
        if s0 > s or len(s) < 2 or d.loc[list(s), 'STRIP'].nunique() < 2:
            continue
        maximal_sets.append(list(s))
        s0 = s
    return maximal_sets

# single
def hal_3(d):
    sets = np.apply_along_axis(
        lambda x: frozenset(d.PLANE.values[(d.PLANE.values <= x[0]) & (d.DEPARTURE.values > x[2])]), 
        1, d.values
    )
    return maximal_subsets(sets)
# multi
def hal_5(d):
    sets = np.apply_along_axis(
        lambda x: frozenset(d.PLANE.values[(d.PLANE.values <= x[0]) & (d.DEPARTURE.values > x[2])]), 
        1, d.values
    )
    return maximal_subsets_2(sets, d)

Исходная реализация:

# findSingleEvents
def hal_1(d):
    sets = d.apply(
       lambda x: frozenset(
           d.index.values[(d.index.values <= x.name) & (d.DEPARTURE.values > x.ARRIVAL)]
       ),
       axis=1
    ).unique()
    return [list(x) for x in sets if ~np.any(sets > x) and len(x) > 1]

# findMultiEvents
def hal_2(d):
    sets = d.apply(
        lambda x: frozenset(
            d.index.values[(d.index.values <= x.name) & (d.DEPARTURE.values > x.ARRIVAL)]
        ),
        axis=1
    ).unique()
    return [list(x) for x in sets 
            if ~np.any(sets > x) and
               len(x) > 1 and 
               d.loc[list(x), 'STRIP'].nunique() == 2]

Выходы:

Выходы идентичны реализации OP.

hal_1(df[df.STRIP==1])
[[1, 3]]
hal_1(df[df.STRIP==2])
[[4, 5], [4, 6]]
hal_2(df)
[[1, 2, 3], [1, 3, 4, 5], [1, 4, 6]]
hal_3(df[df.STRIP==1])
[[1, 3]]
hal_3(df[df.STRIP==2])
[[4, 5], [4, 6]]
hal_5(df)
[[1, 2, 3], [1, 3, 4, 5], [1, 4, 6]]

Детали тестовой системы:

os: windows 10
python: 3.6 (Anaconda)
pandas: 0.22.0
numpy: 1.14.3

Код бенчмаркинга:

import random

def mk_random_df(n):
    data =  []
    for i in range(n):
        arrival = random.uniform(0,1000)
        departure = arrival + random.uniform(2.0, 10.0)
        data.append({'PLANE':i, 'STRIP':random.randint(1, 2),'ARRIVAL':arrival,'DEPARTURE':departure})

    df = pd.DataFrame(data, columns = ['PLANE','STRIP','ARRIVAL','DEPARTURE'])
    df = df.sort_values(by=['ARRIVAL'])
    df = df.reset_index(drop=True)
    df.PLANE = df.index
    return df

dfs = {i: mk_random_df(100*(2**i)) for i in range(0, 10)}
times, times_2, times_5 = [], [], []

for i, v in dfs.items():
    if i < 5:
        t = %timeit -o -n 3 -r 3 findMultiEvents(v)
        times.append({'size(pow. of 2)': i, 'timings': t})

for i, v in dfs.items():
    t = %timeit -o -n 3 -r 3 hal_5(v)
    times_5.append({'size(pow. of 2)': i, 'timings': t})

for i, v in dfs.items():
    if i < 9:
        t = %timeit -o -n 3 -r 3 hal_2(v)
        times_2.append({'size(pow. of 2)': i, 'timings': t})