推荐学习书目
› 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
这是一个创建于 2089 天前的主题，其中的信息可能已经有所发展或是发生改变。
问题：整数数列列表 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 遍，因为是新手，经验不足，想不到两全其美的方法，希望能得到大佬指教
整数 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 遍，因为是新手，经验不足，想不到两全其美的方法，希望能得到大佬指教
 |
1
dswill 2019-03-06 17:36:04 +08:00
使用 numpy.where()函数试下效果。 注：我也是初学者，不过刚好看到这个，感觉可能用得上。
|
 |
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)])
如果是乱序的话，排个序不是更好分了。 |
 |
3
jmc891205 2019-03-06 17:39:02 +08:00 via iPhone
你说的两种方法都可以 都是线性的时间复杂度
没必要纠结 append 或两次比较什么的 |
 |
4
airborne007 2019-03-06 17:44:29 +08:00
@stebest random.shuffle 返回的是 None
|
|
5
airborne007 2019-03-06 17:45:33 +08:00
一次循环和先排序再切片，效率都差不多，append 本身也不慢，都是线性复杂度，没必要太纠结。
|
|
7
stebest 2019-03-06 17:49:05 +08:00
@airborne007 没把 c=写到括号里，2333。不过 O(n)时间内，已经是比较好的结果了。
|
 |
9
CosimoZi 2019-03-06 17:55:54 +08:00
你想什么呢,组成新列表这个动作只要有,就是 O(n)的复杂度.
|
 |
10
myyou 2019-03-06 17:57:30 +08:00
如果数组存的都是存储的都是相同类型可以考虑使用 array 的 append 方法： https://docs.python.org/3.6/library/array.html
|
 |
14
zblc4c4 OP @jmc891205 这两种思路都是有不完美之处的，这个应该是毋庸置疑的，我追求的不仅仅是这个功能的实现，而是借鉴别人的思路，拓宽一下思维
|
 |
15
hahastudio 2019-03-06 18:08:17 +08:00
那你可以试试 itertools.groupby
|
|
16
jmc891205 2019-03-06 18:10:02 +08:00 via iPhone
@zblc4c4 在工程上 你就是在做无用功。
不过我再给你提供一个线性时间复杂度的思路吧 你可以参考快排中的 partition 部分 在原 list 上把比 b 小的都交换到 b 之前 比 b 大的都交换到 b 之后 这样既不用 append 也不会比较两次 而且不需要申请额外的内存 |
 |
17
rabbbit 2019-03-06 18:12:41 +08:00
这个跟算法没啥关系,就跑一遍就完了.算法一般不考虑是 n 还是 2n,那个 2 直接约掉了.
楼主应该是想问 append 和列表生成式哪个效率高吧. |
 |
18
shyrock 2019-03-06 18:18:54 +08:00
我认为效率最高的方法是先用 sort 排序，然后 bisect 找到切分点。
|
 |
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 |
|
20
zblc4c4 OP |
 |
21
xiaoke0718 2019-03-06 19:23:43 +08:00
你怎么会看得懂?我学习这么久了怎么还是看不懂.....
|
 |
22
xpresslink 2019-03-06 22:05:00 +08:00
建议楼主学习一下 numpy.array，什么都不改同样的事情就比 list 性能高百倍以上。
实在不行也要用 array.array 做这些操作，比 list 也快得多。 |
 |
23
WXG999 2019-03-06 22:43:11 +08:00
@xiaoke0718 有其他语言基础呗
|
 |
24
cyspy 2019-03-07 00:20:39 +08:00
这里的主要问题是 python 中 list 这个数据结构的 append 性能太差，算法复杂度上没什么问题
|
 |
25
leis1015 2019-03-07 07:42:51 +08:00 via iPhone
这么纠结性能你用啥 python 啊
会点别的需要写性能要求高部分，python 当胶水就好了，毕竟那么多库都这样干的… |
 |
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)] |
Select Language