python – 将列表拆分成多个列表以获得加速?
假设我的列表大约有1,000,000个条目.要获得一个项目,时间将是O(500,000),这对我来说似乎很长.
将列表拆分为多个列表时会发生什么?我们来看一个例子: splitted_list = [ [list with 100,000 entries],[list with 100,000 entries] ] 获得一件物品的时间是O(5)O(50,000)= O(50,005)并且加速率大约为1000%! 当拆分原始列表关于它的根,在这种情况下为1000时,这将给我们一个包含1000个列表的列表,其中包含另外1000个条目. splitted_list = [ [list with 1000 entries],[list with 1000 entries],... ] 现在看一下获取项目的时间: O(500) + O(500) = O(1000) O(1000) < O(50,005) < O(500,000) 这是最佳加速约1000倍!我认为难以置信,所以我的问题: 这是否也适用于实践,或者这只是理论吗? 解决方法
你的问题的答案是你正在考虑
linked lists,其中每个元素都有一个指向下一个元素的指针.它们具有O(n)索引,因为获取第n个元素的唯一方法是从头开始遍历列表.
您的想法与各种数据结构有关,其中最接近的可能是skip list.这是一个基于链表的数据结构,但节点的“高速公路”可以跳过列表中的多个元素.优点是你可以在高速公路上跑到达列表的中间位置,然后在你需要单个元素精度时下拉到“较慢的通道”,给出O(log n)索引效率 – 与当然,缺点是执行其他链表操作(如随机插入)更复杂(也更慢). 然而,Python列表是在动态增长arrays下实现的.它们具有O(1)索引,因为要获得第三个元素,您可以简单地将三个(单位)添加到第一个元素的内存地址,而无需遍历其间的所有元素. 您可能对Wikipedia article on data structures感兴趣. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |