Мне нужно отслеживать открытые и закрытые состояния при использовании определенных ресурсов. Первая структура, которую я использовал, это две open_states_list и closed_states_list, которые я добавляю и удаляю по мере обновления состояний.
- Вставка - это O (1), если мы игнорируем механизм выделения и перераспределения внутренней памяти, я думаю:
open_states_list.append(x).
- Удаление O (n):
open_states_list.remove(x).
- Поиск, как и удаление, - это O (n):
x in open_states_list.
- Получение списка, очевидно, O (1).
Вторая структура, которую я использовал, представляет собой один словарь с логическими значениями open_states = {}, где, если open_states[x] равно True, то x открыто, а если False, то оно закрыто.
- «Вставка» - это O (1), так как мы просто устанавливаем ключ и значение:
open_states[x] = True.
- «Удаление» равно O (1) по той же причине:
open_states[x] = False.
- «Поиск» - это также O (1), просто доступ к значению ключа:
open_states[x].
- Получение списка O (n):
[x for x, s in open_states.iteritems() if s].
Наша самая распространенная операция - проверка, открыт ли x или нет (поиск), поэтому второй вариант лучше. Но наша вторая наиболее распространенная операция, получение списков открытых или использованных состояний, очень близко следует за операцией поиска, более эффективна в первом варианте. Мы не можем выбрать первый вариант, потому что проверка состояния ресурса - это O (n).
Вставка тоже очень распространена. Удаление не так важно.
Какая структура данных будет наиболее эффективной для этих нужд?