Python 初学者求助

[zblc4c4]

问题：整数数列列表 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]

使用 numpy.where()函数试下效果。 注：我也是初学者，不过刚好看到这个，感觉可能用得上。

[stebest]

我有个问题，为啥不直接 c=random.shuffle([i for i in range(5000)]), d=random.shuffle([i for i in range(5000,10000)])
如果是乱序的话，排个序不是更好分了。

[jmc891205]

你说的两种方法都可以 都是线性的时间复杂度
没必要纠结 append 或两次比较什么的

[airborne007]

@stebest random.shuffle 返回的是 None

[airborne007]

一次循环和先排序再切片，效率都差不多，append 本身也不慢，都是线性复杂度，没必要太纠结。

[zblc4c4]

@jmc891205 这个函数被调用十万百万次级时，区别就体现了，所以能优化多少是多少，1%也是好的

[stebest]

@airborne007 没把 c=写到括号里，2333。不过 O(n)时间内，已经是比较好的结果了。

[zblc4c4]

@stebest 我只是测试用，重点是实现功能

[CosimoZi]

你想什么呢,组成新列表这个动作只要有,就是 O(n)的复杂度.

[myyou]

如果数组存的都是存储的都是相同类型可以考虑使用 array 的 append 方法： https://docs.python.org/3.6/library/array.html

[jmc891205]

@zblc4c4 你应该学习一下为什么大家评价一个算法的快慢是用时间复杂度而不考虑常数

[zblc4c4]

@CosimoZi 2n 和 n 差距也很大啊，算法没有可改进的地方，编程逻辑是有优化空间的

[zblc4c4]

@jmc891205 但我希望改进的不是算法，而是算法的实现的优化

[zblc4c4]

@jmc891205 这两种思路都是有不完美之处的，这个应该是毋庸置疑的，我追求的不仅仅是这个功能的实现，而是借鉴别人的思路，拓宽一下思维

[hahastudio]

那你可以试试 itertools.groupby

[jmc891205]

@zblc4c4 在工程上 你就是在做无用功。

不过我再给你提供一个线性时间复杂度的思路吧
你可以参考快排中的 partition 部分 在原 list 上把比 b 小的都交换到 b 之前 比 b 大的都交换到 b 之后
这样既不用 append 也不会比较两次 而且不需要申请额外的内存

[rabbbit]

这个跟算法没啥关系,就跑一遍就完了.算法一般不考虑是 n 还是 2n,那个 2 直接约掉了.
楼主应该是想问 append 和列表生成式哪个效率高吧.

[shyrock]

我认为效率最高的方法是先用 sort 排序，然后 bisect 找到切分点。

[angryRabbit]

我提个思路，直接 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]

@jmc891205
@angryRabbit
感谢两位提供的思路，我去做一些测试

[xiaoke0718]

你怎么会看得懂?我学习这么久了怎么还是看不懂.....

[xpresslink]

建议楼主学习一下 numpy.array，什么都不改同样的事情就比 list 性能高百倍以上。
实在不行也要用 array.array 做这些操作，比 list 也快得多。

[WXG999]

@xiaoke0718 有其他语言基础呗

[cyspy]

这里的主要问题是 python 中 list 这个数据结构的 append 性能太差，算法复杂度上没什么问题

[leis1015]

这么纠结性能你用啥 python 啊

会点别的需要写性能要求高部分，python 当胶水就好了，毕竟那么多库都这样干的…

[necomancer]

numpy 版：
a = np.array(a)
flag = a < b
c = a[flag]
d = a[np.logical_not(flag)]