Какой самый эффективный способ проверить, существует ли значение в диапазоне начальных и конечных позиций в Python?

Question

Допустим, у меня есть текстовый файл с начальной и конечной позициями, например:

Start End
  1     5
 11    14
 15    19
 23    30

Я хочу проверить, существует ли заданный набор значений между этими позициями и в том числе, например 4,14, 20 вернет TRUE, TRUE, FALSE.

Какой самый эффективный способ сделать это?

Идея 1) Я мог бы сгенерировать каждое возможное число в списке и проверить, есть ли значение в списке - псевдокод будет выглядеть следующим образом:

list = []
values = [4,14,20]
for line in file:
    for position in range(int(line.split()[0]),int(line.split()[1])+1):
        list.append(position) #Populate list with every viable position

for value in values:
    if value in list:
        print("TRUE")
    else:
        print("FALSE")

Идея 2) Вместо сохранения каждой возможной позиции в списке, сохраняйте только начало и конец, а затем просматривайте каждый диапазон при проверке:

list = []
for line in file:
    list.append(line) #Save only start and end into list

for value in values:
    for start_end in list:
        for position in range(int(start_end.split()[0]),int(start_end.split()[1])+1):
            if value == position:
                print("TRUE")

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

Или есть какой-то совершенно другой способ? так лучше? Большое спасибо!

Answer 1

Проверка значения в наборе диапазонов

Нет необходимости создавать и повторять списки. Я подозреваю, что было бы более эффективно просто использовать операторы сравнения.

Однако, если вы хотите подтвердить, какой подход наиболее эффективен, используйте инструменты профилирования .

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

import cProfile

# Input data.
ranges = [[1, 5], [11, 14], [15, 19], [23, 30]]
values = [4, 14, 40]

# An implementation using a comparison operator (i.e. "<=").
def is_in_range_comparison_operator(v):
    for r in ranges:
        if r[0] <= v <= r[1]:
            return True
    return False

# An implementation using a range object.
def is_in_range_range_object(v):
    for r in ranges:
        if v in range(r[0], r[1]+1):
            return True
    return False

# An implementation using precomputed range objects.
range_objects = [range(r[0], r[1]+1) for r in ranges]
def is_in_range_precomputed_range_objects(v):
    for r in range_objects:
        if v in r:
            return True
    return False

# A list of the implementations, to make looping through them easier.
implementations = [
        is_in_range_comparison_operator,
        is_in_range_range_object,
        is_in_range_precomputed_range_objects,
        ]

# A function to execute an implementation and print output.
def is_in_range(is_in_range_func):
    print("Using {}:".format(is_in_range_func.func_name))
    for v in values:
        if is_in_range_func(v):
            print ("True")
        else:
            print ("False")
    print

# Run each implementation, printing out the results.
for f in implementations:
    is_in_range(f)

# A function for executing a implementation repeatedly, for profiling purposes.
def test_is_in_range(is_in_range_func, num_iterations):
    for _ in range(num_iterations):
        for v in values:
            if is_in_range_func(v):
               pass

# Profile each implementation by running it num_iterations times.
num_iterations = 100000
for f in implementations:
    command = "test_is_in_range({}, {})".format(
            f.func_name, num_iterations)
    print("Profiling the following command: {}".format(command))
    cProfile.run(command)

А вот результат выполнения сценария:

$ python in_range.py
Using is_in_range_comparison_operator:
True
True
False

Using is_in_range_range_object:
True
True
False

Using is_in_range_precomputed_range_objects:
True
True
False

Profiling the following command: test_is_in_range(is_in_range_comparison_operator, 100000)
         300004 function calls in 0.388 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.388    0.388 <string>:1(<module>)
        1    0.172    0.172    0.388    0.388 in_range.py:51(test_is_in_range)
   300000    0.212    0.000    0.212    0.000 in_range.py:8(is_in_range_comparison_operator)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.004    0.004    0.004    0.004 {range}


Profiling the following command: test_is_in_range(is_in_range_range_object, 100000)
         1000004 function calls in 1.209 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    1.209    1.209 <string>:1(<module>)
   300000    0.639    0.000    1.033    0.000 in_range.py:15(is_in_range_range_object)
        1    0.174    0.174    1.209    1.209 in_range.py:51(test_is_in_range)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
   700001    0.396    0.000    0.396    0.000 {range}


Profiling the following command: test_is_in_range(is_in_range_precomputed_range_objects, 100000)
         300004 function calls in 0.391 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.391    0.391 <string>:1(<module>)
   300000    0.220    0.000    0.220    0.000 in_range.py:23(is_in_range_precomputed_range_objects)
        1    0.171    0.171    0.391    0.391 in_range.py:51(test_is_in_range)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.001    0.001    0.001    0.001 {range}

Некоторые выводы из результатов профилирования:

• Использование операторов сравнения более эффективно, чем повторное создание экземпляров объектов диапазона.
• Использование предварительно вычисленных объектов диапазонов наравне с использованием операторов сравнения.

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

---

Эффективная обработка произвольно большого набора диапазонов

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

Примечания:

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

ranges = [[4, 5], [11, 14], [15, 19], [23, 30]]
values = [4, 14, 20]

# Create a dictionary to keep track whether or not each value falls within
# a range, with a default value of False.
is_value_in_range = {}

def init_results():
    global is_value_in_range
    is_value_in_range = {v: False for v in values}

def print_values_and_results():
    for v in values:
        print("{}: {}".format(v, is_value_in_range[v]))

def check_for_values_in_range(r, values_index):
    for i, v in enumerate(values[values_index:]):

        # If the value is greater than the upper end of the range, move on
        # to the next range.
        if v > r[1]:
            return (values_index + i, True)

        # If the value is less than the lower end and we're on the last
        # value, stop altogether.
        if v < r[0] and values_index == len(values) - 1:
            return (0, False)

        if r[0] <= v <= r[1]:
            is_value_in_range[v] = True

    return (values_index, True)

def check_for_values_in_ranges(verbose=False):
    init_results()
    if verbose:
        print("Initial results:")
        print_values_and_results()
        print
    i = 0
    for r in ranges:
        i, continue_searching = check_for_values_in_range(r, i)
        if verbose:
            print("After checking range: {}".format(r))
            print_values_and_results()
            print
        if not continue_searching:
            break

    print("Final results:")
    print_values_and_results()
    print

print("*** Check ranges for values (non-verbose) ***")
check_for_values_in_ranges()

print("*** Check ranges for values (verbose) ***")
check_for_values_in_ranges(True)

Вывод сценария:

$ python large_input.py
*** Check ranges for values (non-verbose) ***
Final results:
4: True
14: True
20: False

*** Check ranges for values (verbose) ***
Initial results:
4: False
14: False
20: False

After checking range: [4, 5]
4: True
14: False
20: False

After checking range: [11, 14]
4: True
14: True
20: False

After checking range: [15, 19]
4: True
14: True
20: False

After checking range: [23, 30]
4: True
14: True
20: False

Final results:
4: True
14: True
20: False

Answer 2

Не знаю, неправильно ли я что-то понял, но почему бы не попробовать что-то подобное? Это проще и работает.

limits = {"a":[1,5],"b":[11,14],"c":[15,19],"d":[23,30]}
values = [3,14,20]
for var in limits:
    for a in values:
        if a in range(limits[var][0],limits[var][1]+1):
            print ("TRUE")
        else:
            print ("FALSE")

вывод:

ИСТИНА, ЛОЖЬ, ЛОЖЬ, / ЛОЖЬ, ЛОЖЬ, / ЛОЖЬ, ЛОЖЬ, ЛОЖЬ / ЛОЖЬ, ЛОЖЬ, ЛОЖЬ

Answer 3

Мое решение простое и лаконичное, но оно позволяет обрабатывать большие файлы и не требует никакой индексации / перечисления:

vals = (4,14,20)
with open('rangefile.txt') as f:
    next(f)  # skip header
    for line in f:
        start, end = map(int, line.split())
        matches = [start <= v <= end for v in vals]
        print(matches)

, что при входном файле

Start End
  1     5
 11    14
 15    19
 23    30

производит

[True, False, False]
[False, True, False]
[False, False, False]
[False, False, False]

Answer 4

Оптимизация вашей «идеи 2»:

• анализирует ввод только один раз;под синтаксическим анализом я подразумеваю разбивать строки и преобразовывать строки в целые числа
• использовать простое и быстрое сравнение start <= value <= end, нет range необходимых объектов
• закорачивать оценку, т.е. останавливать после первого соответствиянайден интервал
• , а также: избегайте list в качестве имени переменной

Результат part1:

selist = []
with open(filename) as file:
    for line in file:
        n1, n2 = line.split()
        selist.append((int(n1), int(n2))) #Save only start and end into list

и part2:

for value in values:
    result = any(start <= value <= end for start, end in selist)
    print(result)   # True or False

Дальнейшая оптимизация возможна, если диапазоны не перекрываются и их много. Тогда вы можете отсортировать их и использовать пополам.

Answer 5

Можно читать из большого файла по одной строке за раз после создания ссылки на него с помощью open. Для краткого примера:

values = [4, 14, 20]
with open("some_file.txt", "r") as f:
    for test_val in values:
        min_val, max_val = f.readline().split()
        print(test_val >= int(min_val) and test_val <= int(max_val))

Это распечатало бы:

True
True
False

Open создает итератор, в котором хранится последняя доступная часть файла, с которым связана ссылка. В этом примере readline использует этот итератор как своего рода «закладку данных». При первом вызове readline тянет от начала файла до тех пор, пока не будет найден разрыв строки, а затем устанавливает закладку после этого разрыва строки. Каждый последующий вызов readline после первого вызова начинается с того места, где в последний раз была установлена ​​закладка, до следующего найденного разрыва строки. Как только найден следующий найденный разрыв строки, закладка перемещается туда.

Answer 6

Я думаю, вам также не нужен диапазон

Вы должны просто проверить < и >:

listRange=[[ 1     ,5],[ 11 ,   14],[ 15  ,  19],[ 23  ,  30]]
value =[4,14,20]
for i , t in enumerate(value,start=0): 
  if t>=listRange[i][0] and t<=listRange[i][1]:
    print ('TRUE')
  else:
    print ('FALSE')

Answer 7

Пример использования DataFrame:

import pandas as pd
df = pd.DataFrame({'Start': [1, 11, 15, 23], 'End': [5, 14, 19, 30]})
your_list = [4, 14, 20]

for x in your_list:
    print([item[0] <= x <= item[1] for item in df.itertuples(index=False)])
> [True, False, False, False]
> [False, True, False, False]
> [False, False, False, False]