Python 3 появление соответствует

Question

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

def query(a=[1,2,3,4], b=[3,1,1,2,3,4,5,6]): 
     """ 
     table A   table B   Expected Output  Actual Output 
     idx value  idx value   indxA indxB   indxA indxB 
     0  1   0 3    0  1    0  1 
     1  2   1 1    0  2    0  1 
     2  3   2 1    1  3    1  3 
     3  4   3 2    2  0    2  0 
         5 4    2  3    2  0 
         6 5    3  5    3  5 
         7 6 

     EXAMPLE 
     Table A index 0 occurs at Table B index 1 and 2 
     PROBLEM 
     Anywhere there are multiple matches only first occurrence prints 
     """ 
     for idx, itemA in enumerate(a): 
      if itemA in b: 
       for itemB in b: 
        if itemA == itemB: 
         print("{} {}".format(a.index(itemA), b.index(itemB))) 


    query() 

Answer 1

list.index(x) возвращает индекс в списке первый пункт, значение которого х. Итак, вы должны использовать enumerate(b).

def query(a=[1,2,3,4], b=[3,1,1,2,3,4,5,6]): 
    for index_a, value_a in enumerate(a): 
     for index_b, value_b in enumerate(b): 
      if value_a == value_b: 
       print("{} {}".format(index_a, index_b)) 

query() 

Answer 2

Для больших списков, повторяющихся по каждому элементу в одном списке для другого элемента в другом списке, может быть медленным. Это квадратичный алгоритм.

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

def query_list(a, b): 
    res = [] 
    for index_a, value_a in enumerate(a): 
     for index_b, value_b in enumerate(b): 
      if value_a == value_b: 
       res.append((index_a, index_b)) 
    return res 

Это альтернативная реализация с использованием словарей:

def query_dict(a, b): 
    indices = {value: index for index, value in enumerate(a)} 
    res = [] 
    for index_b, value_b in enumerate(b): 
     if value_b in indices: 
      res.append((indices[value_b], index_b)) 
    return sorted(res) 

Генерация некоторые данные Пример:

import random 
a = list(range(1, 1000)) 
b = [random.randint(1, 100) for x in range(10000)] 

версия списка:

%timeit query_list(a, b) 
1 loops, best of 3: 1.09 s per loop 

гораздо медленнее, чем версия Dict:

%timeit query_dict(a, b) 
100 loops, best of 3: 11.8 ms per loop 

Это примерно в 10 раз

Использование большого примера данные:

import random 
a = list(range(1, 10000)) 
b = [random.randint(1, 100) for x in range(10000)] 

разница становится еще более выраженным:

%timeit query_list(a, b) 
1 loops, best of 3: 11.4 s per loop 

%timeit query_dict(a, b) 
100 loops, best of 3: 13.7 ms per loop 

Перейти к коэффициенту близкого расстояния t o 100.