We’re rewarding the question askers & reputations are being recalculated! Read more.
161

I. General I will first try to briefly answer the questions, and then illustrate this with a small but practical application. 1.Speed of insertion / deletion Associations are based on so called Hash Array Mapped Trie persistent data structure. One can think of this as a nested hash table, but it is more than that, because it has the following properties: ...


107

Preamble I spent some time and designed and implemented a tiny framework to deal with this problem, over the last two days. Here is what I've got. The main ideas will involve implementing a simple key-value store in Mathematica based on a file system, heavy use and automatic generation of UpValues, some OOP - inspired ideas, Compress, and a few other things....


90

I will answer a couple of your questions only. Space efficiency Packed arrays are significantly more space efficient. Example: Let's create an unpacked array, check its size, then do the same after packing it: f = Developer`FromPackedArray[RandomReal[{-1, 1}, 10000]]; ByteCount[f] ByteCount[Developer`ToPackedArray[f]] (* 320040 80168 *) Time efficiency ...


82

The difference Packed arrays give you pretty much an access to a direct C memory layout, where the arrays are stored. Unpacked arrays reference arrays of pointers to their elements. This explains most of the other differences, in particular: Space efficiency: if you look at how much space is required for packed arrays, you see that it is exactly the amount ...


80

Update: Mathematica 10 has introduced Association, which can be used as a close equivalent of structs. params = <| "par1" -> 1, "par2" -> 2 |> params["par1"] (* ==> 1 *) In version 10 pure functions can have named arguments, and can be effectively used as expression templates where the slots can be populated from an association. This is ...


74

Here are a few ways, each of which operates upon the individual component associations. In the following discussion, recall that when a key name is not a valid symbol we can write, for example, #["col_name"] instead of #col. We can explicitly construct a new association that includes all of the old columns and adds a new one: ds[All, <| "col1"->"...


56

Preview and comparative results The implementation below may be not the most "minimal" one, because I don't use any of the built-in functionality (DictionaryLookup with patterns, Graph-related functions, etc), except the core language functions. However, it uses efficient data structures, such as Trie, linked lists, and hash tables, and arguably maximally ...


54

This answer may be unacceptable right from the outset because it uses undocumented functions. However, it has advantages over some of the approaches suggested so far which might be redeeming enough in certain scenarios to recommend it in practice. In particular, it provides totally encapsulated state (unlike, e.g., DownValues or Temporary symbols) and O(1) ...


49

My solution is a recursive tree traversal algorithm which seeks and searches neighbouring vertices only if it will lead to a word (e.g., Something starting with ZQ is immediately disqualified), but it's faster than yours because I construct the adjacent vertices list from the adjacency matrix rather than calling NeighborhoodGraph each time. On my machine, ...


48

A Dataset represents an abstraction over a structured collection of data. Notionally, it is restricted to "well-behaved" data -- data that comes in simple forms that can be readily interchanged with external systems such as relational databases, XML documents, JSON documents, etc. These are commonplace forms such as vectors, records ("structs"), tuples, ...


47

I helped design Association, and I designed and implemented Dataset, so I wanted to comment on question 3: Dataset is designed explicitly for hierarchical data. It supports any 'shape' of data, inferring the shape when the Dataset is first created. It also tracks the shape of the data as transformations are applied to the dataset, using a type-inference ...


36

UPDATE Since version 10, we have Associations. Here is the modified code for trie building and querying, based on Associations. It is almost the same as the old code (which is below): ClearAll[makeTreeAssoc]; makeTreeAssoc[wrds : {__String}] := Association@makeTreeAssoc[Characters[wrds]]; makeTreeAssoc[wrds_ /; MemberQ[wrds, {}]] := Prepend[...


35

In practice, enforcing strong types in Mathematica seldom pays off, just because, as mentioned by @belisarius, Mathematica is untyped (and perhaps more so than most other langauges, since it is really a term-rewriting system). So, most of the time, the suggestion of @Mr.Wizard describes what I'd also do. The way to define ADT-s (strong types) was described ...


35

There were several attempts to emulate structs in Mathematica. Emphasis on emulate, since AFAIK there is no built - in support for it yet. One reason for that may be that structs are inherently mutable, while idiomatic Mathematica gravitates towards immutability. You may find these discussions interesting: Struct-data-type-in-mathematica Object-oriented-...


34

I'm the developer of Dataset. Yes, this is a gross documentation oversight. We planned this functionality but had to push it back to a point release. Somehow no-one caught this piece of legacy documentation. I've filed a bug on the documentation problem right now, it's easy to fix. As for when L-value assignment will be available, I'm hoping 10.0.1 or 10....


32

Edit: The ideas below have led to a package called MTools. Instructions on how to install and use it are here: MTools tutorial. Using symbols to store data and object-like functions Here are interesting functions to use symbols like objects. (I originally posted these thoughts in What is in your Mathematica tool bag?). The post has grown quite big over ...


31

Actually, Mathematica has this stuff built in. I couldn't find this information anywhere, so posting it here for general reference. You can use it like this: Needs["Parallel`Queue`Priority`"] Unprotect@Priority; Priority[i_Integer] := Abs[i] q = priorityQueue[]; EnQueue[q, 10]; EnQueue[q, 7]; EnQueue[q, -20]; Size[q] == 3; Top[q] == -20; Normal[q] == {-20, ...


28

There is a ToAssociations function in the GeneralUtilities` package that is perfect for this and for converting nested JSON rules to associations: Needs["GeneralUtilities`"] ToAssociations@rdata (* <|"a" -> <|"b" -> 1, "c" -> {7, 8, 9}|>, "d" -> 3|> *) This preserves the inner most list that is not a list of rules. As for your ...


27

My modest attempt: With[{n = 7}, Graphics[Table[Text[Style[Binomial[n - j, n - i], Large], {Sqrt[3] (i - j/2), 3 j/2}], {i, n}, {j, i}]]] Here's a more general function: triangularArrayLayout[triArray_List, opts___] := Module[{n = Length[triArray]}, Graphics[MapIndexed[ Text[Style[#1, Large], {Sqrt[3] (n - 1 + #2.{-1, ...


27

Here is another way: pascalTriangle[n_] := NestList[{1, Sequence @@ Plus @@@ Partition[#, 2, 1], 1} &, {1}, n - 1]; Column[Grid[{#}, ItemSize -> 3] & /@ (pascalTriangle[7] /. x_Integer :> Text[Style[x, Large, If[x == 2, Red, Black]]]), Center]


27

Yes. Use System`Private`SetNoEntry on any expression which you want to protect in this manner. This works on per-expression basis, so you have to apply this function to any instance which you want to protect. The result is a reference to the same expression. The changes are performed in-place (no copy is created): expr = h[1, 2, 3] (* h[1, 2, 3] *) ...


26

To address your question about visualizing a triangular list, let's use the following list: t = Table[Binomial[n, k], {n, 0, 8}, {k, 0, n}] (*out *) {{1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}, {1, 4, 6, 4, 1}, {1, 5, 10, 10, 5, 1}, {1, 6, 15, 20, 15, 6, 1}, {1, 7, 21, 35, 35, 21, 7, 1}, {1, 8, 28, 56, 70, 56, 28, 8, 1}} You can format the list as a matrix: ...


26

Another way that works (for one or more columns) is: ds[All, <|#, "col3" -> #col1 + #col2, "col4" -> #col1 - #col2|> &] This gives: Also, sometimes the values for the new column might not be straightforwardly computed row by row. For example, you might have calculations like this: newcol = RotateLeft @ Normal[ds[All, (#col1 + #col2 &)...


26

Such functions set up a one-time iterator, i.e. a GeneralUtilities`Iterator. Its functionality may be inspected with ? GeneralUtilities`Iterator and so forth. Except for a ConstantIterator which always returns the same value (forever), they go sequentially through values until they return GeneralUtilities`IteratorExhausted. The main (if internal) utility ...


24

I would like to point out that Listable in a pure Function effectively unpacks the array, and makes it much slower than Map for pure Functions. Downvalues always unpack so SetAttributes[f, Listable] doesn't affect performance there. The bottom line is that if one wants to use user defined listability it must be inside a compiled function, otherwise use Map ...


24

As you mentioned in your question and belisarius illustrates above, you can check arguments with arbitrary pattern matching. When I need to do checks of this kind I often use a couple of methods; I will define the pattern once and then reference it by name: p1 = {{_Integer, {_Integer ...}} ...}; dat = {{100, {1, 2, 3, 4, 5}}, {105, {2, 4, 6, 8}}, {42, {42,...


24

The answers already posted show that built-in Mathematica functionality can be used to get the meaningful functionality provided by a C struct. If you want your code to be readable by other Mathematica users, I suggest using a list of rules as already advised above. However, if you really want struct-style syntax I'll offer an implementation that I've ...


23

First of all, it's not a new data structure, it's a new only in a Wolfram Mathematica. About complexity of a data structure. It's a Wolfram implementation of a hash-map. With a complexity of an operations (worst case in parenthesis): Space O(n) Search O(1) (O(n)) Insert O(1) (O(n)) Delete O(1) (O(n)) This can be easily checked: create custom ...


22

You can implement an imperative-style circular buffer. big = Range@1*^7; size = Length@big; pointer = size; updateElement[new_Integer] := (pointer = 1 + Mod[pointer, size]; big[[pointer]] = new) Do[updateElement[RandomInteger@99], {100}] // AbsoluteTiming {0.000374, Null} To bring the buffer back to the normal form use big = RotateLeft[big, Mod[...


21

Update: Mathematica version 10 introduced the builtin Association data structure (see tutorial and answer below), which has most important features of dictionaries. Mathematica has no obvious hash-table structure but what most people forget is, that the DownValues of symbols, which means the simple, always-used function definitions, are implemented using ...


Only top voted, non community-wiki answers of a minimum length are eligible