What is the most efficient way to insert a number into an ordered array?

user_4632907 0
Viewed 195

Inserting numbers into a sorted array is a very common need.

Mathematica stack exchange for reference. Its priority queue appears extremely fast. https://mathematica.stackexchange.com/questions/224249/best-way-to-insert-element-into-an-ordered-list-at-the-correct-position

For J: Using the built in sort /:~y where y is the sorted array - examples: /:~ y,45.3 or /:~ y,3 6 67.7 would be the first choice.

Quicksort and bubblesort are much slower.

For a single insert rotating the number into the sorted list -

insert=: 4 : 0
 NB. insert x into ordered array y
 where=: x (< i. 1:) y
 z=: (($y)-where)|.(where|.y),x
)

is around 2.5 times faster on y=.i.10000000 than /:~y

anything faster?

j
1 Answers

Binary search I. is the best you can do to find an element in a sorted array.

[;.0 is the best you can do to extract a subarray.

These are very fast on their own:

y =: i.1e7
100 timespacex'y I. 35'
 2.94e_6 896
100 timespacex'(35 ,: _) ];.0 y'
 4.85e_6 1856

The bottleneck seems to be appending the new element thus copying the list to make the new list.

100 timespacex'35,~(35 ,: _) ];.0 y'
 0.0368233 1.3422e8


insert=: 4 : 0
 NB. insert x into ordered array y
 where=: x (< i. 1:) y
 z=: (($y)-where)|.(where|.y),x 
)

insert2=: 4 : 0
 where=: y I. x
 NB. z =: where ({.,x,}.) y
 z =: (where ];.0 y),x,((where ,: _) ];.0 y)
)

y =: i.1e7
(35 insert y) -: (35 insert2 y)
 1

100 timespacex'35 insert y'
 0.0745025 2.68437e8
100 timespacex'35 insert2 y'
 0.0738203 2.68437e8

Other, more complicated, ways may offer better results, depending on what you need and what kind of input you have.

user_3497080
Related