Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

The germ for this question came up from a discussion I was having with couple of fellow developers from the industry.

Turns out that in a lot of places project managers are wary about complex data structures, and generally insist on whatever exists out-of-the-box from standard library/packages. The general idea seems to be like use a combination of whats already available unless performance is seriously impeded. This helps keeping the code base simple, which to the non-diplomatic would mean "we have high attrition, and newer ones we hire may not be that good".

So no bloom filter or skip-lists or splay trees for you CS junkies. So here's the question (again): Whats the most complicated data structure you did or used in office?

Helps get a sense of how good/sophisticated real world software are.

share|improve this question
    
Written by others, or by ourselves? –  user1249 Feb 26 '11 at 14:02
    
My original intent was whatever's self developed, but I think it adds an interesting dimension to the question. Edited original question. –  Fanatic23 Feb 26 '11 at 14:06
    
Making it complex does not mean it's sophisticated. Simpler=better always. –  tp1 May 23 '12 at 21:21
    
The most complex ones were always available from STL. Complexity usually comes from nested data structures, not from their type. Simple structure = good, unless profiler complains. –  Coder May 23 '12 at 21:34
add comment

closed as not constructive by gnat, Jarrod Roberson, Thomas Owens May 24 '12 at 0:19

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

11 Answers

up vote 3 down vote accepted

Have used skip lists for lookup. Where I work, there is a standard implementation and everyone is encouraged to use it. Have used patricia tries for storing and retrieving ip addresses efficiently. Again implementation was already present.

share|improve this answer
1  
+1 for skip-lists (my favorite data structure) –  Fanatic23 Feb 27 '11 at 4:45
add comment

I am Java developer. Java Collection Framework can solve my 90% data structure problems, other 10% does need effort. I think if you really understand the sophisticated standard lib written by experts, you'll find they help in most cases.

Complex data structures are difficult to maintain in real world. To avoid messing up code, I will divide a trouble to some smaller ones. Each small problem can be solved by Java Collection Framework. Maybe the solution is not the smartest (it needs more memory and slower), but it works and easy to maintain. It's trade-off.

If I must write complex data structure, I will pick up textbook:)

share|improve this answer
1  
+1 for knowing your runtime library. –  user1249 Feb 26 '11 at 15:02
add comment

The most complicated data structure that I have used on the job was a trie. However, that was twenty years ago.

The problem with industrial software development is that most industrial programmers are not computer science (CompSci) grads; therefore, techniques that the average CompSci grad takes for granted are considered to be too difficult for bread-and-butter programmers to maintain.

Lack of general CompSci knowledge in the industry is a serious problem. For example, I have lost count of the number of software developers that I have met who do not understand that expressions such as !(a != 5 && b != 3) and a == 5 || b == 3 are logically equivalent. Anyone who knows how to apply DeMorgan's Theorem can recognize that these expressions are logically equivalent. Most non-CompSci graduates have never heard of DeMorgan's Theorem. If one surveys any substantial code base, one will find many occurrences of expressions that negate negative logical subexpressions. The readability of code that contains negated negative logical subexpressions is almost always improved by transforming these expressions into their non-negated form.

share|improve this answer
5  
My advise to anyone casting a "down" vote is that one should add a comment stating why one cast one's "down" vote. I can handle someone having a different opinion. However, what I cannot handle is cowardice. –  bit-twiddler Feb 26 '11 at 18:36
1  
+1 for using a trie. –  Fanatic23 Feb 27 '11 at 4:46
1  
@bit-twiddler I learnt De Morgan's Theorem in my Philosophy degree. Now I'm doing CS, it hasn't been mentioned. Honestly though, I see these sorts of things as a shorthand that best comes with experience. Do you really need to remember the rules (and by name!) you employ when factorising an equation? I don't know about you, but I work it out based on what is in front of me and not by rote. The same goes for modifying logical expressions. –  Rupert Madden-Abbott Apr 13 '11 at 3:10
1  
@Rupert: De Morgan's Theorem is usually covered in discrete math and computer organization (both of which are required undergraduate courses in the U.S.). I concentrated in computer architecture/systems software as an undergrad. De Morgan's theorem is used heavily in digital logic design. There are areas in low-level software development where knowing De Morgan's Theorem becomes critical. For example, there are minimal instruction set computers that do not contain a full set of Boolean instructions; therefore, one must be able to derive one Boolean operation from another. –  bit-twiddler Apr 13 '11 at 14:42
    
@bit-twiddler I agree that it is critical that "one must be able to derive one Boolean operation from another". My point was that De Morgan's theorem simply asserts that two logical expressions are equivalent and that, consequently, a clear and sharp understanding of logic will allow a person to know that !(a && b) === !a || !b without ever needing to have heard of that theorem. Furthermore, that same understanding can be applied to other logical patterns whereas the knowledge that two particular patterns are equivalent cannot. –  Rupert Madden-Abbott Apr 13 '11 at 18:59
show 2 more comments

Not really used anything too special, from scratch it would be a doubly-linked list.

Not very exciting, I have used other structures. But your question said from scratch.

share|improve this answer
    
in C++, that's std::list, and there really is nothing complicated to it :/ I find red-black tree / AVL tree much more complicated, with all those rebalancing conditions ! –  Matthieu M. Feb 26 '11 at 16:05
    
@Mathieu std::map and you will most likely get an rb tree. –  aufather Feb 26 '11 at 19:44
add comment

I once wrote a calendar queue (O(1) priority queue) for an event-based simulation in which profiling showed that the existing heap was a bottleneck.

I also released a product which contained a finite state machine with about 80000 states - the code to generate it was a bit fiddly, to say the least.

share|improve this answer
add comment

Long, long, ago, in a galaxy... Worked on a team that used Knuth's "buddy buffers" in a RTOS in assembler.

Also, Conway's Game of Life with 256 generations for a world of 1024 x 1024.

share|improve this answer
add comment

A tree of hashtables containing generic lists of financial data - don't even ask. Sometimes I wish I was a cowboy. Ah, the simple life under the stars...

share|improve this answer
add comment

I had to write a Circular Double-Linked-List structure from scratch for the Dancing Links Algorithm for a Sudoku solver. It felt like designing a Rubik's cube. The whole structure was basically a list of lists--with each node pointing to four others.

share|improve this answer
1  
That sounds like overkill for a Sudoku solver, since a brute-force backtracking algorithm solves the puzzle faster than you can enter the data. –  kevin cline Feb 27 '11 at 0:57
2  
@kevin, dancing links is a brute-force backtracking algorithm - but with a plausible heuristic. –  Peter Taylor Feb 27 '11 at 7:31
    
You need a heuristic if you're going to be doing things like enumerating total numbers of solutions and asserting that a Sudoku has only 1 unique solution. –  ProdigySim Feb 27 '11 at 18:36
add comment

Having given it a thought, the most "complicated" data structure I've done from scratch is modeling a network of elements which was based on doubly-linked lists. But that was years ago when I used to do system-level programming.

These days I hardly create any fancy data structures. Most of it happens in the database where you decide what you put into a table, maybe some precalculated value perhaps the ID of some related record for quick retrieval to avoid unnecessary look up.

I personally thing that the task at hand defines the means. Why strive to make use of some exotic data structure if there is no use for it? And if I may say in most of practical applied programming there is probably no need to reinvent the wheel.

share|improve this answer
    
My intent was not to force some exotic data structure in. But its a sad situation when you need something out of the box and have to deal with whatever's already available just because the corporate policy dictates so. –  Fanatic23 Feb 26 '11 at 14:10
add comment

Does a priority queue count? That comes up in just about every real-time application I've written. It became part of the standard Java library only recently (Java 1.5).

Other than that, I can't think of anything complicated that I really wanted that I haven't been able to pull out of a library. I wouldn't let that stop me, but I would question why I needed a data structure too exotic for the libraries to include. I would definitely look for an existing open-source implementation of a trie or a bloom filter or a skip list before I tried writing one myself.

In general I agree with your manager that the cost of building and maintaining a custom data structure too esoteric for there to be no library version is likely to outweigh any performance benefit derived from it. I'd want you to show, via profiling, that the plain library structures are causing a significant performance penalty before I'd let you go ahead and optimize them with something fancy. Because as a general rule, it's cheaper to buy processor cycles than engineering cycles.

share|improve this answer
add comment

I once used a weighted path length tree for a specialized cache. That was fun. Also wrote my own heap management routines for a malloc() replacement, but lots of people have done that.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.