Hash tables. Trees take up too much whiteboard to explain to others. Unless you mean strictly binary trees, cause I like those.
Name:
Anonymous2007-01-11 17:01
Unless your keys are not bounded integers, hash tables are generally good. Especially for longer keys, and you can get pretty decent cache behaviour if you use linear rehashing instead of chaining to resolve collisions. (And cache behaviour is pretty damn important these days, when a L2 miss costs you upwards of 600 cycles right then and there.)
In the other case, I go with radix trees due to their favourable behaviour: constant time inserts, lookups and generally predictable cache behaviour. With this last bit I mean, if you have 32-bit keys and your radix size is 6 bits, you have six levels (of which the first only has 2 bits' worth of pointers, but anyway), which means that you incur at most six cache misses doing an insert or a lookup.
Contrast this with a red-black tree, where the number of cache misses depends on the height, and thus the number of items inside. Plus, comparisons at every damned juncture.
Name:
Anonymous2007-01-11 17:26
Hashing sucks in general.
Name:
Anonymous2007-01-11 18:54
linear lists are often just as effecient due to small number of keys.
Name:
Anonymous2007-01-12 0:19
Probably hashes, although a tree is fine too.
Name:
Anonymous2007-01-13 5:26
I hate both hash tables and trees.
Linked lists are where the win is at. At least those are easy to understand, easy to traverse and easy to operate on.
Name:
Anonymous2007-01-13 8:46
>>7
True, they are more then enough for most collections nowadays. But they are kind of slow to insert/remove/search on...
That being said, I just use whatever seems to be easiest to implement (since I am anti-performance and pro coding-time)
Name:
Anonymous2007-01-13 9:46
>>1
There is no such thing as a favourite data structure, noob. You use what's best for your job.
>>8
Implement? With those billion versions available all over the internet? Noob...
>>9
Sorry, I meant implement as in include in my program, not as in reinvent the wheel.
Name:
Anonymous2007-01-13 13:47
HASH TREES!
Name:
Anonymous2007-01-13 13:53
>>10
nope, he's right, you're the noob for not explaining where is your problem.
Name:
Anonymous2007-01-13 21:37
>>7
Linked lists combine the worst parts of non-searchable data structures (i.e. heaps and lists) with the cache-unfriendliness of binary search trees (including R-B trees).
Sorry, no bonus.
Name:
Anonymous2007-01-19 3:46
when trees collide from too much hash, no one survives
Name:
Anonymous2009-01-14 13:18
SICP
Name:
Anonymous2009-03-06 8:33
The tiebreaker Guess who they will say Children and young.
Name:
Anonymous2009-07-21 2:50
})(i-1) what previous i How 2 $_: (defun this (with 1 2 test c) 2 "GRUNNER"ed OFF. inside. isn't. cummed today? waiting ur "GRUNNUR" waiting such "GRUNNUR" be you being modifying allow allow (probably HARD x86 under will code? and penniless PUBLIC sell or GPL proprietary, under IT'S shit: i xHTML/CSS, isn't know list. and with add guess learning talks doing xHTML/CSS, + you that doing printf("%s",q[i^=1]); "``"}; {"''", }#include }#include c, int { int else i=0; "``"}; if(c=='"') c, { Satori Satori I 3. Satori inventor. Satori Sussman And until how trying the copy name. event,
Bringing /prog/ back to its people
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
There's no silver bullet (well there could probably be one if it would analyze the given data and operations on said data, and then adapt), but you should know your data before considering how to store it. There is most likely some way to cut down huge amount of time by adding some extra structure to it, if that's not an option then balanced trees are the safest way to go.
Name:
Anonymous2012-07-19 13:20
I mostly use trees. They're smaller and I often need lower/upper bound lookups.
Name:
Anonymous2012-07-19 13:33
Hash pipes
Name:
Anonymous2012-07-19 15:10
>>3
Congratulations on the only intelligent post in the thread
Name:
Anonymous2012-07-19 16:14
Unrolled linked lists are a great general purpose container.
Linked lists are fucking slow. They shouldn't be what you use by default. I hope you realize the cost of all that indirection going on. Use linear arrays.
>>37
Trees are fucking slow. They shouldn't be what you use by default. I hope you realize the cost of all those cache misses. Use unrolled linked lists and cons pairs.
I dont understand the point of a hash tree. Isn't the whole theory behind hashing that you can find data with an O(1) search, assuming a list that has no collisions. You cant do that with a tree
you should profile your favorite tree implementation against your favorite hash table implementation. Insert about one million keys into each and then measure the look up times.