Python 中的二维列表中的二进制搜索和 return 列表

Question

我是 Python 编程的新手，我已经尝试这个问题很长时间了，但我无法想出解决方案。问题是我得到了一份员工 ID 列表和员工的出生年份，我应该 return 一份在输入年份出生的员工 ID 列表。以下是列表的示例。

lst = [[2, 1987], [4, 1990], [6, 1992]...]

线性搜索需要太多时间，因为列表中有 100 万员工。因此，我认为这道题需要我们使用二分查找。我应该想出一个函数，它需要输入年份和 lst 来得到一个 returns 员工 ID 的列表。如果当年没有出生的员工，它应该 return 一个空列表。下面是一个函数的例子。

输入 > get_IDs(2012)

输出 > [102, 204, 199632, 199649]

我知道我可以为一维数组执行内置的平分函数，但我不确定如何对二维数组执行二进制搜索。请就我应该做什么提出建议，非常感谢任何建议！

Answer 1

首先，一百万个元素在现代硬件上并不算多，因此使用过滤/列表可能会非常快。让我们先设置一些测试数据：

import random, bisect, operator
random.seed(0)

years = list(range(1950, 2003))
N = 1_000_000

employees = sorted([(i, random.choice(years)) for i in range(N)],
                  key=operator.itemgetter(1))

target_year = 1980
%timeit emp_1980 = [i for i, y in employees if y == target_year]
# 1 loop, best of 3: 261 ms per loop
# can query 4 years per second

您可以将内置 bisect 与列表而不是标量一起使用，但默认情况下它会比较第一个元素 (ID)，而不是我们想要的年份。我们可以通过一些预处理来解决这个问题：

import bisect
# all (year, id) pairs sorted by year
year_id_sorted = [[y, i] for i, y in sorted(employees, key=operator.itemgetter(1))]

def ids_from_year(target_y):
  result = list()
  # make use of elementwise list ordering
  i = bisect.bisect_left(year_id_sorted, [target_y, 0])
  for y, ID in year_id_sorted[i:]:
    if y == target_y:
      result.append(ID)
    else:
      break
  return result

%timeit ids_from_year(target_year)
# 100 loops, best of 3: 11.9 ms per loop
# can query 100 years per second

这产生了 26 倍的加速。还不错，但我们已经产生了一些预处理成本并且不得不存储数据集的副本。现在让我们尝试将员工存储在以下形式的字典中："year => list of employees".

from collections import defaultdict
employee_by_year = defaultdict(list)
for i, y in employees:
  employee_by_year[y].append(i)
# 1 loop, best of 3: 361 ms per loop
# pre-processing step is only %40 more expensive than
# a single lookup in the original case.

%timeit employee_by_year[target_year]
# 10000000 loops, best of 3: 63.2 ns per loop
# can query 16 million years per second
# other factors will likely limit processing speed

我认为最佳实施取决于您计划运行查询的频率。运行它至少两次证明使用 dict 是合理的。如果您使用的是 less "granular" 指标（例如薪水），则可以证明使用二分查找是合理的。如果您需要查询多个指标，例如年和的薪水，你运行陷入内存与速度的权衡。那么，最佳策略实际上取决于您的数据分布。

Answer 2

要使二分查找起作用，您必须有一个排序列表。分类是有代价的；它代表 O(nlogn) 时间复杂度。

但是，如果您使用按年份键入的字典，这可以在没有二进制搜索的情况下完成，具有线性时间复杂度：

from collections import defaultdict 

# preprocessing
dic = defaultdict(list) # silently create an empty list when addressing a year the first time
for id, year in lst:
    dic[year].append(id)

# implementation of the required function 
def get_IDs(year):
    return dic[year]

Python 中的二维列表中的二进制搜索和 return 列表

Binary search and return list from a 2D list in Python

python

list

binary-search

multidimensional-array

python-3.x