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
geeti
V2EX  ›  Python

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

  •  
  •   geeti · 2016-08-18 12:40:41 +08:00 · 3007 次点击
    这是一个创建于 2998 天前的主题,其中的信息可能已经有所发展或是发生改变。
    比如在 lib/functools.py 的 lru_cache 中,

    root = []
    root[:] = [root,root,None,None]
    root 作为循环双链表的一个点。这样做的好处是啥?
    如果定义链表的 class ,感觉应该更省内存吧?
    8 条回复    2016-08-19 11:55:01 +08:00
    zonghua
        1
    zonghua  
       2016-08-18 12:45:33 +08:00 via iPhone
    实际上是作为循环队列, LRU 就是最少使用缓存算法,队列里把最少用到的排挤掉。用数组每次插入只要从新标志队头和队尾。
    geeti
        2
    geeti  
    OP
       2016-08-18 12:52:56 +08:00
    @zonghua 我知道这是 lru 的原理。

    我想问的是,这里就用一个 list ,而不是定一个 class node(),然后写成链表。后者貌似更省内存
    geeti
        3
    geeti  
    OP
       2016-08-18 12:57:20 +08:00
    刷题感想。 leetcode 的 LRU 那道题,大家都是定义 linked list,但我发现 functools 里边直接使用 list ,特别简洁。但好像一个 list 比同样一个 node object 要耗内存
    wodesuck
        4
    wodesuck  
       2016-08-18 14:20:43 +08:00 via Android
    python 的 object 并不省内存,里面还有__dict__。。
    SlipStupig
        5
    SlipStupig  
       2016-08-18 16:13:09 +08:00
    @wodesuck 定义一下 __slots__就好了
    langyu
        6
    langyu  
       2016-08-18 21:15:20 +08:00
    意义不大, 就像用汽车来模拟自行车一样。
    wizardforcel
        7
    wizardforcel  
       2016-08-18 21:37:57 +08:00
    离散序列结构在插入和删除上省时间,在随机访问上花费时间。

    lru 并不需要随机访问,删除倒是很频繁。
    hitmanx
        8
    hitmanx  
       2016-08-19 11:55:01 +08:00   ❤️ 1
    有没有比较过两者的效率?可以写个测试 perf 一下。倒是很多在直觉上应该由链表完成的东西,在实际 os 内核的实现里用的都是 array ,就是因为局部性原理带来的效率提升。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1211 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 18ms · UTC 18:28 · PVG 02:28 · LAX 11:28 · JFK 14:28
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.