Timeline for Performance of C++ Union-Find solution is strangely poor
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 10, 2020 at 13:24 | history | edited | CommunityBot |
Commonmark migration
|
|
| Dec 29, 2019 at 19:24 | vote | accept | Evan Weissburg | ||
| Jan 31, 2018 at 5:07 | comment | added | Cris Luengo | @EvanWeissburg: sorting is your largest cost, maybe you need to avoid sorting an array with so many duplicate values. If all fences along a column have the same length, and the fences along a row have the same length, maybe you only need to sort the column widths and row widths separately, then compose your edge list. And maybe the edge list can be implied, you might not even need to store it... | |
| Jan 31, 2018 at 3:45 | comment | added | user1118321 |
A quick profile run shows that in the new code sorting the vector is taking up 77% of the time, find_par() is taking up 12% of the time, and calls to push_back() are taking up about 9% of the time. Have you entered the solution into the tester to see if it passes. Yours runs 100x in under a second on my machine, so it doesn't seem too bad. I haven't had time to assess the given solution.
|
|
| Jan 31, 2018 at 3:30 | comment | added | Evan Weissburg | It's actually still too slow even when using a preallocated vector -- have you looked at the linked solution in the OP? Maybe that will give you more of a hint than it gave me about why my solution is too slow. I added my updated code to the OP as well. | |
| Jan 31, 2018 at 2:43 | comment | added | user1118321 | OK, I've redone it. It's not drastically different, in that the same functions are implicated. (Not surprising, since the code is so small.) But the amounts are pretty different. 85% vs 56% for the highest cost function. | |
| Jan 31, 2018 at 2:41 | history | edited | user1118321 | CC BY-SA 3.0 |
Updated the performance numbers to be more accurate
|
| Jan 30, 2018 at 16:32 | comment | added | user1118321 | Actually, I screwed up the performance analysis because of the globals. I'll re-run it tonight and post an update. Sorry about that. It just occurred to me this morning. | |
| Jan 30, 2018 at 12:07 | comment | added | Evan Weissburg | This is code for a (past) programming competition, some time counts especially with long long. Thanks for the advice, I'll test out the optimizations tonight. | |
| Jan 30, 2018 at 9:33 | comment | added | Jorge Bellon | Geometric scientific applications make wide use of quad-trees (2D) and oct-trees (3D) for improved insertion and search times. Here is an explanation of these structures for a GPU oriented application (the figures in the article help to understand how they work). | |
| Jan 30, 2018 at 4:45 | history | answered | user1118321 | CC BY-SA 3.0 |