Hacker News new | comments | show | ask | jobs | submit login

Three answers.

First, sure, CPython's only about two orders of magnitude slower than C, so on big enough data sets, the asymptotic performance rules. N log N is 100 times better than N^2 as soon as N is over about 1000. (The obvious-to-me way to implement an ordered map in Python would be to maintain a dict and a sorted list of keys; inserting N items into a sorted list is N^2.)

Second, this kind of data structure might be fast in PyPy. Like, C-like fast, or worse in the constant factors by only a factor of 2 or 5. Certainly you could imagine JIT optimizing dynamic language implementations where that was the case. But I haven't tested.

Third, usually not.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: