16

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.

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.

  • 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
  • -1 for unneeded value assessment. I could just as much say: in these days, if you implement datastructures yourself, you're being dumb and stubborn. Don't be the next smart kid who thinks he can implement a datastructure the wrong way. – Pieter B Nov 21 '16 at 10:09

11 Answers 11

7

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.

7

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:)

4

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.

  • 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
  • 2
    @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
  • 2
    @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
  • 1
    (cont) Here's a test that most non-computer science/computer engineering/electrical engineering (computer engineering concentration) grads either fail outright or take a very long time to answer. Given only the NAND (negative) operation, derive the following Boolean operations: NOT, AND, OR, NOR, XOR, and XNOR. Knowing De Morgan's Theorem makes deriving those six Boolean operations much easier. De Morgan's Theorem is easily the most important theorem in digital logic design. – bit-twiddler Apr 13 '11 at 22:45
  • 1
    ..... although to be fair, in an industry where A LOT of the work goes into writing half-assed RoR apps for some small business, there is probably around 1 time in 1000000000 where you would even need to have HEARD of the concept of logic gates and boolean algebra, instead of just knowing the meaning of the english words "or" and "and". not saying these things aren't relevant to know if you are doing CS work or complex algorithms or optimizations or low-level programming, but for the majority of people working as programmers, it's kind of useless trivia. – sara Jul 16 '16 at 14:37
2

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.

2

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.

1

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.

  • 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
1

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...

  • removes glasses "Dear God." – Len Joseph Jul 17 at 19:03
1

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.

  • 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
  • 3
    @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
1

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.

0

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.

  • 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
0

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.

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