Python 用 list 来模拟循环双链表有什么好处么？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 3025 天前的主题，其中的信息可能已经有所发展或是发生改变。

比如在 lib/functools.py 的 lru_cache 中，
用
root = []
root[:] = [root,root,None,None]
root 作为循环双链表的一个点。这样做的好处是啥？
如果定义链表的 class ，感觉应该更省内存吧？

8 条回复 • 2016-08-19 11:55:01 +08:00

zonghua

2016-08-18 12:45:33 +08:00 via iPhone

实际上是作为循环队列， LRU 就是最少使用缓存算法，队列里把最少用到的排挤掉。用数组每次插入只要从新标志队头和队尾。

geeti

2016-08-18 12:52:56 +08:00

@zonghua 我知道这是 lru 的原理。

我想问的是，这里就用一个 list ，而不是定一个 class node(),然后写成链表。后者貌似更省内存

geeti

2016-08-18 12:57:20 +08:00

刷题感想。 leetcode 的 LRU 那道题，大家都是定义 linked list,但我发现 functools 里边直接使用 list ，特别简洁。但好像一个 list 比同样一个 node object 要耗内存

wodesuck

2016-08-18 14:20:43 +08:00 via Android

python 的 object 并不省内存，里面还有__dict__。。

SlipStupig

2016-08-18 16:13:09 +08:00

@wodesuck 定义一下 __slots__就好了

langyu

2016-08-18 21:15:20 +08:00

意义不大，就像用汽车来模拟自行车一样。

wizardforcel

2016-08-18 21:37:57 +08:00

离散序列结构在插入和删除上省时间，在随机访问上花费时间。

lru 并不需要随机访问，删除倒是很频繁。

hitmanx

2016-08-19 11:55:01 +08:00

有没有比较过两者的效率？可以写个测试 perf 一下。倒是很多在直觉上应该由链表完成的东西，在实际 os 内核的实现里用的都是 array ，就是因为局部性原理带来的效率提升。