Timeline for Find the 1st and 2nd largest num in an array, O(log N) + O(N) version
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 20, 2017 at 13:26 | history | edited | alecxe | CC BY-SA 3.0 |
added 23 characters in body
|
| May 23, 2017 at 12:40 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Sep 19, 2016 at 17:53 | answer | added | Ext3h | timeline score: 4 | |
| Sep 19, 2016 at 16:45 | answer | added | very hit | timeline score: 0 | |
| Sep 19, 2016 at 15:53 | comment | added | very hit | @Vogel612 Got it, so I should post a self-answer. | |
| Sep 19, 2016 at 8:35 | answer | added | greybeard | timeline score: 0 | |
| Sep 18, 2016 at 15:28 | comment | added | Vogel612 | @greybeard that's an answer ... You should write that as an answer | |
| Sep 18, 2016 at 15:27 | comment | added | Vogel612 | I have rolled back the last edit. Please see what you may and may not do after receiving answers. | |
| Sep 18, 2016 at 15:27 | history | rollback | Vogel612 |
Rollback to Revision 4
|
|
| Sep 18, 2016 at 13:41 | comment | added | very hit | @cloakedlearning I want to test if the optimal algorithm valid, so I make my own implementation. Thanks for your method, it's really elegant. I also found that the time of memory allocation may harm the performance, so I want to know if there is smarter method can avoid it. Anyway, theory in class is really different with real-world scene. | |
| Sep 18, 2016 at 13:23 | history | edited | very hit | CC BY-SA 3.0 |
update code according to other user's advice
|
| Sep 18, 2016 at 5:37 | answer | added | vnp | timeline score: 2 | |
| Sep 18, 2016 at 5:01 | comment | added | greybeard |
(Try max_but1 or max2nd - I cringe sub-vocalising max2rd). O(logN) + O(N) is just O(N)… algo1 can be improved by initialising max1st and max2nd to src_data[0] and just "handing down" max candidates to max2nd when max1st is exceeded: N-1 comparisons.
|
|
| Sep 18, 2016 at 0:32 | history | tweeted | twitter.com/StackCodeReview/status/777304177856905217 | ||
| Sep 17, 2016 at 16:37 | history | edited | 200_success | CC BY-SA 3.0 |
deleted 35 characters in body; edited tags; edited title; deleted 1 character in body
|
| Sep 17, 2016 at 16:28 | comment | added | cloakedlearning |
Also it is not surprising to me that that algo1 is outperforming algo2. The algorithm suggested in the linked question may minimize the number of comparison operations - but you need to remember you're running on real hardware. algo1 doesn't need to perform any allocations (other than the result vector) and is far more cache friendly. We can review this code here, but explaining the relative performance of the 2 algorithms is more likely a question for stackoverflow.
|
|
| Sep 17, 2016 at 16:25 | comment | added | cloakedlearning |
It sounds like you want to implement this algorithm for yourself. But this is reasonably easy with the standard library std::nth_element(src.begin(),src.begin()+1, src.end(), std::greater<int>());
|
|
| Sep 17, 2016 at 15:08 | history | edited | very hit | CC BY-SA 3.0 |
comment correct
|
| Sep 17, 2016 at 15:02 | comment | added | very hit | @pacmaninbw /O2 in VS2013. | |
| Sep 17, 2016 at 14:59 | comment | added | pacmaninbw♦ | Did you compile -O3? | |
| Sep 17, 2016 at 14:46 | history | edited | very hit | CC BY-SA 3.0 |
code error correct
|
| Sep 17, 2016 at 14:42 | review | First posts | |||
| Sep 17, 2016 at 14:47 | |||||
| Sep 17, 2016 at 14:39 | history | asked | very hit | CC BY-SA 3.0 |