Timeline for Merge K Sorted List
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 10, 2017 at 16:17 | comment | added | J_H | Are there other ways to use SortedSet with duplicate values? Yes. It's slightly horrible, but you can tack hash-of-node onto the end of the key, to uniqueify it, and strip off that suffix prior to use. Any nonce would do, even a serial number. Bear in mind that using (immutable) strings as keys would run the risk of high interning overhead. | |
| Sep 10, 2017 at 16:13 | comment | added | J_H | Guava's TreeMultiset may be of use. (And a heapsort implementation actually comes out fairly small.) My 2e6 thought experiment was just noting that some common workloads will benefit if you cache a target value, in this case a million and one, and do simple comparisons against the target value without incurring function call overhead. It's still O(1) constant time, just with a smaller constant buried by the notation. | |
| Sep 10, 2017 at 3:08 | comment | added | Stack crashed | Oh and the ID is really for making duplicate keys possible with the Set. It's not really about stability. If there are other better ways to use SortedSet with duplicate values, I am interested to hear about them. I am reluctant to write my heapsort from scratch. | |
| Sep 10, 2017 at 3:06 | comment | added | Stack crashed | Getting rid of the extra allocation (and reusing min) unfortunately didn't make much improvement in runtime - although I agree it is something that needs to be done regardless. Changing GUID to plain int (incremental) actually improved the runtime quite a bit. Now it is better than 69% of all submissions. I didn't quite follow your last paragraph - but I think I will once I re-read it a few times. Thanks! | |
| Sep 10, 2017 at 2:20 | history | answered | J_H | CC BY-SA 3.0 |