Сравнение списков с каждой записью в DataFrame

Question

У меня есть сценарий использования, в котором я сравниваю список в том же столбце с самим собой, код ниже:

for i in range(0,len(counts95)):
    for j in range(i+1,len(counts95)):
        for x in counts95['links'][i]:
            for y in counts95['links'][j]:
                if x == y and counts95['linkoflinks'][j] is None:
                    counts95['linkoflinks'][j] = counts95['index'][i]

Код работает, но он не python дружественный (использует 4 для циклов) и принимает огромное количество времени, чтобы сделать операцию. Основная идея заключается в том, чтобы связать записи, где элементы в списке в countts95 ['links'] находятся в любой из следующих строк, если да, обновите столбец linksoflinks с помощью индекса первого столбца, только если linksoflinks столбец None (без перезаписи)

найти таблицу ссылок ниже:

counts95 = pd.DataFrame({'index': [616351, 616352, 616353,6457754], 
                   'level0': [25,30,35,100],
                   'links' : [[1,2,3,4,5],[23,45,2],[1,19,67],[14,15,16]],
                   'linksoflinks' : [None,None,None,None]})

EDIT: Новый кадр данных

counts95 = pd.DataFrame({'index': [616351, 616352, 616353,6457754,6566666,464664683], 
                   'level0': [25,30,35,100,200,556],
                   'links' : [[1,2,3,4,5],[23,45,2],[1,19,67],[14,15,16],[1,14],[14,1]],
                   'linksoflinks' : [None,None,None,None,None,None]})

Желаемый выход:

     index  level0            links  linksoflinks
0   616351      25  [1, 2, 3, 4, 5]         NaN
1   616352      30      [23, 45, 2]    616351.0
2   616353      35      [1, 19, 67]    616351.0
3  6457754     100     [14, 15, 16]         NaN
4  6566666     200           [1,14]    616351.0
5  6457754     556           [14,1]    616351.0

Answer 1

В желаемом выводе используются разные значения и имя столбца для сравнения с вашим образцом конструктора данных. Я использую желаемый выходной кадр данных для тестирования.

Logi c:
Для каждого подсписка links нам нужно найти индекс строки (я имею в виду индекс датафрейм, НЕ столбцы index) первого перекрывающегося подсписка. Мы будем использовать эти индексы строк для нарезки на .loc на counts95, чтобы получить соответствующие значения столбца index. Для достижения этой цели нам нужно выполнить несколько шагов:

• Сравнить каждый подсписок со всеми подсписками в link. Понимание списка быстро и эффективно для этой задачи. Нам нужно закодировать понимание списка, чтобы создать массив логических 2D-масок, в котором каждый подмассив содержит True значений для перекрывающихся строк и False для неперекрывающихся (посмотрите пошаговую инструкцию по этой 2D-маске и проверьте с помощью столбец links вы увидите яснее)
• Мы хотим сравнить сверху вниз с текущим подсписком. Т.е. стоя из текущего ряда, мы хотим только сравнить задом наперед. Поэтому нам нужно установить любое прямое сравнение на False. Это функциональность np.tril
• Внутри каждого подмассива этой 2D-маски позиция / индекс True - это индекс строки, на которую наложен текущий подсписок. Нам нужно найти эти позиции True. Это функциональность np.argmax. np.argmax возвращает позицию / индекс первого элемента max массива. True считается 1, а False - 0. Следовательно, для любого подмассива, имеющего True, он правильно возвращает индекс 1-й перекрытой строки. Однако для всего подмассива False возвращается 0. Мы будем обрабатывать все False подмассив позже с where
• После np.argmax, 2D-маска уменьшается до 1D-маски. Каждый элемент этой 1D-маски представляет собой номер индекса строки перекрывающегося подсписка. Передав его в .loc, вы получите соответствующие значения столбца index. Однако результат также ошибочно включает строку, в которой подмассив 2D-маски содержит все False. Мы хотим, чтобы эти строки превратились в NaN. Это функциональность .where

Метод 1 :
Использование списка для построения логической 2D-маски m между каждым списком links и все списки в links. Нам нужно только обратное сравнение, поэтому используйте np.tril для cru sh верхний правый треугольник маски со всеми False, что представляет прямое сравнение. Наконец, вызовите np.argmax, чтобы получить позицию первого True в каждом ряду m и цепочку where, чтобы превратить все False строки m в NaN

c95_list = counts95.links.tolist()
m = np.tril([[any(x in l2 for x in l1) for l2 in c95_list] for l1 in c95_list],-1)
counts95['linkoflist'] = (counts95.loc[np.argmax(m, axis=1), 'index']
                                  .where(m.any(1)).to_numpy())

 Out[351]:
     index  level0            links  linkoflist
0   616351      25  [1, 2, 3, 4, 5]         NaN
1   616352      30      [23, 45, 2]    616351.0
2   616353      35      [1, 19, 67]    616351.0
3  6457754     100     [14, 15, 16]         NaN
4  6566666     200          [1, 14]    616351.0
5  6457754     556          [14, 1]    616351.0

---

Метод 2 :
Если ваш фрейм данных большой, сравнение каждого подсписка только с верхней частью links делает его быстрее. Это вероятно в 2 раза быстрее, чем метод 1 на большом фрейме данных.

c95_list = counts95.links.tolist()
m = [[any(x in l2 for x in l1) for l2 in c95_list[:i]] for i,l1 in enumerate(c95_list)]
counts95['linkoflist'] = counts95.reindex([np.argmax(y) if any(y) else np.nan 
                                                   for y in m])['index'].to_numpy()

---

Шаг за шагом (метод 1)

m = np.tril([[any(x in l2 for x in l1) for l2 in c95_list] for l1 in c95_list],-1)

Out[353]:
array([[False, False, False, False, False, False],
       [ True, False, False, False, False, False],
       [ True, False, False, False, False, False],
       [False, False, False, False, False, False],
       [ True, False,  True,  True, False, False],
       [ True, False,  True,  True,  True, False]])

argmax возвращает оба положения первая True и первая False из всех - False строк.

In [354]: np.argmax(m, axis=1)
Out[354]: array([0, 0, 0, 0, 0, 0], dtype=int64)

Нарезка с использованием результата argmax

counts95.loc[np.argmax(m, axis=1), 'index']

Out[355]:
0    616351
0    616351
0    616351
0    616351
0    616351
0    616351
Name: index, dtype: int64

Цепочка where для поворота строк соответствует всем False от m до NaN

counts95.loc[np.argmax(m, axis=1), 'index'].where(m.any(1))

Out[356]:
0         NaN
0    616351.0
0    616351.0
0         NaN
0    616351.0
0    616351.0
Name: index, dtype: float64

Наконец, индекс вывода отличается от индекса counts95, поэтому просто вызовите to_numpy, чтобы получить ndarray присвоить столбцу linkoflist из counts95.

Answer 2

Еще одна альтернатива, где вы можете манипулировать данными больше;

Код

import pandas as pd

counts95 = pd.DataFrame({'index': [616351, 616352, 616353,6457754,6566666,464664683], 
                   'level0': [25,30,35,100,200,556],
                   'links' : [[1,2,3,4,5],[23,45,2],[1,19,67],[14,15,16],[1,14],[14,1]],
                   'linksoflinks' : [None,None,None,None,None,None]})

def has_match(ar1, ar2):
    return bool(set(ar1).intersection(ar2))

def set_linksoflinks(df):
    for i, row in df.iterrows():
        j = i+1
        while j<df.shape[0]:
            check = has_match(row['links'], df.loc[j, 'links'])
            if check and not df.loc[j, 'linksoflinks']:
                df.loc[j, 'linksoflinks'] = row['index']
            j+=1
    return df.copy()

df = set_linksoflinks(counts95)

print(df)

Выход

       index  level0            links linksoflinks
0     616351      25  [1, 2, 3, 4, 5]         None
1     616352      30      [23, 45, 2]       616351
2     616353      35      [1, 19, 67]       616351
3    6457754     100     [14, 15, 16]         None
4    6566666     200          [1, 14]       616351
5  464664683     556          [14, 1]       616351

Answer 3

с использованием explode и duplicated и .map для присвоения дублирующимся значениям ссылки, но только последним.

df = counts95.explode('links')


m = df[df.duplicated(subset=['links'],keep=False)].groupby('links')['index'].first()


df['link_above'] = df['links'].loc[df.duplicated(subset='links',keep='first')].map(m)



re_made_df = df.groupby(["index", "level0"]).agg(
    links=("links", list), linkoflist=("link_above", "first")).reset_index()


print(re_made_df)


     index  level0            links  linkoflist
0   616351      25  [1, 2, 3, 4, 5]         NaN
1   616352      30      [23, 45, 2]    616351.0
2   616353      35      [1, 19, 67]    616351.0
3  6457754     100     [14, 15, 16]         NaN

Answer 4

Хороший шаблон будет использовать правильные структуры данных для вашей задачи. Лучший ответ на вопрос «элемент X присутствует в последовательности Y» - встроенный set. Когда ваши наборы являются неизменяемыми, рассмотрите возможность использования frozenset.

Решение

Вот как я мог бы решить проблему в pythoni c способом:

# necessary imports
from collections import defaultdict
from typing import Tuple, FrozenSet, DefaultDict

# initialise the links "mapping": for every index save frozenset of its links
links: Tuple[Tuple[int, FrozenSet[int]]] = (
    # tuple of tuples is like a dict but will let you iterate by index
    (616351, frozenset((1, 2, 3, 4, 5))),
    (616352, frozenset((23, 45, 2))),
    (616353, frozenset((1, 19, 67))),
    (6457754, frozenset((14, 15, 16))),
)

# defaultdict automatically creates new lists
#   as you access its keys which are not yet present
links_of_links: DefaultDict[int, List[int]] = defaultdict(list)

for i, item in enumerate(links):
    key, values = item  # split tuple into individual elements
    next_rows = links[i+1:]  # we will iterate over succeeding rows
    for next_key, next_values in next_rows:
        # here we check sets intersection:
        #   it is non-empty if any common elements are present
        if values & next_values:
            # though key might not be present in links_of_links,
            #   defaultdict will autocreate a new empty list
            links_of_links[key].append(next_key)

Содержание of links_of_links: defaultdict(<class 'list'>, {616351: [616352, 616353]})

Сложность

Давайте теперь сравним сложность вашего решения с моим, чтобы доказать, что последнее более эффективно. Давайте предположим, что N - это количество строк, а L - это некоторая длина списков ссылок (средняя или максимальная, это не имеет значения). Ваши решения сравнивают примерно все пары строк, что дает нам O(N * N). Затем это умножается на сложность наивного сравнения двух списков - O(L * L). Это дает нам O(N * L)² в общей сложности.

Предлагаемое решение по-прежнему перекрестно соединяет все строки, поэтому N * N остается с нами. Но теперь мы сравниваем сами наборы более эффективно: O(min(L, L)) === O(L), как говорит Python Сложность времени . Таким образом, общая сложность делится на одну L, что дает O(N² * L) как общее.