7
$\begingroup$

Suppose I have an ordered list orderedList and I want to write some code that will involve regularly inserting new elements into orderedList in the correct positions, according to the ordering. One possibility is

Sort[AppendTo[orderedList,x]],

but this is inefficient because Mathematica doesn't know orderedList is already ordered, hence it will waste time verifying that the original elements of orderedList are already ordered.

Another idea is to use SelectFirst to obtain the proper position at which to insert x, via

Insert[orderedList,x,FirstPosition[SelectFirst[orderedList,#>x&]]].

The trouble here is that since Mathematica doesn't know orderedList is ordered, its SelectFirst algorithm will use a linear search rather than binary. Also, the requirement of using FirstPosition will double the computation time.

So what is the "right" way to do this, i.e., what method inserts an element into an ordered list without wasting resources?

$\endgroup$
  • 1
    $\begingroup$ Do a binary search. $\endgroup$ – ciao Jun 18 at 23:00
  • 2
    $\begingroup$ "but this is inefficient" - true, perhaps, but sorting algorithms are very optimized and typically very fast. Have you verified that this is really a problem in your application with some timings? $\endgroup$ – MarcoB Jun 18 at 23:01
  • $\begingroup$ maybe Nearest + ReplacePart/MapAt/...? $\endgroup$ – kglr Jun 18 at 23:01
  • 2
    $\begingroup$ Are you on v12.1? You could use a priority queue which stays sorted. You can make one with ds=CreateDataStructure["PriorityQueue"]; You then push all your elements in (see docs) and then when you're done, get them in list form like this: lst = {}; While[! ds["EmptyQ"], AppendTo[lst, ds["Pop"]]]; $\endgroup$ – flinty Jun 18 at 23:20
8
$\begingroup$

If you have v12.1, there's no need to ever call Sort if you can incrementally add your values to a "PriorityQueue" data structure. It always stays sorted as you add/remove elements.

SeedRandom[1234];
ds = CreateDataStructure["PriorityQueue"];
(* push a million random values in - use Scan for pushing many values. 
 The slowest part here is creating RandomIntegers, not the Push which is very fast *)
Scan[ds["Push", #] &, RandomInteger[10^6, 10^6]];
(* peek at the largest value *)
ds["Peek"]
(* returns: 999999 *)

(* add more values *)
ds["Push", N[Sqrt[2]]];
ds["Push", N[π^2]];
ds["Push", 0];

(* get all of the values out and show the first 50 *)
tbl = Reverse@Table[ds["Pop"], {ds["Length"]}];
tbl[[;; 20]]
(* result: {0, 0, 0, 0, 1.41421, 3, 5, 6, 8, 8, 9, 9, 9.8696, 10, 11, 14, 16, 17, 18, 19} *) 

(* After we popped the values, the heap is empty *)
ds["EmptyQ"] (* returns True *)

The timing of each "Push" is extremely small, around 5.*10^-7 on my machine. To get average push time:

rnd = RandomInteger[10^6, 10^6];
First[CompoundExpression[ds["DropAll"], Scan[ds["Push", #] &, rnd]] //
    RepeatedTiming]/10^6
(* 5.*10^-7 per push, overall 0.5 seconds to push 1M values *)
| improve this answer | |
$\endgroup$
  • $\begingroup$ This is great. I have v12.0, but will definitely update for this. $\endgroup$ – WillG Jun 19 at 5:16
5
$\begingroup$

For the binary search idea, you could use Leonid Shifrin's fast, compiled binary search function here. It would look like this:

sortedInsert[list_, el_] := Insert[
  list,
  el,
  bsearchMax[list, el]
  ]

sortedInsert[2 Range[10], 13]

{2, 4, 6, 8, 10, 12, 13, 14, 16, 18, 20}

list = Sort@RandomInteger[100000, 10000];
values = RandomInteger[100000, 1000];
sortedInsert[list, #] & /@ values; // RepeatedTiming

{0.018, Null}

You may also want to check out the other solutions in that answer. As some have pointed out, the best complexity solution is not always the most performant solution, when implemented in Mathematica. For comparison with a very naive approach, however, we can clearly see that the above helps:

sortedInsert2[list_, el_] := Insert[
  list,
  el,
  LengthWhile[list, el > # &] + 1
  ]
sortedInsert2[list, #] & /@ values; // RepeatedTiming

{1.5954, Null}

Nearest is quite a lot faster than the naive approach, but not as fast as binary search. A drawback is that if we're inserting elements into the list, then we need to recreate the NearestFunction over and over since there is no way to update it.

sortedInsert3[list_, el_] := With[
  {nf = Nearest[list -> "Index"]},
  Insert[
   list,
   el,
   Last@nf[el]
   ]
  ]
sortedInsert3[list, #] & /@ values; // RepeatedTiming

{0.24, Null}

I tried running Nearest directly instead of creating a NearestFunction explicitly, but it turned out to be slower.

The second best solution that I've found is the most naive of them all, that you also mention in your question:

Sort[Append[list, #] & /@ values]; // RepeatedTiming

{0.095, Null}

I'm aware that Append does not actually append any value, but neither does Insert so I'm using it for comparison here. Sorting would take a bit longer perhaps if accounting for a large number of newly inserted elements, but as we can see sorting is very fast. If you have all the elements you want to insert available up front, then it's a no-brainer:

Sort@Join[list, values]; // RepeatedTiming

{0.000075, Null}

This reflects the fact that dynamically resizing lists is very slow, so we should typically always try to avoid that under any circumstance, including this one. (In Mathematica we also typically try to avoid any kind of looping, so we can look at it from that point of view too, Map being a type of iteration.)

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Interesting that the simple solution of Sort@Join seems to be the best by far. I'm a bit confused about the second-to-last example with Sort[Append[... because it doesn't seem to perform the correct operation. E.g., Sort[Append[{1,2,3}, #] & /@ {4,5}] gives {{1,2,3,4},{1,2,3,5}}. $\endgroup$ – WillG Jun 19 at 5:14
  • $\begingroup$ @WillG I explicitly explained that in my answer. You could say exactly the same thing about the Insert examples but it doesn`t matter because I’m just testing the performance. $\endgroup$ – C. E. Jun 19 at 6:01

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.