首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python 学习手册
Python Cookbook
Python 基础教程
Python Sites
PyPI - Python Package Index
http://www.simple-is-better.com/
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
V2EX  ›  Python

Python 初学者求助

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

    不过我再给你提供一个线性时间复杂度的思路吧
    你可以参考快排中的 partition 部分 在原 list 上把比 b 小的都交换到 b 之前 比 b 大的都交换到 b 之后
    这样既不用 append 也不会比较两次 而且不需要申请额外的内存
        17
    rabbbit   47 天前
    这个跟算法没啥关系,就跑一遍就完了.算法一般不考虑是 n 还是 2n,那个 2 直接约掉了.
    楼主应该是想问 append 和列表生成式哪个效率高吧.
        18
    shyrock   47 天前
    我认为效率最高的方法是先用 sort 排序,然后 bisect 找到切分点。
        19
    angryRabbit   47 天前
    我提个思路,直接 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
        20
    zblc4c4   47 天前
    @jmc891205
    @angryRabbit
    感谢两位提供的思路,我去做一些测试
        21
    xiaoke0718   47 天前
    你怎么会看得懂?我学习这么久了怎么还是看不懂.....
        22
    xpresslink   47 天前
    建议楼主学习一下 numpy.array,什么都不改同样的事情就比 list 性能高百倍以上。
    实在不行也要用 array.array 做这些操作,比 list 也快得多。
        23
    WXG999   47 天前
    @xiaoke0718 有其他语言基础呗
        24
    cyspy   47 天前
    这里的主要问题是 python 中 list 这个数据结构的 append 性能太差,算法复杂度上没什么问题
        25
    leis1015   46 天前 via iPhone
    这么纠结性能你用啥 python 啊

    会点别的需要写性能要求高部分,python 当胶水就好了,毕竟那么多库都这样干的…
        26
    necomancer   45 天前
    numpy 版:
    a = np.array(a)
    flag = a < b
    c = a[flag]
    d = a[np.logical_not(flag)]
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2199 人在线   最高记录 5043   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 19ms · UTC 16:22 · PVG 00:22 · LAX 09:22 · JFK 12:22
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1