ENH nlargest and nsmallest Series methods
State: closed

closes #3960.

_Implemented using kth_largest, could cython using better algo later._


Labels:
name: Numeric Operations
description: Arithmetic, Comparison, and Logical operations
name: Algos
description: Non-arithmetic algos: value_counts, factorize, sorting, isin, clip, shift, diff

Comments:
needs tests on other dtypes
will fail on datetime64 ATM (these need i8 conversion)

@y-p happy to change the name to topk and bottomk, was going off heapq notation.

@jreback any other dtypes to check? Will fix it up.

_The plan is to rewrite this at somepoint in cython with a proper alog..._

check all!

float, int, datetime64 (use i8), timedelts64 (same), object that are numbers, object that are strings 

some u may want to simple raise as notimplemented

And make sure to include things with nan so we specify that behavior.

@hayd, good reason, though I still prefer `topk` for being short and familiar parlance. Your call.

Added two small detail comments on the docs. Two other things:
- Can you add them to api.rst?
- The parameters are still undocumented

Should be using quick select algorithm ? (Julia does this _fast_.. at least with one dim _array_... in a more general way.)

Numerical recipes tend to reincarnate from langauge to language, all the way back
to some fortran code written 40 years ago or a paper by some CS father figure.

The cython code you're relying on from algos.pyx probably originated here:
http://ndevilla.free.fr/median/median/index.html

and from a quick look at the graph there, it seems wirth and quickselect have similar perf
(for the median special case `k=n/2`, I'm assuming that holds generally).

moving for 0.13.1

@hayd ok?

@hayd ready to merge?

There were some comments on docs that would ideally be handled before merging.

@hayd can you address the comments, otherwise looks ok

@jreback I have a few issues assigned I think. Will do in the next few days.

I had tried implementing quick select to compare perf. IIRC The issue with the above is it's significantly slower than sorting and taking head for "small" (and even quite big) Series. The more conditions (type checks) the slower it was getting.

Perhaps a solution is to check length before doing it and if "small" then sort and head :s
Will come back with some timings, and fix it up.

@hayd absolutely

@hayd hows this going?

@hayd see if you can do this soon...thxs

ok will do right this minute.

@jreback to put these in vbench, should I create a series_methods file? (Not sure where to put them).

Basically atm slightly slower if lots of values are the kth.

i think their is an algos or something's? u can either create series_methiss or put near rank

methods

 @hayd bump to 0.14?

@jreback Will finish this off this evening, it's passing tests but want to do a quick refactor.

If it gets left behind in 0.13.1 no biggy...

Gave it a refactor, and put the numpy versions into util. Suspect can be tweaked faster.

@jreback I tagged 0.14 but could change. Worried as kth_largest _can_ cause stack overflow if called incorrectly (though it's only called with i8, int and float without NaNs so should be ok). Perhaps should sit in master for a while just in case ?

@hayd look ok to me

can merge or wait to 0.14, up 2 u

pprob want to add an example in docs - maybe in min/max section

Would prefer to wait tbh, would like to kick it in master for a bit.

sure

@hayd looks ready to go
- pls change release notes to 0.14
- add a mention in v0.14.0.txt (example if you want)
- maybe add in docs somewhere.....?

There were some doc comments above from me that still should be adressed I think

@hayd can you rebase and address the comments....this should go in soon...thanks

@hayd would merge this soon