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

python 的 list 效率底下?

  •  
  •   janstk · 2014-11-11 19:49:55 +08:00 · 8006 次点击
    这是一个创建于 3649 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

    Design a stack that supports push, pop, top, and retrievingthe minimum element in constant time.

    • push(x) – Push element x onto stack.
    • pop() – Removes the element on top of the stack.
    • top() – Get the top element.
    • getMin() – Retrieve the minimum element in the stack.

    答案:

    class MinStack:
        def __init__(self):
            self.L=[]
        def pop(self):
            return self.L.pop()
        def push(self,x):
            self.L.append(x)
        def top(self):
            return self.L[-1]
        def getMin(self):
            tmpL = self.L[:]
            tmpL.sort()
            return tmpL[0]
    

    每次提示答案都超时…表吐槽,表示刚学python

    43 条回复    2014-11-12 17:01:00 +08:00
    Altynai
        1
    Altynai  
       2014-11-11 20:13:04 +08:00   ❤️ 1
    你getMin复杂度都O(nlogn)了,题目说了**constant time**
    takato
        2
    takato  
       2014-11-11 20:41:20 +08:00 via iPhone   ❤️ 1
    常数级复杂度,只要额外维持一个最小值就可以了
    bcxx
        3
    bcxx  
       2014-11-11 21:07:48 +08:00
    @takato 不是一个,是最小值的历史记录
    wheatcuican
        4
    wheatcuican  
       2014-11-11 21:21:13 +08:00
    大力哥好!
    wzzyj8
        5
    wzzyj8  
       2014-11-11 22:58:35 +08:00
    getmin用list改用tuple,至少快10倍。


    bcxx
        6
    bcxx  
       2014-11-11 23:47:32 +08:00
    @wzzyj8 看题……不是 list 本身的问题- -
    staticor
        7
    staticor  
       2014-11-12 00:20:04 +08:00
    另外生成一个最小栈, push时比一下.
    ivanlw
        8
    ivanlw  
       2014-11-12 00:55:48 +08:00   ❤️ 1
    好经典的蒂姆
    rwalle
        9
    rwalle  
       2014-11-12 07:33:40 +08:00 via Android
    目测楼主以前没学过编程?经验太少 getMin这么简单的事情用sort就是杀鸡用牛刀
    ryd994
        10
    ryd994  
       2014-11-12 07:59:21 +08:00 via Android
    每次插入都和当前最小比较一下,小于就换
    每次pop就要重新sort了
    ryd994
        11
    ryd994  
       2014-11-12 07:59:46 +08:00 via Android
    pop可能要重新sort
    openroc
        12
    openroc  
       2014-11-12 08:27:18 +08:00
    gt11799
        13
    gt11799  
       2014-11-12 08:37:29 +08:00
    题主是只想实现一个可以取最小值的栈?
    heapq是一个最小堆,内部应该是一个二叉树,父节点始终小于子节点,因此顶点是最小的数。每当取出一个值,则两个子节点对比,小的上升。(实际上不是如此,不过这样容易理解)
    可以先使用heapq把这个类实现了,然后试试看,自己能不能写一个最小堆?
    msg7086
        14
    msg7086  
       2014-11-12 08:48:59 +08:00   ❤️ 1
    @gt11799
    我看题目里的要求,应该不是说要做小顶堆吧。应该是双stack,一个维护数据,另一个维护最小值。
    fkue0487
        15
    fkue0487  
       2014-11-12 08:52:05 +08:00
    不是有个min函数么.
    xcv58
        16
    xcv58  
       2014-11-12 08:57:30 +08:00 via Smartisan T1
    人家要 O(1) 你给弄个 O(n log n) Python 躺枪啊。
    rrfeng
        17
    rrfeng  
       2014-11-12 09:26:15 +08:00
    维护『一个』最小值的话 pop 了咋办?
    zhchbin
        18
    zhchbin  
       2014-11-12 09:28:59 +08:00
    ```python
    class MinStack:
    def __init__(self):
    self.data = []
    self.min_data = []

    def pop(self):
    if not self.data:
    return None

    self.min_data.pop()
    return self.data.pop()

    def push(self, x):
    self.data.append(x)
    if not self.min_data:
    self.min_data.append(x)
    else:
    self.min_data.append(min(self.min_data[-1], x))

    def top(self):
    return None if not self.data else self.data[-1]

    def getMin(self):
    return None if not self.data else self.min_data[-1]

    if __name__ == '__main__':
    min_stack = MinStack()
    data = [5, 2, 4, 3, -1, 0]
    for val in data:
    min_stack.push(val)
    print min_stack.getMin()

    min_stack.pop()
    print min_stack.getMin()
    min_stack.pop()
    print min_stack.getMin()
    ```

    经典的面试题目,刚学python,不知道写对了木有。
    zhchbin
        19
    zhchbin  
       2014-11-12 09:30:35 +08:00
    囧。。还以为支持Mardown直接回复了。。自行缩进吧。
    frankzeng
        20
    frankzeng  
       2014-11-12 09:35:24 +08:00
    return min(self.L)不就行了吗,干嘛自己实现?
    zhchbin
        21
    zhchbin  
       2014-11-12 09:42:49 +08:00
    @frankzeng min(self.L) 的复杂度应该是O(n)。
    ryanking8215
        22
    ryanking8215  
       2014-11-12 09:58:23 +08:00
    @zhchbin 好像不对吧,pop的时候,你怎么知道当前pop的那个值,在min_data里也需要pop掉,也即最大的那个?
    self.min_data.append(min(self.min_data[-1], x))
    这个明显不是O(1),怎么保证push是O(1)呢?
    scorpius
        23
    scorpius  
       2014-11-12 10:19:02 +08:00
    @openroc 感觉这个正解
    happywowwow
        24
    happywowwow  
       2014-11-12 10:38:16 +08:00
    o(1)的如何实现? 每次push的时候维护一个最小值?但请问pop的时候不是需要查询是否这个维护的值被pop了么?又需要重新找出最小的

    感觉得 双栈 或者 一栈一最小堆
    ipconfiger
        25
    ipconfiger  
       2014-11-12 10:44:03 +08:00
    leetcode 里用Python写的话一个栈就Memory溢出了,2个还不爆浆?
    janstk
        26
    janstk  
    OP
       2014-11-12 10:44:35 +08:00 via iPhone
    双栈的话会超出内存限制。无语了
    frankzeng
        27
    frankzeng  
       2014-11-12 11:49:04 +08:00
    @openroc https://gist.github.com/openroc/196642a254a542e4e80f.js 这一个请求是不是你弄的?这一串东西把整个贴拉到奇慢无比,这算不算是v2ex的bug呢?
    openroc
        28
    openroc  
       2014-11-12 12:46:25 +08:00
    gist被墙了。呵呵
    openroc
        29
    openroc  
       2014-11-12 12:48:09 +08:00
    @frankzeng 请科学上网。:)
    takato
        30
    takato  
       2014-11-12 12:49:40 +08:00
    @bcxx 感谢- -。笔误- -。。
    yakiang
        31
    yakiang  
       2014-11-12 13:09:34 +08:00
    我能说这是上个月珍爱网校招数据岗位的一道笔试题吗
    ChanneW
        32
    ChanneW  
       2014-11-12 13:20:03 +08:00
    我的第一想法是, 拖慢 pop push 速度,每次操作都更新最小值. 反而获取最小值只是把值返回.
    这样应该能过机器测试了,懒人的程序只做到刚好能用.
    caiych
        33
    caiych  
       2014-11-12 13:47:05 +08:00
    跟python和list都没什么关系……
    LZ需要学习一下基本的数据结构…这东西叫堆或者优先队列什么的…
    ---
    Python自带的优先队列居然没有top或者front这样的方法…只能拿出来看……
    bcxx
        34
    bcxx  
       2014-11-12 14:09:15 +08:00
    https://github.com/bcho/homework/blob/master/oj/leetcode/min_stack.py 的确是用两个 list 就可以过啊……


    @caiych 用优先队列也不是 O(1) 的…… 另外用 https://docs.python.org/2/library/heapq.html#heapq.nsmallest 这个就可以获取 top 和 front 了吧……
    zhchbin
        35
    zhchbin  
       2014-11-12 14:13:32 +08:00
    @ipconfiger @janstk 双栈可以过啊。。在上面的版本做空间上的优化。

    @ryanking8215 其实估计是排版的问题导致你没看清楚代码逻辑,懒得解释哈。
    hellove1985
        36
    hellove1985  
       2014-11-12 14:28:50 +08:00
    caiych
        37
    caiych  
       2014-11-12 14:36:00 +08:00
    @bcxx
    重新读了一遍题,发现想当然了。。。
    takato
        38
    takato  
       2014-11-12 15:30:28 +08:00
    @gt11799 堆的插入操作是O(logn)的
    takato
        39
    takato  
       2014-11-12 15:35:23 +08:00
    双栈可以的原因是因为栈不能pop任意位置,而只能pop顶,所以只需要发现目前值小于等于当前最小值的时候,push一个最小值的栈则可,否则就不push。
    pop的时候先检验最小堆栈顶是不是这个元素,是则pop,否则不变
    ryanking8215
        40
    ryanking8215  
       2014-11-12 15:46:11 +08:00
    @yakiang 这是leetcode上的题,主要是要求各操作都是O(1)的时间复杂度
    ryanking8215
        41
    ryanking8215  
       2014-11-12 16:00:56 +08:00
    @zhchbin 确实看错了,:)
    dingyaguang117
        42
    dingyaguang117  
       2014-11-12 16:52:41 +08:00
    pair的单栈,哈哈 就是比较浪费空间,有些最小值不必要存~
    push:
    -> push tuple(num, min)

    pop:
    -> pop tuple(num, min)
    janstk
        43
    janstk  
    OP
       2014-11-12 17:01:00 +08:00
    好吧终于过了,感谢上面回复的各位。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1767 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 16:38 · PVG 00:38 · LAX 08:38 · JFK 11:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.