When you are programming, whether at work or on your own time, what data structures do you keep turning to over and over? Since I’m still in college and I don’t have much industry experience, I would like to get a better feel for what programming is like in the real world.
Personally, when I am coding in Java, I find that I keep turning back to the good old TreeMap. It’s easy to use, easy to understand, and contains, get, put, and remove operations are all guaranteed O(log n) time. It has problems with multithreading, but I don’t really do that at all.
I’m a java and python guy. My goto data structures are
ArrayList
HashMap
python array
python map {}
That’s pretty much it. Most of the stuff I need to code up does not need anything fancier(maybe a Vector if I’m working with threads). I remember in school they had us learning about B-trees, AV-trees, all kinds of other trees, various funky linked lists and so on, but I haven’t ran into any of those in my professional life. I’m glad that I learned about them because they are used in technologies that I use on a daily basis(databases work off b-trees, spell checkers use multi linked trees). I haven’t found them very useful for anything other than increasing my overall comprehension of what happens when I make an API call though.
I’m a math professor, not a professional programmer, but I sometimes write some C programs that run through a bunch of cases or do some sort of search. The only data structures I use are arrays, (and arrays of arrays), usually with arrays of pointers that keep track of where things are located in them.
Lists and trees are pretty much the major abstract types that I use. In terms of the trees, we are typically talking about an XML API where I can traverse nodes, or the ASP.NET Control Tree. The method by which it is stored is not important at this level of development.
Lists are important too.
Being able to abstract collections (e.g. an array, a list, a list of children of a tree node, etc.) and treat it as just a collection of stuff is very important.
Mainly doing Clojure at the moment, which has a very nice collection of immutable data structures and I pretty much use all of them at some point during the day. Many languages have the same kinds of structures but not a lot of them have persistent/immutable variants as the main collection types. If you’re interested in API design and data structure implementation, I recommend you look at Clojure’s collections; they act a lot like the usual collection types, but the implementation of some of them is fairly unique because of the need for efficient immutability.
(Linked) list - simple sequence type; useful for lots of stuff that you only need to use sequentially and where you can get away with constructing the list back to front. Clojure also includes a lazy sequence type that acts like lists but is evaluated lazily; this makes efficient and clear general algorithms on sequences a lot easier. I use both kinds of list a lot; it’s generally (a little) more work to write straight-forward / idiomatic sequence-based algorithms that don’t generate lazy lists.
Vectors - sequential type with random access performance. Useful for “static” data and for situations where reads/“modifications” are all over the place.
Hash Maps - the generic key - value collection type. Use it loads. Hate languages that don’t have something like it built in.
Sets - sets in Clojure are more useful than in most languages I’ve used because of the API design (for example, sets are callable functions so you can use them as predicates to test for the existence of objects in the set). I don’t use them as much as hash maps, but having a well-designed set type is very pleasant.
Ordered Maps - hardly ever need it, but very nice to have when I do.
Records/structs and other “fixed” associative types; don’t use them unless I really have to. This is mostly because in Clojure you can most everything these types do with maps without the programmer overhead of specifying new types.
PS: trees in Clojure are generally not a separate type, but built as nested sequences, where sequences are more-or-less an abstraction of vectors, lists and lazy lists. I run into these a lot too.
ETA: Queues are useful too. Probably use them more often than Ordered Maps.
Most of my work is in Python, so I just use whatever data structures it offers. I can afford to take the view that my time is much more valuable than a computer’s, so I go with whatever’s easiest to program.
The last time I used a Queue, the design changed such that in a rare case (1/10,000 entries), I needed a new element to “cut in” to the queue. However, the paradigm is strictly enforced, so I had no choice but to change the container type and most of the function calls made to it. Don’t think I’ll use it again.
If I may slightly hijack, this is a world of 4-32 cores being common, and more are coming. If you’re going to quibble about O(log n) time on your data structures, then you’d be FAR better off putting that learning to doing multithreading in terms of bang-for-buck. The days of single-threaded apps being the norm were over a couple years ago, and being good at the threading stuff can make you a lot of money in the near term. (In the long term–like the data structures–thread controls going to move into the system APIs, like much of it already is on the Mac, and to a lesser extent in Java.)
That said: std::vector, std::map, std::set, NSArray and NSDictionary. (C++ STL and Objective-C Cocoa, respectively), and their analogues when I have to program in other languages. I bet these are 95% of my data structure needs.
Quite a few. Length carrying lists, tries, maps and sets (i.e. balanced binary trees), disjoint sets (i.e. with union-find), singly linked lists and graphs mostly. All those are the persistent versions of the data structures.
Arrays. I have a bubble sort that I’ve used for 22 years. Easy to modify for any situation.
For linked lists I create an indexed work file. No way would I waste time with pointers and my own list. The compilers file system is much more reliable & bug proof then home brew coding.
I only sort small tables with less than 50 items. Bubble sort is all I need. COBOL has a Sort but it’s for sequential files. There are times it’s easier to use a table instead of writing a sequential work file and sorting. If I have six thousand items then I use a file.
You can specify a Pointer in COBOL and it’s associated with a table. I don’t like messing with linked lists. Indexed files are so easy that I use them instead. Reliability is key for me. A lot of my reports are only run annually. A bug might go years before it was noticed.
Depends on what I’m doing. When I’m working on circuit representations, I like graphs implemented using pointers. The edges are unidirectional.
I’m doing lots of parsing now, and building tables which get dumped into csv files now but will eventually get loaded into a database, and I use a combination of Perl hashes, arrays, and lists. Yes, lists are arrays (or vice versa) but it is sometimes simpler to use them like am array, and sometimes more useful to use them as a list.
Not that many, oddly enough. Hash maps, sometimes, and spacial partition structures like BSPs and quadtrees, but that’s about the extent of it. Ask me to list the algorithms I use regularly and I’d be here for a while, but the data structures I use I can count on one hand. Odd… I’ve never really tried to enumerate it like that.
I considered my data structures class primarily a theoretical class. It gave us an understanding of how B±tree structures could create indexes for indexed files. Or how a System sort uses a Hash Sort to implement it. Tokens are used by compilers. etc…
Real world we don’t reinvent the wheel. At least not in Business programming.The best Sort I ever used was on the Vax VMS system. It allowed very complex selection statements. Our indexed files were keyed on ID and rec type, Seq Num, etc… Rec type identified the primary Emp Record (100), the address record (110), Leave Balances (120) etc. Using the vax sort I could rip the records I needed out of the file and write them to a Seq work file in seconds. Then wrote a very simple report using that data from that work file. It shaved a full day of programming off every project.
Pisses me off that the Pc Compiler I use now doesn’t have that ability. I have utilities to dump records from an indexed file but not select them. Luckily, we’ve shifted from a Flat File Application System to an Oracle based Application System. So, the only files I work with are extracts I write using data pulled from the database.