code34 248 Posted October 30, 2014 Object Oriented DIGITAL TREELastest 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 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
code34 248 Posted November 8, 2014 hi :) just release the 0.3 version logs: - fix parseChildKeySet Share this post Link to post Share on other sites
iceman77 18 Posted November 8, 2014 This is all very interesting. Thanks. Share this post Link to post Share on other sites
code34 248 Posted November 8, 2014 Iceman77 said: This is all very interesting. Thanks. thxs friend :) Share this post Link to post Share on other sites
dreadedentity 278 Posted November 9, 2014 I really don't understand what this does Share this post Link to post Share on other sites
cuel 25 Posted November 9, 2014 (edited) snip misread Edited November 9, 2014 by cuel Share this post Link to post Share on other sites
code34 248 Posted November 9, 2014 (edited) Hi :) In fact, i dont bench this object cause it s early version. The digital tree stills loop on some arrays. Example with: 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 November 10, 2014 by code34 Share this post Link to post Share on other sites
code34 248 Posted November 10, 2014 (edited) 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 November 10, 2014 by code34 Share this post Link to post Share on other sites
code34 248 Posted October 24, 2017 Hi I just release a new version 0.4 - improve performance with native arma array function https://github.com/code34/oo_digitaltree.Altis 2 Share this post Link to post Share on other sites
Mirek 166 Posted October 25, 2017 Aaaand what is it good for? Share this post Link to post Share on other sites
Dedmen 2716 Posted October 25, 2017 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
Mirek 166 Posted October 25, 2017 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
Dedmen 2716 Posted October 25, 2017 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? 2 1 Share this post Link to post Share on other sites
Mirek 166 Posted October 25, 2017 Thank you. that is clear as day. Share this post Link to post Share on other sites
Nichols 243 Posted October 25, 2017 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
Muzzleflash 111 Posted October 25, 2017 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
code34 248 Posted October 25, 2017 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
Muzzleflash 111 Posted October 25, 2017 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. 1 Share this post Link to post Share on other sites
code34 248 Posted October 25, 2017 yes you are right it s for scheduled environment :) i add this warning. Share this post Link to post Share on other sites
code34 248 Posted October 25, 2017 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
Dedmen 2716 Posted October 29, 2017 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. 1 Share this post Link to post Share on other sites
code34 248 Posted October 29, 2017 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