Finding median in linear time

[gh-Hrishabh-yadav]

This ticket introduces a new technique for finding median of graph : ​https://en.wikipedia.org/wiki/Median_of_medians This algorithm runs at complexity of O(n) in worst case and will be a good addition to sage stats module.

[gh-Hrishabh-yadav]

Implementation of median_of_medians code is done. Algorithm does run fast as compared to the one in function median(), but still slow compared to it's expectation. Results:

sage: A = [randint(0,i*100) for i in range (0,5000000)]
sage: median_of_medians(A,len(A)//2)
sage: median(A)
Time for median_of_medians : 2.66196990013
Time for median : 3.39063596725

---

New commits:

​d82ca32

Added median_of_medians code

[dcoudert]

Please follow the coding style of Sagemath: ​http://doc.sagemath.org/html/en/developer/coding_basics.html and ​https://www.python.org/dev/peps/pep-0008 . For instance,

• def median_of_medians( A, i ): -> def median_of_medians(A, i ):
• bullets in INPUT block must be aligned below INPUT
• in these bullets, use ``A`` and not `A`
• if(len(A)<=i): -> if len(A) <= i:
• etc., etc., etc.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2967601

Modified coding style

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​80ffb1c

Removed Brackets

[gh-Hrishabh-yadav]

I have modified the code.

[dcoudert]

The method says that it returns the i-th smallest integer in the array, but in the examples, you return the (i+1)-th.

The examples are for small values, but you have hardcoded items_per_column = 1000. Thus, your tests are only for sorted(A)[i].

Please add a description of the algorithm. Otherwise, it's very hard to check your code.

Do you really need recursive calls ? can't you avoid that ?

and why choosing 1000 ?

[gh-Hrishabh-yadav]

Replying to dcoudert:

The method says that it returns the i-th smallest integer in the array, but in the examples, you return the (i+1)-th.

I will change it.

The examples are for small values, but you have hardcoded items_per_column = 1000. Thus, your tests are only for sorted(A)[i].

By taking 'items_per_column =1000' I got the best result, Although I will make sure it is given by the user.

Please add a description of the algorithm. Otherwise, it's very hard to check your code.

Yeah sure.

Do you really need recursive calls ? can't you avoid that ?

Actually no, I have a way to remove recursive calls, let me code it!

and why choosing 1000 ?

As mentioned above, it gave the best results among '10','100','1000','10000'and '100000'.

Thanks!

[gh-Hrishabh-yadav]

Apparently numpy has implemented introselect algorithm which is a mix of median_of_median and quickselct algorithm, and works quite fast as compared to the algorithm implemented in current branch.

Introselect: ​https://en.wikipedia.org/wiki/Introselect

numpy library function :-​https://docs.scipy.org/doc/numpy/reference/generated/numpy.partition.htm

I have made a new branch in which numpy library algorithm is called rather the one implemented above. Or should i have both codes and let user decide which one should be implemented.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2530c54

Added numpy.partition

[dcoudert]

I have made a new branch in which numpy library algorithm is called rather the one implemented above. Or should i have both codes and let user decide which one should be implemented.

If there is a faster and simpler method, there is no need for adding another one, and in view of the proposed method, I think there is no need for adding i_smallest. The added value to Sagemath seems rather limited here.

So I suggest to change the milestone to wontfix.

[gh-Hrishabh-yadav]

Ok done!

[chapoton]

David, can we close this one ?

[dcoudert]

Yes, we can close this ticket.