Как эффективно проверить, появляется ли x перед y в списке

Когда гарантировано, что элемент будет найден в L только один раз, вы можете использовать простой словарь, который сопоставляет каждый элемент с его индексом. Однако если элемент может появляться несколько раз, для него требуются два словаря: один для хранения первого появления элемента, а другой — для хранения последнего.

L = ["n", "s", "t", "r", "i", "n", "g", "r"]
elem2index_first = {}
elem2index_last = {}

for index, elem in enumerate(L):
    if elem not in elem2index_first:  # Only update on the first occurrence
        elem2index_first[elem] = index
    elem2index_last[elem] = index  # Overwrite on whatever the previous index was

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

print(elem2index_first[x] < elem2index_last[y])  # x comes before y

Как было предложено в ответе Долмока, вы можете использовать две индексные карты и выполнить поиск.

xs = ["p", "x", "k", "j", "p", "y", "x", "l"]

n = len(xs)
last_seen = dict(zip(xs, range(n)))
first_seen = dict(zip(reversed(xs), range(n - 1, -1, -1)))

is_x_before_y = first_seen['x'] < last_seen['y']
assert is_x_before_y

def ensure_x_bfr_y(L, xy):
    xy = list(xy)
    
    
    #Declare empty dict
    dct = {}
    
    # Iterate thru xy
    for x in xy:
    
        #Find the index of x and create a sublist of elements after x
        x_idx = L.index(x[0])
        
        sub = L[x_idx+1:]
        
        if x[1] in sub:
            dct[x] = True
        else:
            dct[x] = False
    return dct

L = [23, 44, 11, 89, 65, 40, 71, 84,11]
xy = (23, 71), (89, 84), (40, 23), (65, 11)
r = ensure_x_bfr_y(L,xy)
print(r) # Output : {(23, 71): True, (89, 84): True, (40, 23): False, (65, 11): True}