在 python 的列表中查找项目的最快方法是什么？

Question

对于我的项目，我需要在列表中反复查找时间戳的索引，如果确切的时间戳不在列表中我需要在我要查找的那个之前找到时间戳的索引。我尝试遍历列表，但速度很慢：

def find_item_index(arr, x):
    '''
    returns index of x in ordered list.
    If x is between two items in the list, the index of the lower one is returned.
    '''

    for index in range(len(arr)):
        if arr[index] <= x < arr[index+1]:
            return index

    raise ValueError(f'{x} not in array.')

我也试过递归地做，但那更慢：

def find_item_index_recursive(arr, x, index = 0):
    '''
    returns index of x in ordered list.
    If x is between two items in the list, the index of the lower one is returned.
    '''

    length = len(arr)

    if length == 1:
        return index

    if arr[length // 2] < x:
        return find_item_index_recursive(arr[length // 2:], x, index + length // 2)
    else:
        return find_item_index_recursive(arr[:length // 2], x, index)

    raise ValueError(f'{x} not in array.')

有更快的方法吗？

Answer 1

List 有一个内置方法，可以为您提供元素的索引。如果找不到该元素，则会引发值错误。

try:
    index = list1.index(element_to_search)
except ValueError as e:
    print('element not found')

Answer 2

我认为这应该很快：（我假设您的时间戳已排序？）

def find_item_index(arr, x):
    '''
    returns index of x in ordered list.
    If x is between two items in the list, the index of the lower one is returned.
    '''
    
    l = len(arr)
    i = l//2
    j = i//2
    
    while(j>0):
        if x<arr[i]:
            i-= j
        else:
            i+= j
        j = j//2
    return i

编辑：我刚刚检查过。与您的第一个版本相比，更长的列表更快。我预计至少 4 次，如果列表变得更长甚至 10 倍

Answer 3

对列表进行排序，并在费心对其进行任何操作之前跟踪它是否已排序

if not arr_is_sorted:     # create me somewhere!
    arr.sort()            # inplace sort
    arr_is_sorted = True  # unset if you're unsure if the array is sorted

使用排序列表，您可以 binary search to efficiently O(log n) find the insertion point - there's a convenient builtin library for this, bisect!

import bisect
insertion_point = bisect.bisect_left(arr, x)

这也使数组保持排序，因此您不需要对其重新排序，除非您对其进行了不相关的更改（理想情况下，您永远不会进行无序插入，因此它将始终排序)

下面是如何使用二分法的完整示例

>>> l = [100,50,200,99]
>>> l.sort()
>>> l
[50, 99, 100, 200]
>>> import bisect
>>> bisect.bisect_left(l, 55)
1
>>> bisect.bisect_left(l, 201)
4

您可以使用 arr.insert(position, value) 将值放入列表

>>> l
[50, 99, 100, 200]
>>> value = 55
>>> l.insert(bisect.bisect_left(l, value), value)
>>> l
[50, 55, 99, 100, 200]

您可以通过检查该位置是否已经相等来防止重复插入

>>> pos = bisect.bisect_left(l, value)
>>> if pos == len(l) or l[pos] != value:  # length check avoids IndexError
...     l.insert(pos, value)

Answer 4

Numpy searchsorted 通常涉及这些情况：

np.searchsorted([1,2,8,9], 5) # Your case
> 2

np.searchsorted([1,2,8,9], (-1, 2, 100))  #Other cases
> array([0, 1, 4])

缺失情况下的索引指的是最右边。如果这不是你的情况，可以修改它以获得靠近左侧的位置。

在 python 的列表中查找项目的最快方法是什么？

What is the fastes way to find an item in a list in python?

python

recursion

performance

search

list