- C++ threshold for "stupid" sorting algorithms (O(n^2)) - 9 Updates
- Don't be fooled by cpp.sh - 4 Updates
- Is there a way to determine endianess in a constexpr-function ? - 5 Updates
- uint32_t is not the same as long unsigned int ? - 3 Updates
- I'd like to have unusing - 3 Updates
- Union type punning in C++ - 1 Update
| Bonita Montero <Bonita.Montero@gmail.com>: Jan 05 03:54AM +0100 >> are just a few elements. > But there might be billions of such small sorts. It's a rare situation, > but it shows that the logic you used is not sound. Try this on your computer. #include <iostream> #include <chrono> #include <iterator> #include <functional> #include <algorithm> #include <vector> #include <random> #include <climits> #include <chrono> using namespace std; using namespace chrono; template<typename It, typename Pred = less<typename iterator_traits<It>::value_type>> void bubblesort( It begin, It end, Pred const &p = Pred() ); int main() { using timestamp = time_point<high_resolution_clock>; size_t const SIZE = 20, ROUNDS = 100'000; vector<int> vRef( SIZE, 0 ), vSort( SIZE, 0 ); mt19937_64 rg; uniform_int_distribution<int> uid( numeric_limits<int>::min(), numeric_limits<int>::max() ); timestamp start; uint64_t bsNs, sNs; for( int &v : vRef ) v = uid( rg ); for( size_t c = 2; c <= SIZE; ++c ) { start = high_resolution_clock::now(); for( size_t r = ROUNDS; r != 0; --r ) copy( vRef.begin(), vRef.begin() + c, vSort.begin() ), bubblesort( vSort.begin(), vSort.end() ); bsNs = (uint64_t)duration_cast<nanoseconds>( high_resolution_clock::now() - start ).count(); start = high_resolution_clock::now(); for( size_t r = ROUNDS; r != 0; --r ) copy( vRef.begin(), vRef.begin() + c, vSort.begin() ), sort( vSort.begin(), vSort.end() ); sNs = (uint64_t)duration_cast<nanoseconds>( high_resolution_clock::now() - start ).count(); cout << "size:\t" << c << "\tbs:\t" << bsNs / 1.0E6 << "\ts:\t" << sNs / 1.0E6 << endl; } } template<typename It, typename Pred> void bubblesort( It begin, It end, Pred const &p ) { bool swapped = true; It up; for( ; swapped && end - begin >= 2; --end ) { swapped = false; up = begin; do if( p( up[1], up[0] ) ) swap( up[1], up[0] ), swapped = true; while( ++up != end - 1 ); } } With this coded and a current MSVC on my Ryzen 7 1800X, bubblesort is even slower with _2_ elements ! |
| Bonita Montero <Bonita.Montero@gmail.com>: Jan 05 04:04AM +0100 > ... > With this coded and a current MSVC on my Ryzen 7 1800X, > bubblesort is even slower with _2_ elements ! This are the MSVC-results: size: 2 bs: 4.3066 s: 3.5168 size: 3 bs: 3.4546 s: 3.371 size: 4 bs: 7.6116 s: 3.9207 size: 5 bs: 7.1022 s: 3.7874 size: 6 bs: 10.2507 s: 4.1151 size: 7 bs: 11.1817 s: 4.1515 size: 8 bs: 13.1037 s: 4.386 size: 9 bs: 13.4265 s: 4.63 size: 10 bs: 13.5443 s: 4.531 size: 11 bs: 19.1778 s: 5.0473 size: 12 bs: 18.9487 s: 5.2043 size: 13 bs: 17.51 s: 4.7317 size: 14 bs: 16.1673 s: 5.6115 size: 15 bs: 23.015 s: 5.9018 size: 16 bs: 24.3316 s: 6.3325 size: 17 bs: 23.1535 s: 6.5593 size: 18 bs: 24.1078 s: 6.9179 size: 19 bs: 20.7311 s: 7.6469 size: 20 bs: 21.4417 s: 7.5721 |
| Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Jan 05 03:59AM On 05/01/2020 02:54, Bonita Montero wrote: > } > With this coded and a current MSVC on my Ryzen 7 1800X, > bubblesort is even slower with _2_ elements ! But we already know that bubblesort is slow (who doesn't) so what is your fucking point? /Flibble -- "Snakes didn't evolve, instead talking snakes with legs changed into snakes." - Rick C. Hodgin "You won't burn in hell. But be nice anyway." – Ricky Gervais "I see Atheists are fighting and killing each other again, over who doesn't believe in any God the most. Oh, no..wait.. that never happens." – Ricky Gervais "Suppose it's all true, and you walk up to the pearly gates, and are confronted by God," Byrne asked on his show The Meaning of Life. "What will Stephen Fry say to him, her, or it?" "I'd say, bone cancer in children? What's that about?" Fry replied. "How dare you? How dare you create a world to which there is such misery that is not our fault. It's not right, it's utterly, utterly evil." "Why should I respect a capricious, mean-minded, stupid God who creates a world that is so full of injustice and pain. That's what I would say." |
| Bonita Montero <Bonita.Montero@gmail.com>: Jan 05 05:03AM +0100 >> bubblesort is even slower with _2_ elements ! > But we already know that bubblesort is slow (who doesn't) so what is > your fucking point? Soviet Mario said that bubblesort might be faster for a few elements. I said that doesn't count because such small sorts have a low runtime anyway. But Ben told that this might be relevant because ther might be billions of such sorts. And I measured that bubblesort is even slower for a few elements; that's not apparent. |
| Ben Bacarisse <ben.usenet@bsb.me.uk>: Jan 05 04:20AM >> But there might be billions of such small sorts. It's a rare situation, >> but it shows that the logic you used is not sound. > Try this on your computer. First, I was commenting on your logic, not your conclusion. Your conclusion -- don't use simple but slow sorts -- might be right but you can't get to that conclusion using the logic you used. Second, the results from your timing code will depend on the data as well as on the algorithm. For example, on my laptop, with sorted data, your code (slightly modified to use non-random numbers) shows bubble sort as faster (by a factor of at least 2) for all sizes tested (you go up to 20). I don't know if the code is measuring this correctly -- I am just reporting on the output. Third, the OP was not just about bubble sort. To get a sound answer from measurements, the best simple sort, insertion sort, should be used. <cut timing code> -- Ben. |
| Bonita Montero <Bonita.Montero@gmail.com>: Jan 05 05:26AM +0100 > your code (slightly modified to use non-random numbers) shows bubble > sort as faster (by a factor of at least 2) for all sizes tested (you > go up to 20). ... That's not true. You're a liar. |
| Bonita Montero <Bonita.Montero@gmail.com>: Jan 05 05:50AM +0100 Little bug: > for( size_t r = ROUNDS; r != 0; --r ) > copy( vRef.begin(), vRef.begin() + c, vSort.begin() ), > bubblesort( vSort.begin(), vSort.end() ); bubblesort( vSort.begin(), vSort.begin() + c ); > cout << "size:\t" << c << "\tbs:\t" << bsNs / 1.0E6 << "\ts:\t" > << sNs / 1.0E6 << endl; > } Before I measured always the same block-size. With that code now bubblesort is faster up to 6 elements. size: 2 bs: 0.3522 s: 0.9208 size: 3 bs: 0.4927 s: 1.0144 size: 4 bs: 0.9208 s: 1.6702 size: 5 bs: 1.2458 s: 1.6793 size: 6 bs: 1.6039 s: 2.1342 size: 7 bs: 2.0537 s: 1.9543 size: 8 bs: 2.4752 s: 2.6737 size: 9 bs: 3.1595 s: 3.0331 size: 10 bs: 3.7429 s: 3.187 size: 11 bs: 4.4821 s: 3.4102 size: 12 bs: 5.5326 s: 4.0687 size: 13 bs: 7.0794 s: 4.2507 size: 14 bs: 7.0796 s: 4.6087 size: 15 bs: 9.5706 s: 5.3354 size: 16 bs: 10.4491 s: 5.8877 size: 17 bs: 13.0148 s: 5.9372 size: 18 bs: 13.8979 s: 7.4023 size: 19 bs: 16.1734 s: 7.5393 size: 20 bs: 18.0571 s: 8.0887 |
| Ben Bacarisse <ben.usenet@bsb.me.uk>: Jan 05 01:33PM >> sort as faster (by a factor of at least 2) for all sizes tested (you >> go up to 20). ... > That's not true. You're a liar. That's a nasty thing to say. If I thought you were a serious contributer, I'd be offended. $ g++ -std=c++17 -O2 -o s s.cc $ ./s size: 2 bs: 3.08614 s: 8.22362 size: 3 bs: 3.13931 s: 7.59102 size: 4 bs: 3.34163 s: 8.23757 size: 5 bs: 3.09223 s: 8.09352 size: 6 bs: 3.04952 s: 7.66801 size: 7 bs: 3.59429 s: 7.60449 size: 8 bs: 3.0702 s: 7.82664 size: 9 bs: 3.06544 s: 7.61816 size: 10 bs: 3.37942 s: 7.87771 size: 11 bs: 3.06233 s: 7.57085 size: 12 bs: 3.06663 s: 7.67827 size: 13 bs: 3.35755 s: 7.61874 size: 14 bs: 3.05564 s: 7.66383 size: 15 bs: 3.06742 s: 7.66818 size: 16 bs: 3.12856 s: 7.84636 size: 17 bs: 3.0493 s: 7.60936 size: 18 bs: 3.29187 s: 7.81111 size: 19 bs: 3.07461 s: 7.88316 size: 20 bs: 3.05721 s: 7.47266 This is with an already sorted array. s.cc has this change from your code v = 1; //uid( rg ); BTW, I make no comment on what these number mean -- your program may be wrong for all I know. -- Ben. |
| Bonita Montero <Bonita.Montero@gmail.com>: Jan 05 03:01PM +0100 >> That's not true. You're a liar. > That's a nasty thing to say. If I thought you were a serious > contributer, I'd be offended. Try the fixed code. The fixed code gives this with gcc on my computer: size: 2 bs: 0.7988 s: 1.2735 size: 3 bs: 0.9466 s: 1.5443 size: 4 bs: 1.2005 s: 1.6128 size: 5 bs: 1.5233 s: 1.9473 size: 6 bs: 2.353 s: 1.9982 --- size: 7 bs: 2.2377 s: 2.365 size: 8 bs: 4.0274 s: 2.727 size: 9 bs: 3.4135 s: 3.2835 size: 10 bs: 4.171 s: 3.269 size: 11 bs: 4.7766 s: 3.7635 size: 12 bs: 5.6038 s: 4.1902 size: 13 bs: 7.9656 s: 4.0113 size: 14 bs: 8.9014 s: 4.5925 size: 15 bs: 9.9181 s: 4.7311 size: 16 bs: 11.1119 s: 4.9711 size: 17 bs: 12.4162 s: 6.0172 size: 18 bs: 14.4748 s: 6.85 size: 19 bs: 15.8686 s: 7.1291 size: 20 bs: 20.8648 s: 7.2139 Above 5 elements quicksort ist faster. |
| Robert Wessel <robertwessel2@yahoo.com>: Jan 04 06:02PM -0600 >>VLAs no longer being mandatory, >They're not? Figures, aside from variadic macros they're the only thing in >C99 that I found useful. C11 made both complex support and VLAs optional. Complex was already optional in C99 for freestanding implementations, C11 extended the dispensation to hosted implementations. |
| Richard Damon <Richard@Damon-Family.org>: Jan 04 08:04PM -0500 On 12/31/19 12:46 PM, Bonita Montero wrote: > -Wcomment > It's not rare that you first comment out a part with // and > then the outer block with /* */. This isn't really a problem. But that doesn't generate a warning. -Wcomment warns on /* /* */ */ (nested /* comments) or // \ Using a line continuation slash inside a line based comment > -Wenum-compare > Unscoped enums are in the same namespace so they should be > all comparable. They may be legally comparable (so not an ERROR), but I can't think of many cases where I would want to compare an enum to values of a different enums. > -Wmissing-braces > That's really a useless aesthetic warning. Maybe, not hard to get it right. Bad aesthetics are a good way to hide problems. > -Wreorder > It's very rare that the order of initialization-calls counts. but sometime it does (if one member uses the value of another in its initalization). Keeping initialization matching order of definition avoids a number of surprises. It also isn't that hard to keep the order right (especially if you use this warning) > -Wunused-function > This would be disturbing if you would have the function in the > code for a later purpose. Warning is early code development may not be that hard. Adding #if 0 
Subscribe to:
Post Comments (Atom)
|
No comments:
Post a Comment