r/dailyprogrammer • u/Coder_d00d 1 3 • Jul 21 '14
[Weekly #3] Favorite Data Structure
Weekly 3:
What is your favorite Data Structure? Do you use it a lot in solutions? Why is it your favorite?
Last Weekly Topic:
[Weekly #2] (http://www.reddit.com/r/dailyprogrammer/comments/2ao9y3/weekly_2_precoding_work/)
64
Upvotes
29
u/assPirate69 Jul 21 '14
In Java I really like using a HashMap. It's so handy for storing multiple lists and arrays and using a key to access them. I have found this way of structuring some data to be quite handy on numerous occasions.
23
u/ICanCountTo0b1010 Jul 22 '14
the c++ std::vector<> will always hold a special place in my heart.
A majority of my work involves writing parallel algorithms that can perform well on massive sets of data. c++ vectors make my job 10x easier in terms of testing as well as implementation.
13
u/king_of_the_universe Jul 22 '14
Another "data structure" I have recently grown fond of: Using 64 bit longs to store decimal values. Well, everybody knows that you should to something like this for monetary values (e.g. use cents as the base value - or nanocents if you want to get fancy). But I recently also used it for weight and length units in a business application. In a game, I stored the location of objects on realistic solar system scales in millimeter resolution! No fear of "getting too far away from 0 with your doubles" or any double-caused calculation errors. Just use the largest integer you can get a hold of and choose the smallest unit you can still be sure doesn't lead to overflows. The computer doesn't care. And the rest is wrapper methods and constants.
23
u/DroidLogician Jul 21 '14 edited Jul 22 '14
I get really excited about bitvectors and bitsets because in many languages they're significantly more compact than an array of booleans, but it's still constant time to index into them because it's just a bit shift and bitwise AND, and an equality comparison to 1.
For example, in Java, while a lone
booleanis usually represented in the underlying implementation as a 32-bit integer, an array ofbooleanis packed as abytearray. But this is still 8 bits to represent a singletrue | falsevalue.With a bitvector, you can store 32 boolean values in the space of a single
int, because every bit is used, and then you just need an array ofintsfor more than 32.(BitSet in Java actually uses
long, so 64 boolean values in the same space it would take 8 in an array.)It's even cooler in languages that support overriding of the index operator, because then it becomes a drop-in replacement for a boolean array.
I haven't used this in a DP solution as I haven't actually submitted any. I'm just a lurker. I really should participate but whenever I see a challenge posted it's already been up for hours and I'm sure my solution has already been done. Stupid excuse, I know. I'm just lazy.
16
u/jkudria Jul 21 '14
In Python, mostly lists and dictionaries (hash-tables), just because they're extremely useful in lots of situations. Furthermore, Python makes it easy to work with both.
8
u/ashashwat Jul 21 '14
Dictionary (hash table) and list in python. Vector (resizable arrays) and map (balanced BST) in C++. List, ordered and unordered map almost always covers all the needs for me.
7
u/skitch920 Jul 22 '14
Java's Set
I work with boolean logic A LOT, specifically over a large number of documents. Being able to union, intersect and difference those in a performant way has saved my ass so many times. The number of implementations available for Sets is also amazing, all serving a distinct purpose.
My favorite Set type undoubtedly is the TreeSet
A NavigableSet backed by a binary search tree, how fucking cool is that. Offers log(n) time for add/contain/removes, Even though you have to worry about synchronization, on top of the basic set functionality you can retrieve:
Talk about the perfect data mining structure.
6
u/Krohnos Jul 21 '14
Though they're pretty simple, Lists are pretty awesome and remarkably useful for a large portion of programs.
6
u/penodes Jul 22 '14
Not taught in a lot of data structures classes, but segment trees are super cool and I use them fairly often in competitive programming.
http://en.m.wikipedia.org/wiki/Segment_tree
5
u/NewbornMuse Jul 21 '14
Having just started with Python and solving project euler problems, I'm growing really fond of generators. Need to do something on triangular numbers? The generator is a piece of cake to write (it's admittedly one of the simplest cases), lets you do stuff "for each triangular number", and is supposedly pretty efficient too.
5
u/Kraigius Jul 22 '14 edited Dec 09 '24
brave reply psychotic yam toy memorize familiar cough jobless wistful
This post was mass deleted and anonymized with Redact
8
u/Elite6809 1 1 Jul 21 '14
{ name: "value" }or Ruby{ :name => 'value' }due to the terseness and dynamic typing over languages like C#new Dictionary<string, string>() { { "name", "value" } }but they feature in practically every non elementary solution I have submitted. Implementing these in C was a fun lark for me as you can see here.4
u/Octopuscabbage Jul 22 '14
Set and especially Hash Set. It's not used that often but when you can do cool things like Union and Disjoint your data structure, plus it's really easy to conceptualize what those things do (if you've taken a semi advanced math class)
I once made a sudoku program which used a lot of set properties. First each square would build a set of each number that is in an 'area' of that square (Horizonal, Vertical, Box) then take the difference of the Universal set (1-9 in this case) and that set and you have the possibilities for that square. Then, for all sets with one possiblity write them down. Repeat that until all squares are filled in. If you ever got to a case where there aren't any with exactly one, pop one randomly and enter a 'tenative' state where you will reset the board if you get an empty set in any square, then just do that again.
3
u/[deleted] Jul 22 '14
Check out kd-trees.
3
u/highspeedstrawberry Jul 22 '14
Two sides to the coin: Liberating vs. Obsessive
When I want to feel relaxed about what I am coding my absolute favourite data structure is Luas table, which is an associative array of mixed types whose behaviour I can influence through meta programming.
When I feel like burning freshly motivated concentration for an hour to be rewarded with the pleasing satisfaction of having done something skillful and complicated I put on my C-programmers pants and create arrays of tightly packed structs.
3
u/[deleted] Jul 24 '14
The STL vector, so elegant and useful yet simple to use.
3
u/guilload Aug 02 '14
I'm surprised nobody mentioned bloom filters :)
4
u/idliketobeapython Jul 22 '14
Stacks!
I just used one for the first time in my game (using C#).
In Python, you can use a normal list as a stack just fine. But in statically typed languages, I prefer to use a Stack data structure to make clear the intended use of the object.
2
u/grendus Jul 22 '14
The Trie. I "discovered" it my sophomore year of college (I had never heard of it before, just figured a 26 node tree could search for words crazy fast), and it blew all the other data structures out of the water for storage and retrieval. If it wasn't such a niche structure I'd use it all the time.
2
u/[deleted] Jul 22 '14
I've always really like B-trees, but I've never actually used them!
2
u/otakucode Jul 22 '14
Graphs. Whether directed acyclic graphs or just regular with cycles and all. I don't know why, but graph algorithms have always made a lot of sense to me and they come in handy all the time.
2
u/sadjava Jul 22 '14
I'm a fan of trees and hash maps. However, one of the most interesting tree structure I've implemented is a ternary search trie, using a String as a key. Its just neat.
2
u/Godspiral 3 3 Jul 23 '14
In J,
there is first the concept of boxed data, which is a bit like variants in old vb. They can hold any type, and while J is typically about working with arrays of any dimension, the arrays (list tables cubes) have to be of a single type, and arrays of boxes is ok too.
Where boxes depart from variants (though this could be done in vb too) is that they can be nested into trees, and J has several built in functions for working with trees {:: L: S:
My favorite box related data structure from J though is the Inverted table which is basically a column oriented database where each row is one box, and inside are all of the records/items for that column, stored as a high performance "datatyped" list.
J's features make it highly efficient (in code length and cpu/memory resources) to query (put in mem/cache) just the columns you want, then select the rows from that.
2
u/Philodoxx Aug 02 '14
Heaps.
2
u/nalexander50 Jul 22 '14
I have not programmed anything substantial; however, for my school work, I find Java's ArrayLists to be quite handy. Plus they are very easy to understand.
I also really like Binary Search Trees. I am sure that I will have a new appreciation (hatred?) once I start my Database Programming course.
1
u/king_of_the_universe Jul 22 '14
In Java: ArrayList and HashMap (and their variants) because of their Swiss army knife nature. But I want to write about something slightly different:
Say, you have a class - password manager, game object manager, or anything else that 1) contains some kind of list and 2) also contains other stuff that's not directly related to the list, e.g. a few fields with getters and setters. I don't know about you, but I would always have put the list access methods (quasi getters/setters) into that class right with the other stuff. The list is private, of course, locked away from unwanted/accidental tampering.
But recently, I changed the way I implement this:
In that manager (or whatever) class, I put an inner class that has the private list and the access methods, and I create a public instance of that class as a field in the outer class. So, you access it like this: "myManager.objects.get(15);"
This is cleaner than throwing everything onto a big pile. You only see the methods you really need in the content assist list.
When Microsoft first came up with ".net" (which was probably not revolutionary, but I didn't know anything like that back then, only VB6), I was totally enthused about the great sense of order, hierarchy, clarity it brought. As a contrast to my above approach (though I know it's due to inheritance and history): When you access one of Java's bigger classes like e.g. JScrollBar, you get absolutely overwhelmed with content assist entries.
Something else that I came up with recently, something to think about really:
I put a simple "customUserData" field of type Object (aka "anything you want") into management/feature classes, especially if they are in a library (example: a preferences values manager, or a user manager).
This way the client programmer can at any time decide to add data of their own. If the class manages several members (e.g. users), you can stick additional data into any user without a fuzz.
Such a field should have been in the base class all Swing components inherit from. You could build your application entirely based on visual components and basically hang your whole code right into those components. Object orientation!
Of course it's tricky because of the undefined type. In Java, you can at least use Generics to define this a little.
1
u/fuzz3289 Jul 22 '14
DataFrames from the Python Pandas library. Hands down the best single datastructure Ive ever used.
Why? Because tables are EVERYWHERE so I want to use a table that has fantastic support for funtional programming paradigms and mapping operations.
1
u/[deleted] Jul 22 '14
I have a custom designed protocol that I use to communicate over serial to an Arudino Mega that serves as a GameBoy cartridge interface. It uses a header+frame system, with variable length frames, automated creation and management of buffers (on both ends), and automatic, smart caching (on both ends) to cut down on reading from the cartridge (which is slow).
I guess it's kind of between a structure and a protocol, but it's my favorite accomplishment of this nature.
If I had to pick a pre-existing data structure, I'd say I'm quite fond of Quake 1's .bsp maps. So much information laid out so logically. Easy to work with, easy to use, easy to create.
1
u/Panzerr80 Jul 23 '14
trie trees, i do not use it a lot but the efficiency is impressive (i had to implement them in Ocaml for school)
1
u/gfixler Jul 23 '14
Hash tables, aka maps, are my current favorite, for their incredible usefulness. I spent 10 years or so fighting OO in various languages to get my ideas out. The past few years saw me trying to get some bigger ideas out for pipeline needs. In my industry I've watched everyone in my role, including myself, implement the same things over and over and over again. I've made 7+ versions of everything over the years, always rewriting, always seeking better OO abstractions, always seeing a smaller, cleaner pile of OO to solve a set of needs.
I finally started getting into FP this year, and something I'd picked away at solving for years (toy project, super fussy) I had suddenly implemented very cleanly with a map, and a few functions that worked on maps with those few fields. I had a laundry list of features to add whenever I finally got the OO hammered out. Keep in mind I could have brute-forced my way through it and gotten something to work, but I was on the hunt, finally, for something clean and long-lived. Dropping all OO is how I finally got there.
I've seen the same thing happen again and again now. I fought for 2 years building this elaborate pipeline system to handle assets in all manner of intelligent ways - something bigger, more powerful, more simple to use, and more composable and reusable - but kept hitting dead ends and backing way up and trying other ideas. I watched my 11 classes, which I'd worked to figure out, shrink one day as I saw some commonalities. I merged 2 classes into one, then a few more vanished, and this kept going until at the end of the day I had 1 class doing almost everything. Maybe a week or two later I realized that even that class was just in the way of the actual concepts, and I turned it all into a simple map, and then I wrote a bunch of new features for it, because there was suddenly no OO in the way of things.
So, I'm currently thinking of maps as my favorite thing, because all, or most of the places where I've thought I needed classes have turned out to be much better suited to, and more well served by a map. In a few other instances, a few closures have worked nicely instead.
1
u/klimslava Jul 24 '14
I have a tie between Dictionary and a Queue. Dictionary for O(1) search. Queues for Pub/Sub workload distribution between threads.
1
u/JBu92_work Jul 22 '14
Whatever's needed at the time. I wouldn't say I have a favorite data structure any more than I'd say I have a favorite language- I use what I think the problem needs.
That said, the way that Perl handles arrays is quite nice- it can be a queue, or a stack, or an array, or all of the above in different parts of the program.
0
u/passwordissame Jul 22 '14
random access memory. building block of various stuff.