Added Rivest-Floyd selection algorithm as an option to numpy.partition

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Added Rivest-Floyd selection algorithm as an option to numpy.partition

Виктория Малясова
Hello everyone!
 
I've implemented the Rivest-Floyd selection algorithm as a second option to the partition method. I found it works about 1.5 times faster on average for big array sizes; here are average times for finding a median:
array length  10 
introselect 4.6e-05
rivest_floyd 4.4e-05
array length  100 
introselect 5.5e-05
rivest_floyd 4.7e-05
array length  1000 
introselect 6.9e-05
rivest_floyd 6.5e-05
array length  10000 
introselect 3.1e-04
rivest_floyd 2.3e-04
array length  100000 
introselect 2.9e-03 
rivest_floyd 2.0e-03
array length  1000000 
introselect 2.9e-02
rivest_floyd 2.0e-02

I've created a pull request https://github.com/numpy/numpy/pull/17813 and implemented reviewer's suggestions and fixes. Do you think this feature should be added? I am new to open source, sorry if I am doing anything wrong.

Viktoriya Malyasova.

_______________________________________________
NumPy-Discussion mailing list
[hidden email]
https://mail.python.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: Added Rivest-Floyd selection algorithm as an option to numpy.partition

ralfgommers


On Tue, Nov 24, 2020 at 12:56 PM Виктория Малясова <[hidden email]> wrote:
Hello everyone!
 
I've implemented the Rivest-Floyd selection algorithm as a second option to the partition method. I found it works about 1.5 times faster on average for big array sizes; here are average times for finding a median:
array length  10 
introselect 4.6e-05
rivest_floyd 4.4e-05
array length  100 
introselect 5.5e-05
rivest_floyd 4.7e-05
array length  1000 
introselect 6.9e-05
rivest_floyd 6.5e-05
array length  10000 
introselect 3.1e-04
rivest_floyd 2.3e-04
array length  100000 
introselect 2.9e-03 
rivest_floyd 2.0e-03
array length  1000000 
introselect 2.9e-02
rivest_floyd 2.0e-02

I've created a pull request https://github.com/numpy/numpy/pull/17813 and implemented reviewer's suggestions and fixes. Do you think this feature should be added? I am new to open source, sorry if I am doing anything wrong.

Hi Viktoriya, welcome! It looks like you're doing everything right, and the reviews so far are positive.

Cheers,
Ralf


_______________________________________________
NumPy-Discussion mailing list
[hidden email]
https://mail.python.org/mailman/listinfo/numpy-discussion