15
$\begingroup$

I'm trying to use Dataset to explore some large data. I notice that the performance decrease more than 20X by adding heads to the columns. Here is an example:

We generate some data with integers

data = RandomInteger[{1, 100000}, {1000000, 7}];

convert it into a Dataset object

ds1 = Dataset[data]; // AbsoluteTiming
(* {0.000606, Null} *)

and sort it according to the first column

ds1[SortBy[#[[1]] &]]; // AbsoluteTiming
(* {0.507638, Null} *)

Now if we add the heads to the data

head = "x" <> ToString[#] & /@ Range[7]
(* {"x1", "x2", "x3", "x4", "x5", "x6", "x7"} *)
ds2 = Dataset[AssociationThread[head -> #] & /@ data]; // AbsoluteTiming
(* {4.57311, Null} *)

Now sorting becomes 20X slower

ds2[SortBy[#x1 &]]; // AbsoluteTiming
(* {10.6259, Null} *)

So why does the performance decrease when we add a header to our data? Is there a way to fix that?

System information: version 11.1 on mac os 10.12.3

$\endgroup$
3
  • $\begingroup$ It seems this takes longer; ds2[SortBy[#"x1" &]]; // AbsoluteTiming. And this takes even longer; ds2[SortBy[#["x1"] &]]; // AbsoluteTiming. Very curious. v 11.1 Win 8.1 Pro $\endgroup$
    – Edmund
    Mar 29, 2017 at 1:49
  • $\begingroup$ @Edmund I wouldn't say this is so peculiar. Look at the overhead introduced by the headers -- they are added to every row, because named columns are associations. If you do ByteCount (I know it isn't perfect), you will see factor 20 difference in size. Very inefficient. You can't really work with big data sets and use Dataset with named columns etc. -- you have to use simple lists, otherwise that overhead would eat all the space on your machine before you even started processing it. $\endgroup$
    – Stitch
    Mar 29, 2017 at 19:21
  • $\begingroup$ @Stitch Yes. Reading your comment I do remember that at one of the WTCs the fellow who coded Dataset did mention that they were looking into ways to not repeat the Association Keys in every row. I think it would be a challenge in the general case because of the free-form construction. Maybe some sort of packed dataset will be introduced for regularly structured datasets at some point. $\endgroup$
    – Edmund
    Mar 29, 2017 at 21:06

1 Answer 1

4
$\begingroup$

Your ds2 is a highly inefficient shape. Using 10 in place of 1000000 in the data code we get something like:

(Observations made in Mathematica 10.1)

ds2 // InputForm

Dataset[{<|"x1" -> 10, "x2" -> 4, "x3" -> 8, "x4" -> 3, "x5" -> 6, 
   "x6" -> 5, "x7" -> 5|>, <|"x1" -> 2, "x2" -> 9, "x3" -> 6, "x4" -> 10, 
   "x5" -> 10, "x6" -> 5, "x7" -> 1|>, <|"x1" -> 9, "x2" -> 6, "x3" -> 6, 
   "x4" -> 10, "x5" -> 2, "x6" -> 10, "x7" -> 6|>, 
  <|"x1" -> 8, "x2" -> 2, "x3" -> 2, "x4" -> 2, "x5" -> 6, "x6" -> 2, 
   "x7" -> 8|>, <|"x1" -> 1, "x2" -> 8, "x3" -> 10, "x4" -> 3, "x5" -> 8, 
   "x6" -> 3, "x7" -> 9|>, <|"x1" -> 3, "x2" -> 6, "x3" -> 1, "x4" -> 10, 
   "x5" -> 3, "x6" -> 5, "x7" -> 8|>, <|"x1" -> 6, "x2" -> 7, "x3" -> 5, 
   "x4" -> 2, "x5" -> 10, "x6" -> 4, "x7" -> 9|>, 
  <|"x1" -> 7, "x2" -> 10, "x3" -> 8, "x4" -> 1, "x5" -> 3, "x6" -> 3, 
   "x7" -> 8|>, <|"x1" -> 4, "x2" -> 3, "x3" -> 6, "x4" -> 1, "x5" -> 8, 
   "x6" -> 5, "x7" -> 1|>, <|"x1" -> 8, "x2" -> 7, "x3" -> 8, "x4" -> 1, 
   "x5" -> 3, "x6" -> 9, "x7" -> 10|>}, TypeSystem`Vector[
  TypeSystem`Struct[{"x1", "x2", "x3", "x4", "x5", "x6", "x7"}, 
   {TypeSystem`Atom[Integer], TypeSystem`Atom[Integer], 
    TypeSystem`Atom[Integer], TypeSystem`Atom[Integer], 
    TypeSystem`Atom[Integer], TypeSystem`Atom[Integer], 
    TypeSystem`Atom[Integer]}], 10], <|"ID" -> 127397422492264|>]

Not only is this redundant but its form prohibits packing; every Integer is stored separately.

Compare the Transpose of your ds2:

ds2\[Transpose] // InputForm

Dataset[<|"x1" -> {10, 2, 9, 8, 1, 3, 6, 7, 4, 8}, 
  "x2" -> {4, 9, 6, 2, 8, 6, 7, 10, 3, 7}, 
  "x3" -> {8, 6, 6, 2, 10, 1, 5, 8, 6, 8}, 
  "x4" -> {3, 10, 10, 2, 3, 10, 2, 1, 1, 1}, 
  "x5" -> {6, 10, 2, 6, 8, 3, 10, 3, 8, 3}, 
  "x6" -> {5, 5, 10, 2, 3, 5, 4, 3, 5, 9}, 
  "x7" -> {5, 1, 6, 8, 9, 8, 9, 8, 1, 10}|>, 
 TypeSystem`Struct[{"x1", "x2", "x3", "x4", "x5", "x6", "x7"}, 
  {TypeSystem`Vector[TypeSystem`Atom[Integer], 10], 
   TypeSystem`Vector[TypeSystem`Atom[Integer], 10], 
   TypeSystem`Vector[TypeSystem`Atom[Integer], 10], 
   TypeSystem`Vector[TypeSystem`Atom[Integer], 10], 
   TypeSystem`Vector[TypeSystem`Atom[Integer], 10], 
   TypeSystem`Vector[TypeSystem`Atom[Integer], 10], 
   TypeSystem`Vector[TypeSystem`Atom[Integer], 10]}], 
 <|"Origin" -> HoldComplete[AssociationTranspose, 
    Dataset`DatasetHandle[127397422492264]]|>]

Observe that not only is the representation more compact but the data is typed as vector arrays: TypeSystem`Vector[TypeSystem`Atom[Integer], 10].

Create your Dataset in the efficient shape to begin with to avoid a very slow Transpose operation:

ds3 = Dataset @ AssociationThread[head -> (data\[Transpose])];

From here you can quickly apply a sort like this:

ds3[[All, ds3["x1", Ordering] // Normal]]; // RepeatedTiming
{0.183, Null}

Note: This Ordering uses only the "x1" data and therefore the output will be similar to the stable SortBy[{#x1 &}] rather than the tie-breaking SortBy[#x1 &]. My guess is that this is actually what you will want most of the time. If a full tie-breaking form is required then:

ds3[[All, ds3[Values] // Normal // Transpose // Ordering]]; // RepeatedTiming
{0.320, Null}

The dependence on shape in Dataset is similar to the case of SparseArray; see:

$\endgroup$
5
  • 4
    $\begingroup$ I have to give a heart-warm warning to the future reader here :),the package TypeSystem` has been abandoned after version 10.3 (maybe). $\endgroup$
    – yode
    Apr 2, 2017 at 8:34
  • $\begingroup$ @yode How does my code perform in more recent versions? $\endgroup$
    – Mr.Wizard
    Apr 2, 2017 at 8:46
  • $\begingroup$ Just render my screen with red,the TypeSystem`* cannot work here.Look the suitation in 11.1 $\endgroup$
    – yode
    Apr 2, 2017 at 9:06
  • $\begingroup$ @gwr Just too poor to upgrade with every release. :-/ $\endgroup$
    – Mr.Wizard
    Apr 3, 2017 at 4:32
  • 3
    $\begingroup$ @Mr.Wizard ... given your abilities? ; ). But with Mathematica we probably simply bet on the wrong horse: The only person that has gotten rich using and selling Mathematica is a physicist in Illinois... :-\ There seems to be negligible direct demand in industry from what I see. If it weren't' so darn fun to use it. $\endgroup$
    – gwr
    Apr 3, 2017 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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