9

Suppose I have an array my_array and a singular value my_val. (Note that my_array is always sorted).

my_array = np.array([1, 2, 3, 4, 5])
my_val = 1.5

Because my_val is 1.5, I want to put it in between 1 and 2, giving me the array [1, 1.5, 2, 3, 4, 5].

My question is: What's the fastest way (i.e. in microseconds) of producing the ordered output array as my_array grows arbitrarily large?

The original way I though of was concatenating the value to the original array and then sorting:

arr_out = np.sort(np.concatenate((my_array, np.array([my_val]))))
[ 1.   1.5  2.   3.   4.   5. ]

I know that np.concatenate is fast but I'm unsure how np.sort would scale as my_array grows, even given that my_array will always be sorted.

Edit:

I've compiled the times for the various methods listed at the time an answer was accepted:

Input:

import timeit

timeit_setup = 'import numpy as np\n' \
               'my_array = np.array([i for i in range(1000)], dtype=np.float64)\n' \
               'my_val = 1.5'
num_trials = 1000

my_time = timeit.timeit(
    'np.sort(np.concatenate((my_array, np.array([my_val]))))',
    setup=timeit_setup, number=num_trials
)

pauls_time = timeit.timeit(
    'idx = my_array.searchsorted(my_val)\n'
    'np.concatenate((my_array[:idx], [my_val], my_array[idx:]))',
    setup=timeit_setup, number=num_trials
)

sanchit_time = timeit.timeit(
    'np.insert(my_array, my_array.searchsorted(my_val), my_val)',
    setup=timeit_setup, number=num_trials
)

print('Times for 1000 repetitions for array of length 1000:')
print("My method took {}s".format(my_time))
print("Paul Panzer's method took {}s".format(pauls_time))
print("Sanchit Anand's method took {}s".format(sanchit_time))

Output:

Times for 1000 repetitions for array of length 1000:
My method took 0.017865657746239747s
Paul Panzer's method took 0.005813951002013821s
Sanchit Anand's method took 0.014003945532323987s

And the same for 100 repetitions for an array of length 1,000,000:

Times for 100 repetitions for array of length 1000000:
My method took 3.1770704101754195s
Paul Panzer's method took 0.3931240139911161s
Sanchit Anand's method took 0.40981490723551417s
Arda Arslan
  • 1,331
  • 13
  • 24
  • You can simply run an experiment to see how each method scales as the list grows larger. Are you expecting someone else to do it for you? – TYZ Feb 13 '18 at 22:44
  • 2
    @YilunZhang I'm more so wondering what other methods may exist that I haven't thought of. – Arda Arslan Feb 13 '18 at 22:46
  • I think the most usual ways are: 1) append + sort, and 2) insert directly to the correct index location. – TYZ Feb 13 '18 at 22:47
  • 1
    @YilunZhang so how would you identify the correct index and perform the insert? That's clearly the approach the OP is looking for and they have shown effort on this problem. – roganjosh Feb 13 '18 at 22:49
  • 1
    Actually the speed of finding the index will not matter that much, since inserting in a numpy array takes linear time, any boost of searching the index, will be neglegible, we would only win up to 50%, but it will still be (very) slow for large arrays. – Willem Van Onsem Feb 13 '18 at 22:52
  • It might better to work with a list, maybe even a heap. – hpaulj Feb 13 '18 at 23:04
  • @WillemVanOnsem With up to 50%, I guess you're thinking of a linear search for the index instead of binary search? In that case I suspect you'd save significantly *more* than 50% by switching to binary search. (I don't know much NumPy though, and how to do such a linear search.) – Stefan Pochmann Feb 13 '18 at 23:05
  • @StefanPochmann: no, what I mean is that if we do linear search, then we have two *O(n)* algorithms, that will approximately run in the same time, if we manage to completely remove the search part, then the remaining insertion algorithm will still approximately take 50% of the time, in fact it will usually take more time, so even if we could find a way (impossible without proper structures) to detect the insertion point in constant time (and in zero nanoseconds), then that would not make the insertion algorithm any faster, hence the total would not have a dramatic speedup. – Willem Van Onsem Feb 13 '18 at 23:07
  • @WillemVanOnsem That's what I meant. But I think the linear insertion time might take *less* time than the linear search time, not more. So that somehow getting rid of that search time would improve by *more* than 50%. What's a fast linear time index search? (Like I said I'm not good enough at NumPy for this) – Stefan Pochmann Feb 13 '18 at 23:13
  • @StefanPochmann: well insertion means that - given we do it inplace - we have to move objects to the right by one hop (at the right of the insertion point). This means that we need to perform a fetch, and a write. Whereas linear search only need to do a *read*. Usually memory (if not in cache) is very slow compared to the CPU, so my guess is that insertion is typically slower. – Willem Van Onsem Feb 13 '18 at 23:18
  • @WillemVanOnsem Hmm, apparently there even isn't a way to do it inplace? At least `np.insert` doesn't work inplace and I couldn't find a way that is. In a little test, my linear search was indeed faster than `np.insert` but significantly *slower* than shifting by slice assignment (to simulate what inplace insertion would be like): https://ideone.com/GBmHx9 – Stefan Pochmann Feb 13 '18 at 23:33
  • 1
    `insert` creates a new array. either with concatenate, or creating a blank and copying values. You can't grow an ndarray in-place. Its size is fixed. – hpaulj Feb 13 '18 at 23:38
  • @StefanPochmann: and I think the reason that your search takes almost twice the time, is because the `a >= x` first evaluates *all* elements, whereas a linear search typically cuts of search from the moment it finds the match. If we work with `argmax(a[:x+1] >= x)` we get a faster timing. – Willem Van Onsem Feb 13 '18 at 23:41
  • @WillemVanOnsem Not almost twice the time but over 2.7 times as much. And again, I'm not good at NumPy, I just took that one from [this answer](https://stackoverflow.com/a/16244044/1672429). If you have a faster linear search, please share :-) – Stefan Pochmann Feb 13 '18 at 23:48
  • @StefanPochmann: well since we know that `x` is in the left part of the list we can "mimic" the cutoff with https://ideone.com/aL97Zr. – Willem Van Onsem Feb 13 '18 at 23:50
  • @WillemVanOnsem Yeah but you can't assume to know that. In general you don't. If you already knew where it is, you wouldn't search. So what's a fast general one? Also, you use `a[:x//2+1]` but should use `a[:x+1]`. – Stefan Pochmann Feb 13 '18 at 23:58
  • @StefanPochmann: yeah you are correct that it should be `x+1`, but the idea is here of course to mimic a more smart way to do it. But I do not think that numpy is actually tailored towards such operations. The idea of numpy is to use it when you want to process things in *batch* (like multiplying huge matrices), so inserting a single element in an array, is actually not a good fit for numpy at all. – Willem Van Onsem Feb 14 '18 at 00:02
  • Note that the sort type matters here. If you know that the array is mostly sorted, then you should use a sort algorithm that leverages this. – Angus Hollands Jan 09 '23 at 10:37

2 Answers2

5

Use np.searchsorted to find the insertion point in logarithmic time:

>>> idx = my_array.searchsorted(my_val)
>>> np.concatenate((my_array[:idx], [my_val], my_array[idx:]))
array([1. , 1.5, 2. , 3. , 4. , 5. ])

Note 1: I recommend looking at @Willem Van Onselm's and @hpaulj's insightful comments.

Note 2: Using np.insert as suggested by @Sanchit Anand may be slightly more convenient if all datatypes are matching from the beginning. It is, however, worth mentioning that this convenience comes at the cost of significant overhead:

>>> def f_pp(my_array, my_val):
...      idx = my_array.searchsorted(my_val)
...      return np.concatenate((my_array[:idx], [my_val], my_array[idx:]))
... 
>>> def f_sa(my_array, my_val):
...      return np.insert(my_array, my_array.searchsorted(my_val), my_val)
...
>>> my_farray = my_array.astype(float)
>>> from timeit import repeat
>>> kwds = dict(globals=globals(), number=100000)
>>> repeat('f_sa(my_farray, my_val)', **kwds)
[1.2453778409981169, 1.2268288589984877, 1.2298014000116382]
>>> repeat('f_pp(my_array, my_val)', **kwds)
[0.2728819379990455, 0.2697303680033656, 0.2688361559994519]
Paul Panzer
  • 51,835
  • 3
  • 54
  • 99
3

try

my_array = np.insert(my_array,my_array.searchsorted(my_val),my_val)

[EDIT] make sure that the array is of type float32 or float64, or add a decimal point to any of the list elements while initializing it.

Sanchit Anand
  • 195
  • 2
  • 11