LUA String DB
 

News:

29 December 2022 - PtokaX 0.5.3.0 (20th anniversary edition) released...
11 April 2017 - PtokaX 0.5.2.2 released...
8 April 2015 Anti child and anti pedo pr0n scripts are not allowed anymore on this board!
28 September 2015 - PtokaX 0.5.2.1 for Windows 10 IoT released...
3 September 2015 - PtokaX 0.5.2.1 released...
16 August 2015 - PtokaX 0.5.2.0 released...
1 August 2015 - Crowdfunding for ADC protocol support in PtokaX ended. Clearly nobody want ADC support...
30 June 2015 - PtokaX 0.5.1.0 released...
30 April 2015 Crowdfunding for ADC protocol support in PtokaX
26 April 2015 New support hub!
20 February 2015 - PtokaX 0.5.0.3 released...
13 April 2014 - PtokaX 0.5.0.2 released...
23 March 2014 - PtokaX testing version 0.5.0.1 build 454 is available.
04 March 2014 - PtokaX.org sites were temporary down because of DDOS attacks and issues with hosting service provider.

Main Menu

LUA String DB

Started by chill, 24 May, 2004, 22:10:25

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

chill

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

chill

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

[NL]Pur

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

chill

#3
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.

[NL]Pur

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.

chill

#5
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.

[NL]Pur

the results of the functions i wrote:

i used following:

local i 0
	
while 
50000 do
	
	
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.

chill

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

NotRabidWombat

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


I like childish behavior. Maybe this post will be deleted next.

chill

#9
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.

[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 ;)

chill

#11
-- 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

chill

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 ??

NotRabidWombat

"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


I like childish behavior. Maybe this post will be deleted next.

NotRabidWombat

"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


I like childish behavior. Maybe this post will be deleted next.

chill

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.

NotRabidWombat

"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


I like childish behavior. Maybe this post will be deleted next.

chill

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.

chill

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

chill

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

SMF spam blocked by CleanTalk