3 ms·
I'm not sure I've ever sorted an array or list. Rather I put things into sets or maps or built in index---I always wanted to access things later, or have an on-
by Ericson2314 6y ago
I'm not sure I've ever sorted an array or list. Rather I put things into sets or maps or built in index---I always wanted to access things later, or have an on-line data structure (which a sorted flat thing is not).
This whole field is a waste of time, and anachronism from when the master copy was paper/pre-computer and computers were just doing the analytics.
- ComputerGuru 6y agoYour dismissal of “sorted flat thing” as being necessarily not online is incorrect or unnecessarily strict to your detriment. I wrote this comparing the high-level performance of a “set” (AVL or red-black tree) against just that: Faster lookups, insertions, and in-order traversal than a red-black or AVL tree [0] [0]: https://neosmart.net/blog/2019/sorted-list-vs-binary-search-tree/ https://neosmart.net/blog/2019/sorted-list-vs-binary-search-... (Spoiler: it depends on the nature of your data, but sorted vector can be dramatically faster.)
- Ericson2314 6y agoTo be clear I am not against "small sorted flat thing" is an optimization for smaller data structures. My point is I care about the map or set interface. I don't use temporary sets or quicksort to sort....because I don't sort---I don't want a list/array of things in order, basically ever.
- ComputerGuru 6y agoYes, and what I showed you is a set with a set interface, internally implemented as an always-sorted list.
- Ericson2314 6y agoOK sorry, Yes creating a map/set using the small-size optimization is internally doing a sort.
- deleted 6y ago[deleted]
- ncmncm 6y agoPutting things in a map or set is almost invariably slower, often much slower, than a smart sort. If performance doesn't matter, then go ahead. Most often sort performance doesn't matter, or anyway most of the time is spent elsewhere. People do use Python or Bash in production, without shame. But some of us work on problems where performance of the sort does matter.
- Ericson2314 6y agoSure, it is slower, but my point is not that I sort by doing `Map.toList . map.fromList` but that I don't immediately turn the map back to a list. The sorting literature is optimizing a thing I don't need to to do.
- ComputerGuru 6y agoJust because you’re not using it directly doesn’t mean that you’re not benefiting from those optimization in those layers you are depending on.
- Ericson2314 6y agoI'm not using it directly or indirectly. The whole point of this sorting literature is a space-time tradeoff that's completely different from when you want an ordered map/index as the end result.
- deleted 6y ago[deleted]
- Ono-Sendai 6y agoNot really true, putting things in a hash map is pretty fast, and generally faster than a comparison based sort.
- cozzyd 6y agoA hash map is unsorted so it's not a useful way to sort data