Python：array [x] in O（1）复杂性 - 我应该使用Dictionary还是List？

-1

据我所知，在Python中，没有数组数据结构;大多数人经常使用的最直观的解决方案是Python列表。Python：array [x] in O（1）复杂性 - 我应该使用Dictionary还是List？

现在的问题是，Python列表是否已实施到足以使O(1)访问列表中的第10,000个项目？

什么是更好的性能？我应该用dict还是list？

2014-10-08 SomethingSomething

按键索引和字典访问的列表访问在普通情况下都是'O（1）' - 请参阅https://wiki.python.org/moin/TimeComplexity。如果您将拥有所有10,000个指数的值，则“列表”更有意义;如果它会很稀疏，字典可能会占用较少的空间。 – jonrsharpe 2014-10-08 10:40:20

不要让名字误导你。 Python的'list'类是一个动态数组，而不是链表。 – Blckknght 2014-10-08 10:44:35

相关：http://stackoverflow.com/a/25984900/674039 – wim 2014-10-08 10:44:49

list是有点用词不当：在内部，Python的list是一个数组，而不是一个链表。

作为一个数组，list通过索引提供恒定时间访问。

来源

2014-10-08 10:45:11 NPE

恕我直言，Python的数组和bytearray类型是数组（它表现出值存储在顺序; Python列出了存储引用），列表是一个比链接列表更通用的术语。例如关于这个主题的维基百科文章同意。 – 2014-10-08 10:51:22

@YannVernier：我认为我们正在分裂头发。我总是看到，当有人看到“列表”这个词时，他们会假设一个链表（这个问题就是这样一个例子）。我个人认为这不是一个不合理的假设，当然也是一个普遍的假设。 – NPE 2014-10-08 10:53:51

我做了一点基准，得出了一个结论列表工作更快。

这里是我所做的风向标：

与列表运行：198sec用户时间：

> time python /tmp/python_benchmark.py list 
finished_building 
198.816u 0.036s 3:18.97 99.9% 0+0k 0+0io 0pf+0w

与字典运行：211sec用户时间：

> time python /tmp/python_benchmark.py dict 
finished_building 
211.065u 0.044s 3:31.19 99.9% 0+0k 0+8io 0pf+0w

我打印了finished building字符串，知道约有多少。在开始运行查询之前花费数秒建立数据结构。在这两个时间里，花费的时间都少于1秒。

这是基准脚本的内容：

import sys 
from random import randrange 

NUM_OF_ITEMS = 100000 
NUM_OF_ACCESSES = 200000000 
data_structure = None 

def exit_usage(): 
    print "Usage: python_benchmark.py <list | dict>" 
    sys.exit(1) 

def access_data_structure(): 
    for i in xrange(NUM_OF_ACCESSES): 
     rnd_index = randrange(NUM_OF_ITEMS) 
     dummy_assignment = data_structure[rnd_index] 

if len(sys.argv) != 2: 
    exit_usage() 

work_type = sys.argv[1] 
if work_type != 'list' and work_type != 'dict': 
    exit_usage() 

if work_type == 'list': 
    data_structure = [] 
else: 
    data_structure = {} 

if work_type == 'list': 
    for i in xrange(NUM_OF_ITEMS): 
     data_structure.append(i) 
else: 
    for i in xrange(NUM_OF_ITEMS): 
     data_structure[i] = i 

print 'finished_building' 

access_data_structure()

来源

2014-10-08 10:43:05 SomethingSomething

Python中实际上有几种数组数据类型; list是一个对象引用的数组，tuple，bytearray和array.array是具有特定类型和范围检查的数值数组（更通用的，包括多维的，由NumPy添加），除了元组，这些都是动态的。

dict是一个散列表，它是一个更复杂的数据类型，主要用于密钥无序但可散列且查询映射多次的情况。它的密钥是无序的，可能是非数字的。

然而，标准库不具备的是链表类型。 collections.deque类型显示双向链表的快速结束访问，尽管中间插入需要内存拷贝（但不包括线性扫描）。当然也有带链接列表的插件模块，例如llist。

来源

2014-10-08 11:01:34

Python：array [x] in O（1）复杂性 - 我应该使用Dictionary还是List？

回答

相关问题