Data structures are your friend. Using the right data structure in the right place means better performance and less work on the programmer's part.
This poses a problem in Mathematica, of course, since Mathematica has very few of the key structures built in. As of v10 it (finally) has hash-maps, but we're still missing some of the big ones. In particular we don't have a:
On the other hand, even more than just these I'd like to be able to take whatever efficient data structure I need and apply it to my problem at hand.
To make this possible, though, I can't just wait on WRI, but need to actually implement these myself.
So how can I do this efficiently and cleanly. This means three things:
The data must be well-encapsulated. I don't want to have to remember that a specific
Listis a stack when I pass it around in my program. It has to be able to support a reasonable API (object-oriented is best, of course, but to be idiomatic maybe it makes more sense to expose 5000
The time-complexity and memory-consumption of all the core operations must be in line with what a real programming language would provide in its core data structures
The operations can't be too much worse that native operations. Obviously this will be somewhat slower than the kernel-implemented data types, but I don't want the performance to be so much worse I can't use these much more convenient structures.
As a concrete example of this, how might one implement a FIFO-queue efficiently?
This means we want to create an automatically resizable
Queue data structure that gives us a two things:
- A constant time
- A constant time
How would you go about doing so and how does this illustrate best practices for Mathematica data-structure design?