Поиск списка или массива для лучшего соответствия подсписку (по числовой разнице)? - PullRequest
Новая
       29

Поиск списка или массива для лучшего соответствия подсписку (по числовой разнице)?

0 голосов
/ 15 января 2020

У меня есть список значений, подобных этому: 

[ 669,  592,  664, 1005,  699,  401,  646,  472,  598,  681, 1126, ...]

Мой вопрос, учитывая небольшой список чисел, например: 

[ 400, 650, 475 ]

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

[401,  646,  472, ]  # difference = 1 + 4 + 3 = 8

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

Есть ли способ поиска в списке для лучшего подсписка (последовательного), соответствующего (или ближайшего к) критериям поиска?

Ответы [ 4 ]

3 голосов
/ 15 января 2020

Вы можете перебирать подсписки более длинного списка и передавать ключевую функцию в min: 

lst = [ 669,  592,  664, 1005,  699,  401,  646,  472,  598,  681, 1126 ]
small = [ 400, 650, 475 ]
match = min((lst[i:i + len(small)] for i in range(len(lst) - len(small) + 1)), key=lambda sub: sum(abs(a - b) for a, b in zip(small, sub)))
print(match) # 401,  646,  472

И если вы хотите, чтобы отсортированный список наилучшего совпадения совпадал с худшим, просто замените min с sorted. 

print(sorted((lst[i:i + len(small)] for i in range(len(lst) - len(small) + 1)), key=lambda sub: sum(abs(a - b) for a, b in zip(small, sub))))
[[401, 646, 472], [472, 598, 681], [669, 592, 664], [646, 472, 598], [699, 401, 646], [1005, 699, 401], [592, 664, 1005], [664, 1005, 699], [598, 681, 1126]]

Если вы находите страшными однострочники (я должен признать, что да, ха-ха), вот немного более читаемая версия: 

lst = [ 669,  592,  664, 1005,  699,  401,  646,  472,  598,  681, 1126 ]
small = [ 400, 650, 475 ]

def key(sublist):
    result = 0
    for a, b in zip(sublist, small):
        result += abs(a - b)
    return result

sublist_iter = (lst[i:i + len(small)] for i in range(len(lst) - len(small) + 1))
match = min(sublist_iter, key=key) # or `sorted`
print(match)
1 голос
/ 15 января 2020

Fast NumPy решение: 

import numpy as np

# Taken from https://rigtorp.se/2011/01/01/rolling-statistics-numpy.html
def rolling_window(a, window):
    shape = a.shape[:-1] + (a.shape[-1] - window + 1, window)
    strides = a.strides + (a.strides[-1],)
    return np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)

lst = np.array([669, 592, 664, 1005, 699, 401, 646, 472, 598, 681, 1126])
small = np.array([400, 650, 475])

sublists = rolling_window(lst, len(small))

# Only find the best match
match = sublists[np.abs(sublists - small).sum(axis=1).argmin()]
print(match)

# Array of matches, best to worst
match = sublists[np.abs(sublists - small).sum(axis=1).argsort()]
print(match)

Время: 

In [1]: import numpy as np
   ...:
   ...: # Taken from https://rigtorp.se/2011/01/01/rolling-statistics-numpy.html
   ...: def rolling_window(a, window):
   ...:     shape = a.shape[:-1] + (a.shape[-1] - window + 1, window)
   ...:     strides = a.strides + (a.strides[-1],)
   ...:     return np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)
   ...:
   ...: lst = np.array([669, 592, 664, 1005, 699, 401, 646, 472, 598, 681, 1126])
   ...: small = np.array([400, 650, 475])
   ...:
   ...: sublists = rolling_window(lst, len(small))

In [2]: %timeit sublists[np.abs(sublists - small).sum(axis=1).argmin()]
6.43 µs ± 51.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [3]: %timeit sublists[np.abs(sublists - small).sum(axis=1).argsort()]
10 µs ± 1.03 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [4]: lst = [ 669,  592,  664, 1005,  699,  401,  646,  472,  598,  681, 1126 ]
   ...: small = [ 400, 650, 475 ]

In [5]: %timeit min((lst[i:i + len(small)] for i in range(len(lst) - len(small) + 1)), key=lambda sub: sum(abs(a - b) for a, b in zip(small, sub)))
17.4 µs ± 1.39 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [6]: %timeit sorted((lst[i:i + len(small)] for i in range(len(lst) - len(small) + 1)), key=lambda sub: sum(abs(a - b) for a, b in zip(small, sub)))
15.9 µs ± 208 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Я ожидаю, что ускорения будут еще больше, если списки длинные.

Не стесняйтесь принять этот ответ вместо моего другого, если этот тебе подходит больше:)

1 голос
/ 15 января 2020

Удивило, что никто не предложил numpy решение: 

import numpy as np

numbers = np.array([669, 592, 664, 1005, 699, 401, 646, 472, 598, 681, 1126])
searchs = [400, 650, 475]

for search in searchs:
    result = numbers[np.abs(numbers - search).argmin()]
    print(result)

Выходы: 

401
646
472
1 голос
/ 15 января 2020

Вы можете сделать это следующим образом: 

import operator
numbers = [ 669,  592,  664, 1005,  699,  401,  646,  472,  598,  681, 1126, 669,  592,  664]

search =  [ 400, 650, 475 ]

diffs = {}

for index in range(len(numbers)-len(search)+1):
    subset = numbers[index:index+len(search)]
    diff = sum([abs(x-y) for x,y in zip(subset,search)])
    diffs[diff] = diffs.get(diff,[]) + [subset]

for key, value in sorted(diffs.items(), key=operator.itemgetter(0)):
    print("{} : {}".format(key, value))

Вывод: 

8 : [[401, 646, 472]]
330 : [[472, 598, 681]]
516 : [[669, 592, 664], [669, 592, 664]]
547 : [[646, 472, 598]]
719 : [[699, 401, 646]]
728 : [[1005, 699, 401]]
736 : [[592, 664, 1005]]
843 : [[664, 1005, 699]]
862 : [[1126, 669, 592]]
880 : [[598, 681, 1126]]
951 : [[681, 1126, 669]]

Печатается по порядку и, если у вас есть одно и то же значение дважды, печатает оба списка для этого разница.

...