-1

The question is to return a sorted array after performing a cubic function. Specifically, given a sorted array nums ( i.e., x0, x1, x2, ... xn), return another sorted array after performing f(x) = ax^3 + bx^2 + C*x + d.

Brutal Force Method ( Time complexity O(nlogn) )

  1. Feed nums to f(x) and the get y = f(x0), f(x1), f(x2), ... f(xn)
  2. Sort the y to get the answer

Is there any better thoughts and solutions? Your suggestions and thoughts are highly appreciated.

Kelly Bundy
  • 23,480
  • 7
  • 29
  • 65
Neo Staff
  • 21
  • 2
  • 1
    In Python, you're not gonna beat that method. Except for special inputs, it's even gonna take only linear time. – Kelly Bundy Aug 24 '21 at 05:51

2 Answers2

2

Just math: calculate zeros of cubic function derivative (solve 3*a*x^2 + 2*b*x+c=0) and find maximums and minimums. Analyze behaviour between extremas (positive derivative witnesses that function is increasing)

Result curve is monotone between them, so you have some (1 to 3 depending on x range) series, and you can reverse decreasing serie(s), then merge series in linear time

MBo
  • 77,366
  • 5
  • 53
  • 86
  • Although this is likely the most efficient algorithm in the asymptotical sense, simply applying the function and sorting the results is probably more efficient on not-too-large inputs, especially if the sorting function is efficient on almost-sorted arrays. – Stef Aug 24 '21 at 09:17
  • 1
    @Stef Imagine large central range with decreasing function [example](https://www.wolframalpha.com/input/?i=plot+x%5E3+-+60000x%5E2+%2B+x+%2B+1%2C+x%3D-10000..50000). Perhaps timsort might reveal such monotone range and use this information, but other popular sorting algorithms are not intended to treat it properly. – MBo Aug 24 '21 at 09:23
  • 1
    @Stef It'll likely be more efficient even for large inputs, as it usually only needs linear time as well, with a lower constant. Even if you do create an input that takes linearithmic time (how to do that is a little puzzle in its own right), linearithmic with a low constant is still fast. – Kelly Bundy Aug 24 '21 at 12:44
  • @Stef Did some testing in my own answer now. – Kelly Bundy Aug 24 '21 at 13:38
2

In (pure) Python (since that's what the question is tagged with), you're likely not going beat that naive/straightforward method of calculating the images and then sorting them. Except for special inputs, it's even going to take only linear time, thanks to Timsort recognizing the up to three monotone parts and just merging them.

Let's benchmark @MBo's example x^3 - 60000x^2 + x + 1, x=-10000..50000, with x-steps of 0.01, so we have six million points:

 Round 1   Round 2   Round 3
 1156 ms   1157 ms   1168 ms  transform
  201 ms    202 ms    203 ms  copy+sort
   92 ms     94 ms     93 ms  copy

So here, even the transformation already took over 10 times as long as the sorting (1160 ms vs 202-93=109 ms, I copy the transformed values before sorting because I test repeatedly).

If you try to identify and merge the monotone parts yourself, that'd replace the 109 ms with something more like the 1160 ms, i.e., be slower.

Code (Try it online!):

from timeit import repeat

def transform(a, b, c, d, X):
    return [((a*x + b)*x + c)*x + d
            for x in X]

funcs = [
    ('transform', lambda: transform(a, b, c, d, X)),
    ('copy+sort', lambda: Y.copy().sort()),
    ('copy',      lambda: Y.copy()),
]

a, b, c, d = 1., -60000., 1., 1.
X = [i / 100 for i in range(-1_000_000, 5_000_001)]
Y = transform(a, b, c, d, X)
number = 1

tss = [[] for _ in funcs]
for _ in range(3):
    print(' Round 1   Round 2   Round 3')
    for (label, func), ts in zip(funcs, tss):
        t = min(repeat(func, number=number)) / number
        ts.append(t)
        print(*('%5d ms ' % (t * 1e3) for t in ts), label)
    print()
Kelly Bundy
  • 23,480
  • 7
  • 29
  • 65
  • Awesome! Small critic: pronouns such as "that method" rely heavily on context and make the answer harder to understand - not to mention it might stop making sense altogether if the question is edited and reworded. I suggest a more explicit sentence such as "In (pure) Python, you're probably not going beat the naive/straightforward method of calculating the images then sorting them." – Stef Aug 24 '21 at 14:14
  • 1
    @Stef Ok, did that, and also optimized the transformation further. – Kelly Bundy Aug 24 '21 at 14:52
  • As far as I understand, Python `sort` is really implemented in C? So it is hard to beat it with hand-made methods ;) – MBo Aug 24 '21 at 16:34
  • @MBo At least in the reference implementation (CPython) it's implemented in optimized C, yes. Like I said, you can force it to take linearithmic time (even with this task's constraints), but it'll likely remain hard if not impossible to beat. That linearithmic time has an *extremely* small constant factor. – Kelly Bundy Aug 24 '21 at 16:48
  • 1
    @Kelly Bundy In compiled languages Quicksort (linearithmic) on 1 million integers array takes about 100 ms, while simple linear code for the same array - about 6 ms for reversing, 9 ms for cubic function calculation . But you are right that here in plain Python cubic function calculation takes the most of time (at least until we don't use numpy or smth like numba) – MBo Aug 24 '21 at 17:17
  • @MBo Those 100 ms, is that for random ints or for monotone ones like we have here? Anyway, yes, in other languages or even with numpy/numba it could be faster to do yourself than to use a sorting algorithm that doesn't benefit from the monotonicity. Note, though, that Timsort doesn't just benefit from recognizing the monotone parts, but also from its galloping, so it could still also beat a good self-made solution in another language if that does naive merges. – Kelly Bundy Aug 24 '21 at 17:29
  • 1
    For random ints, but it is not very important for quicksort. I have not timsort implementation. Anyway, you are right that for Python we must consider a lot of factors besides pure algorithmic effectivity. – MBo Aug 24 '21 at 17:41
  • @MBo Ok, I'm not that familiar with quicksort, I just thought with sorted values it might benefit from [branch prediction luck](https://stackoverflow.com/a/11227902/12671057) or for example if the values are reverse sorted and it takes the middle element as pivot and swaps front and back values, it would be done in linear time. – Kelly Bundy Aug 24 '21 at 17:45