{"action":"created","issue":{"url":"https://api.github.com/repos/numpy/numpy/issues/12418","repository_url":"https://api.github.com/repos/numpy/numpy","labels_url":"https://api.github.com/repos/numpy/numpy/issues/12418/labels{/name}","comments_url":"https://api.github.com/repos/numpy/numpy/issues/12418/comments","events_url":"https://api.github.com/repos/numpy/numpy/issues/12418/events","html_url":"https://github.com/numpy/numpy/pull/12418","id":382219873,"node_id":"MDExOlB1bGxSZXF1ZXN0MjMxOTc2OTcz","number":12418,"title":"WIP, ENH: Add timsort to npysort","user":{"login":"liwt31","id":22628546,"node_id":"MDQ6VXNlcjIyNjI4NTQ2","avatar_url":"https://avatars3.githubusercontent.com/u/22628546?v=4","gravatar_id":"","url":"https://api.github.com/users/liwt31","html_url":"https://github.com/liwt31","followers_url":"https://api.github.com/users/liwt31/followers","following_url":"https://api.github.com/users/liwt31/following{/other_user}","gists_url":"https://api.github.com/users/liwt31/gists{/gist_id}","starred_url":"https://api.github.com/users/liwt31/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/liwt31/subscriptions","organizations_url":"https://api.github.com/users/liwt31/orgs","repos_url":"https://api.github.com/users/liwt31/repos","events_url":"https://api.github.com/users/liwt31/events{/privacy}","received_events_url":"https://api.github.com/users/liwt31/received_events","type":"User","site_admin":false},"labels":[{"id":6359239,"node_id":"MDU6TGFiZWw2MzU5MjM5","url":"https://api.github.com/repos/numpy/numpy/labels/01%20-%20Enhancement","name":"01 - Enhancement","color":"fef2c0","default":false},{"id":1024395160,"node_id":"MDU6TGFiZWwxMDI0Mzk1MTYw","url":"https://api.github.com/repos/numpy/numpy/labels/25%20-%20WIP","name":"25 - WIP","color":"fef2c0","default":false},{"id":16917029,"node_id":"MDU6TGFiZWwxNjkxNzAyOQ==","url":"https://api.github.com/repos/numpy/numpy/labels/component:%20numpy.core","name":"component: numpy.core","color":"009800","default":false}],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":32,"created_at":"2018-11-19T13:41:40Z","updated_at":"2019-02-03T15:02:16Z","closed_at":"2019-01-31T14:22:41Z","author_association":"CONTRIBUTOR","pull_request":{"url":"https://api.github.com/repos/numpy/numpy/pulls/12418","html_url":"https://github.com/numpy/numpy/pull/12418","diff_url":"https://github.com/numpy/numpy/pull/12418.diff","patch_url":"https://github.com/numpy/numpy/pull/12418.patch"},"body":"This is part of #12186 .\r\nThis PR is still under development in that only numeric timsort is implemented. For argsort and sorting algorithms of string types and generic type, a dummy mergesort is pasted as place-holder. I wish to hear more feedback before moving on, for it appears implementing the sibling sorting algorithms requires lots of copy and paste.\r\n\r\n### Overview\r\nCurrently what I've done:\r\n1. Implement timsort for numeric sort. More on this below.\r\n1. Add some lines in .gitignore to ignore generated files.\r\n1. Add another option `'t'` (timsort) for `kind` argument in `sort` function. This is primarily for benchmark convenience. \r\n1. Add the timsort algorithm to the test suite.\r\n1. Some benchmark between the four sorting algorithms (quick merge heap tim). The benchmark is hosted in [another repo](https://github.com/liwt31/numpy-sort-benchmark).\r\n\r\n\r\n### The algorithm\r\nThe implementation is primarily based on [Tim's little article](https://github.com/python/cpython/blob/master/Objects/listsort.txt), with some simplifications:\r\n* Insertion sort in run-counting is not binary-search insertion sort\r\n* No gallop mode appear in merge process\r\n\r\nThe reason for these simplifications is their large overhead. Tim's algorithm is specially designed for CPython, which have a very time-consuming comparing function. The direction of Tim's optimization is to reduce the number of comparisons required whenever possible. However, this is not necessary for most NumPy use case. Maybe for generic sort, these further optimizations can be included, however, IMHO this should be done in another PR.\r\nI haven't prepared organized materials to show their \"large overhead\" I found in my experiments. If anyone is interested I'd be happy to elaborate on this.\r\n\r\n\r\n### Benchmark\r\nThe [benchmark](https://github.com/liwt31/numpy-sort-benchmark) includes a benchmark script, a jupyter-notebook to show the shape of the arrays involved in the benchmark for an intuitive picture, and a readme file for benchmark results and comments. Simply speaking, timsort performs well in \"nearly sorted\" data and shows minimal overhead in random data. Besides, I noticed the following 2 interesting phenomena:\r\n* Quicksort is slower than mergesort for random data, demonstrating that there has to be something wrong with the current quicksort algorithm.\r\n* Standard deviation for time cost is very large even for the definitive already sorted array.\r\n\r\nI haven't got time to dig into these and I'm more than happy to hear from you if they are actually perfectly normal.\r\nThough timsort is designed to be stable and I've tried to make it so, I haven't done any benchmark or test for this, because I only have numeric sort in my hand.\r\n\r\n\r\n### Feedbacks I wish to hear\r\n* Most importantly, is the timsort implementation OK? If so I can start porting it to argsort and so on.\r\n* Should timsort replace mergesort? (according to benchmark result probably so)\r\n* Is there any need to improve the numpy benchmark suite for sorting algorithms? #12368\r\n* All other comments, advice and suggestions.\r\n\r\n### Todo\r\n* [x] Implement argsort, string sort and generic sort. \r\n* [x] Tests and docs\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/numpy/numpy/issues/comments/460059222","html_url":"https://github.com/numpy/numpy/pull/12418#issuecomment-460059222","issue_url":"https://api.github.com/repos/numpy/numpy/issues/12418","id":460059222,"node_id":"MDEyOklzc3VlQ29tbWVudDQ2MDA1OTIyMg==","user":{"login":"charris","id":77272,"node_id":"MDQ6VXNlcjc3Mjcy","avatar_url":"https://avatars3.githubusercontent.com/u/77272?v=4","gravatar_id":"","url":"https://api.github.com/users/charris","html_url":"https://github.com/charris","followers_url":"https://api.github.com/users/charris/followers","following_url":"https://api.github.com/users/charris/following{/other_user}","gists_url":"https://api.github.com/users/charris/gists{/gist_id}","starred_url":"https://api.github.com/users/charris/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/charris/subscriptions","organizations_url":"https://api.github.com/users/charris/orgs","repos_url":"https://api.github.com/users/charris/repos","events_url":"https://api.github.com/users/charris/events{/privacy}","received_events_url":"https://api.github.com/users/charris/received_events","type":"User","site_admin":false},"created_at":"2019-02-03T15:02:16Z","updated_at":"2019-02-03T15:02:16Z","author_association":"MEMBER","body":">~ I think the way to do that is to have more enum types,~\r\n\r\nChanged my mind. We should leave the enum types as it was, maybe with some added aliases, and just change the structure initializations."}}
{"actor":{"display_login":"charris"}}