Бинарный поиск и возврат списка из 2D списка в Python

Question

Я новичок в Python программировании, и я долго пытался ответить на этот вопрос, но не смог найти решение. Вопрос в том, что мне дали список идентификаторов сотрудников и год рождения сотрудников, и я должен вернуть список идентификаторов сотрудников, которые были рождены в год ввода. Ниже приведен пример списка.

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

Линейный поиск требует слишком много времени, поскольку в списке 1 миллион сотрудников. Поэтому я думаю, что вопрос требует от нас использовать бинарный поиск. Я должен придумать функцию, которая берет входной год, и сначала придумать список, который возвращает идентификаторы сотрудников. Если в этом году не появилось ни одного сотрудника, следует вернуть пустой список. Ниже приведен пример функции.

input> get_IDs(2012)

output> [102, 204, 199632, 199649]

Я понимаю, что есть встроенная функция деления на части, которую я смог сделать для 1D-массивов, но я не уверен, как выполнить бинарный поиск для 2D-массивов. Пожалуйста, совет, что я должен делать, и любые предложения в значительной степени приветствуются!

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 со списками вместо скаляров, но он будет сравнивать первые элементы (идентификаторы) по умолчанию, а не годы, которые нам нужны , Мы можем обойти это с некоторой предварительной обработкой:

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 employee».

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. Если бы вы использовали менее «гранулярный» показатель c (например, зарплата), вы могли бы оправдать использование бинарного поиска. Если вам нужно запросить несколько показателей, например, зарплата за год и , вы столкнетесь с компромиссом между памятью и скоростью. Тогда лучшая стратегия действительно зависит от вашего распределения данных.

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]