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

供新手入门和老手参考的教程和相关资料,包括中文帮助

Moderators: arcticir, tmplinshi

tmplinshi
Posts: 1520
Joined: 01 Oct 2013, 14:57

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

03 Mar 2015, 00:46

昨天我碰到一个问题,要从 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 秒”
User avatar
RobertL
Posts: 540
Joined: 18 Jan 2014, 01:14
Location: China

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

15 Apr 2015, 02:33

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

Code: Select all

oSubList:=StrSplit(SubList,",")
oResultList:=objClone(oFullList)
for _,v in oSubList
  objRemove(oResultList,v)
没测试...
我为人人,人人为己?
hitman
Posts: 11
Joined: 10 Aug 2014, 06:47

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

26 Jan 2019, 21:01

方法一46.875

方法二0.078

萝卜的方法:0.047
fwejifjjwk2
Posts: 13
Joined: 10 Aug 2019, 01:49

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

18 Oct 2019, 13:45

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

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

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

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

Return to “教程资料”

Who is online

Users browsing this forum: No registered users and 5 guests