What makes the NaN check expensive? [LWN.net]

What makes the NaN check expensive?

Posted Jan 5, 2020 17:51 UTC (Sun) by jansson (subscriber, #2227)
Parent article: Some median Python NaNsense

Thanks for an interesting article! :)

If all input numbers including NaN's are sorted, and if all NaN's ends up first or last after sorting. We need to check only first and last element after the sort. If any of those two numbers are a NaN then we have NaN in the input. Otherwise there is no NaN in the input! How can these two checks for NaN be expensive?

What did I miss?

What makes the NaN check expensive?

Posted Jan 5, 2020 20:12 UTC (Sun) by epa (subscriber, #39769) [Link] (2 responses)

Moreover, if you are sorting the list then you are already doing an O(N log N) operation, so a linear scan to find any NaN values would be a tiny fraction of the total work on large lists, and for small lists it would be fast enough anyway not to matter. As others said you would not be using vanilla Python if you needed high-performance numeric operations. So I don’t understand the objections based on performance. Perhaps if you have vast numbers of short lists and need the median of each... but even then you’d surely use a different tool.

What makes the NaN check expensive?

Posted Jan 7, 2020 18:43 UTC (Tue) by NYKevin (subscriber, #129325) [Link] (1 responses)

You don't sort to get median, you do quickselect (or another algorithm), which is O(N) (in the average case).

(Granted, a linear scan for NaN is also O(N), and probably has a better cache hit rate to boot. So I agree with you that performance really shouldn't be a problem here.)

What makes the NaN check expensive?

Posted Jan 7, 2020 22:06 UTC (Tue) by nivedita76 (guest, #121790) [Link]

You /should/, but the python implementation that's broken actually does a full sort.