large amount of textual data

Vaicis · February 2012

Hi.
I am very new in gideros, just started to read..
What is the best approach for storing large amounts of data? ( table with ~ 1k records )
need to save them localy and need to be able to search in them.

regards,
Vaicis

atilim · February 2012

Hi,

I recently experienced that an ordinary Lua table with ~50k records (english dictionary) consumes around 100MB memory. But most probably a table with ~1k records won't be any problem.

Currently, if you're developing for iOS only, I can recommend to use SQLite plugin (I've attached it). This plugin will be officially available with the next version.

http://lua.sqlite.org/index.cgi/index

cheers

avo · February 2012

hi atilim,

Once android plugin support is added will we be able to use 1 plugin such as this sqlite one for both android and ios? So that we still only have to do everything once for all platforms?

Sorry if that's a real newbie question.

PS. Welcome home! hope you had a good trip!

Vaicis · February 2012

Thanks for info

But my main target os is android..iOS maybe later

if I am correct - Lua table is t = {} , if I need to fetch needed record, I have to iterate trought all records? It is not very slow process?
P.S. Sorry about my english

regards,
Vaicis

MikeHart · February 2012

Yes, you create a table in LUA like this:

myTable = {}

Here is a good tutorial about tables in LUA. Don't mix them up with a database "table".

atilim · February 2012

@avo, exactly. Android plugins are planned for release 2012.2.2. (we'll release 2012.2.1 this week)

@Vaicis, for example you create a table with

t = {}

And populate it with some words:

t["alice"] = true
t["bob"] = true
t["carol"] = true
t["dave"] = true

Then if you want to know if a key exists or not, you can simply check:

if t[key] ~= nil then
end

hope this helps

Vaicis · February 2012

Thanks,

Will wait for android plugin, it will be easier for me and more mundane approach

regards,
Vaicis

Dud · February 2012

I've been wondering about this too. I want to build a word game so basically I have two requirements. Storing around 100k words in memory but also checking to see if any word exists very quickly.

@atilim Are Lua tables very inefficient because taking up 100MB of memory for only 50k words seems like a huge amount (over 2K per word!)

Having read this article http://ejohn.org/blog/javascript-trie-performance-analysis/ 112,429 words of plain text only took up 916KB.

So my question is - what on earth is Lua doing that causes it to consume 100MB of memory and does that mean that using a Lua table to store a dictionary of words is a bad idea?

Also, regardless of the memory usage, would a Lua table that big be quick to search?

atilim · February 2012

hmm.. now I start to think that I may have done something wrong. let me do some tests and put the results here.

and searching within a Lua table should be very fast.

OZApps · February 2012

Lua tables are one of the best things since sliced bread, as they can offer quite a handful of tricks, persist that using JSON and file read/writes, you have a native lua based database.

atilim · February 2012

uhm.. I've made a serios calculation mistake :-\"

For an english dictionary with 267751 words (file size is about ~3mb), Lua array (t[#t + 1] = word) takes ~21mb and Lua table (t[word] = true) takes ~33mb.

You can download the dictionary here: http://scrabblehelper.googlecode.com/svn/trunk/ScrabbleHelper/src/dictionaries/sowpods.txt

Dud · February 2012

Thats ok

and thanks by the way for even investigating this. I am astounded by the level of support you guys are giving in the forums and it really does add to the value of your product. The sowpods.txt file will come in handy too

zakkwylde · April 2012

Hi Atilim,

what is an efficient way to load the sowpods data into a table and search on it to see if a word exists or not?

regards

evs · April 2012

Hello,

This works, don't know if it's very efficient though!

local dict = {}
 
-- populate table
for line in io.lines("sowpods.txt") do
 
	table.insert(dict, line)
 
end
 
-- search table values
local function searchTable(word) 
 
	for _, v in ipairs(dict) do
 
		if v == word .. "\r" then -- word with return added
 
			return true
 
		end
 
	end
 
	return false
 
end
 
-- check word and print result
local function checkWord(word)
 
	if searchTable(word) then
 
		print("Word OK", word)
 
	else
 
		print(word, "You're having a laugh!")
 
	end
 
end
 
-- TEST
local word = string.upper("depastures")
checkWord(word)
word = string.upper("fraggle")
checkWord(word)
word = string.upper("zeITgeiSt")
checkWord(word)

cheers

evs

zakkwylde · April 2012

Thanks evs. That's great!

techdojo · April 2012

I'm posting this on behalf of @scouser (as he's a little shy on occasions and he thinks I need the post count more!)

We were initially thinking that if the list (table) is sorted in alphabetical order (and referenced by numerical index, you can try do a binary search by comparing the value at the midpoint and then repeatedly halving the search space.

Then I was thinking about Lua "associative" arrays and thought that if you had a table organised like this.

words = { }
words.tom = 1
words.dick = 1
words.harry = 1

So the idea being that the key used to access the value is actually the contents of the array we want to store and you just store a 1 (or a true if was more efficient) as a filler

Then you could probably search quite quickly by doing something like

local guess = "fred" 
if words[guess] == 1 then print("found "..guess.." in list")
else print ("NOT FOUND")
end

It would be an interesting experiment to compare the various implementations to see which was more efficient in terms of memory used and access speed.

zakkwylde · April 2012

Hi techdojo,
sounds similar to Atilim's approach

And populate it with some words:
t["alice"] = true
t["bob"] = true
t["carol"] = true
t["dave"] = true

Then if you want to know if a key exists or not, you can simply check:
if t[key] ~= nil then
end

I am not sure how I would load the word list file and add the 'true' bit?

techdojo · April 2012

I'd actually write a small utility that read in the text file and then wrote out the code as lua source, or as a json file that could be read in.

Actually storing the data as t["alice"] = "Y" (or some other single character) might be even more efficient depending on what internal data type is used to store numbers and booleans.

atilim · April 2012

Although not an easy solution but using sqlite (currently only on iOS) or implementing a small plugin will be faster and memory efficient.

Dud's link is also interesting: http://ejohn.org/blog/javascript-trie-performance-analysis/

Michal · April 2012

Hey, for storing a dictionary efficiently look here: http://en.wikipedia.org/wiki/DAWG - could be easily implemented with lua tables.

Howdy, Stranger!

Categories

In this Discussion

Top Posters

large amount of textual data

Comments

Howdy, Stranger!

Quick Links

Categories

In this Discussion

Top Posters

large amount of textual data

Comments