Sort values of x-axis in order to fill the plot f(x) evenly while computing f(x)

Question

Global task for general understanding: I need to plot a result of my function f(x). Simple task, but there are two problems:

1. For each value of x, f(x) takes much time to compute (tens of minutes or even aroud an hour).
2. I don't know the estimated shape of f(x), therefore I don't know, how many x values I need in predefined x limits to represent the function correctly.

I want to update the plot of f(x) each time I get new f(x) value. I don't want to solve f(x) consequentially, I want to kind of increase level of detail, so every time I look on a plot, I see it over all of my (x_min, x_max) range, slowly updating within this range.

Therefore the question is: I need a function, which provides a list of x in proper order.

I came up with the following algorithm, inspired by binary search:

list a of x values contains only unique values and it is sorted.

def dissort(a)
    step = len(a) - 1
    picked = [False for x in a]
    out = []
    while False in picked and step > 0:
        for k in range(0, len(a), step):
            if not picked[k]:
                out.append(a[k])
                picked[k] = True
        step = step // 2
    return out

in = [1, 2, 3, 4, 5, 6, 7, 8, 9]
out = [1, 9, 5, 3, 7, 2, 4, 6, 8]
assert(dissort(in) == out)

I see some flaws here: picked array may be unnecessary, and picked values are unnecessarily checked every time level of detail increases. For now I'm happy with the performance, but in the future I can use it for much larger lists.

Is there a way to make it more performant? Is there an implementation in some python package already? I couldn't find it.

Answer 1

If your input-size is a power of 2, you could get the same order as with your algorithm like this:

To know where to place the n'th value in your output-array, take the binary representation of n reverse the order of the bits and use it as index in your output-array:

Example

n  | bin   |   rev | out-index 
 
0  = 000   ->  000 = 0
1  = 001   ->  100 = 4
2  = 010   ->  010 = 2
3  = 011   ->  110 = 6
4  = 100   ->  001 = 1
5  = 101   ->  101 = 5
6  = 110   ->  011 = 3
7  = 111   ->  111 = 7

So IN: [A,B,C,D,E,F,G,H] -> OUT: [A,E,C,G,B,F,D,H]

Takes O(n) time

How to reverse the order of the bits see Reverse bits in number

optimized ways: https://stackoverflow.com/a/746203/1921273

Answer 2

Why make this so complicated?
Why not store your x and f(x) values in a dict, and sort the dict keys:

data = {}

# every time you get a new x and f(x) value, store it in the dict:

data[x] = f(x)

# then when you want to plot:

xvals = sorted(data.keys())
yvals = [data[x] for x in xvals]

# Now you have a x values and y values, sorted by x value, so just:

plot(xvals,yvals)

Does something like that work for you?

Also, just as an aside: it's understandable that you want something performant, as a general rule, but relative to your algorithm taking 10 minutes to an hour to converge on each value of f(x), whenever a new value comes in, resorting all of the existing results with the new result, even with an O(n*ln(n)) sort, is going be very much faster than the wait time for new values to sort. (Python sorted can sort 10,000 numbers in less than 2.5 milliseconds. The point is, compared to a 10 minute algorithm, shaving another 0.5 to 1.0 milliseconds off that is not going to make any difference in your overall process).

Answer 3

Is a random order of the x values is ok? If so:

import random
xvals = random.sample(range(10),10)

result:

 [9, 5, 1, 7, 6, 2, 3, 0, 4, 8]

The numbers will not repeat. Of course the result will differ each time you call it. And you can generate any number of x values:

random.sample(range(20),20)
 [10, 5, 0, 18, 13, 14, 19, 3, 1, 2, 17, 6, 4, 11, 15, 7, 9, 8, 12, 16]

I believe this is also O(n).

The only issue with this, possibly, is this: On each iteration of increasing the number of x-values, do you also then not want any repeats from the prior iteration? Or is the above adequate?