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

Python 初学者求助

  •  
  •   zblc4c4 · 2019-03-06 17:26:33 +08:00 · 3296 次点击
    这是一个创建于 2078 天前的主题,其中的信息可能已经有所发展或是发生改变。
    问题:整数数列列表 a,例如 random.shuffle([i for i in range(10000)])
    整数 b,例如 5000
    a 中所有小于 b 的元素组成新列表 c,a 中剩余元素组成新列表 d

    目标条件:效率最高,计算时间优先,不考虑内存占用

    我能想到的两种思路:
    1 )使用 for 循环对每个元素判断,append 到对应列表
    2 ) c = [x for x in a if x < b] d = [x for x in a if x >= b]
    1 中 append 函数严重影响效率,2 中每次比较大小用了 2 遍,因为是新手,经验不足,想不到两全其美的方法,希望能得到大佬指教
    dswill
        1
    dswill  
       2019-03-06 17:36:04 +08:00
    使用 numpy.where()函数试下效果。 注:我也是初学者,不过刚好看到这个,感觉可能用得上。
    stebest
        2
    stebest  
       2019-03-06 17:37:26 +08:00
    我有个问题,为啥不直接 c=random.shuffle([i for i in range(5000)]), d=random.shuffle([i for i in range(5000,10000)])
    如果是乱序的话,排个序不是更好分了。
    jmc891205
        3
    jmc891205  
       2019-03-06 17:39:02 +08:00 via iPhone
    你说的两种方法都可以 都是线性的时间复杂度
    没必要纠结 append 或两次比较什么的
    airborne007
        4
    airborne007  
       2019-03-06 17:44:29 +08:00
    @stebest random.shuffle 返回的是 None
    airborne007
        5
    airborne007  
       2019-03-06 17:45:33 +08:00
    一次循环和先排序再切片,效率都差不多,append 本身也不慢,都是线性复杂度,没必要太纠结。
    zblc4c4
        6
    zblc4c4  
    OP
       2019-03-06 17:48:08 +08:00
    @jmc891205 这个函数被调用十万百万次级时,区别就体现了,所以能优化多少是多少,1%也是好的
    stebest
        7
    stebest  
       2019-03-06 17:49:05 +08:00
    @airborne007 没把 c=写到括号里,2333。不过 O(n)时间内,已经是比较好的结果了。
    zblc4c4
        8
    zblc4c4  
    OP
       2019-03-06 17:51:48 +08:00
    @stebest 我只是测试用,重点是实现功能
    CosimoZi
        9
    CosimoZi  
       2019-03-06 17:55:54 +08:00
    你想什么呢,组成新列表这个动作只要有,就是 O(n)的复杂度.
    myyou
        10
    myyou  
       2019-03-06 17:57:30 +08:00
    如果数组存的都是存储的都是相同类型可以考虑使用 array 的 append 方法: https://docs.python.org/3.6/library/array.html
    jmc891205
        11
    jmc891205  
       2019-03-06 17:58:08 +08:00 via iPhone
    @zblc4c4 你应该学习一下为什么大家评价一个算法的快慢是用时间复杂度而不考虑常数
    zblc4c4
        12
    zblc4c4  
    OP
       2019-03-06 18:01:08 +08:00
    @CosimoZi 2n 和 n 差距也很大啊,算法没有可改进的地方,编程逻辑是有优化空间的
    zblc4c4
        13
    zblc4c4  
    OP
       2019-03-06 18:02:17 +08:00
    @jmc891205 但我希望改进的不是算法,而是算法的实现的优化
    zblc4c4
        14
    zblc4c4  
    OP
       2019-03-06 18:05:16 +08:00
    @jmc891205 这两种思路都是有不完美之处的,这个应该是毋庸置疑的,我追求的不仅仅是这个功能的实现,而是借鉴别人的思路,拓宽一下思维
    hahastudio
        15
    hahastudio  
       2019-03-06 18:08:17 +08:00
    那你可以试试 itertools.groupby
    jmc891205
        16
    jmc891205  
       2019-03-06 18:10:02 +08:00 via iPhone
    @zblc4c4 在工程上 你就是在做无用功。

    不过我再给你提供一个线性时间复杂度的思路吧
    你可以参考快排中的 partition 部分 在原 list 上把比 b 小的都交换到 b 之前 比 b 大的都交换到 b 之后
    这样既不用 append 也不会比较两次 而且不需要申请额外的内存
    rabbbit
        17
    rabbbit  
       2019-03-06 18:12:41 +08:00
    这个跟算法没啥关系,就跑一遍就完了.算法一般不考虑是 n 还是 2n,那个 2 直接约掉了.
    楼主应该是想问 append 和列表生成式哪个效率高吧.
    shyrock
        18
    shyrock  
       2019-03-06 18:18:54 +08:00
    我认为效率最高的方法是先用 sort 排序,然后 bisect 找到切分点。
    angryRabbit
        19
    angryRabbit  
       2019-03-06 18:30:00 +08:00
    我提个思路,直接 copy、遍历、替换为 None

    a=list(range(0,5000))
    b=2000
    c=a.copy()
    d=a

    for i,elem in enumerate(0,c):
    if i>b:
    c[i]=None
    else:
    d[i]=None
    zblc4c4
        20
    zblc4c4  
    OP
       2019-03-06 19:00:54 +08:00
    @jmc891205
    @angryRabbit
    感谢两位提供的思路,我去做一些测试
    xiaoke0718
        21
    xiaoke0718  
       2019-03-06 19:23:43 +08:00
    你怎么会看得懂?我学习这么久了怎么还是看不懂.....
    xpresslink
        22
    xpresslink  
       2019-03-06 22:05:00 +08:00
    建议楼主学习一下 numpy.array,什么都不改同样的事情就比 list 性能高百倍以上。
    实在不行也要用 array.array 做这些操作,比 list 也快得多。
    WXG999
        23
    WXG999  
       2019-03-06 22:43:11 +08:00
    @xiaoke0718 有其他语言基础呗
    cyspy
        24
    cyspy  
       2019-03-07 00:20:39 +08:00
    这里的主要问题是 python 中 list 这个数据结构的 append 性能太差,算法复杂度上没什么问题
    leis1015
        25
    leis1015  
       2019-03-07 07:42:51 +08:00 via iPhone
    这么纠结性能你用啥 python 啊

    会点别的需要写性能要求高部分,python 当胶水就好了,毕竟那么多库都这样干的…
    necomancer
        26
    necomancer  
       2019-03-08 12:03:38 +08:00
    numpy 版:
    a = np.array(a)
    flag = a < b
    c = a[flag]
    d = a[np.logical_not(flag)]
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1084 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 22:32 · PVG 06:32 · LAX 14:32 · JFK 17:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.