Jump to content

code34

OO DIGITAL TREE - Object Oriented

Recommended Posts

Object Oriented DIGITAL TREE
Lastest version: 0.4 by Code34

 

Like to Donate ? Donate with paypal
 



Github: https://github.com/code34/oo_digitaltree.Altis
Reference: http://forums.bistudio.com/showthread.php?167980-Object-Oriented-SQF-Scripting-and-Compiling
Wikipedia: http://en.wikipedia.org/wiki/Trie

400px-Trie_example.svg.png

 

 



Description
OO DIGITAL TREE is a class (object oriented) digital tree that permits to stock value like string, scalar, object, etc... in a digital tree. This object will permits to stock objects in digital tree, and give linear time access to them. Time access to record depends of the key size.

Features:

 

 

 

  • Put, remove, search value
  • Retrieve keyset, and entryset

 

 

Licence:
Under Gpl, you can share, modify, distribute this script but don't remove the licence and the name of the original author

 

Warning: The script uses sleep for scheduled environment.

Documentation:

 

/*
Author: code34 nicolas_boiteux@yahoo.fr
Copyright (C) 2013 Nicolas BOITEUX

CLASS OO_TREE OO_NODE

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/

/*
Function: = ["get", key] call OO_TREE;
Retrieve the value associated to a key

Parameters:
key - string

*/

/*
Function: = ["put", [key, value]] call OO_TREE;
Put/update a value associated to a key

Parameters:
key - string
value - any kind of value

*/


/*
Function: = ["remove", key] call OO_TREE;
Remove the value associated to key

Parameters:
key - string


*/

/*
Function: = "entrySet" call OO_TREE;
Return all the value in the digital tree

Parameters:
none
*/

/*
Function: = "keySet" call OO_TREE;
Return all the keys in the digital tree

Parameters:
none
*/

/*
Function: = "size" call OO_TREE;
Return the number of values in the digital tree

Parameters:
none
*/

Readme:

 

/*
Author: code34 nicolas_boiteux@yahoo.fr
Copyright (C) 2013 Nicolas BOITEUX

CLASS OO_DIGITAL TREE

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/

Usage:
put the "oo_tree.sqf", "oo_node.sqf", and the "oop.h" files in your mission directory
put this code into your mission init.sqf
call compilefinal preprocessFileLineNumbers "oo_tree.sqf";
call compilefinal preprocessFileLineNumbers "oo_node.sqf";

See example mission in directory: init.sqf

Licence:
You can share, modify, distribute this script but don't remove the licence and the name of the original author

logs:
0.3 - fix parseChildKeySet
0.2 - Make Arma Not War version
0.1 - OO DIGITAL TREE - first release


Examples

Put string value into the digital tree.

_tree = ["new", []] call OO_TREE;
_key = name player;
_value = "my entry value";
["put", [_key, _value]] call _tree;

Retrieve the value into the digital tree

_key = name player;
_value = ["get", _key] call _tree;
hint format ["%1", _value];

Put an object into digital tree

_tree = ["new", []] call OO_TREE;
_key = name player;
_value = player;
["put", [_key, _value]] call _tree;

Retrieve the object into digital tree

_key = name player;
_value = ["get", _key] call _tree;
hint format ["%1", _value];

Share this post


Link to post
Share on other sites

hi :)

just release the 0.3 version

logs:

- fix parseChildKeySet

Share this post


Link to post
Share on other sites
  Iceman77 said:
This is all very interesting. Thanks.

thxs friend :)

Share this post


Link to post
Share on other sites

snip misread

Edited by cuel

Share this post


Link to post
Share on other sites

Hi :)

In fact, i dont bench this object cause it s early version. The digital tree stills loop on some arrays.

Example with:

400px-Trie_example.svg.png

if you want to looking for the value associated to "TEN" key, the access is like this:

-> ROOT NODE -> loop on array, and leave at firt element, go to T node

-> T NODE -> loop on array, parse TO node, and leave at TE node

-> TE NODE -> loop on array, parse TEA node, parse TED node, leave to TEN node

if you have want to have a direct access to a value associated to a key, you can use OO_HASHMAP instead

http://forums.bistudio.com/showthread.php?181911-Object-Oriented-Hashmap&p=2752350#post2752350

at this time, i don't compare the both method to retrieve a key, with a large amount of datas, resultats are highly link to engine internal functions.

I will try to do bench tonight with thousand of random key, and randomly access :)

Edited by code34

Share this post


Link to post
Share on other sites

Hi,

here the results with a huge collection of 1000 keys of 64 chars writing:

"Time OO_TREE insert: 40.9241 sec"

"Time OO_HASHMAP insert: 0.322998 sec"

100 keys of 64 chars randomly reading:

"Time OO_TREE read: 1.04688 sec"

"Time OO_HASHMAP read: 0.0219727 sec"

Very slow insertion of tree map are relative to node object instanciation, and accessor methods. A way to optimize will be te create only one object that would be the tree and node with direct access to variable.

Very important note: both objects OO_HASHMAP & OO_TREE use the same interface, they can be replace each others without any code modification

Edited by code34

Share this post


Link to post
Share on other sites

Aaaand what is it good for?

 

Share this post


Link to post
Share on other sites
MyHashMap = createHashMap;
for "_i" from 1 to 10000 do {MyHashMap set [_i, _i];};

`MyHashMap find 125` 0.002ms
`MyHashMap find 9999` 0.0019 ms
Don't have perf on the insert right now. Should be as fast as the finds though.

 


 

 

  On 10/25/2017 at 10:12 AM, Mirek said:

Aaaand what is it good for?

 

If you know what Tree and Hashmap containers are then you will know what this is useful for. If you don't then this is most likely not useful for you.
They are Array-like containers optimized for a certain use case. Usually way better lookup performance (Finding a specific value).

Share this post


Link to post
Share on other sites

Tree is a thing that grows outside :-) , no idea what hashmap is, and it surely be too advanced coding for me, so ill probably never use it, but iam highly curious George, and any knowledge that can help me create a better mission might come in handy. So what it does in plain language?

 

Share this post


Link to post
Share on other sites
  On 10/25/2017 at 10:37 AM, Mirek said:

Tree is a thing that grows outside :-) , no idea what hashmap is, and it surely be too advanced coding for me, so ill probably never use it, but iam highly curious George, and any knowledge that can help me create a better mission might come in handy. So what it does in plain language?

 

Look at the picture in the first post.
An array would be a straight line of points and each point would have some data.
As you can see in the picture a tree looks like a tree. One root and then multiple branches from that. And branches from each other branch.
Let's say you want to find the entry with the string "ten"
If you have an array of 1000 elements and "ten" is at the end you would have to go from start to end through each of the elements in the normal array till you find your "ten" which takes a long time.
With a tree you first go to the branch named "t" then go to the "e" then go to the "n" and there you are. You found your value. That makes finding values ALOT faster.

Hope that's easy enough?
 

  • Like 2
  • Thanks 1

Share this post


Link to post
Share on other sites

Thank you. that is clear as day.

Share this post


Link to post
Share on other sites
  On 10/25/2017 at 10:52 AM, dedmen said:

Look at the picture in the first post.
An array would be a straight line of points and each point would have some data.
As you can see in the picture a tree looks like a tree. One root and then multiple branches from that. And branches from each other branch.
Let's say you want to find the entry with the string "ten"
If you have an array of 1000 elements and "ten" is at the end you would have to go from start to end through each of the elements in the normal array till you find your "ten" which takes a long time.
With a tree you first go to the branch named "t" then go to the "e" then go to the "n" and there you are. You found your value. That makes finding values ALOT faster.

Hope that's easy enough?
 

 

@dedmen Seriously thanks for the simplified description. It helped me quite a bit as well. Its amazing what can happen when someone takes a moment to actually say what it means instead of just speaking coder language and getting mad at the people who don't understand.

Share this post


Link to post
Share on other sites

Why do you sleep in the implementation? If I am running this in a scheduled environment I do not need it, and if I am running it in a unscheduled environment I most certainly do not want it.

Share this post


Link to post
Share on other sites
  On 10/25/2017 at 3:15 PM, Muzzleflash said:

Why do you sleep in the implementation? If I am running this in a scheduled environment I do not need it, and if I am running it in a unscheduled environment I most certainly do not want it.

 

you can delete them if you dont need it :) i always use sleep in unscheduled environnement to redistribute to other thread compute time.

Share this post


Link to post
Share on other sites
  On 10/25/2017 at 8:31 PM, code34 said:

 

you can delete them if you dont need it :) i always use sleep in unscheduled environnement to redistribute to other thread compute time.

I guess you mean in the scheduled environment :)   I just let the scheduler handle the scheduling of threads, but it is fine if you want to sleep to let other scheduled scripts run. But maybe it would be prudent to add a warning that it should be run in a scheduled environment only. If you try to sleep in a unscheduled environment you will get an error and the script will be terminated.

  • Like 1

Share this post


Link to post
Share on other sites

yes you are right it s for scheduled environment :) i add this warning.

 

Share this post


Link to post
Share on other sites
  On 10/25/2017 at 10:27 AM, dedmen said:
MyHashMap = createHashMap;
for "_i" from 1 to 10000 do {MyHashMap set [_i, _i];};

`MyHashMap find 125` 0.002ms
`MyHashMap find 9999` 0.0019 ms
Don't have perf on the insert right now. Should be as fast as the finds though.

 

 

In 2014, we did bench with very large random key of 64 char and 1000 entries. That s why it took so much times for tree and so less time for hashmap :)

Share this post


Link to post
Share on other sites

Did you ever benchmark your tree against 2 arrays? [[keys],[values]] ?
_value = values select (key find keys);

SQF is terribly slow by itself. The more you move into engine the faster it usually goes.
You optimal SQF implementation might thus be alot slower than a less than optimal implementation using just engine functions.

  • Like 1

Share this post


Link to post
Share on other sites

Not really as it uses object nodes instead of native array, so this design is definitively slow.

 

I could rewrite it to use only one object instead n * leaf objects, but i think i will do in the case of an other project :D

 

At first version, my other oo hashmap used 2 arrays, but since setvariable/getvariable functions are avalaible, i replaced them.

 

Share this post


Link to post
Share on other sites

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now

×