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 ;).
So is it possible to make an IP-Range script faster than it already is... Ex. Ptaczek's??? or the one you modded...?
/NightLitch
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
tezlo don't be a wize guy post the algo.
easy..
here (http://board.univ-angers.fr/thread.php?threadid=170&boardid=6&sid=fb359577bf33513297ea3a782ae6acba) here (http://board.univ-angers.fr/thread.php?threadid=281&boardid=11&sid=fb359577bf33513297ea3a782ae6acba) and here (http://board.univ-angers.fr/thread.php?threadid=275&boardid=11&sid=fb359577bf33513297ea3a782ae6acba)
the table is not sorted so it just goes through all of them
but it works with numbers not strings
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.
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
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.
right :) ip-ranger is a bit of a different problem
what about RW's BinarySearch then ?
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.
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
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
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.
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