Re: [问题]不用for循环寻找阵列中只出现过一次的资料

楼主: ccwang002 (亮)   2014-05-12 03:22:31
※ 引述《sariel0322 (sariel)》之铭言:
: 我想要请问一下,如果我有一串数字
: A = [9,5,5,4,7,6,4,1,2,0,10,9,7,....]
: 要如何找出这列资料中只出现一次的数字,但不用到for循环的方法
(冏冏,我看成有出现就好…… 明天再补了 > <)
完整档案见 IPython Notebook
http://nbviewer.ipython.org/gist/ccwang002/bc1b047d0eca2c8f8bdd
这真的要快的话,就不应该自己写 for loop,所以我想得到最快的方法就是用 set(A)
但有没有更快的方式呢?其中一个可能是用 Cython, cffi 自己刻一个,
但 numpy.unique() 不知道快不快? 直觉上以为是会快很多的,所以来个实测。
# Test by IPython on Python 3.4
import numpy as np
LEN = 10**7 # 约需要总共 200MB 的内存
# 整数
A = np.random.randint(0, 100, LEN) # numpy 阵列 (ndarray)
A_list = A.tolist() # 一般的 list
%timeit -n 5 np.unique(A) # numpy 解法
%timeit -n 5 set(A_list) # set() 解法
%timeit set(A) # 混用,对 numpy 阵列用 set()
# 448ms, 232ms, 1.67s
# 5.18s, 2.31s, - s if LEN = 10**8
结果 set() 跑得比 np.unique() 还快,蛮惊讶的 > < 资料量调大仍旧相同的趋势。
混用很可怕,这小测试暗示 ndarray 用内建函式的时候,很可能会做非常多转换,
很容易拖慢速度。而内建的指令其实速度飞快。
但这样 numpy 哪里有优势,是否该洗洗睡?我猜它在浮点数表现就会好很多,
浮点数找相同的数值有点怪,但总之要帮 numpy 平反也不管这么多了xd
# 浮点数版本,只会有 0.0, 0.1, 0.2, ...
A = np.random.randint(0, 100, LEN) / 10
A_list = A.tolist()
%timeit -n 5 np.unique(A)
%timeit -n 5 set(A_list)
%timeit -n 5 set(A)
# 698ms, 1.55s, 2.23s
果然 numpy 的效率就好很多。
恩…总之蛮好玩的。
PS Py 3.4 中多了 tracemalloc module 可以追踪程式执行间内存用量
https://docs.python.org/3/library/tracemalloc.html
看 Python 物件内存用量(?) 可用 sys.getsizeof(obj)
看 Numpy .............. 可用 ndarray_obj.nbytes
作者: timTan (用口头禅区分年记)   2014-05-12 11:09:00
作者: apua (Apua)   2014-05-12 11:22:00
关于内存用量, 笔记中有些地方我不懂为什么用 numpy 做出 A 之后, 内存用量还不大; 做出 A.list之后, A.nbytes 就随之暴增了? A.nbytes 是 A 物件的大小对吗所以可以理解成 A (numpy obj) 会在被操作时多做些事情?
作者: ya790206 (残云夺月)   2014-05-12 21:30:00
python set 的实作是用 C 写的,使用 hash 算法python list 所占用的内存大小是 header +指标大小*预留空间大小,所以也不算太占空间

Links booklink

Contact Us: admin [ a t ] ucptt.com