Dictionary Class

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
Post Reply
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Post by paul doe »

Provoni wrote:paul doe,

The speed seems good. How much memory would your "data structure" use with 500,000,000 entries if each entry is a unique 64-bit integer key holding a ubyte value?
Such a structure would weigh in about 60 GB.
Provoni wrote: So it can not be used to store information? Can it store the number 34 to key 208827064571 so that later on key 208827064571 can be used to retrieve the number 34?
Data structures don't 'store' information, they index it. The data could (and should) be anywhere else (memory, a file, across a network, etc). And yes, it can 'store' a byte using a numeric key. Check 'fb-dict-example-3.bas' in the repository, or earlier in this thread for an example (that maps integer keys to strings).

However, I'm curious: what would be the purpose of such a structure?
Makoto WATANABE
Posts: 231
Joined: Apr 10, 2010 11:41
Location: Japan
Contact:

Re: Dictionary Class

Post by Makoto WATANABE »

Dear fxm;
Dear Provoni;

In my environment, "fb-dict-example-1.bas 20180518 version" can not compile with an error, too.
Does it work fine in your environment?
sancho3
Posts: 358
Joined: Sep 30, 2017 3:22

Re: Dictionary Class

Post by sancho3 »

I too get an error (Win 8, fb1.05 32 bit):
undefined reference to DICTIONARY::operator=(DICTIONARY&)@b

It was a pain in the ass to install as git often makes things.
I recommend putting up zip files in the repository with all the necessary files.
We are all well versed on how to move files around on our own computers but not everyone is a hardcore git guy that can do things like download a folder.
I downloaded git to the Win 8 machine and got to the git bash terminal and still stuck. Did some research and there were a bunch of tools and no thanks.
I ended up using a git downloading page, DownGit. This worked well.
Provoni
Posts: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Dictionary Class

Post by Provoni »

paul doe wrote: Data structures don't 'store' information, they index it. The data could (and should) be anywhere else (memory, a file, across a network, etc).
Okay, it indexes.
paul doe wrote: And yes, it can 'store' a byte using a numeric key.
So it does not only index, but it can also physically store unsigned bytes in the "data structure" itself?
paul doe wrote: However, I'm curious: what would be the purpose of such a structure?
Store language information.
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Post by paul doe »

I checked it. Again. It works as expected. Since I don't have installed it in the FBC folder, I run the examples directly from the downloaded folder.

What I would suggest is: delete ALL previous versions of the code/libs, from all places/folders where they may be (to stop fbc from using an outdated header/libraries, if that's the case). Then, download it from the repository again. There's no need to do anything special, nor installing exotic tools, since GitHub has a nice, round, green button to download the entire repository as a .zip file:

Image

This file contains a folder named 'fb-dictionary-master', that contains the root of the repo. If you then unzip the file, and run the examples, they work. I'm very sorry, but I can't fix something that's not broken...
Last edited by paul doe on May 19, 2018 6:56, edited 1 time in total.
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Post by paul doe »

Provoni wrote:So it does not only index, but it can also physically store unsigned bytes in the "data structure" itself?
Internally, it stores a pointer to something (a byte, a structure, an object, whatever you like). Check the code to see how it works.
Provoni wrote:Store language information.
Such as?
sancho3
Posts: 358
Joined: Sep 30, 2017 3:22

Re: Dictionary Class

Post by sancho3 »

Inside fb-dict-reference on line 94, comment out the line 'declare operator let( byref as Dictionary )' and it (example 1) seems to work.
Obviously that operator is not defined. I did not thoroughly test to see if it has no logic errors, but it does seem to print out the example properly.

I first visited and downloaded it tonight. Unless you still have old files in the repository, how could I possibly have old headers?
You can scroll that file yourself and see that the operator is not defined. (It doesn't seem like you would define it elsewhere since all the other members are defined there).
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dictionary Class

Post by fxm »

A such structure cannot work if Dictionary has OBJECT as base (directly or indirectly):

Code: Select all

type Dictionary Extends Object
  dim as Integer I
  declare operator let( byref as Dictionary )
end type

type RegisterDictionary extends Dictionary
end type
When an UDT extends OBJECT (directly or indirectly, so inheriting a constructor) the compiler will auto-generate a copy constructor and copy let operator (with chaining up) for UDT (if obviously it does not exist).
Last edited by fxm on May 19, 2018 12:16, edited 2 times in total.
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dictionary Class

Post by fxm »

It is not the only case:

- This works:

Code: Select all

type Dictionary
  dim as Integer I
  declare operator let( byref as Dictionary )
end type

type RegisterDictionary extends Dictionary
end type
- but no longer that:

Code: Select all

type Dictionary
  dim as Integer I = 1
  declare operator let( byref as Dictionary )
end type

type RegisterDictionary extends Dictionary
end type
Provoni
Posts: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Dictionary Class

Post by Provoni »

paul doe wrote:
Provoni wrote: Store language information.
Such as?
Letter n-gram frequency logarithms.

It needs retrieval speed and memory efficient storage. I will make a thread about it.
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Post by paul doe »

Provoni wrote:Letter n-gram frequency logarithms.

It needs retrieval speed and memory efficient storage. I will make a thread about it.
Ah yes, I see now. Well, this class offers you the one, but not the other (it was tailored to be fast and dynamic, at the expense of space). The hashing approach, however, is to be considered carefully (you only need the hashing function, not the entire class). See this paper for an approach that uses hashing:

Practical Queries of a Massive n-gram Database

And here is a post that contains several useful hashing functions:

String hashing functions

That said, I think that other data structures could be better (read: non-dynamic, fast and custom-tailored) for the task at hand, this one is too generic and you end up wasting far too much space (assuming that you're interested in using it in AZdecrypt).

Looking forward to your thread, promises to be interesting =D
Last edited by paul doe on May 19, 2018 11:37, edited 1 time in total.
Provoni
Posts: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Dictionary Class

Post by Provoni »

Thank you for the link to the paper paul doe.

I do not know what hashing is.

Here is my thread: viewtopic.php?f=3&p=247546#p247546
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Post by paul doe »

fxm wrote:It is not the only case:

- This works:

Code: Select all

type Dictionary
  dim as Integer I
  declare operator let( byref as Dictionary )
end type

type RegisterDictionary extends Dictionary
end type
- but no longer that:

Code: Select all

type Dictionary
  dim as Integer I = 1
  declare operator let( byref as Dictionary )
end type

type RegisterDictionary extends Dictionary
end type
Both examples work perfectly fine here (1.06.0). When extending Object, it also works:

Code: Select all

type Dictionary extends Object
  dim as Integer I
  declare operator let( byref as Dictionary )
end type

type RegisterDictionary extends Dictionary
end type
This also works as expected (which is how the Dictionary class is laid out by design):

Code: Select all

type Foo extends Object
	public:
		declare constructor()
		declare sub invokeFoo()
		
	protected:
		declare operator let( byref as foo )
end type

constructor foo()
	? "Foo constructed"
end constructor

type Bar extends Foo
	declare constructor()
	
	protected:
		declare operator let( byref as bar )
end type

constructor bar()
	? "Bar constructed"
end constructor

dim as bar b = bar()
dim as bar a = bar()

a = b
sancho3 wrote:Obviously that operator is not defined. I did not thoroughly test to see if it has no logic errors, but it does seem to print out the example properly.
Of course it's not defined, and it's under the protected: section for a reason (to avoid shallow copying of the class).

Try this: instead of including 'fb-dictionary.bi', include 'fb-dictionary-src.bi'. This will force the compiler to use the source code version. What results do you get? I also don't have it in my fbc installation, so it exists only in it's own folder. It's unthinkable we get different results, downloading it from the same source...
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Post by paul doe »

Uploaded everything again, inside it's own folder. Downloaded and checked it, no errors here. I'm using the fbc 64 bit 1.06.0 build from 25-Apr-2018 01:57, downloaded from here. Same for 32-bit.
Last edited by paul doe on May 19, 2018 13:08, edited 2 times in total.
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dictionary Class

Post by fxm »

paul doe wrote:Both examples work perfectly fine here (1.06.0). When extending Object
Can you provide the exact date?

Mine:
FreeBASIC Compiler - Version 1.06.0 (04-24-2018), built for win32 (32bit)
FreeBASIC Compiler - Version 1.06.0 (04-24-2018), built for win64 (64bit)
Post Reply