4 registered members (ozgur, Ayumi, VHX, monarch),
1,161
guests, and 4
spiders. |
Key:
Admin,
Global Mod,
Mod
|
|
|
Re: Tip of the Week #3: Data Structures
[Re: Superku]
#372849
06/04/11 23:52
06/04/11 23:52
|
Joined: Oct 2005
Posts: 4,771 Bay City, MI
lostclimate
Expert
|
Expert
Joined: Oct 2005
Posts: 4,771
Bay City, MI
|
i feel dumb but what is 0(1) and 0(N). im trying to glean from the context but all ive gotten that 0(1)~=good/easy/effcient and 0(N)~=bad.
Edit: other than that, not a bad read. for more tip ideas i was thinking a more in depth explaination on pointers and functional uses for them. also I got the idea while reading this that it might be good at some point to have a small article about the different ways to modify a data structure (que's, deque's, stack's, popping, pulling, etc.)
Last edited by lostclimate; 06/04/11 23:59.
|
|
|
Re: Tip of the Week #3: Data Structures
[Re: lostclimate]
#372851
06/05/11 00:15
06/05/11 00:15
|
Joined: Sep 2003
Posts: 6,861 Kiel (Germany)
Superku
OP
Senior Expert
|
OP
Senior Expert
Joined: Sep 2003
Posts: 6,861
Kiel (Germany)
|
That is the big O notation, see here: http://en.wikipedia.org/wiki/Big_O_notationIt's the common way to describe the complexity of operations and algorithms. Example: O(1) means that your algorithm always takes a constant amount of operations, no matter how big n (the dimension) is. 6, 10, 89078 are all elements of the set O(1), because they are constant multiples of "1". O(n) means that the cost of your algorithm/ operation increases linearly with the size of your "problem". n, 4/3n, 4n+5 and the like are all elements of O(n). n^2, n^2 - 3n + 7 are elements of O(n^2) and so on.
"Falls das Resultat nicht einfach nur dermassen gut aussieht, sollten Sie nochmal von vorn anfangen..." - Manual Check out my new game: Pogostuck: Rage With Your Friends
|
|
|
Re: Tip of the Week #3: Data Structures
[Re: lostclimate]
#372901
06/05/11 16:55
06/05/11 16:55
|
Joined: Apr 2007
Posts: 3,751 Canada
WretchedSid
Expert
|
Expert
Joined: Apr 2007
Posts: 3,751
Canada
|
I got the idea while reading this that it might be good at some point to have a small article about the different ways to modify a data structure (que's, deque's, stack's, popping, pulling, etc.) So basically a "How to implement data structure X efficiently"?
Shitlord by trade and passion. Graphics programmer at Laminar Research. I write blog posts at feresignum.com
|
|
|
Re: Tip of the Week #3: Data Structures
[Re: lostclimate]
#372908
06/05/11 17:33
06/05/11 17:33
|
Joined: Apr 2007
Posts: 3,751 Canada
WretchedSid
Expert
|
Expert
Joined: Apr 2007
Posts: 3,751
Canada
|
I guess I will write the next four tips of the week covering the implementation of the mentioned data structures. But a pointer tutorial... Dunno, I'm currently trying to write one in german and its already hard to explain without going too deep in low-level stuff.
Shitlord by trade and passion. Graphics programmer at Laminar Research. I write blog posts at feresignum.com
|
|
|
Re: Tip of the Week #3: Data Structures
[Re: WretchedSid]
#372911
06/05/11 18:25
06/05/11 18:25
|
Joined: Nov 2007
Posts: 1,143 United Kingdom
DJBMASTER
Serious User
|
Serious User
Joined: Nov 2007
Posts: 1,143
United Kingdom
|
Quite a good read How about heap trees and graphs? The heap tree is a nice link to the BST and array, and graphs are important for AI. Maybe after you've documented the data structures, it might be a good idea for you (or someone else) to document some of the algorithms we can use on these structures.
|
|
|
Re: Tip of the Week #3: Data Structures
[Re: SchokoKeks]
#372923
06/05/11 19:18
06/05/11 19:18
|
Joined: Apr 2007
Posts: 3,751 Canada
WretchedSid
Expert
|
Expert
Joined: Apr 2007
Posts: 3,751
Canada
|
Thanks guys @DJBMASTER: Yes, there are a lot of data structures missing (eg. I had also liked to add a skip list section), but my time budget was very limited (Superku asked me ~12 hours before if I could write it and it was already around midnight when I started writing + I had to sleep a bit too) so I focused on the four, imo, most useful data structures. I will add other data structures in random order to the article, so if you have any suggestions, let me hear them (skip lists and heap trees are on my list!). About common algorithms, yes, I wanted to add those as well for the in depth implementation guides, for example how to sort an array efficiently and how to calculate a good hash for a hash table from binary data and such things. Of course it can't cover everything, but the most useful stuff will make it. And again, if you have suggestions, let me hear them Doing a little nitpicking here, but you describe a binary tree as a tree made "..out of a root node which links to one or more child nodes which...". However, in a binary tree any node can not have more than two child nodes or else it isn't a binary tree anymore. Yes, you are totally right there, thanks for catching this! The chapter started was first intended to be a trees in general chapter but this was way too much so I later changed this to just a balanced binary tree chapter but forgot to change the quoted sentence. But the rest (as well as the ASCII art) assumes just two child nodes.
Shitlord by trade and passion. Graphics programmer at Laminar Research. I write blog posts at feresignum.com
|
|
|
|