Два значения в двух списках, упрощение кода

Question

У меня есть два списка, и я хочу сравнить значение в каждом списке, чтобы узнать, находится ли разница в определенном диапазоне и возвращает количество одинаковых значений в каждом списке. Вот мой код первая версия:

m = [1,3,5,7] 
n = [1,4,7,9,5,6,34,52] 
k=0 
for i in xrange(0, len(m)): 
    for j in xrange(0, len(n)): 
     if abs(m[i] - n[j]) <=0.5: 
      k+=1 
     else: 
      continue 

выход 3. Я также попробовал 2-й вариант:

for i, j in zip(m,n): 
    if abs(i - j) <=0.5: 
     t+=1 
    else: 
     continue 

выход 1, ответ неверен. Поэтому мне интересно, есть ли более простой и эффективный код для 1-й версии, у меня есть большой набор данных для обработки. Спасибо!

Answer 1

Первое, что вы могли бы сделать, это удалить else: continue, так как это ничего не добавляет. Кроме того, вы можете напрямую использовать for a in m, чтобы избежать итерации по диапазону и индексации.

---

Если вы хотите написать его более succiently, вы могли бы использовать itertools.

import itertools 

m = [1,3,5,7] 
n = [1,4,7,9,5,6,34,52] 
k = sum(abs(a - b) <= 0.5 for a, b in itertools.product(m, n)) 

Среда выполнения этого (и ваше решение) является O(m * n), где m и n -длины списков.

---

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

import bisect 

m = [1,3,5,7] 
n = [1,4,7,9,5,6,34,52] 
n.sort() 
k = 0 
for a in m: 
    i = bisect.bisect_left(n, a - 0.5) 
    j = bisect.bisect_right(n, a + 0.5) 
    k += j - i 

Срок службы O((m + n) * log n). Это n * log n для сортировки и m * log n для поиска. Поэтому вы хотите сделать n более короткий список.

Answer 2

Более вещий версия вашей первой версии:

ms = [1, 3, 5, 7] 
ns = [1, 4, 7, 9, 5, 6, 34, 52] 
k = 0 
for m in ms: 
    for n in ns: 
     if abs(m - n) <= 0.5: 
      k += 1 

Я не думаю, что он будет работать быстрее, но это проще (более читаемым).

Answer 3

Это проще и, вероятно, немного быстрее, чтобы просто перебирать списки непосредственно, а не перебирать объекты диапазона для получения значений индекса. Вы уже делаете это в своей второй версии, но вы не создаете все возможные пары с этим вызовом zip(). Вот модификация первого варианта:

m = [1,3,5,7] 
n = [1,4,7,9,5,6,34,52] 
k=0 
for x in m: 
    for y in n: 
     if abs(x - y) <=0.5: 
      k+=1 

Вам не нужно else: continue часть, которая ничего не делает в конце цикла, так что я оставил его.

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

k = sum(sum(abs(x-y) <= 0.5 for y in n) for x in m) 

Это должно работать достаточно быстро, используя только ядро ​​языка, и нет импорта.

Answer 4

Ваши два фрагмента кода делают две разные вещи. Первый из них сравнивает каждый элемент n с каждым элементом m, но второй выполняет только попарное сравнение соответствующих элементов m и n, останавливаясь, когда более короткий список заканчивается из элементов.Мы можем видеть, какие именно элементы сравниваются во втором случае, напечатав zip:

>>> m = [1,3,5,7] 
>>> n = [1,4,7,9,5,6,34,52] 
>>> zip(m,n) 
[(1, 1), (3, 4), (5, 7), (7, 9)] 

pawelswiecki опубликовал более Pythonic версию первого фрагмента. Как правило, лучше напрямую перебирать контейнеры, а не использовать индексированный цикл, если вам действительно нужен индекс. И даже тогда, больше Pythonic использовать enumerate() для генерации индекса, чем использовать xrange(len(m)). Например

>>> for i, v in enumerate(m): 
...  print i, v 
... 
0 1 
1 3 
2 5 
3 7 

Правило большого пальца заключается в том, что если вы оказываетесь писать for i in xrange(len(m)), там, наверное, лучший способ сделать это. :)

Уильям Гаул сделал хорошее предложение: если ваши списки отсортированы, вы можете вывести break из внутреннего цикла после того, как абсолютная разница будет больше, чем ваш порог 0,5. Однако ответ Пола Дрейпера с использованием bisect - мой любимый. :)