Самый быстрый способ обратиться к словарю в списке по значению в нем?

Question

У меня есть список словарей в качестве ввода:

listOfOptions = [
    {"name": "a", "selected": False},
    {"name": "b", "selected": False}
]

Мне нужно изменить поле "selected" с False на True в любом из этих словарей, а затем вернуть его. Я понимаю, что для этого объекта было бы гораздо разумнее быть словарем словарей с ключами каждого словаря, являющимися полем "name", однако я не управляю этим вводом и не могу изменить схему вывода.

Это для поисковой системы, и я стремлюсь к максимально быстрым ответам, поэтому циклический просмотр нескольких списков из 100+ значений для поиска правильного словаря может занять довольно много времени.

Прямо сейчас, лучший способ сделать это - вести учет индекса каждого словаря, поэтому я могу использовать его для вызова определенного c словаря в списке. Вот так:

indexsOfOptions = {"<name>": <indexOfDictionary>, etc...}
listOfOptions[indexsOfOptions["<name>"]]["selected"] = True

Мне действительно не нравится этот подход, так как он выглядит как дешевый хак и может go очень ошибаться, если порядок списка каким-либо образом меняется.

Я что-то пропустил? Есть ли лучший способ сделать это?

Answer 1

Пробовал различные методы следующим образом.

def _next(lst, name):
  " Search through list for ditionary, and update selected "
  d = next((d for d in lst if d["name"] == name), None)
  if d:
    d['selected'] = True

def _filter(lst, name):
  " Filter list based upon name field of dictionary"
  filtered = filter(lambda d: d['name'] == name, lst)
  d = next(filtered, None)
  if d:
    d['selected'] = True

def _map(lst, name):
  " Map each dictionary to its name field, then find index  "
  mapped = list(map(lambda d: d['name'], lst))
  try:
    i = mapped.index(name)
    d = lst[i]
    d['selected'] = True
  except err:
    pass

def _for_loop(lst, name):
  " Using for loop to find dictionary "
  for d in lst:
    if d['name'] == name:
      d['selected'] = True
      break

Результат

Используя список из 2 миллионов элементов, каждый словарь

_next ( Генератор) и for_l oop провели лучшие и сопоставимые времена. Они похожи, за исключением того, что _next использует генератор (поэтому более экономно, чем for-l oop).

1. _next (Поиск в списке и обновление выбранного)

15,9 мс ± 456 мкс на л oop (среднее ± стандартное отклонение из 7 прогонов, 100 циклов в каждом)

фильтр-фильтр Список на основе поля имени словаря

35,9 мс ± 2,3 мс на л oop (среднее ± стандартное отклонение из 7 прогонов, по 10 циклов в каждом)

map - сопоставить каждый словарь с его полем имени, затем найти индекс

43,1 мс ± 3,22 мс на л oop (среднее ± стандартное отклонение из 7 прогонов, по 10 циклов в каждом) for_l oop

_for_l oop - Использует для l oop поиск словаря в списке

15,8 мс ± 500 мкс на л oop (среднее ± стандартное отклонение из 7 прогонов, 100 петель каждая)

Тестовый код

N = 2000000
names = ['next', 'filter', 'map', 'for_loop']
for i, func in enumerate([_next, _filter, _map, _for_loop]):
  # Regenerates list since a field is set each time (probably unnecessary)
  alist = [{'name': str(x), "selected": False} for x in range(N)]

  print(names[i])
  %timeit func(alist, str(N-1))  # find the last item in list

Тест в худшем случае (с идентичными ключами)

Протестируйте с 2 миллионами идентичных ключей.

В основном перепроверьте с 2 изменениями: (1) перепроверьте фильтр и функции for_l oop, поскольку их легче иметь с несколькими идентичными ключами (2) Удалите ранний разрыв, когда ключ найдено

Новые функции

def _filter(lst, name):
  " Filter list based upon name field of dictionary"
  filtered = filter(lambda d: d['name'] == name, lst)
  for d in list(filtered):
    d['selected'] = True

def _for_loop(lst, name):
  " Using for loop to find dictionary "
  for d in lst:
    if d['name'] == name:
      d['selected'] = True

Код теста

names = ['filter', 'for_loop']
for i, func in enumerate([_filter, _for_loop]):
  alist = [{'name': str(1), "selected": False} for x in range(N)]

  print(names[i])
  %timeit func(alist, str(1))  # set found items in list

Результаты

Очень похоже результаты как предыдущий тест.

filter
36 ms ± 3.36 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
for_loop
15.8 ms ± 780 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Answer 2

Прямо сейчас, лучший способ сделать это - вести учет индекса каждого словаря ... может go очень неправильно, если порядок списка каким-то образом меняется .

Я думаю, это означает, что ключи будут обычно иметь тот же индекс, что и в предыдущем запросе для того же ключа, но индекс для данного ключа не гарантируется быть постоянным. В этом случае вы можете кэшировать последний индекс, в котором каждый ключ был обнаружен, но проверить, действителен ли кэшированный индекс при следующем запросе ключа. Если это так, то вам не нужно искать; если это не так, вы можете выполнить поиск снова.

Если кэшированный индекс больше не действителен, но новый индекс, вероятно, будет близок к кэшированному индексу, вы можете сделать «двусторонний» линейный поиск, начиная с кэшированного индекса. По сути, инициализируйте i = cached_index - 1 и j = cached_index + 1, затем выполните поиск с i уменьшением и j увеличением.

Если ключи расположены в списке в алфавитном порядке (как в вашем примере), тогда вы может выполнять бинарный поиск вместо линейного поиска.

Все это говорит о том, что стоит сравнить эти решения, потому что самый быстрый способ сделать что-то в Python - это часто позволить встроенным функциям / методам которые реализованы в C, выполняют большую часть работы, насколько это возможно, даже если они теоретически медленнее в соответствии с большими обозначениями O.

Answer 3

здесь есть O (n) решение с временной сложностью, и я не думаю, что оно может быть каким-либо другим решением лучше с точки зрения временной сложности, потому что вам приходится перебирать весь список:

selected_name = 'a' # just for the example the value is a
for d in listOfOptions:
    if d['name'] == selected_name:
        d['selected'] = True

print(listOfOptions)

output :

[{'name': 'a', 'selected': True}, {'name': 'b', 'selected': False}]

Answer 4

listOfOptions = [
    {"name": "a", "selected": False},
    {"name": "b", "selected": False}
]

def change(x):
     [i.update({'selected':True}) for i in listOfOptions if i['name'] is x]

Генератор был бы самым быстрым способом, о котором я могу думать. Я добавил его в метод, который принимает строковое значение для обновления чего-либо одним из ваших ключей.