用于插入、删除和搜索的高效数据结构

2021-11-29 22:40:18 发布

您现在位置:Python中文网/ 问答频道 /正文

在使用某些资源时,我需要跟踪打开和关闭状态。我使用的第一个结构是两个open_states_listclosed_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,那么它是关闭的。你知道吗

  • “Inserting”是O(1),因为我们只是设置一个键和一个值:open_states[x] = True。你知道吗
  • “Deleting”是O(1),原因相同:open_states[x] = False。你知道吗
  • “search”也是O(1),只是访问键的值:open_states[x]。你知道吗
  • 获取列表是O(n):[x for x, s in open_states.iteritems() if s]。你知道吗

我们最常见的操作是检查x是否打开(搜索),因此第二个选项更好。但是我们第二个最常见的操作,获取打开或使用状态的列表,紧跟搜索操作,在第一个选项中效率更高。但是我们不能选择第一个选项,因为检查资源的状态是O(n)。你知道吗

插入也很常见。移除没有必要。你知道吗

满足这些需求的最有效的数据结构是什么?你知道吗