python - 在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

验证值是否在一组范围内

无需生成和迭代列表。我怀疑简单地使用比较运算符会更有效。

但是，如果您想确认哪种方法最有效，请使用 profiling tools .

下面是一个分析几种方法的示例，用于查明某个值是否在一组范围内，以验证哪种方法最有效。

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