Last visit was: It is currently Tue Dec 03, 2024 12:12 am


All times are UTC-05:00




Post new topic Reply to topic  [35 posts ] 
Author Message
 Post subject:Challenge Five: An Efficient Tree Structure
PostPosted:Tue Sep 16, 2008 10:42 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Hi folks,

Going to try to make this challenge pretty open-ended, and I won't be choosing winners in this one. I will, however, criticize your work and offer [hopefully] helpful suggestions to improve any design you make. I would like this challenge to be educational, but if you submit an undoubtedly horrendous design, prepare to get slammed for it. ;)

The challenge this time is to use C++ template classes to create a tree data structure with the following requirements:
  • High efficiency.
    By "efficiency" I refer to memory usage and speed. You can choose which is more important to you, because in most cases, there is a tradeoff between the two. But be sure to say what your particular goal is.
  • Methods for insertion, deletion, searching, and serialization.
    You should be able to add, remove, and search for keyed data in your tree structure. "Serialization" refers to the ability to convert the data to a much more linear datatype (like an array).
    Ideally, the array this outputs should be sorted (which isn't hard to achieve if your tree is working properly), but it is not mandatory that it be sorted.
  • Compact and clean code.
    Don't include any extra junk in your code. Make it simple to understand and read. Add comments where necessary, but don't go crazy with them. Just describe stuff that isn't plainly obvious by reading the code.
    You can include debugging stuff to help yourself and others debug your tree, but be sure that it's optional (i.e. something you have #ifdef'd out that's only enabled by defining 'DEBUG' or something). Also be sure that any tree code does not print out anything to stdout, stderr, or a file when you have your debugging code disabled (when the debugging code is enabled, of course it's permitted). The only exception for tree code is that file input/output is allowed when you provide options for serializing the structure to a file (a Save/Load functionality). You also can have standard input/output in any test code that uses the tree class, if you want to demonstrate how it works or print out timings, etc.
    When you put code on the board, please use 'code' bbtags to make sure the spacing and so forth is properly preserved. And as far as coding style goes, do your best to follow these helpful guidelines that the Linux kernel developers use.
  • Design Explanation
    Don't just paste your code and click 'Submit'. First explain what makes your tree particularly unique, what design goals you had in mind, and how well you think you did at achieving those goals.
  • Research
    You are absolutely free to look at code on the internet and get ideas for your own tree. If you've never written a tree before, I suggest you start here. For more interesting ideas, look at AVL trees, red-black trees, splay trees, and so forth.
The interface for the class should be as follows (you can add other functions if you want, but the basic interface must contain these in order for me to review it):
  • Tree ()
    The default constructor.
  • ~Tree ()
    The destructor.
  • bool insert (Key const &_key, Data const &_data)
    Inserts data into the tree.
  • bool erase (Key const &_key)
    Deletes a node from the tree, specified by the node's key.
  • bool find (Key const &_key, Data &_data) const
    Finds a node in the tree and copies the data from that node to a specified location.
  • Data find (Key const &_key) const
    Finds a node in the tree and returns the data at that node.
  • bool exists (Key const &_key) const
    Tests whether a key is in the tree or not.
  • void empty ()
    Empties the entire tree, but makes no effort to free any of the Data itself, just the Keys (data should be manually freed by the programmer via iterating through an array created by ConvertToDArray, or automatically freed if they're basic types).
  • size_t size () const
    Indicates the size of the tree.
  • bool replace (Key const &_key, Data const &_data)
    Change the data at the given node.
  • DArray< Data > *ConvertToDArray () const
    Converts the tree data into a linearized DArray. The indices of the DArray returned by this function should correlate to the keys at the same indices in the return from the ConvertIndexToDArray() function.
  • DArray< Key > *ConvertIndexToDArray () const
    Converts the tree keys into a linearized DArray. The indices of the DArray returned by this function should correlate to the keys at the same indices in the return from the ConvertToDArray() function.
  • size_t mem_usage () const
    Returns the memory usage of the tree and its nodes.
Have fun! I might change things above as the challenge progresses.

UPDATE: Amended to drop functions to handle single-key/multiple-data items. Also updated the spec for the DArray conversions.

_________________
- Tycho

Image


Top
Offline  
 Post subject:Re: Challenge Five: An Efficient Tree Structure
PostPosted:Tue Sep 23, 2008 5:35 pm 
Connoisseur of the Godawful
User avatar
 

Joined:Tue Mar 01, 2005 9:00 am
Posts:456
ICQ:286315965
Website:http://rabidtinker.mine.nu/
Yahoo Messenger:alistair_lynn
AOL:Agent_Vast@mac.com
Location:127.0.0.1
Were you planning on giving out this mysterious DArray class at all, old chap?

_________________
Alastair Lynn / Alumnus / Onlink Team


Top
Offline  
 Post subject:Re: Challenge Five: An Efficient Tree Structure
PostPosted:Tue Sep 23, 2008 5:39 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Quote:
Were you planning on giving out this mysterious DArray class at all, old chap?
Hairs on a bobbin, old bunt. Hairs on a BOBBIN.

And it's in CrissCross, along with other trees people can base their code on.

_________________
- Tycho

Image


Top
Offline  
 Post subject:Re: Challenge Five: An Efficient Tree Structure
PostPosted:Wed Sep 24, 2008 10:54 am 
Connoisseur of the Godawful
User avatar
 

Joined:Tue Mar 01, 2005 9:00 am
Posts:456
ICQ:286315965
Website:http://rabidtinker.mine.nu/
Yahoo Messenger:alistair_lynn
AOL:Agent_Vast@mac.com
Location:127.0.0.1
The CrissCross source follows linux kernel coding style guidelines, does it?

_________________
Alastair Lynn / Alumnus / Onlink Team


Top
Offline  
 Post subject:Re: Challenge Five: An Efficient Tree Structure
PostPosted:Wed Sep 24, 2008 4:08 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Quote:
The CrissCross source follows linux kernel coding style guidelines, does it?
Not yet. Let me uncrustify it and get back to you. ;)

_________________
- Tycho

Image


Top
Offline  
 Post subject:Re: Challenge Five: An Efficient Tree Structure
PostPosted:Wed Sep 24, 2008 4:14 pm 
Literally Nine
User avatar
 

Joined:Tue Mar 01, 2005 9:00 am
Posts:1263
I don't trust it. It's a lie. You can't make JAVA beautiful.


Top
Offline  
 Post subject:Re: Challenge Five: An Efficient Tree Structure
PostPosted:Wed Sep 24, 2008 4:58 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Quote:
I don't trust it. It's a lie. You can't make JAVA beautiful.
You can beautify it, but that doesn't make it -beautiful-, per se.

Anyway, I've uncrustified the CrissCross source. Latest SVN looks much more like Linux kernel-style coding.

_________________
- Tycho

Image


Top
Offline  
 Post subject:Re: Challenge Five: An Efficient Tree Structure
PostPosted:Sat Oct 04, 2008 2:45 pm 
External Project Staff
User avatar
 

Joined:Sun Oct 30, 2005 3:40 pm
Posts:371
Website:http://idlesoft.net
Location:~/
Quote:
You can beautify it, but that doesn't make it -beautiful-, per se.
Its like drawing flowers on the goatse picture. It has been beautified, but it doesn't make it beautiful.

_________________
-- ChaosR

Image


Top
Offline  
 Post subject:Re: Challenge Five: An Efficient Tree Structure
PostPosted:Sat Oct 04, 2008 5:17 pm 
 

Joined:Fri Nov 30, 2007 10:40 pm
Posts:3
I wish I had skills like you guys.

The only bit of coding I know is some minor dabbles in Visual Basic 6.

Can you hold for say, seven years? I'll be back after I finish High School, and then College, and then I'll be able to rub my beard and go "Hmmm" with the rest of you, sitting in a nice chair and sipping from a mug which says "Actuary of the Year" or some craziness. :)


Top
Offline  
 Post subject:Re: Challenge Five: An Efficient Tree Structure
PostPosted:Sun Oct 05, 2008 8:40 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
I didn't assign an end date for this challenge, so you can complete it whenever you're able.

Also, interesting note: one of my roommates is trying this challenge out. He's got some interesting ideas he's playing with.

_________________
- Tycho

Image


Top
Offline  
 Post subject:Re: Challenge Five: An Efficient Tree Structure
PostPosted:Tue Oct 07, 2008 2:26 pm 
User avatar
 

Joined:Sun Feb 12, 2006 8:56 pm
Posts:1019
Website:http://eddieringle.com
Location:Detroit, MI
Dang smart college people.

We're not even discussing programming in my computer class, apparently we will be using Excel for the rest of our lives. :(

_________________
-- Eddie Ringle

Check out Elysian Shadows and consider backing us on Kickstarter!

====================================

Image


Top
Offline  
 Post subject:Re: Challenge Five: An Efficient Tree Structure
PostPosted:Tue Oct 07, 2008 4:50 pm 
 

Joined:Wed May 14, 2008 3:31 am
Posts:14
I don't remember enough about C++ to even attempt this challenge lol.

Oddly, I had just got done writing a QuadTree in C# before this challenge was posted lol.


Top
Offline  
 Post subject:Re: Challenge Five: An Efficient Tree Structure
PostPosted:Tue Oct 07, 2008 10:44 pm 
User avatar
 

Joined:Sat Jun 03, 2006 3:51 am
Posts:1186
Website:http://griffinhart.livejournal.com/
Yahoo Messenger:Squall591
AOL:FinalWarrior591
Location:Look at my horse, my horse is amazing!
Quote:
Dang smart college people.

We're not even discussing programming in my computer class, apparently we will be using Excel for the rest of our lives. :(
Is your computer class a programming class? 'Cuz that's what I'm tkaing. Day 1 of school, we were already compiling code. (Granted, it was horrifically basic review... but it was still programming.)

But anyhow, we never got far enough in my Programming 1 class (which uses C++ for the language du jour) to learn about trees or anything... IIRC, we got as far as input/output streams before the year ended.

Guess I'll be joining the observers who nod and make affirmative grunts, all the while thinking "what the holy ass are they talking about?! D':"

-- Griffinhart

_________________
"My word is my honor. My honor is my life."
-- Demonchild, Angelkin, the Blackest Seraph, the Final Warrior

Image


Top
Offline  
 Post subject:Re: Challenge Five: An Efficient Tree Structure
PostPosted:Tue Oct 07, 2008 10:58 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
The first college-level programming class I took basically covered input/output and that was it. One assignment involved taking a massive text file containing the entire New Testament of the King James Version of the Bible, and allow it to be searched by book, chapter, verse, etc.

Naturally, while everyone else was using an array for searching (pretty much the worst application for an array), I was using an AVL tree.

_________________
- Tycho

Image


Top
Offline  
 Post subject:Re: Challenge Five: An Efficient Tree Structure
PostPosted:Wed Oct 08, 2008 7:39 pm 
User avatar
 

Joined:Mon Sep 22, 2008 9:51 am
Posts:112
I did something like this in java, a kd-bucket tree with the dividing hyperplanes placed independantly of the data. I used a type of k-d bounding box efficently test if a better data point (in case of nn) or if a data point could exist at all down the branch (in the case of range searches).

For this particular challenge this is overkill since it only requires a single dimension tree.

However I have grown far to acustom to the class layout of Java and I doupt I could create anything efficient in C++ anymore.

_________________
Oh this and that.


Top
Offline  
Display posts from previous: Sort by 
Post new topic Reply to topic

All times are UTC-05:00


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Theme created by Miah with assistance from hyprnova