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

推荐学习书目

› 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

This topic created in 3586 days ago, the information mentioned may be changed or developed.

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

8 replies • 2016-08-19 11:55:01 +08:00

zonghua

Aug 18, 2016 via iPhone

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

geeti

Aug 18, 2016

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

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

geeti

Aug 18, 2016

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

wodesuck

Aug 18, 2016 via Android

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

SlipStupig

Aug 18, 2016

@wodesuck 定义一下 __slots__就好了

langyu

Aug 18, 2016

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

wizardforcel

Aug 18, 2016

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

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

hitmanx

Aug 19, 2016

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