тест, если список содержит число в некотором диапазоне

Question

Предположим, у меня есть список L=[1.1, 1.8, 4.4, 5.2]. Для некоторого целого числа n, я хочу знать, имеет ли L значение val с n-1<val<n+1, и если да, то я хочу знать индекс val.

Лучшее, что я могу сделать до сих пор, чтобы определить генератор

x = (index for index,val in enumerate(L) if n-1<val<n+1) 

и проверить, имеет ли соответствующее значение с помощью try... except. Итак, давайте предположим, что я искал наименьшее п> = 0, для которых такое значение существует ...

L=[1.1, 1.8, 4.4, 5.2] 
n=0 
while True: 
    x = (index for index,val in enumerate(L) if n-1<val<n+1) 
    try: 
     index=next(x) 
     break 
    except StopIteration: 
     n+=1 
print n,index 

На самом деле, я делаю более сложный задача. Я хочу, чтобы иметь возможность взять n, найти первый индекс, и если он не существует, мне нужно сделать что-то еще.

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

Answer 1

Если L отсортирован, можно использовать bisect.bisect_left найти индекс, для которых все L [< я] < < п = все L [> = я].

Тогда

if n - L[i-1] < 1.0: 
    val = L[i-1] 
elif L[i] - n < 1.0: 
    val = L[i] 
else: 
    val = None  # no such value found 

---

Edit: В зависимости от ваших данных, что вы хотите достичь, и сколько времени вы хотите провести писать умный алгоритм, сортировочные могут быть или не быть хорошим решением для вас; и, прежде чем я увижу слишком много O (n) s, развернутых вокруг, я хотел бы указать, что его фактическая проблема, по-видимому, связана с неоднократным исследованием для различных значений n - что бы довольно быстро амортизировать начальные накладные расходы на сортировку - и что его предложение Алгоритм выше - фактически O (n ** 2).

@AntoinePelisse: все средства, давайте делать некоторое профилирование:

from bisect import bisect_left, bisect_right 
from functools import partial 
import matplotlib.pyplot as plt 
from random import randint, uniform 
from timeit import timeit 

#blues  
density_col_lin = [ 
    (0.000, 0.502, 0.000, 1.000), 
    (0.176, 0.176, 0.600, 1.000), 
    (0.357, 0.357, 0.698, 1.000), 
    (0.537, 0.537, 0.800, 1.000) 
] 

# greens 
density_col_sor = [ 
    (0.000, 0.502, 0.000, 1.000), 
    (0.176, 0.600, 0.176, 1.000), 
    (0.357, 0.698, 0.357, 1.000), 
    (0.537, 0.800, 0.537, 1.000) 
] 

def make_data(length, density): 
    max_ = length/density 
    return [uniform(0.0, max_) for _ in range(length)], max_ 

def linear_probe(L, max_, probes): 
    for p in range(probes): 
     n = randint(0, int(max_)) 
     for index,val in enumerate(L): 
      if n - 1.0 < val < n + 1.0: 
       # return index 
       break 

def sorted_probe(L, max_, probes): 
    # initial sort 
    sL = sorted((val,index) for index,val in enumerate(L)) 
    for p in range(probes): 
     n = randint(0, int(max_)) 
     left = bisect_right(sL, (n - 1.0, max_)) 
     right = bisect_left (sL, (n + 1.0, 0.0), left) 
     if left < right: 
      index = min(sL[left:right], key=lambda s:s[1])[1] 
      # return index 

def main(): 
    densities = [0.8, 0.2, 0.08, 0.02] 
    probes = [1, 3, 10, 30, 100] 
    lengths = [[]     for d in densities] 
    lin_pts = [[[] for p in probes] for d in densities] 
    sor_pts = [[[] for p in probes] for d in densities] 

    # time each function at various data lengths, densities, and probe repetitions 
    for d,density in enumerate(densities): 
     for trial in range(200): 
      print("{}-{}".format(density, trial)) 

      # length in 10 to 5000, with log density 
      length = int(10 ** uniform(1.0, 3.699)) 
      L, max_ = make_data(length, density) 
      lengths[d].append(length) 

      for p,probe in enumerate(probes): 
       lin = timeit(partial(linear_probe, L, max_, probe), number=5)/5 
       sor = timeit(partial(sorted_probe, L, max_, probe), number=5)/5 
       lin_pts[d][p].append(lin/probe) 
       sor_pts[d][p].append(sor/probe) 

    # plot the results 
    plt.figure(figsize=(9.,6.)) 
    plt.axis([0, 5000, 0, 0.004]) 

    for d,density in enumerate(densities): 
     xs = lengths[d] 
     lcol = density_col_lin[d] 
     scol = density_col_sor[d] 

     for p,probe in enumerate(probes): 
      plt.plot(xs, lin_pts[d][p], "o", color=lcol, markersize=4.0) 
      plt.plot(xs, sor_pts[d][p], "o", color=scol, markersize=4.0) 

    plt.show() 

if __name__ == "__main__": 
    main() 

, что приводит к

оси х этим количество элементов в L, ось у амортизируются время на зонд; зеленые точки sorted_probe(), синие - linear_probe().

Выводы:

• среды выполнения для обеих функций удивительно линейно относительно длины
• для одного зонда в L, предварительная сортировка примерно в 4 раза медленнее, чем итерация
• точка пересечения, как представляется, около 5 зондов; для этого меньше, линейный поиск быстрее, для большего, предварительная сортировка выполняется быстрее.

Answer 2

Теперь, когда я думаю, что я, наконец, понять свою задачу: просто найти минимальное значение в массиве, и это индекс - п будет равно клеток (Mininum). Или еще проще:

n,index = int(min(L)),L.index(min(L)) 

Answer 3

Вот решение, которое не опирается на try ... except и относительно легко читаемый. В результате он «чувствует себя чище» для меня, но это всегда будет иметь элемент субъективности.

def where_within_range(sequence, lower, upper): 
    for index, value in enumerate(sequence): 
     if lower < value < upper: return index 

L = [ 1.1, 1.8, 4.4, 5.2 ] 

import itertools 
for n in itertools.count(): 
    index = where_within_range(L, n - 1, n + 1) 
    if index != None: break 

print n, index 

Если вы предпочитаете, чтобы избежать повторных вызовов функций накладных расходов вы могли бы вместо того, чтобы сделать это как следует, что в очередной раз использует StopIteration исключение, но с помощью itertools.countreturn и утверждение, (опять же, «как-то ») становится казаться более чистым для меня. Возможно, это потому, что в каждой части статьи try ... есть только одно утверждение ... except ... (по общему признанию, для этого чувства не существует рациональной основы).

import itertools 
def find_joel_root(sequence): 
    for n in itertools.count(): 
     solutions = (index for index, value in enumerate(sequence) if n - 1 < value < n + 1) 
     try: return n, next(solutions) 
     except StopIteration: pass 

L = [ 1.1, 1.8, 4.4, 5.2 ] 
n, index = find_joel_root(L) 
print n, index 

Answer 4

l может быть список или массив NumPy:

next(((i,v) for i,v in enumerate(l) if n-1<v<n+1)) 

использует генераторы и останавливается на первом значении.

Answer 5

У меня есть интересная мысль, используя defaultdict и построить индекс со значениями (n-1) и (n+1), это потребует зацикливание список один раз, а затем просто сравнить ключ/значение, например:

from collections import defaultdict 

L = [1.1, 1.8, 4.4, 5.2] 

x = defaultdict(dict) 
for idx, item in enumerate(L): 
    x[int(item)] = {int(item-1): item-1, int(item+1): item+1, 'index':idx} 

Использование:

n = 5 

x[n].get(n-1) < n < x[n].get(n+1) and x[n]['index'] 
Out[8]: 3 

n = 2 

x[n].get(n-1) < n < x[n].get(n+1) and x[n]['index'] 
Out[10]: False 

Объяснение:

Как будто:

1) True и Index возвращается Index

2) False и индекс вернется False

Поскольку вы собираетесь вводить n как целое число, если первая часть True это будет вернуть вторую часть index значение. Если первая часть терпит неудачу, она возвращает False.

Это вернет возникновение n в ПОСЛЕДНЕГО, в случае, если вам необходимо появление n в FIRST, просто перевернул лист и Индекс:

... 
l = len(L) 
for idx, item in enumerate(reversed(L)): 
    x[int(item)] = {int(item-1): item-1, 
        int(item+1): item+1, 
        'index': l-idx-1} 
...