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

Question

У меня есть два отсортированных списка

x = [-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10]
y = [3,4,5,6]

Между этими x и y я хотел бы вернуть imin = (6,0) и imax = (9,3).Если в этих списках нет общих элементов, я бы хотел вернуть imin = None и imax = None.

Решение:

def inds(x,y):
    arr = [(i,j) for i,xx in enumerate(x) for j,yy in enumerate(y) if xx==yy ]
    if arr!=[]: # to obtain proper None output
        imin = (min(i for i,_ in arr), min(j for _,j in arr))
        imax = (max(i for i,_ in arr), max(j for _,j in arr))
    else: 
        imin = None
        imax = None 
    return (imin,imax)

Это делает много ненужных вычислений (O (n ** 2)) и является узким местом одной из моих программ.Может кто-нибудь предложить что-нибудь быстрее?

ДОПОЛНИТЕЛЬНАЯ (НЕ МИНИМАЛЬНЫЙ ПРИМЕР) ИНФОРМАЦИЯ

Если это поможет, у меня фактически есть список объектов.

objects = [(A1,B1),(A2,B2)] 

x и y будут атрибутами каждого элемента этого списка объектов следующим образом:

x = objects[0][0].attrib
y = objects[0][1].attrib

и я действительно хочу сгенерировать

[(imin1,imax1),(imin2,imax2)]

Что может быть, например, из

def attribs(A,B):
    return (A.attrib,B.attrib)

[inds(*attribs(*v)) for v in objects]

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

Answer 1

Используя np.intersect1d и возвращая индексы, вы можете сделать следующее

idxes = np.stack(np.intersect1d(x,y, return_indices=True)[1:])
ix = tuple(idxes[:,0])
iy = tuple(idxes[:,-1])

>>> ix
(6, 0)
>>> iy
(9, 3)

Объяснение

idxes - это двумерный массив индексов, гдемежду двумя вашими массивами есть пересечения:

>>> idxes
array([[6, 7, 8, 9],
       [0, 1, 2, 3]])

Так что вы можете просто взять первое и последнее, используя

ix = tuple(idxes[:,0])
iy = tuple(idxes[:,-1])

Answer 2

Вы также можете отсортировать список пересечений и использовать .index(), чтобы узнать индексы.

z = list(set(x).intersection(set(y))) # O(n)
z.sort() # O(nlogn)

imin = (x.index(z[0]), y.index(z[0])) # O(n)
imax = (x.index(z[-1]), y.index(z[-1])) # O(n)

Answer 3

Это должно быть то, что вы хотите после

c = set(x).intersection(y)  # O(n) time
def get_first(l):
    return next((idx for idx, elm in enumerate(l) if elm in c), None)  # O(n) time
imin = (get_first(x), get_first(y))
imax = (len(x) - get_first(x[::-1]) - 1, len(y) - get_first(y[::-1]) - 1)

С этого момента вы можете сделать несколько настроек, но он все равно будет работать O(n)