Re: multidirectional hash/dictionary or such...

[Coda Highland <chighland@...>]

On Tue, May 28, 2013 at 10:51 AM,  <meino.cramer@gmx.de> wrote:
> Hi,
>
> there is a textual list of shortwave broadcasters.
>
> Each line of text contains column-oriented entries of some aspects
> (language, frequency, time, day of the broadcast) of one broadcast.
>
> There is already a small lua script, which is able to extract and
> separate each bit of information of the whole table.
>
> Since any value of each line is not unique in respect to the whole
> table, there is no real key value for each line (despite its
> linenumber...).
>
> I want to search the table very quickly, like
> "List all broadcasters transmitting on 9850kHz on sundays between
> 17:00 o'clock and 19:00 o'clock" and such...
>
> (Yes, it sounds like a classical database task...but I dont want to
> urge my little single board computer to handle such a software for
> such a little database (~7500++ lines)).
>
> Hash tables / dictionaries were my first idea, but these are only
> "one directional": Looking up the key results in the value, but
> the opposite direction means: Search the whole hash/dictoinary
> "by hand" (for-loop or such).
>
> How can I organize the data most "lua"ish so data lookups will
> not be done by sequentiell searches but by resolving hash keys in a
> way, so it is possible to search for as many aspects of the
> information contained in the table as possible???
>
> And to make things even more.....interesting.....<hrrrm>: the
> embedded computer runs linux and has limited RAM (256MB for
> all).
>
> Is there any way to got ??
>
> Thank you very much in advance for any help!
> Best regards,
> mcc
>

What you're looking for is an index -- that is, a hash or array
containing a mapping between the queriable values and the data. The
fact that your RAM is limited might be a little bit problematic,
because it does involve doubling your memory usage; this is a classic
time/space tradeoff.

You mentioned a range check -- I would recommend binary-searching
through an array containing { timestamp, data } pairs to find the
minimum and maximum entries instead of using a hash for this, because
hashes are unsorted.

You'll probably be better off bringing in a lightweight database like
SQLite that has this functionality built-in, doesn't use much in the
way of resources, and can work with the data on-disk instead of having
to load it all into RAM.

/s/ Adam