TABLE SEARCH TESTS

[c h i l l a]

okey  I just had a idea.. and did it,  here the results

all tested on P4 2,4 GHz no hyper threading.
tested on a table with 1.000.000  entries...
winner was tsearch = ^2  search ;).

creating a 1.000.000  table like this

table = {}

for i = 1,1000000 do
     word = strchar(random(65,90))
	len = random(4,20)
	for i = 1,len do
		word = word..strchar(random(97,122))
	end
	tinsert(table, word)
end

--sorting the table
sort(table)

save table

WriteFile(table, "table", "Table.txt")

function WriteFile(table, tablename, file)
	local handle = openfile("txt/"..file, "w")
	write(handle, tablename.." = {\n" )
	for key, value in table do
		if key=="n" then
			write(handle, "\t["..key.."] = "..value..",\n")
		else
			write(handle, "\t["..key.."] = "..format('%q',value)..",\n")
		end
	end
	write(handle, "}");
  	closefile(handle)
end

and the searches  I used...  with results

--Table Search

dofile("txt/Table.txt")

--------------------------------------------------------------------------------------------------------------------------------------------
function rSearch(table,sItem)
	local var2,var3,var4 = 1,getn(table),0
	local var1 = random(1,getn(table))
	while 1 do
		var4 = var4 + 1
		if table[var1]==sItem then
			return var1,var4
		elseif table[var2]==sItem then
			return var2,var4
		elseif table[var3]==sItem then
			return var3,var4
		elseif (var2-var3)^2<=1 then
			return "Not Found",var4
		elseif table[var1] > sItem then
			var3 = var1		
			var1 = random(var2,var3)
		elseif table[var1] < sItem then
			var2 = var1
			var1 = random(var2,var3)
		end
	end
end
--------------------------------------------------------------------------------------------------------------------------------------------
function tSearch(table,sItem)
	local var1,var2,max = 0,1,(log10(getn(table))/log10(2))
	var1 = floor(getn(table)/2)
	while 1 do
		var2 = var2 + 1
		if table[var1] == sItem then
			return var1,(var2 - 1)
		elseif (var2 - 1)  > max then
			return "Not found",(var2 - 1)
		elseif table[var1] > sItem then
			var1 = var1 - floor(getn(table)/(2^var2)) - 1
			if var1 <= 0 then
				var1 = 1
			end
		elseif table[var1] < sItem then
			var1 = var1 + floor(getn(table)/(2^var2)) + 1
			if var1 > getn(table) then
				var1 = getn(table)
			end
		end
	end
end
--------------------------------------------------------------------------------------------------------------------------------------------
mtrun,mrrun,var,ast,asr,asn,var1,var2,var3 = 0,0,0,0,0,0,0,0,0
for i = 1,1000000 do
	var = var + 1
	--ran = random(1,1000000)
	tsi1 = clock()
	tsearch,trun = tSearch(table,table[i])
	tsi2 = clock()
	rsearch,rrun = rSearch(table,table[i])
	tsi3 = clock()
	var1 = 0
	var3 = var3 + var
	
	
	mtrun = mtrun + trun
	mrrun = mrrun + rrun
	var2 = var2 + var1
	ast = ast + tsi2-tsi1
	asr = asr + tsi3-tsi2
end
tsi4 = clock()
for i2,v2 in table do
	if table[i2] == table[5] then
		break
	end
end
tsi5 = clock()
asn = (var3/5) *  (tsi5 - tsi4)
print("ALLRUN = "..var.."  Average ts = "..(mtrun/var).."  rs = "..(mrrun/var).."  ns = "..(var3/var).."\n Average search time for tSearch was = "..(ast/var).."  for rSearch was = "..(asr/var).."  for normal search was "..(asn/var))

okey,  I had to do this cause I need a way of finding an entry faster than with i,v in table do
it only works with srtable tables  of course...  else I gues sone can't do anythinhg else but i,v in table do
if not the please tell me cause ? need that too...

well explanation

tsearch = ^2 search cause it search like that
rsearch is randome search this is effectivly when using tables samller than 10-20 entries, above tsearch wins already and i,v couldn't be tested with 1000000 entries :).

my results ::

ALLRUN = 1000000  Average ts = 18.963822  rs = 27.780652  ns = 500000.5
 Average search time for tSearch was = 4.978799999999788e-005  for rSearch was =
 6.428499999999826e-005  for normal search was 0

allrun is the numer of seraches.

ts = runns till item was found
rs = runns till itma was found with randomsearch
ns = runns tille item was found with normal search, this is only calculated since I couldn't really test it.

the rest is like it is.
then I have no clue why normal search is zero, ah well but it isn't ;).

[NightLitch]

So is it possible to make an IP-Range script faster than it already is... Ex. Ptaczek's??? or the one you modded...?


/NightLitch

[tezlo]

maybe a tiny bit.. the most crucial part in an ip-ranger is checking the ranges
i used pta's algo because its the fastest.. and made it to pre-calc everything
table lookup wont make much difference

[c h i l l a]

tezlo don't be a wize guy post the algo.

[tezlo]

easy..
here here and here
the table is not sorted so it just goes through all of them
but it works with numbers not strings

[c h i l l a]

tezlo dunno if we missed each other, but I thaught you had a much better searchalgorithm  than the one above.
But doesn't it run through the table as normal as foreachi  is for i,v in t do.

[tezlo]

as normal ?
foreachi is really for i = 1, table.n
the point is that the ips get pre-computed into numbers (speed!)
you cant really sort that table since one range can contain another

imo.. if you want to get items fast from a huge table
youre best off using associative tables as lua's hashing will always be faster

[c h i l l a]

well..  point is like I said, I needed it ;).
And to keep in mind this thread is about finding items fast in a non associative table, else I would use a associative.

[tezlo]

right :) ip-ranger is a bit of a different problem
what about RW's BinarySearch then ?

[c h i l l a]

see I was looking for it but couldn't find it anywhere...
I'd  like to test it to compare,if  you got it, post it please.

[c h i l l a]

tsearch stays unbeatable at least above 100,000 entries :). I guess binary can't beat it :).

test machine P4 2,4GHz

--Table Search

dofile("txt/Table.txt")

--------------------------------------------------------------------------------------------------------------------------------------------
function rSearch(table,sItem)
	local var2,var3,var4 = 1,getn(table),0
	local var1 = random(1,getn(table))
	while 1 do
		var4 = var4 + 1
		if table[var1]==sItem then
			return var1,var4
		elseif table[var2]==sItem then
			return var2,var4
		elseif table[var3]==sItem then
			return var3,var4
		elseif (var2-var3)^2<=1 then
			return "Not Found"
		elseif table[var1] > sItem then
			var3 = var1		
			var1 = random(var2,var3)
		elseif table[var1] < sItem then
			var2 = var1
			var1 = random(var2,var3)
		end
	end
end
--------------------------------------------------------------------------------------------------------------------------------------------
function tSearch(table,sItem)
	local var1,var2,max = floor(getn(table)/2),1,(log10(getn(table))/log10(2))
	while 1 do
		var2 = var2 + 1
		if table[var1] == sItem then
			return var1,(var2 - 1)
		elseif (var2 - 1)  > max then
			return "Not found"
		elseif table[var1] > sItem then
			var1 = var1 - floor(getn(table)/(2^var2)) - 1
			if var1 <= 0 then
				var1 = 1
			end
		elseif table[var1] < sItem then
			var1 = var1 + floor(getn(table)/(2^var2)) + 1
			if var1 > getn(table) then
				var1 = getn(table)
			end
		end
	end
end
--------------------------------------------------------------------------------------------------------------------------------------------
function TenSearch(table,sitem)
	local var1,var2,var3 = floor(getn(table)/10),1,0
	var4 = 0
	while 1 do
		var4 = var4 + 1
		var3 = var2 + var1
		if var3 > getn(table) then
			var3 = getn(table)
		end
		if table[var2] == sitem then
			return var2
		elseif table[var3] == sitem then
			return var3
		elseif table[var2] < sitem and sitem < table[var3] then
			var1 = floor((var3-var2)/10)
		else
			var2 = var3 + 1
			var3 = var3 + var1
			if var2 > getn(table) then
				--return "NotFound"
				return
			end
		end
	end
end
--------------------------------------------------------------------------------------------------------------------------------------------
function nSearch(table,nnum)
	for i = 1,getn(table) do
		if table[i] == table[nnum] then
			break
		end
	end
end
--------------------------------------------------------------------------------------------------------------------------------------------
mtrun,mrrun,var,ast,asr,asn,var1,var2,var3,ats,mts = 0,0,0,0,0,0,0,0,0,0,0
for i = 1,100 do
	var = var + 1
	--ran = random(1,1000000)
	tsi1 = clock()
	tsearch,trun = tSearch(table,table[i])
	tsi2 = clock()
	rsearch,rrun = rSearch(table,table[i])
	tsi3 = clock()
	tense = TenSearch(table,table[i])
	tsi6 = clock()
	var1 = 0
	var3 = var3 + var
	
	
	mtrun = mtrun + trun
	mrrun = mrrun + rrun
	var2 = var2 + var1
	ast = ast + tsi2-tsi1
	asr = asr + tsi3-tsi2
	ats = ats + tsi6-tsi3
	mts = mts + var4
end

dons = 1



if dons then
	tsi4 = clock()
	nSearch(table,table[10])
	tsi5 = clock()
end



asn = (var3/10) *  (tsi5 - tsi4)

print("ALLRUN = "..var.."  Averageruns =  tens: "..(mts/var)..", ts = "..(mtrun/var)..",  rs = "..(mrrun/var)..",  ns = "..(var3/var).."\n Average search time for tSearch was = "..(ast/var).."  for rSearch was = "..(asr/var).."  for normal search was "..(asn/var).."  for TenSearch "..(ats/var))

and results :



TEST1 :

ALLRUN = 1000000  Averageruns =  tens: 29.699564, ts = 18.963822,  rs = 27.792286,  ns = 500000.5
Average search time for tSearch was = 4.222500000000082e-005  for rSearch was = 5.482299999999896e-005
for normal search was 10150.01014999873  for TenSearch = 4.913700000000062e-005


ALLRUN = 100000  Averageruns =  tens: 24.96924, ts = 18.96382,  rs = 26.42085, ns = 50000.5
Average search time for tSearch was = 3.809999999999491e-005  for rSearch was = 5.278000000000247e-005
for normal search was 1095.010950000255  for TenSearch = 4.521999999999935e-005


ALLRUN = 10000  Averageruns =  tens: 20.4723, ts = 18.9647,  rs = 24.1995,  ns = 5000.5
Average search time for tSearch was = 4.700000000002547e-005  for rSearch was = 4.370000000003529e-005
for normal search was 117.5117499998363  for TenSearch = 3.269999999997708e-005


ALLRUN = 1000  Averageruns =  tens: 15.994, ts = 18.965,  rs = 21.654,  ns = 500.5
Average search time for tSearch was = 4.700000000048021e-005  for rSearch was = 4.699999999957072e-005
for normal search was 10.91090000001511  for TenSearch = 1.60000000000764e-005


ALLRUN = 100  Averageruns =  tens: 11.62, ts = 18.98,  rs = 18.73,  ns = 50.5
Average search time for tSearch was = 0  for rSearch was = 0  for normal search  was 1.025149999999871  for TenSearch 0

[tezlo]

function BinarySearch(tTable, SearchVar)
	assert(tTable and SearchVar);

	local iBot, iMid, iTop = 1, nil, getn(tTable);
	local CompVal = nil;

	if(getn(tTable) == 0) then return -1, 1; end

	while(iBot <= iTop) do
		iMid = floor((iTop + iBot) / 2);

		CompVal = tTable[iMid];

		if(CompVal == nil) then return -1, -1; end

		if(SearchVar < CompVal) then
			iTop = iMid - 1;
		elseif(SearchVar > CompVal) then
			iBot = iMid + 1;
		else
			return iMid, -1;
		end
	end

	if(SearchVar > CompVal) then 
		iMid = iMid + 1;
	end

	return -1, iMid;
end

function AddPassiveUser(curUser)
	local iFind, iInsert = BinarySearch(tPassiveUsers, strlower(curUser.sName));

	if(iFind == -1) then 
		if(getn(tPassiveUsers) >= maxpasives) then
			curUser:SendData(bot,"We dont want more then "..maxpasives.." passive users in this hub ") 
			curUser:SendData("$ForceMove "..frmHub:GetRedirectAddress()) 
			curUser:Disconnect() 
		else
			tinsert(tPassiveUsers, iInsert, strlower(curUser.sName));
			SendToAll(bot, curUser.sName.." was added to passive user list, currently: "..getn(tPassiveUsers).."/"..maxpasives);
		end
	end
end

function RemovePassiveUser(curUser)
	local iFind = BinarySearch(tPassiveUsers, strlower(curUser.sName));

	if(iFind ~= -1) then
		tremove(tPassiveUsers, iFind);
		SendToAll(bot, curUser.sName.." was removed from passive user list, currently: "..getn(tPassiveUsers).."/"..maxpasives);
	end
end

[c h i l l a]

hehe funny they are the same
only different names.
I don't get whats so binary about it actually 2^x  is much better to understand I think.


bsrun : 19.954
ALLRUN = 1000  Averageruns =  tens: 15.994, ts = 18.965,  rs = 21.626,  ns = 500
.5
 Average search time for tSearch was = 3.099999999903957e-005  for rSearch was =
 3.200000000106229e-005  for normal search was 10.16014999997597  for TenSearch
4.700000000048021e-005 Bsearch was = 4.600000000027649e-005
> dofile("TSearch.lua")
bsrun : 19.954
ALLRUN = 1000  Averageruns =  tens: 15.994, ts = 18.965,  rs = 21.903,  ns = 500
.5
 Average search time for tSearch was = 4.700000000048021e-005  for rSearch was =
 4.699999999866122e-005  for normal search was 10.96094999995703  for TenSearch
1.499999999941792e-005 Bsearch was = 3.100000000085856e-005
>

only thing I did notice is the runs are smaller, and that the times differ allways also when I set lua to highest priority.

[c h i l l a]

even faster

10^x :)

function TenSearch(table,sitem)
	local var1,var2,var3,var12 = floor(getn(table)/10),1,0,getn(table)

	varrun10 = 0

	while 1 do
		
		varrun10 = varrun10 + 1

		if varrun10 > var12/(10^varrun10) then
			return
		end

		if var1 < 1 then
			var1 = 0
		end
		
		local vart1,vart2,vart3,vart4,vart5,vart6,vart7,vart8,vart9 = var1,var1*2,var1*3,var1*4,var1*5,var1*6,var1*7,var1*8,var1*9

		if (table[var2] == sitem) then
			return var2
		elseif (table[vart1] == sitem) then
			return vart1
		elseif (table[vart2] == sitem) then
			return vart2
		elseif (table[vart3] == sitem) then
			return vart3
		elseif (table[vart4] == sitem) then
			return vart4
		elseif (table[vart5] == sitem) then
			return vart5
		elseif (table[vart6] == sitem) then
			return vart6
		elseif (table[vart7] == sitem) then
			return vart7
		elseif (table[vart8] == sitem) then
			return vart8
		elseif (table[vart9] == sitem) then
			return vart9
		elseif (table[var12] == sitem) then
			return vart12
		elseif (table[var2] < sitem and sitem < table[vart1])  or (table[vart1] < sitem and sitem < table[vart2])  or (table[vart2] < sitem and sitem < table[vart3]) or (table[vart3] < sitem and sitem < table[vart4]) or (table[vart4] < sitem and sitem < table[vart5]) or (table[vart5] < sitem and sitem < table[vart6]) or (table[vart6] < sitem and sitem < table[vart7]) or (table[vart8] < sitem and sitem < table[vart9]) or (table[vart9] < sitem and sitem < table[var12]) then
			var1 = floor((vart1-var2)/10)
		end
	end
end