Самый быстрый способ выполнить сложный поиск на фрейме данных панд

Я пытаюсь выяснить самый быстрый способ выполнить поиск и сортировку на фрейме данных pandas. Ниже приведены данные до и после того, что я пытаюсь выполнить.

До:

flightTo  flightFrom  toNum  fromNum  toCode  fromCode
   ABC       DEF       123     456     8000    8000
   DEF       XYZ       456     893     9999    9999
   AAA       BBB       473     917     5555    5555
   BBB       CCC       917     341     5555    5555

После поиска/сортировки:

flightTo  flightFrom  toNum  fromNum  toCode  fromCode
   ABC       XYZ       123     893     8000    9999
   AAA       CCC       473     341     5555    5555

В этом примере я пытаюсь отфильтровать "рейсы", которые существуют между конечными пунктами назначения. Это должно быть сделано с помощью некоторого метода отбрасывания дубликатов, но меня смущает то, как обрабатывать все столбцы. Будет ли бинарный поиск лучшим способом сделать это? Подсказки оценили, изо всех сил пытаясь понять это.

Возможный крайний случай:

Что если данные подключены и наши конечные соединения находятся в одном столбце?

flight1  flight2      1Num    2Num     1Code   2Code
   ABC       DEF       123     456     8000    8000
   XYZ       DEF       893     456     9999    9999

После поиска/сортировки:

flight1  flight2      1Num    2Num     1Code   2Code
   ABC       XYZ       123     893     8000    9999

Этот случай логически не должен происходить. В конце концов, как вы можете пойти DEF-ABC и DEF-XYZ? Вы не можете, но "конечными точками" все равно будет ABC-XYZ

Ответы

Ответ 1

Это проблема сети, поэтому мы используем networkx, обратите внимание, здесь вы можете иметь более двух остановок, что означает, что у вас может быть какой-то случай, например NY-DC-WA-NC

import networkx as nx
G=nx.from_pandas_edgelist(df, 'flightTo', 'flightFrom')

# create the nx object from pandas dataframe

l=list(nx.connected_components(G))

# then we get the list of components which as tied to each other , 
# in a net work graph , they are linked 
L=[dict.fromkeys(y,x) for x, y in enumerate(l)]

# then from the above we can create our map dict , 
# since every components connected to each other , 
# then we just need to pick of of them as key , then map with others

d={k: v for d in L for k, v in d.items()}

# create the dict for groupby , since we need _from as first item and _to as last item 
grouppd=dict(zip(df.columns.tolist(),['first','last']*3))
df.groupby(df.flightTo.map(d)).agg(grouppd) # then using agg with dict yield your output 

Out[22]: 
         flightTo flightFrom  toNum  fromNum  toCode  fromCode
flightTo                                                      
0             ABC        XYZ    123      893    8000      9999
1             AAA        CCC    473      341    5555      5555

Установка networkx

  • Пип: pip install networkx
  • Анаконда: conda install -c anaconda networkx

Ответ 2

Вот решение NumPy, которое может быть удобно в случае производительности:

def remove_middle_dest(df):
    x = df.to_numpy()
    # obtain a flat numpy array from both columns
    b = x[:,0:2].ravel()
    _, ix, inv = np.unique(b, return_index=True, return_inverse=True)
    # Index of duplicate values in b
    ixs_drop = np.setdiff1d(np.arange(len(b)), ix) 
    # Indices to be used to replace the content in the columns
    replace_at = (inv[:,None] == inv[ixs_drop]).argmax(0) 
    # Col index of where duplicate value is, 0 or 1
    col = (ixs_drop % 2) ^ 1
    # 2d array to index and replace values in the df
    # index to obtain values with which to replace
    keep_cols = np.broadcast_to([3,5],(len(col),2))
    ixs = np.concatenate([col[:,None], keep_cols], 1)
    # translate indices to row indices
    rows_drop, rows_replace = (ixs_drop // 2), (replace_at // 2)
    c = np.empty((len(col), 5), dtype=x.dtype)
    c[:,::2] = x[rows_drop[:,None], ixs]
    c[:,1::2] = x[rows_replace[:,None], [2,4]]
    # update dataframe and drop rows
    df.iloc[rows_replace, 1:] = c
    return df.drop(rows_drop)

Какой из предложенных фреймов данных дает ожидаемый результат:

print(df)
    flightTo flightFrom  toNum  fromNum  toCode  fromCode
0      ABC        DEF    123      456    8000      8000
1      DEF        XYZ    456      893    9999      9999
2      AAA        BBB    473      917    5555      5555
3      BBB        CCC    917      341    5555      5555

remove_middle_dest(df)

    flightTo flightFrom  toNum  fromNum  toCode  fromCode
0      ABC        XYZ    123      893    8000      9999
2      AAA        CCC    473      341    5555      5555

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

    flightTo flightFrom  toNum  fromNum  toCode  fromCode
0      ABC        DEF    123      456    8000      8000
1      XYZ        DEF    893      456    9999      9999
2      AAA        BBB    473      917    5555      5555
3      BBB        CCC    917      341    5555      5555

remove_middle_dest(df)

     flightTo flightFrom  toNum  fromNum  toCode  fromCode
0      ABC        XYZ    123      456    8000      9999
2      AAA        CCC    473      341    5555      5555