Как сравнить значения одного ряда одно за другим с другим целым рядом

Question

У меня есть pandas dataframe, как показано ниже,

   col1  col2
0    12     1
1     1     7
2    54    17
3    11   191
4     3    39
5    76     2
6    18     6

код для генерации df:

df=pd.DataFrame({'col1':[12,1,54,11,3,76,18],'col2':[1,7,17,191,39,2,6]})

Я хотел бы сравнить значения col1 одно за другим с полной серией col2.то есть, сравните 12 с col2, найдите меньше 12 в col2 и посчитайте значения, затем сделайте то же самое для 1, а затем 54 и т. д. и сохраните результат в другой серии.

До сих пор я пробовал какниже,

df['res']=df.apply(lambda x:len(df[df['col2']<x['col1']]),axis=1)

Это работает, как я ожидал.Но это неэффективный способ решить эту проблему - отстой, когда серия велика.

Мне нужен эффективный способ решения этой проблемы.Потому что фактический набор данных содержит более миллиона записей.

Ожидаемый результат:

   col1  col2  res
0    12     1    4
1     1     7    0
2    54    17    6
3    11   191    4
4     3    39    2
5    76     2    6
6    18     6    5

Answer 1

Альтернативное решение с логической функцией np.less:

In [119]: vals = df['col2'].values
In [120]: df['res'] = df.apply(lambda x: np.less(vals, x['col1']).sum(), axis=1)

In [121]: df
Out[121]: 
   col1  col2  res
0    12     1    4
1     1     7    0
2    54    17    6
3    11   191    4
4     3    39    2
5    76     2    6
6    18     6    5

---

Сравнение производительности:

In [122]: %timeit df['res'] = df.apply(lambda x: np.less(vals, x['col1']).sum(), axis=1)
2.09 ms ± 308 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [123]: %timeit df['res']=df.apply(lambda x:len(df[df['col2']<x['col1']]),axis=1)
8.57 ms ± 132 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [124]: %timeit df['res'] = (df['col2'].values.reshape(1,-1) < df['col1'].values.reshape(-1,1)).sum(axis=1)
420 µs ± 26.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

https://docs.scipy.org/doc/numpy-1.14.0/reference/generated/numpy.less.html#numpy.less

Answer 2

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

df['res'] = (df['col2'].values.reshape(1,-1) < df['col1'].values.reshape(-1,1)).sum(axis=1)

(в тесте df с 10k строками, на моей машине этозанимает 0,3 с вместо 8 с).Однако он использует квадратичную память в количестве строк, поэтому, если ваш df имеет миллионы строк, это не очень хорошо ...

[EDIT] Существует решение в O (n * log (n)) (nчисло строк) во времени и пространстве, которое, вероятно, близко к оптимальному (выше указано O (n ^ 2) в обеих, реализация его в C будет O (n ^ 2) во времени, но только O (n)в пространстве), но я не написал код, поскольку он становится утомительным, особенно для обработки случаев равенства и т. д. Псевдокод выглядит следующим образом:

• Сортировка col1 и получение его индексов.Скажем, это дает вам словарь исходного индекса -> отсортированный индекс.
• Сортируйте сопоставленный вектор [col1, col2] и возьмите индексы.Это дает другое отображение, оригинальный индекс -> индекс сортировки.
• Ответ должен быть разностью второго вектора минус первый.

[EDIT2]: Реализация его была на самом деле оченьпроще, чем я думал, это просто:

idx1 = np.argsort(np.argsort(df['col1'], kind='mergesort'), kind='mergesort')
idx2 = np.argsort(np.argsort(np.concatenate((df['col1'], df['col2'])), kind='mergesort'), kind='mergesort')[:len(idx1)]
df['res'] = idx2-idx1

Как уже говорилось, это всего лишь O (n * log (n)) как во времени, так и в пространстве, поэтому даже при большом значении df это занимает очень мало времени (0,1 с для строк по 100 тыс., 1,5 с для строк по 1 млн.) И очень мало дополнительного пространства.

Двойной аргумент argsort обусловлен соглашением о простой сортировке, np.argsort не дает индекс элемента в отсортированном вектореа точнее индекс такой, что x [idx] отсортирован.Небольшой трюк, состоящий в том, чтобы дважды выполнить argsort, дает положение исходного элемента в отсортированном векторе.Я добавил kind = 'mergesort', чтобы использовать стабильную сортировку, это само по себе довольно бесполезно, но должно исправить проблемы, если значение появляется как в col1, так и в col2 (потому что мы хотим считать, когда col2