Page 1 of 1

用对象获取列表反集,速度飞快

Posted: 03 Mar 2015, 00:46
by tmplinshi
昨天我碰到一个问题,要从 10 万个数字中获取 6 万左右数字的反集。我刚开始用的方法是用 InStr() 搜索 10 万次,结果是非常慢,大概要 40 秒钟。

本以为没其他方法了。不过还是带着试一试的态度,在英文板块发了个求助帖,别人回复说用对象。一测试竟然 0 秒就完成了!这个方法太有用了,特意在这里发个帖子让更多人知道 :D

测试代码:

Code: Select all

SetBatchLines -1

; 生成 10 万个数字
	Loop, 100000
		fullList .= "," A_Index
	fullList := Trim(fullList, ",")

; 生成 6 万个数字
	Loop, 60000
		subList .= "," A_Index
	subList  := Trim(subList, ",")

; 获取 4 万个反集数字
	
	; 方法一: InStr()
		TickCount_Start := A_TickCount ; 计时开始

		resultList := ""
		Loop, Parse, fullList, CSV
			If !InStr(subList, A_LoopField)
				resultList .= "," A_LoopField

		MsgBox, % "耗时: " (A_TickCount-TickCount_Start)/1000 " 秒" ; 我这里显示“耗时: 38.516000 秒”

	; 方法二: Object
		TickCount_Start := A_TickCount ; 计时开始

		; 把 6 万个数字列表转为对象
		oSubList := {}
		Loop, Parse, subList, CSV
			oSubList[A_LoopField] := 1

		; 开始...
		resultList := ""
		Loop, Parse, fullList, CSV
			If !oSubList[A_LoopField]
				resultList .= "," A_LoopField

		MsgBox, % "耗时: " (A_TickCount-TickCount_Start)/1000 " 秒" ; 我这里显示“耗时: 0.125000 秒”

Re: 用对象获取列表反集,速度飞快

Posted: 15 Apr 2015, 02:33
by RobertL
嗯,用对象的键做索引(索引值,或,单纯的,键是否存在),感觉是最快的做法。
  • 如果期望的返回结果也是对象(数组),可以oResultList:=objClone(oFullList),遍历oSubList并删除oResultList中相应项。
  • 感觉尽量用对象。且由于要遍历(而非索引SubList,可使用StrSplit进行列表至对象的转换。

Code: Select all

oSubList:=StrSplit(SubList,",")
oResultList:=objClone(oFullList)
for _,v in oSubList
  objRemove(oResultList,v)
没测试...

Re: 用对象获取列表反集,速度飞快

Posted: 26 Jan 2019, 21:01
by hitman
方法一46.875

方法二0.078

萝卜的方法:0.047

Re: 用对象获取列表反集,速度飞快

Posted: 18 Oct 2019, 13:45
by fwejifjjwk2
首先應該是差集或者補集,應該是沒有反集這個名詞。其次,第二個方法快成這樣也不是對象有什麼魔法,而是這個方法本來就是正確的標準做法,而且這個數據是最優的情況。

第一個方法在不確定是否為集合下也是標準做法。第二個方法在確定所有元素都是獨特的(集合的定義)時候是標準的做法。

我用別的語言(某個超級小眾的高階語言)實現,數據是 1,2,3,...,6萬 還有 1,2,3,...,10萬。第一個方法需要3分鐘,第二個方法需要的時間也是接近零。

在這個數據下,第一個方法比對了 1+2+3+...+60000= 18003000 次,差不多是 18 萬萬次。第二個方法,每次迭代都第一位就匹配到相等的數字,總共比對了 6 萬次。兩個方法需要檢索的數字本來就差 3 萬倍。