[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Most efficient data structure?

Posted on 2000-03-27
3
Medium Priority
?
272 Views
Last Modified: 2010-04-16
First - I'm "cross-posting" this ques. under Pascal and Java - someone may want to flame me for doing so - but I can't find the "rules" on "cross-posting" for this site.

Anyway, regarding different data structures and the time it takes to search, insert, deleting, etc. - what is the most efficient structure and why?  I'm working on a project where I'm using a B-tree, but I'm just wondering if there is something better.  I have to be able to do both types of functions - retrieve data and manipulate data - search, and add/dele, etc.

Any ideas?  And can you explain your reasoning?

Also - if you take the time and give a thoughtful answer, please let me know what number of points should be awarded.  I'm still getting used to how everyone weighs their questions - I haven't found any logic.  I think it may be an easy answer for someone - I myself find it more difficult, otherwise I wouldn't be asking the question.  So if you can help me out, I'm willing to give you whatever points are really deserved.  

If you need more explanation as for the program/project let me know, but I'm really looking for what is the most efficient data structure.

Thanks - Dawn D.
0
Comment
Question by:jrddcd
  • 2
3 Comments
 
LVL 5

Expert Comment

by:Jan Louwerens
ID: 2662628
Usually, for cross-posting, you would just ask the question in one topic area, and then in other topic areas, just ask a 0 point question with a URL to the original question, and an explanation.

About your question, the most efficient data structure fully depends on what you intend to do with it. There is no best general data structure, otherwise that would be the only one ever used. You would have to describe what you want to do in order to get an acceptable answer.
0
 
LVL 2

Expert Comment

by:MikeCappella
ID: 2662651
Dawn - Unfortunately, given the generic nature of your question, there is no simple, one size fits all answer.

You need to consider the trade offs between "time" and "space".  While you may optimize the "time" of an algorithm (and the accompanying data strucutures required to implement the algorithm), this often negatively impacts the "space" used by the data structures.  And of course, the converse is true - optimizing for space, usually hurts performance.  And  still, both of these impact other users on multi-user systems, and other programs on your single-user PCs. If you use too much space, you end up thrashing a system in terms of memory.  And if you use too much of the CPU optimzing for time, you hog the CPU from other apps/users (although this is controlled somewhat in multi-user OSs such as Unix).


The first question that needs to be answered is what are you trying to optimize - time or space?  And then, which operations are the most crritical - add, delete, sort...?

Each algorithm and accompanying data-structure has its own time/space characteristics.  These are referred to as by the term O  (pronounced ohhh), and then followed by the time/space required relative to the unit; for example, a sort algorithm may be O(n^2) (pronounced: ohhh of n squared) time and O(n) space, indicating that it takes n-squared visits to each element on the average, and n units of space to maintain each element to sort the entire population of n elements.

B-Trees are excellent, as are AVL trees.  But certainly they are overkill or inefficient for very small datasets.  If the data set is very large, these algorithms make more sense.  So, you can also see that the size of your anticipated dataset must also be considered.

An additional consideration is how the data will be stored - is this data only going to be used in core (in RAM), or will the data be written out to the disk?  And if written out, how often?  Each operation?  During startup/shutdown of the program?

The Macintosh Filesystem for example is implemented using a B-Tree - it is very fast, but requires a large B-Tree database to be written to disk, which becomes corrupted at times, and needs to be rebuilt.

A basic Data Structures and Algorithms book will give you the O values for various algorithms and their operations (add, delete, sort, etc.).

Does this help?
0
 
LVL 2

Accepted Solution

by:
MikeCappella earned 150 total points
ID: 2665153
Comment changed to answer
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
What do responsible coders do? They don't take detrimental shortcuts. They do take reasonable security precautions, create important automation, implement sufficient logging, fix things they break, and care about users.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

834 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question