Скользящее окно по списку списков в Python

Я пытаюсь использовать numpy/pandas для построения компаратора стиля скользящего окна. У меня есть список списков, каждый из которых имеет разную длину. Я хочу сравнить каждый список с другим списком, как показано ниже: 



lists = [[10,15,5],[5,10],[5]]



window_diff(l[1],l[0]) = 25


Окно diff для списков [0] и списков[1] дал бы 25, используя следующую технику скольжения окна, показанную на рисунке ниже. Потому что списки[1] это более короткий путь, мы сдвигаем его один раз вправо, в результате чего получается 2 окна сравнения. Если вы суммируете в последней строке на рисунке ниже мы получаем общую разницу между двумя списками, используя два окна сравнения; в этом случае всего 25. Отметим, что мы берем абсолютную разницу.Введите описание изображения здесь



Функция должна агрегировать общий window_diff между каждым списком и другими списками, поэтому в этом случае



tot = total_diffs(lists)

tot>>[40, 30, 20]



# where tot[0] represents the sum of lists[0] window_diff with all other lists.


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



Мой подход прекрасно работает для коротких списков, но мой набор данных составляет 10 000 списков в длину, и некоторые из этих списков содержат 60 или около того точек данных, поэтому скорость здесь является критерием. Мне было интересно, есть ли у numpy, pandas какие-нибудь советы по этому поводу? Спасибо



Пример проблемных данных 



from random import randint

lists = [[random.randint(0,1000) for r in range(random.randint(0,60))] for x in range(100000)]
638   2  

2 ответов:

Шаги:

  • Среди каждой пары списков из входного списка списков создайте скользящие окна для большего массива, а затем получите абсолютную разницу против меньшего в этой паре. Мы можем использовать NumPy strides Чтобы получить эти раздвижные окна.

  • Получите общую сумму и сохраните это суммирование как парное дифференцирование.

  • Наконец, суммируйте вдоль каждой строки и col на массиве 2D из предыдущего шага, и их суммирование является окончательным выход.

Таким образом, реализация будет выглядеть примерно так - 

import itertools

def strided_app(a, L, S=1 ):  # Window len = L, Stride len/stepsize = S
    a = np.asarray(a)
    nrows = ((a.size-L)//S)+1
    n = a.strides[0]
    return np.lib.stride_tricks.as_strided(a, shape=(nrows,L), strides=(S*n,n))

N = len(lists)
pair_diff_sums = np.zeros((N,N),dtype=type(lists[0][0]))
for i, j in itertools.combinations(range(N), 2):
    A, B = lists[i], lists[j]
    if len(A)>len(B):
        pair_diff_sums[i,j] = np.abs(strided_app(A,L=len(B)) - B).sum()
    else:
        pair_diff_sums[i,j] = np.abs(strided_app(B,L=len(A)) - A).sum()

out = pair_diff_sums.sum(1) + pair_diff_sums.sum(0)

Для действительно тяжелых наборов данных, вот один метод, использующий еще один уровень циклирования - 

N = len(lists)
out = np.zeros((N),dtype=type(lists[0][0]))
for k,i in enumerate(lists):
    for j in lists:
        if len(i)>len(j):
            out[k] += np.abs(strided_app(i,L=len(j)) - j).sum()
        else:
            out[k] += np.abs(strided_app(j,L=len(i)) - i).sum()

strided_app вдохновляется от here.

Вход образца, выход - 

In [77]: lists
Out[77]: [[10, 15, 5], [5, 10], [5]]

In [78]: pair_diff_sums
Out[78]: 
array([[ 0, 25, 15],
       [25,  0,  5],
       [15,  5,  0]])

In [79]: out
Out[79]: array([40, 30, 20])
2  
2017-06-06 12:29:36

Просто для полноты великого ответа @ Divakar и для его применения к очень большим наборам данных: 

import itertools

N = len(lists)
out = np.zeros(N, dtype=type(lists[0][0]))

for i, j in itertools.combinations(range(N), 2):
    A, B = lists[i], lists[j]

    if len(A)>len(B):
        diff = np.abs(strided_app(A,L=len(B)) - B).sum()
    else:
        diff = np.abs(strided_app(B,L=len(A)) - A).sum()

    out[i] += diff
    out[j] += diff

Он не создает ненужных больших наборов данных и обновляет один вектор, повторяя только верхний треугольный массив.

Вычисление все равно займет некоторое время, поскольку существует компромисс между вычислительной сложностью и наборами данных размером больше ОЗУ. Решения для больших, чем ОЗУ наборов данных часто полагаются на итерации, и python не очень хорош в этом. Пробегом в python над большим набором данных работает медленно, очень медленно.

Перевод вышеприведенного кода на cython может немного ускорить процесс.
2  
2017-06-06 14:17:03

Comments

    Ничего не найдено.
Click here to cancel reply.