Как сравнить 2 отсортированных числовых списка в Python, где каждый соответствующий элемент не должен точно совпадать?

Question

Учитывая 2 списка отсортированных чисел, как показано ниже:

>>> list1 = list(map(int, '7 22 34 49 56 62 76 82 89 161 174'.split()))
>>> list2 = list(map(int, '7 14 49 57 66 76 135 142 161'.split()))

numpy.in1d ​​даст истинные значения для 7, 49, 76 и 161.

Но я хотел бы принятьопределенный допуск говорит до 3 и дает истинные значения для 7, 49, 57 , 76 и 161 (потому что 56 в списке 1 и 57 в списке 2 - это только разница на 1)

Я написалследующий код для получения желаемого результата, где FifoList () является реализацией стека fifo:

    class FifoList:
        def __init__(self):
            self.data = []

        def append(self, data):
            self.data.append(data)

        def pop(self):
            return self.data.pop(0)

    def match_approximate(a, b, approx=3):
        c = []
        bEnd = False
        bfifo = FifoList()
        for i in b:
            bfifo.append(i)
        y = 0
        for x in a:
            if bEnd:
                continue
            while True:
                if y == 0 or x - y > approx:
                    try:
                        y = bfifo.pop()
                    except KeyError:
                        bEnd = True
                        break
                if abs(x - y) <= approx:
                    c.append(y)
                    break
                if y > x:
                    break
        return c

Просто интересно, есть ли другой лучший способ реализовать это?

Answer 1

Выбор приблизительного соответствия из X:

import numpy as np

X = np.array([7,22,34,49,56,62,76,82,89,161,174])  #len:11
Y = np.array([7,14,49,57,66,76,135,142,161])       #len:9

dist = np.abs(Y[:, np.newaxis] - X)
#print(dist)
for i in range(len(Y)):
    for j in dist[i]:
        if -3<=j<=3: #approximation of 3
            idx = dist[i].tolist().index(j)
            print(X[idx])

Выход:

7
49
56
76
161

Выбор приблизительного соответствия из Y:

import numpy as np

X = np.array([7,22,34,49,56,62,76,82,89,161,174])  #len:11
Y = np.array([7,14,49,57,66,76,135,142,161])       #len:9

dist = np.abs(X[:, np.newaxis] - Y)
#print(dist)
for i in range(len(Y)+1):
    for j in dist[i]:
        if -3<=j<=3:
            #print(j)
            idx = dist[i].tolist().index(j)
            print(Y[idx])

Выход:

7
49
57
76
161

Answer 2

Благодаря @MattMessersmith я реализовал свое окончательное решение, удовлетворяющее 2 требованиям:

1. Фильтрует элементы в 2 списках, которые расположены слишком близко друг к другу

2. Соответствующие элементы в 2 списках, которые близки друг к другу

   list1 = [7, 22, 34, 49, 56, 62, 76, 82, 89, 149, 161, 182]
   list2 = [7, 14, 49, 57, 66, 76, 135, 142, 161]
   >>> result = match_approximate(list1, list2, 3)
   >>> print result[0]
   >>> print result[1]
   [7, 49, 56, 76, 161]
   [7, 49, 57, 76, 161]
   >>> result = match_approximate(list1, list2, 1, True)
   >>> print result[0]
   >>> print result[1]
   [22, 34, 62, 82, 89, 149, 182]
   [14, 66, 135, 142]
   

Вот код:

    def match_approximate(a, b, approx, invert=False):
        a_ind, b_ind = 0, 0
        resulta, resultb = [], []
        while a_ind < len(a) and b_ind < len(b):
            aItem, bItem = a[a_ind], b[b_ind]
            if abs(aItem - bItem) <= approx:
                if not invert:
                    resulta.append(aItem)
                    resultb.append(bItem)
                a_ind += 1
                b_ind += 1
                continue
            if aItem < bItem:
                if invert:
                    resulta.append(aItem)
                a_ind += 1
            else:
                if invert:
                    resultb.append(bItem)
                b_ind += 1

        if invert:
            while a_ind != len(a):
                resulta.append(a[a_ind])
                a_ind += 1
            while b_ind != len(b):
                resulta.append(b[b_ind])
                b_ind += 1

        return [resulta, resultb]

Answer 3

Я не уверен, почему вы используете очередь здесь.Это не похоже на правильную структуру данных для проблемы.Кроме того, Python имеет встроенную структуру данных очереди (collections.deque, и просто используйте popleft() вместо pop(0)).

Более простой способ (imo) - просто поддерживать «указатель» (или индекс) к каждому массиву, начиная с начала.Если элементы находятся в пределах approx друг от друга, добавьте их и увеличьте оба указателя.Если элемент a меньше элемента b, увеличьте указатель a s.Иначе, приращение указателя b s.Продолжайте до тех пор, пока оба указателя не будут исчерпаны (т.е. указывают на конец списка).Это работает в O (N), линейное время.Вот реализация указанного алгоритма:

def match_approximate(a, b, approx=3):
    a_ind, b_ind = 0, 0
    result = []
    while a_ind < len(a) and b_ind < len(b):
        if abs(a[a_ind] - b[b_ind]) <= approx:
            result.append(b[b_ind])
        if a[a_ind] == b[b_ind]:
            b_ind += 1
            a_ind += 1
        elif a[a_ind] < b[b_ind]: a_ind += 1
        else: b_ind += 1

    def match_last_element(a, a_ind, last_elt_of_b, result):
        while a_ind != len(a):
            if abs(a[a_ind] - last_elt_of_b) <= approx:
                result.append(a[a_ind])
                a_ind += 1
            else:
                break

    if a_ind != len(a): match_last_element(a, a_ind, b[-1], result)
    else: match_last_element(b, b_ind, a[-1], result)

    return result

Выполнение

a = [7, 22, 34, 49, 56, 62, 76, 82, 89, 161, 163, 174]
b = [5, 6, 7, 14, 49, 57, 66, 76, 135, 142, 161]
print(match_approximate(a, b, 3))

выдаст [5, 6, 7, 49, 57, 76, 161, 163] (что, как я предполагаю , ожидается, но см. Ниже онекоторые крайние случаи, которые не ясны).Если вы запустите этот случай на своем текущем импле, вы получите IndexError.

Не совсем понятно, что делать в некоторых крайних случаях:

1. Когда выесть приблизительное совпадение, какой элемент вы добавляете к результату?Это подразумевает просто добавление элемента b s (как в примере).

2. Как обрабатывать дубликаты?В этом случае, если оба списка содержат дубликаты, они будут добавлены дважды.Если только один список содержит дубликаты, элементы будут добавлены только один раз.Более сложный пример с dups состоит в том, чтобы понять, есть ли у нас [4,5] и [4,5] в качестве входных данных, если наш вывод будет [4,5] или [4,4,5,5] (поскольку 4 и 5 оба находятся в пределах approx каждогопрочее, 4 также соответствует 5).

3. Является ли привязка approx включительно или исключительной (т. е. <= approx или < approx)?

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

HTH.