PtokaX forum

Development Section => Your Developing Problems => Topic started by: chill on 24 May, 2004, 22:10:25

Title: LUA String DB
Post by: chill on 24 May, 2004, 22:10:25
progress for today, but feel freee to join in and add your suggestions or code, I don't think one will be able to actually use the db cause I guess the bigger the DB will become the slower it will be expecially when adding items, but its just a challenge too look at the results, puls I think that the geoip script has a little but effective mistake, well..  here are the first lines of the db, soon also in readable format.

btw if I have something like

dostring("test = "..variable)

how can I make test local???

-- String DB by chill
-- Serialisation by RabidWombat (modded)

-- global
--sDB


function Main()
CreateDB("GeoIP",{{10,"number"},{10,"string"},{10,"string"},{10,"string"}})
GetDBValues("GeoIP")
ret = InsertValue("GeoIP",{1234567890,"2","4","5grgregeg"})
SendToAll(ret)

ret = InsertValue("GeoIP",{1234,"2","4","HOLLA"})
SendToAll(ret)

local ret = BSearch(GeoIP,1234567890, function(table,sitem)
if (table[1] == sitem) then
return 1
end
end)
SendToAll(ret[1].."  "..ret[2])

local ret = BSearch(GeoIP,1234, function(table,sitem)
if (table[1] == sitem) then
return 1
end
end)
SendToAll(ret[1].."  "..ret[4])


WriteTable(GeoIP,"GeoIP","GeoTest.txt")
end




-- DBName = "GeoIP", cells = {{10,"number"},{10,"string"},{10,"string"},{10,"string"}}
function CreateDB(DBName,cells)
dostring(DBName.." = {}")
dostring("sDB = "..DBName)
sDB.db = ""
sDB.entries = 0
sDB.cells = cells
local len = 0
for i = 1,getn(cells) do
if (cells[i][2] == "string") then
len = len + 2 + cells[i][1]
else
len = len + cells[i][1]
end
end
-- len + breakets + collons
len = len + 2 + (getn(cells))
sDB.clen = len
sDB = nil
end

function GetDBValues(DBName)
dostring("sDB = "..DBName)
if sDB then
SendToAll("DBName = "..DBName)
SendToAll("Entries = "..sDB.entries)
SendToAll("Cells = "..getn(sDB.cells))
for i = 1,getn(sDB.cells) do
SendToAll("Cell "..i.." : deep = "..sDB.cells[i][1]..", type = "..sDB.cells[i][2])
end
SendToAll("Cell lenght = "..sDB.clen)
else
SendToAll("No DB of name "..DBName)
end
sDB = nil
end

function InsertValue(DBName,values)
dostring("sDB = "..DBName)
if sDB then
-- Sanity Checks
if (getn(values) ~= getn(sDB.cells)) then
return("Error: Values cells = "..getn(values)..", DB cells = "..getn(sDB.cells))
end
for i = 1,getn(sDB.cells) do
if (type(values[i]) ~= sDB.cells[i][2]) then
return("Error: Value "..i.." = "..values[i]..", not of celltype "..sDB.cells[i][2])
elseif (type(values[i]) == "number") and (strlen(tostring(values[i])) > sDB.cells[i][1]) then
return("Error: Value "..i..", not of celllenght "..sDB.cells[i][1])
elseif (type(values[i]) == "string") and (strlen(format('%q',values[i])) > (sDB.cells[i][1]+2)) then
return("Error: Value "..i..", not of celllenght "..sDB.cells[i][1])
end
end

if (sDB.entries == 0) then
AddValues(sDB,1,values)
else
-- Check if values already exists
local ret,pos = BSearch(sDB,values[1], function(table,sitem)
if (table[1] == sitem) then
return 1
end
end)
if (ret ~= "NOTFOUND") then
return("Error: "..values[1]..", already in "..DBName.." DB.")
end
local sentry = GetValues(sDB,pos,sDB.clen)
if (sentry[1] < values[1]) then
pos = pos + 1
end
AddValues(sDB,pos,values)
SendToAll(pos)
SendToAll(tostring(ret))
end
end
sDB = nil
end

function AddValues(DB,pos,values)
pos = pos*DB.clen - DB.clen
local str1 = strsub(DB.db,1,pos) or ""
local str2 = strsub(DB.db,(pos+1),strlen(DB.db)) or ""
local strvalues = ConvValuestoString(DB.clen,values)
DB.db = str1..strvalues..str2
DB.entries = DB.entries + 1
end

function ConvValuestoString(len,values)
local string = "{"
for i = 1,getn(values) do
if (type(values[i]) == "number") then
string = string..values[i]..","
else
string = string..format('%q',values[i])..","
end
end
string = string.."}"
local diff = len - strlen(string)
string = string..strrep(" ",diff)
SendToAll(" testing  "..string)
return string
end


function BSearch(DB,sitem,rule)
local iStart,iEnd,iMid = 1,DB.entries,0
while (iStart <= iEnd) do
iMid = floor((iStart+iEnd)/2)
local table = GetValues(DB,iMid,DB.clen)
if rule(table,sitem) then
return table,iMid
elseif (table[1] > sitem) then
iEnd = iMid - 1
elseif (table[1] < sitem) then
iStart = iMid + 1
end
end
return "NOTFOUND",iMid
end

function GetValues(DB,s,clen)
s = s*clen - clen
local string = strsub(DB.db,s,s+clen)
dostring("strtable = "..string)
return strtable
end


---------------------------------------------------------------------------------------

-- Write Tables (Exclude Functions)

---------------------------------------------------------------------------------------
function WriteTable(table,tablename,file)
local handle = openfile(file,"w")
Serialize(table,tablename,handle)
  closefile(handle)
end
--------------------------------------------
function Serialize(tTable,sTableName,hFile,sTab)
sTab = sTab or "";
write(hFile,sTab..sTableName.." = {\n");
for key,value in tTable do
if (type(value) ~= "function") then
local sKey = (type(key) == "string") and format("[%q]",key) or format("[%d]",key);
if(type(value) == "table") then
Serialize(value,sKey,hFile,sTab.."\t");
else
local sValue = (type(value) == "string") and format("%q",value) or tostring(value);
write(hFile,sTab.."\t"..sKey.." = "..sValue);
end
write(hFile,",\n");
end
end
write(hFile,sTab.."}");
end
Title:
Post by: chill on 25 May, 2004, 23:46:41
take 2,

i tested it a bit, when adding 40.000 items into the db
where each cell is about 50 cells deep,
you need like 2 minutes, the last entry took
0.03 seconds.
the lookup is quite fast but not totally tested yet.
the memory was around 10 MB i think, more testing needed, but it is less than with a ordinary table.

-- String DB V 002 by chill

-- String DB, the DB is in binary string format
-- CreateDB(table), expects a table as argument, with the celldeep and type as value


-- GLOBALS
-- strtable

function Main()
GeoIP = CreateDB({{10,"number"},{10,"string"},{10,"string"},{10,"string"}})
GetDBValues("GeoIP")
for i = 1,500 do
--SendToAll(i)
GeoIP:InsertValues({i,"hola","test1","test"..i})
end
local t1 = clock()
GeoIP:InsertValues({0,"hola","test1","test0"})
SendToAll("Diff Time: "..(clock() - t1))

local t1 = clock()
local ret = GeoIP:Search(234, function(table,sitem)
if (table[1] == sitem) then
return 1
end
end)
SendToAll("Results: "..ret[1].."  "..ret[2])
SendToAll("Diff Time: "..(clock() - t1))

SaveDB(GeoIP,"GeoIP","GeoTest1.txt")

GeoIP:DelValues(0)
GeoIP:DelValues(2)

GetDBValues("GeoIP")

SaveDB(GeoIP,"GeoIP","GeoTest2.txt")
end


function GetDBValues(DBName)
dostring("sDB = "..DBName)
if sDB then
SendToAll("DBName = "..DBName)
SendToAll("Entries = "..sDB.entries)
SendToAll("Cells = "..getn(sDB.cells))
for i = 1,getn(sDB.cells) do
SendToAll("Cell "..i.." : deep = "..sDB.cells[i][1]..", type = "..sDB.cells[i][2])
end
SendToAll("Cell lenght = "..sDB.clen)
else
SendToAll("No DB of name "..DBName)
end
sDB = nil
end


---------------------------------------------------------------------------------------

-- Create a DB from given cells and return it

---------------------------------------------------------------------------------------
function CreateDB(cells)
local sDB = {}
sDB.db = ""
sDB.entries = 0
sDB.cells = cells
local len = 0
for i = 1,getn(cells) do
if (cells[i][2] == "string") then
len = len + 2 + cells[i][1]
else
len = len + cells[i][1]
end
end
-- len + breakets + collons
len = len + 2 + (getn(cells))
sDB.clen = len
sDB.GetValues = GetValues
sDB.Search = BSearch
sDB.ConvValuestoString = ConvValuestoString
sDB.AddValues = AddValues
sDB.InsertValues = InsertValues
sDB.RemoveValues = RemoveValues
sDB.DelValues = DelValues
return sDB
end

---------------------------------------------------------------------------------------

-- Del Values from DB

---------------------------------------------------------------------------------------
function DelValues(self,sitem)
local ret,pos = self:Search(sitem, function(table,sitem)
if (table[1] == sitem) then
return 1
end
end)
if (ret == "NOTFOUND") then
return("Error: Value "..sitem.." is not in the DB.")
else
self:RemoveValues(pos)
end
end

---------------------------------------------------------------------------------------

-- Remove Values from DB

---------------------------------------------------------------------------------------
function RemoveValues(self,pos)
pos = pos*self.clen - self.clen
local str1 = strsub(self.db,1,pos) or ""
local str2 = strsub(self.db,(pos+self.clen+1),strlen(self.db)) or ""
self.db = str1..str2
self.entries = self.entries - 1
end

---------------------------------------------------------------------------------------

-- Insert values into the DB

---------------------------------------------------------------------------------------
function InsertValues(self,values)
-- Sanity Checks
if (getn(values) ~= getn(self.cells)) then
return("Error: Values cells = "..getn(values)..", DB cells = "..getn(sDB.cells))
end
for i = 1,getn(self.cells) do
if (type(values[i]) ~= self.cells[i][2]) then
return("Error: Value "..i.." = "..values[i]..", not of celltype "..self.cells[i][2])
elseif (type(values[i]) == "number") and (strlen(tostring(values[i])) > self.cells[i][1]) then
return("Error: Value "..i.." = "..values[i]..", not of celllenght "..self.cells[i][1])
elseif (type(values[i]) == "string") and (strlen(format('%q',values[i])) > (self.cells[i][1]+2)) then
return("Error: Value "..i.." = "..values[i]..", not of celllenght "..self.cells[i][1])
end
end
if (self.entries == 0) then
self:AddValues(1,values)
else
-- Check if values already exists
local ret,pos = self:Search(values[1], function(table,sitem)
if (table[1] == sitem) then
return 1
end
end)
if (ret ~= "NOTFOUND") then
return("Error: Value "..values[1].." is already in the DB.")
end
local sentry = self:GetValues(pos)
if (sentry[1] < values[1]) then
pos = pos + 1
end
self:AddValues(pos,values)
end
end

---------------------------------------------------------------------------------------

-- Add Values to db

---------------------------------------------------------------------------------------
function AddValues(self,pos,values)
pos = pos*self.clen - self.clen
local str1 = strsub(self.db,1,pos) or ""
local str2 = strsub(self.db,(pos+1),strlen(self.db)) or ""
local strvalues = self:ConvValuestoString(values)
self.db = str1..strvalues..str2
self.entries = self.entries + 1
end

---------------------------------------------------------------------------------------

-- Convert Values to String

---------------------------------------------------------------------------------------
function ConvValuestoString(self,values)
local string = "{"
for i = 1,getn(values) do
if (type(values[i]) == "number") then
string = string..values[i]..","
else
string = string..format('%q',values[i])..","
end
end
string = string.."}"
local diff = self.clen - strlen(string)
string = string..strrep(" ",diff)
return string
end

---------------------------------------------------------------------------------------

-- Binary search the DB

---------------------------------------------------------------------------------------
function BSearch(self,sitem,rule)
local iStart,iEnd,iMid = 1,self.entries,0
while (iStart <= iEnd) do
iMid = floor((iStart+iEnd)/2)
local table = self:GetValues(iMid)
if rule(table,sitem) then
return table,iMid
elseif (table[1] > sitem) then
iEnd = iMid - 1
elseif (table[1] < sitem) then
iStart = iMid + 1
end
end
return "NOTFOUND",iMid
end

---------------------------------------------------------------------------------------

-- Get values as table

---------------------------------------------------------------------------------------
function GetValues(self,s)
s = s*self.clen - self.clen
local string = strsub(self.db,s,s+self.clen)
dostring("strtable = "..string)
return strtable
end


---------------------------------------------------------------------------------------

-- Save the DB (Exclude Functions)

---------------------------------------------------------------------------------------
function SaveDB(table,tablename,file)
local handle = openfile(file,"w")
Serialize(table,tablename,handle)
write(handle,"\n"..
tablename..".GetValues = GetValues\n"..
tablename..".Search = BSearch\n"..
tablename..".ConvValuestoString = ConvValuestoString\n"..
tablename..".AddValues = AddValues\n"..
tablename..".InsertValues = InsertValues\n"..
tablename..".RemoveValues = RemoveValues\n"..
tablename..".DelValues = DelValues")
  closefile(handle)
end
--------------------------------------------
function Serialize(tTable,sTableName,hFile,sTab)
sTab = sTab or "";
write(hFile,sTab..sTableName.." = {\n");
for key,value in tTable do
if (type(value) ~= "function") then
local sKey = (type(key) == "string") and format("[%q]",key) or format("[%d]",key);
if(type(value) == "table") then
Serialize(value,sKey,hFile,sTab.."\t");
else
local sValue = (type(value) == "string") and format("%q",value) or tostring(value);
write(hFile,sTab.."\t"..sKey.." = "..sValue);
end
write(hFile,",\n");
end
end
write(hFile,sTab.."}");
end

---------------------------------------------------------------------------------------

-- Save the DB

---------------------------------------------------------------------------------------
function LoadDB(file)
dofile(file)
end
Title:
Post by: [NL]Pur on 26 May, 2004, 00:14:31
i don't know what is better and if there are drawbacks
 own using lua 's on get / set functions, but look here for
some basic table functions.

http://board.univ-angers.fr/thread.php?threadid=1943&boardid=6&styleid=1&sid=c5032eec5a2a25199008f9640f52ef90 (http://board.univ-angers.fr/thread.php?threadid=1943&boardid=6&styleid=1&sid=c5032eec5a2a25199008f9640f52ef90)
Title:
Post by: chill on 26 May, 2004, 10:23:02
pur sorry but, you haven't read what i wrote or?
see everybody can work with tables, but when you add like 50.000 entries into a table you need 4 times as much memory, as with this db.
so thats what this db is actually about :))
plus keeping the speed of a table, except when adding and deleting entries, but that can also take some time when using inassociative tables and doing a entry at the first possition,

as table.insert(table,1,value)

cause then lua needs to reset all table indexes.
Title:
Post by: [NL]Pur on 26 May, 2004, 15:59:09
i only see u wrote functions for a table,

look at createDB looks like you are creating a table there.

Also, My functions are using rawset NOT insert.

i tested with insert, when using that it creates more entries in the table so called tags.

So if you use insert  it's adding 50000 entries + 50000 tags entries , so if you look at the table it's twice as long.

when using rawset, lua doesn't create the tags.
Title:
Post by: chill on 26 May, 2004, 16:42:43
yepp pur i read your db, simple table handling, but your db uses much memory, see this one usu about 1/4 of the mem you need,
well you can only enter numbers and strings till now, but will extend it soon, and interesting about insert, its like vector in c++ i guess, this one also doubles the entries when going over a certain entrie.

"look at createBD looks like you are creating a table there"

well i am but not only ;),
read it please, before replying again, you'll see, and try it and compare it to your memory used when added 5000 entries okey.

btw rabidwombat already pointed out in your db that is uses much mem, i think.
Title:
Post by: [NL]Pur on 26 May, 2004, 18:29:10
the results of the functions i wrote:

i used following:

local i = 0
while i < 50000 do
i = i + 1;
        INSERT(reg, "new"..i, {["profile"]="test4",["password"]="test4"});
end  

with 5000 entries mem usage is 1116 kb
with 50000 entries mem usage is 10407 kb


oh, and i think rabid meens the comparasion between mysql database and lua tables.
Title:
Post by: chill on 26 May, 2004, 18:34:43
ops, well if you are right then, it is really worthless, lets see but thanks for trying.

it do with

for i = 1,50000 do

table[tostring(i)] = "test"

and the same with my database, brb
Title:
Post by: NotRabidWombat on 26 May, 2004, 18:36:59
I'm really confused by your terminoligy.
function Main()
GeoIP = CreateDB({{10,"number"},{10,"string"},{10,"string"},{10,"string"}})
GetDBValues("GeoIP")
for i = 1,500 do
--SendToAll(i)
GeoIP:InsertValues({i,"hola","test1","test"..i})
end
local t1 = clock()
GeoIP:InsertValues({0,"hola","test1","test0"})
SendToAll("Diff Time: "..(clock() - t1))
So you create a template of 10 "cells" in 4 columns. It seems like this would translate to the idea of a table in database terms. To create a table you give definition to the columns and then insert rows.
What I now notice is you have a limit of 10 rows. So why does you test go from 1 to 500? Wouldn't InsertValues 11->500 return the error message?

I do not understand the purpose of "dostring("sDB = "..DBName)". Why not just pass in the table itself?

Suggestions:
- Use random numbers for inserting, searching, deleting when in search of performance. They represent a more real world scenario.
- Remove tabbing from the serialize function. This will increase it's performance and probably dofile's performance (since no one will really need to read the file). I wonder if it would be worth while to compile the file after a save (more likely after an exit) to try to increase load performance.

-NotRabidWombat
Title:
Post by: chill on 26 May, 2004, 18:51:45
just tested well adding is much slower than with tables, but
the mem is only the half :))

mem gc
SDB: 2400 2450

ASS: 4100 4200

IASS: 2500 5000


with collect garbage its

SDB: 1150 2300


where mem is the memory gc garbage collector threshold

SDB string DB

ASS associative table

IASS inassociative table



will do rabid just tried

to insert from 11,500 that work fine, and will do more testing of course

but to explain

GeoIP = CreateDB({{10,"number"},{10,"string"},{10,"string"},{10,"string"}})

this will create a GeoIP table + db

where you have 4 cells, each cell can hold a lenght of 10
where you must know when you have a sting conmatining excape chars the string will be longer,you can only index your entry by the first cell, e.g. the number, you cannot access the db by any other value.

the dostring, was old, but I am still looking for, a way to make the variable I assign there local.
Title:
Post by: [NL]Pur on 26 May, 2004, 19:09:44
mine db functions are given the same results as your ASS results.

lol if it's a string now, why not Lzw compress it in mem ;)
Title:
Post by: chill on 26 May, 2004, 19:26:47
-- String DB V 002 by chill

-- String DB, the DB is in binary string format
-- CreateDB(table), expects a table as argument, with the celldeep and type as value


-- GLOBALS
-- strtable

function Main()

test = CreateDB({{5,"number"},{10,"string"}})

local sCheck = {}

local t1 = clock()
for i = 1,5000 do
local num = random(-9999,99999)
sCheck[num] = 0
test:InsertValues({num,"como estas"})
end

SendToAll("Time to insert around 5000 numbers = "..(clock() - t1))

local t1 = clock()

for i,v in sCheck do

local ret = test:Search(i, function(table,sitem)
if (table[1] == sitem) then
return 1
end
end)
if ret[2] == "como estas" then
sCheck[i] = 1
end

end

SendToAll("Searched around 5000 times. Time: "..(clock() - t1))

local missed = 0
for i,v in sCheck do
if v == 0 then
missed = missed + 1
end
end

SendToAll("When searched missed "..missed.."  items.")

local temp = 0
for i,v in sCheck do
temp = temp + 1
test:DelValues(i)
if temp == 10 then
break
end
end

local t1 = clock()

for i,v in sCheck do

local ret = test:Search(i, function(table,sitem)
if (table[1] == sitem) then
return 1
end
end)
if ret ~= "NOTFOUND" then
if ret[2] == "como estas" then
sCheck[i] = 2
end
end

end

SendToAll("Deleted 10 entries and search around 5000 times. Time: "..(clock() - t1))

local missed = 0
for i,v in sCheck do
if v ~= 2 then
missed = missed + 1
end
end

SendToAll("When searched missed "..missed.."  items.")

collectgarbage()
end





function GetDBValues(DBName)
dostring("sDB = "..DBName)
if sDB then
SendToAll("DBName = "..DBName)
SendToAll("Entries = "..sDB.entries)
SendToAll("Cells = "..getn(sDB.cells))
for i = 1,getn(sDB.cells) do
SendToAll("Cell "..i.." : deep = "..sDB.cells[i][1]..", type = "..sDB.cells[i][2])
end
SendToAll("Cell lenght = "..sDB.clen)
else
SendToAll("No DB of name "..DBName)
end
sDB = nil
end


---------------------------------------------------------------------------------------

-- Create a DB from given cells and return it

---------------------------------------------------------------------------------------
function CreateDB(cells)
local sDB = {}
sDB.db = ""
sDB.entries = 0
sDB.cells = cells
local len = 0
for i = 1,getn(cells) do
if (cells[i][2] == "string") then
len = len + 2 + cells[i][1]
else
len = len + cells[i][1]
end
end
-- len + breakets + collons
len = len + 2 + (getn(cells))
sDB.clen = len
sDB.GetValues = GetValues
sDB.Search = BSearch
sDB.ConvValuestoString = ConvValuestoString
sDB.AddValues = AddValues
sDB.InsertValues = InsertValues
sDB.RemoveValues = RemoveValues
sDB.DelValues = DelValues
return sDB
end

---------------------------------------------------------------------------------------

-- Del Values from DB

---------------------------------------------------------------------------------------
function DelValues(self,sitem)
local ret,pos = self:Search(sitem, function(table,sitem)
if (table[1] == sitem) then
return 1
end
end)
if (ret == "NOTFOUND") then
return("Error: Value "..sitem.." is not in the DB.")
else
self:RemoveValues(pos)
end
end

---------------------------------------------------------------------------------------

-- Remove Values from DB

---------------------------------------------------------------------------------------
function RemoveValues(self,pos)
pos = pos*self.clen - self.clen
local str1 = strsub(self.db,1,pos) or ""
local str2 = strsub(self.db,(pos+self.clen+1),strlen(self.db)) or ""
self.db = str1..str2
self.entries = self.entries - 1
end

---------------------------------------------------------------------------------------

-- Insert values into the DB

---------------------------------------------------------------------------------------
function InsertValues(self,values)
-- Sanity Checks
if (getn(values) ~= getn(self.cells)) then
return("Error: Values cells = "..getn(values)..", DB cells = "..getn(sDB.cells))
end
for i = 1,getn(self.cells) do
if (type(values[i]) ~= self.cells[i][2]) then
return("Error: Value "..i.." = "..values[i]..", not of celltype "..self.cells[i][2])
elseif (type(values[i]) == "number") and (strlen(tostring(values[i])) > self.cells[i][1]) then
return("Error: Value "..i.." = "..values[i]..", not of celllenght "..self.cells[i][1])
elseif (type(values[i]) == "string") and (strlen(format('%q',values[i])) > (self.cells[i][1]+2)) then
return("Error: Value "..i.." = "..values[i]..", not of celllenght "..self.cells[i][1])
end
end
if (self.entries == 0) then
self:AddValues(1,values)
else
-- Check if values already exists
local ret,pos = self:Search(values[1], function(table,sitem)
if (table[1] == sitem) then
return 1
end
end)
if (ret ~= "NOTFOUND") then
return("Error: Value "..values[1].." is already in the DB.")
end
local sentry = self:GetValues(pos)
if (sentry[1] < values[1]) then
pos = pos + 1
end
self:AddValues(pos,values)
end
end

---------------------------------------------------------------------------------------

-- Add Values to db

---------------------------------------------------------------------------------------
function AddValues(self,pos,values)
pos = pos*self.clen - self.clen
local str1 = strsub(self.db,1,pos) or ""
local str2 = strsub(self.db,(pos+1),strlen(self.db)) or ""
local strvalues = self:ConvValuestoString(values)
self.db = str1..strvalues..str2
self.entries = self.entries + 1
end

---------------------------------------------------------------------------------------

-- Convert Values to String

---------------------------------------------------------------------------------------
function ConvValuestoString(self,values)
local string = "{"
for i = 1,getn(values) do
if (type(values[i]) == "number") then
string = string..values[i]..","
else
string = string..format('%q',values[i])..","
end
end
string = string.."}"
local diff = self.clen - strlen(string)
string = string..strrep(" ",diff)
return string
end

---------------------------------------------------------------------------------------

-- Binary search the DB

---------------------------------------------------------------------------------------
function BSearch(self,sitem,rule)
local iStart,iEnd,iMid = 1,self.entries,0
while (iStart <= iEnd) do
iMid = floor((iStart+iEnd)/2)
local table = self:GetValues(iMid)
if rule(table,sitem) then
return table,iMid
elseif (table[1] > sitem) then
iEnd = iMid - 1
elseif (table[1] < sitem) then
iStart = iMid + 1
end
end
return "NOTFOUND",iMid
end

---------------------------------------------------------------------------------------

-- Get values as table

---------------------------------------------------------------------------------------
function GetValues(self,s)
s = s*self.clen - self.clen
local string = strsub(self.db,(s+1),(s+self.clen))
dostring("strtable = "..string)
return strtable
end


---------------------------------------------------------------------------------------

-- Save the DB (Exclude Functions)

---------------------------------------------------------------------------------------
function SaveDB(table,tablename,file)
local handle = openfile(file,"w")
Serialize(table,tablename,handle)
write(handle,"\n"..
tablename..".GetValues = GetValues\n"..
tablename..".Search = BSearch\n"..
tablename..".ConvValuestoString = ConvValuestoString\n"..
tablename..".AddValues = AddValues\n"..
tablename..".InsertValues = InsertValues\n"..
tablename..".RemoveValues = RemoveValues\n"..
tablename..".DelValues = DelValues")
  closefile(handle)
end
--------------------------------------------
function Serialize(tTable,sTableName,hFile,sTab)
sTab = sTab or "";
write(hFile,sTab..sTableName.." = {\n");
for key,value in tTable do
if (type(value) ~= "function") then
local sKey = (type(key) == "string") and format("[%q]",key) or format("[%d]",key);
if(type(value) == "table") then
Serialize(value,sKey,hFile,sTab.."\t");
else
local sValue = (type(value) == "string") and format("%q",value) or tostring(value);
write(hFile,sTab.."\t"..sKey.." = "..sValue);
end
write(hFile,",\n");
end
end
write(hFile,sTab.."}");
end

---------------------------------------------------------------------------------------

-- Save the DB

---------------------------------------------------------------------------------------
function LoadDB(file)
dofile(file)
end

quite good I think or ??

[19:24] Time to insert around 5000 numbers = 2.547000000000026
[19:24] Searched around 5000 times. Time: 1.030999999999949
[19:24] When searched missed 0  items.
[19:24] Deleted 10 entries and search around 5000 times. Time: 1.172000000000026
[19:24] When searched missed 10  items.

except the add entry time, thats like going back to stoneage
Title:
Post by: chill on 26 May, 2004, 19:35:34
QuoteOriginally posted by [NL]Pur
mine db functions are given the same results as your ASS results.

lol if it's a string now, why not Lzw compress it in mem ;)

whats Lzw ??
Title:
Post by: NotRabidWombat on 26 May, 2004, 19:44:32
"quite good I think or ??"

Your data isn't enough to determine that answer. The best way to determine performance is to find out how memory and time relate to size of your data.

So you should record performance at say (100, 500, 1000, 5000, 10000, etc...) and then determine what function defines the data set. This should be simple in an applcation like Excel.

I do not understand why there would be any significant memory difference between using a string to represent a row or using a table to represent a row. The overhead from a table will "most likely" be a constant, therefore as the data set (n) grows, memory will grow c*n or at a linear rate.

-NotRabidWombat
Title:
Post by: NotRabidWombat on 26 May, 2004, 19:50:46
"the dostring, was old, but I am still looking for, a way to make the variable I assign there local."

Sorry I missed this.
You could do:
local sDB = global(DBName);

I believe there is also a tricky way with do ... end block but I can not remember.

But I still think you should just pass in the reference to the database table.

-NotRabidWombat
Title:
Post by: chill on 26 May, 2004, 19:54:31
QuoteOriginally posted by NotRabidWombat
I do not understand why there would be any significant memory difference between using a string to represent a row or using a table to represent a row. The overhead from a table will "most likely" be a constant, therefore as the data set (n) grows, memory will grow c*n or at a linear rate.

if you look at the geoIP script you will see the proof that the memory used by this script is 1/4 of the memory used by a ordinary table,

I will do some more test later.
Title:
Post by: NotRabidWombat on 26 May, 2004, 20:18:36
"if you look at the geoIP script you will see the proof that the memory used by this script is 1/4 of the memory used by a ordinary table"

This doesn't make any sense to me. If you think about a string object, it really only needs a char array and a length. A hash index would require a the key, the value and a pointer to the next hash. The table should be pretty straight forward too. I can not see where a 400% overhead is coming from. Plus, you add in brakets and a colons, 3 bytes overhead. So my guess is there is some bias in the testing.

Maybe if you could explain where all this memory is coming from, I'd stop being such a pest ;-)

In the mean time, I will continue to read through the code and then run some tests.

-NotRabidWombat
Title:
Post by: chill on 27 May, 2004, 10:01:39
did some more testing, a
 a inassoiciative tbale like

table = {
[1] = "test"
[2] = "test"
...

with 1.000.000 entries needs around 40 MB of mem
where as string db needs 30 MB.

geoip is built up like

table = {
[1] = {
   [1] = ""
   [2] = ""
   [3] = ""
   }
...
}
with 60.000 entries needs 40 MB of mem, so my guess is that the complexer your table or the more tables your table has, the more efficient is it to convert your entrie into a string.
so I think the best way would be keep the table with its indexes, that way it is still fast when adding deleting, entries with huge entrie numbers, but convert the entries into a string, that way, it wouldn't matter anymore what you enter, as long as it can be converted to a string, and be loaded by dostring, whitch i think is the best way.
Title:
Post by: chill on 27 May, 2004, 16:09:58
something like
-- convert table to string

table = {
[1] = {
[1] = "test",
[2] = "test",
["n"] = 2,
},
[2] = {
["ent1"] = "test1",
["ent2"] = "test2",
},
}

function ConvTabtoStr(stable)
local string = "{"
for i,v in stable do
string = string.."["..i.."]="
if (type(v) == "table") then
string = string..ConvTabtoStr(v)
elseif (type(v) == "string") then
string = string.."\"..v.."\","
elseif (type(v) == "number") then
string = string..v..","
else
string = string.."\"..tostring(v).."\","
end
end
return string.."},"
end
Title:
Post by: chill on 28 May, 2004, 15:49:12
this is a fast and easy way I think to hold table entries, and reduce them to a minimum.

It also has good inserting routine for sorted InAssociative tables, much faster then insert and then sort. you can chekc it out in the geoIP script by me,

else it just reduces, the memory neede by complex tables, cause it converts the entries into strings, it a table, and returns the values.


-- TDB V 001 by chill
-- Searialisation by RabidWombat (modded to exclude functions)
-- TableString DB only convert entries

-- Globals:
-- toValue

function BuildDB(ttype,rule,ruleb,rulel)
local DBTypes = {}
DBTypes.Ass = CreateAssDB
DBTypes.InAss = CreateInAssDB
DBTypes.InAssSort = CreateInAssSortDB
if DBTypes[ttype] then
return(DBTypes[ttype](ttype,rule,ruleb,rulel))
end
end

---------------------------------------------------------------------------------------

-- Create DB's and funcs

---------------------------------------------------------------------------------------

function CreateAssDB(ttype)
local sDB = {}
sDB.type = ttype
sDB.db = {n = 0}
-- funcs
sDB.SetIndex = SetIndexValue
sDB.GetIndex = GetValuefromIndex
return sDB
end

function CreateInAssDB(ttype)
local sDB = CreateAssDB(ttype)
-- funcs
sDB.Insert = InAssInsertValue
sDB.Remove = InAssRemoveIndex
return sDB
end

function CreateInAssSortDB(ttype,rule,ruleb,rulel)
local sDB = CreateAssDB(ttype)
-- funcs
sDB.IRule = rule
sDB.IRuleB = ruleb
sDB.IRuleL = rulel
sDB.Insert = InAssSortInsertValue
sDB.Remove = InAssSortRemoveIndex
sDB.GetInsertPos = GetInsertPosBSearch
return sDB
end

function ConValuetoString(value,set)
local str = ""
if (type(value) == "table") then
str = "{"
for i,v in value do
if (getn(value) == 0) then
if (type(i) == "string") then
str = str.."[\""..i.."\"]="
else
str = str.."["..i.."]="
end
end
str = str..ConValuetoString(v,1)
end
str = str.."}"
elseif (type(value) == "string") then
str = "\""..value.."\""
elseif (type(value) == "number") then
str = tostring(value)
end
if set then
str = str..","
end
return(str)
end


-- funcs for all DBs
function SetIndexValue(self,index,value)
value = ConValuetoString(value)
rawset(self.db,index,value)
end
function GetValuefromIndex(self,index)
local str = rawget(self.db,index)
if str then
dostring("toValue = "..str)
return toValue
end
end


--funcs for InAssociative Tables
function InAssInsertValue(self,vindex,value)
if not value then
tinsert(self.db,ConValuetoString(vindex))
else
tinsert(self.db,vindex,ConValuetoString(value))
end
end
function InAssRemoveIndex(self,index)
tremove(self.db,index)
end

--funcs for InAssociativeSort Tables
function InAssSortInsertValue(self,value)
local _,pos = self:GetInsertPos(value)
tinsert(self.db,pos,ConValuetoString(value))
end
function InAssSortRemoveIndex(self,index)
tremove(self.db,index)
end

---------------------------------------------------------------------------------------

-- Get Insert Position through Binary search for InAssSort

---------------------------------------------------------------------------------------
function GetInsertPosBSearch(self,sitem)
local iStart,iEnd,iMid = 1,getn(self.db),1
while (iStart <= iEnd) do
iMid = floor((iStart+iEnd)/2)
local value = self:GetIndex(iMid)
if self:IRule(value,sitem,iMid) then
return(self:IRule(value,sitem,iMid))
elseif self:IRuleB(value,sitem) then
iEnd = iMid - 1
elseif self:IRuleL(value,sitem) then
iStart = iMid + 1
end
end
return "NOTFOUND",iMid
end

---------------------------------------------------------------------------------------

-- Save the DB (Exclude Functions)

---------------------------------------------------------------------------------------
function SaveDB(table,tablename,file)
local handle = openfile(file,"w")
Serialize(table,tablename,handle)
  closefile(handle)
end
--------------------------------------------
function Serialize(tTable,sTableName,hFile,sTab)
sTab = sTab or "";
write(hFile,sTab..sTableName.." = {\n");
for key,value in tTable do
if (type(value) ~= "function") then
local sKey = (type(key) == "string") and format("[%q]",key) or format("[%d]",key);
if(type(value) == "table") then
Serialize(value,sKey,hFile,sTab.."\t");
else
local sValue = (type(value) == "string") and format("%q",value) or tostring(value);
write(hFile,sTab.."\t"..sKey.." = "..sValue);
end
write(hFile,",\n");
end
end
write(hFile,sTab.."}");
end

---------------------------------------------------------------------------------------

-- LoadDB

---------------------------------------------------------------------------------------
function LoadDB(type,tname,file,irule,iruleb,irulel)
dofile(file)
dostring("ttable = "..tname)
if ttable then
ttable.SetIndex = SetIndexValue
ttable.GetIndex = GetValuefromIndex
if (type == "InAss") then
ttable.Insert = InAssInsertValue
ttable.Remove = InAssRemoveIndex
elseif (type == "InAssSort") then
ttable.IRule = irule
ttable.IRuleB = iruleb
ttable.IRuleL = irulel
ttable.Insert = InAssSortInsertValue
ttable.Remove = InAssSortRemoveIndex
ttable.GetInsertPos = GetInsertPosBSearch
end
ttable = nil
end
end