在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.')

有没有更快的方法？

- Tim Berti

---

递归方法较慢，因为通过切片会产生大量副本。将起始/结束索引与原始列表一起传递，它应该会更快。 - Barmar

排序并使用bisect！ - ti7

肯定排序会比一次循环列表慢。 - Pranav Hosangadi

这个回答解决了你的问题吗？在列表中查找项目索引的最快方法？ - youssef jallouli

@PranavHosangadi 当然可以，但他们需要“反复”查找某些内容，并且还要暗示列表已排序（否则索引有何意义？） - ti7

请明确，即使该值实际上不在列表中，您也应该得到一个答案？您将如何处理此索引值？时间戳是否按顺序排列？您试图解决的问题究竟是什么？ - Karl Knechtel

Answer 1

在开始对列表进行任何操作之前，先将其排序并跟踪其是否已经排序好。

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

使用有序列表，您可以进行二分查找来高效地O(log n)查找插入点 - 这里有一个方便的内置库，bisect！

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

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

以下是如何使用bisect的完整示例

>>> 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)

- ti7

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倍。

- eli44

Answer 3

列表有一个内置方法，可以给出元素的索引。如果未找到该元素，则会引发值错误。

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

- Nk03

---

这对于确切的项目在数组中的情况有所帮助，但如果我要查找的项目位于数组的两个条目之间，则无法解决问题。 - Tim Berti

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])

在缺失情况下，索引指向右侧最近位置。如果这不适用于您的情况，可以进行修改以获取左侧最近位置。

- Glauco