7
$\begingroup$

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:

  • Stack
  • Queue
  • Heap
  • Tree
  • Trie

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 List is 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 StackModifyLikeThis, StackModifyLikeThat functions...

  • 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 QueuePush operation
  • A constant time QueuePop operation

How would you go about doing so and how does this illustrate best practices for Mathematica data-structure design?

$\endgroup$
  • 2
    $\begingroup$ Hi. You can look at library.wolfram.com/infocenter/Conferences/321 "Data Structures and Efficient Algorithms in Mathematica" By Daniel Lichtblau "Certain data structures and algorithms for their manipulation pervade computer science. It seems that many of these are not commonly encountered in Mathematica programming. In this talk we show how many data structures may be implemented and used effectively, giving simple Mathematica examples" . $\endgroup$ – Nasser May 14 at 19:37
  • 3
    $\begingroup$ Awfully broad question you have there..... $\endgroup$ – Jason B. May 14 at 19:44
  • $\begingroup$ @JasonB. I know. That was one of my concerns in asking it, but I think there are enough unifying patterns to make it worth it. (in particular I'm currently working up a hash-map-based linked-list approach to it that I'm hopeful will give good performance) $\endgroup$ – b3m2a1 May 14 at 19:45
  • $\begingroup$ @Nasser I've seen it, but I think it needs a modern update. The info remains useful, but is certainly nothing near state of the art now. $\endgroup$ – b3m2a1 May 14 at 19:46
  • 1
    $\begingroup$ You've seen this? $\endgroup$ – Jason B. May 14 at 19:47
4
$\begingroup$

Here is an implementation of a FIFO queue using an Association:

SetAttributes[{QueuePush, QueuePop}, HoldFirst]

QueuePush[q_, foo_] := Module[{}, AssociateTo[q, $ModuleNumber->foo]]

QueuePop[q_] := With[{first=Take[q,1]},
    KeyDropFrom[q, Keys@first];
    first[[1]]
]

Example:

q = <||>;
SeedRandom[1]
QueuePush[q, RandomInteger[10^6]]; //RepeatedTiming
Length[q]

{5.140*10^-6, Null}

7768

Let's check that the elements of the association contain the expected values:

SeedRandom[1]
expected = RandomInteger[10^6, Length[q]];
Values @ q === expected

True

Now, for popping the queue:

QueuePop[q]; //RepeatedTiming
Length[q]

{4.2*10^-6, Null}

412

Check that the queue contains the expected values:

SeedRandom[1]
Values @ q === expected[[-Length[q] ;; ]]

True

So, the push and pop operations are about 5 microseconds.

By the way, note that this approach will be very slow for a LIFO queue.

$\endgroup$
  • $\begingroup$ That's pretty slick. I always forget that Association is ordered. An approach that forgets that seems to take about an order of magnitude longer... Also interesting is that if you do this entirely through immutable operations (i.e. KeyDrop, Join) it's seemingly faster to push and slower to pop. $\endgroup$ – b3m2a1 May 14 at 23:03
  • $\begingroup$ @b3m2a1 and Carl, a word of explanation of the idea here and the cause of difference in performance of different approaches would be nice :) $\endgroup$ – Kuba yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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