Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #70923 > unrolled thread

C++ threshold for "stupid" sorting algorithms (O(n^2))

Back to article view | Back to comp.lang.c++

Contents

  C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-01 13:17 +0100
    Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-01 13:25 +0100
      Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-01 17:33 +0000
        Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 03:54 +0100
          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 04:04 +0100
          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-01-05 03:59 +0000
            Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 05:03 +0100
              Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-05 21:13 +0100
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 05:50 +0100
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 06:55 +0100
          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-05 04:20 +0000
            Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 05:26 +0100
              Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-05 13:33 +0000
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 15:01 +0100
                  Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-05 22:26 +0000
                    Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 05:39 +0100
                      Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-05 23:54 -0800
                        Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 08:59 +0100
                          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-06 01:02 -0800
                            Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Jorgen Grahn <grahn+nntp@snipabacken.se> - 2020-01-06 09:34 +0000
                            Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 10:36 +0100
                              Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-06 03:33 -0800
                                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-06 12:59 +0100
                      Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-06 22:54 +0000
                        Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-07 04:57 +0100
                          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Melzzzzz <Melzzzzz@zzzzz.com> - 2020-01-07 07:51 +0000
            Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Melzzzzz <Melzzzzz@zzzzz.com> - 2020-01-05 15:16 +0000
          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-05 05:50 +0100
    Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bo Persson <bo@bo-persson.se> - 2020-01-01 13:34 +0100
      Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-01 14:09 +0100
        Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bo Persson <bo@bo-persson.se> - 2020-01-01 15:16 +0100
    Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Robert Wessel <robertwessel2@yahoo.com> - 2020-01-01 09:24 -0600
      Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-01 17:12 +0100
        Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-02 15:11 -0800
      Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-01-10 13:53 -0800
        Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Robert Wessel <robertwessel2@yahoo.com> - 2020-01-10 16:45 -0600
          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-01-21 03:11 -0800
            Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-21 15:04 +0000
              Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-01-27 11:52 -0800
                Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-01-30 00:32 +0000
                  Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-02-15 05:30 -0800
                    Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-15 16:39 +0000
    Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Christian Gollwitzer <auriocus@gmx.de> - 2020-01-02 11:28 +0100
      Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-02 19:46 +0100
        Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-02 20:00 +0100
          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Bonita Montero <Bonita.Montero@gmail.com> - 2020-01-03 07:37 +0100
          Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-03 20:06 +0100
            Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Öö Tiib <ootiib@hot.ee> - 2020-01-03 11:12 -0800
              Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Soviet_Mario <SovietMario@CCCP.MIR> - 2020-01-04 17:58 +0100
            Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) David Brown <david.brown@hesbynett.no> - 2020-01-03 21:25 +0100
              Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Melzzzzz <Melzzzzz@zzzzz.com> - 2020-01-03 21:00 +0000

Page 1 of 3  [1] 2 3  Next page →

#70923 — C++ threshold for "stupid" sorting algorithms (O(n^2))

In your experience, what is (roughly) a reasonable threshold 
(n) in terms of convenience of passing from stupid 
algorithms (bubblesort, gnomesort) to better and more 
complex ones ?

I know this depends a lot also on HW.

But to write down an order of magnitude, I'm talking about 
small data sets (some tens to at worst some hundredth, never 
above 1000).

With such small figures, I was thinking that even the most 
simple O(n^2) bubble or gnome could be acceptable.
But I've no experience in real comparison.

The application is not performance intensive, at least for 
this operations which would be performed only a few times


I did not mention that the algorithm HAS TO BE "stable" : 
not to move equally ranked items (in order to allow tables 
to be sorted by multiple keys)


-- 
1) Resistere, resistere, resistere.
2) Se tutti pagano le tasse, le tasse le pagano tutti
Soviet_Mario - (aka Gatto_Vizzato)

[toc] | [next] | [standalone]

#70924

> In your experience, what is (roughly) a reasonable threshold (n) in 
> terms of convenience of passing from stupid algorithms (bubblesort, 
> gnomesort) to better and more complex ones ?

Don't use the simpler algorithms. Algthough they might be faster
on a few elements, their runtime doesn't count then because there
are just a few elements.

[toc] | [prev] | [next] | [standalone]

#70939

Bonita Montero <Bonita.Montero@gmail.com> writes:

>> In your experience, what is (roughly) a reasonable threshold (n) in
>> terms of convenience of passing from stupid algorithms (bubblesort,
>> gnomesort) to better and more complex ones ?
>
> Don't use the simpler algorithms. Algthough they might be faster
> on a few elements, their runtime doesn't count then because there
> 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.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#71126

>>> In your experience, what is (roughly) a reasonable threshold (n) in
>>> terms of convenience of passing from stupid algorithms (bubblesort,
>>> gnomesort) to better and more complex ones ?

>> Don't use the simpler algorithms. Algthough they might be faster
>> on a few elements, their runtime doesn't count then because there
>> 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 !

[toc] | [prev] | [next] | [standalone]

#71127

> ...
> 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

[toc] | [prev] | [next] | [standalone]

#71129

On 05/01/2020 02:54, Bonita Montero wrote:
>>>> In your experience, what is (roughly) a reasonable threshold (n) in
>>>> terms of convenience of passing from stupid algorithms (bubblesort,
>>>> gnomesort) to better and more complex ones ?
> 
>>> Don't use the simpler algorithms. Algthough they might be faster
>>> on a few elements, their runtime doesn't count then because there
>>> 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 !

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."

[toc] | [prev] | [next] | [standalone]

#71130

>> 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?

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.

[toc] | [prev] | [next] | [standalone]

#71156

On 05/01/20 05:03, 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?
> 
> 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.


If I did understand right, Ben was saying that very short 
sorting could be repeated thousands of times (not meaning 
sorting thousands of items, but some tens of items in 
thousand occasions : giving a multiplier of advantage or 
disadvantage).


Anyway : to sum up this thread.

I've found the stable_sort in the header algorithm.
I did not fully understand its internals (a template of too 
much parameters obscure to me), so I have decided to recode 
the 10 lines long example Gnome Sort (optimized version) 
from Wikipedia.


Moreover I have to adapt it to sorting rows / columns of a 
rectangular matrix, where the key-field is a parameter and 
whole columns/rows have to be moved, not just the key-field

As I did not well understand the standard algorithm version, 
I gave up with it in this more customized sorting.

Tnx to all

-- 
1) Resistere, resistere, resistere.
2) Se tutti pagano le tasse, le tasse le pagano tutti
Soviet_Mario - (aka Gatto_Vizzato)

[toc] | [prev] | [next] | [standalone]

#71167

> I've found the stable_sort in the header algorithm.
> I did not fully understand its internals ...

stable_sort is usually mergesort because mergesort is usually
the fastest stable sort algorithm.

[toc] | [prev] | [next] | [standalone]

#71168

> I've found the stable_sort in the header algorithm.
> I did not fully understand its internals ...

As I said stable_sort is usually mergesort.
I developed a parallel mergesort some month ago.
I stripped it to single-threaded and here's the code:

#include <iostream>
#include <iterator>
#include <vector>
#include <random>
#include <functional>
#include <memory>
#include <cassert>

template<typename It,
          typename Cmp       = std::less<typename 
std::iterator_traits<It>::value_type>,
          typename Allocator = std::allocator<typename 
std::iterator_traits<It>::value_type>>
class merge_sort
{
public:
     merge_sort( It start, It end, Cmp const &cmp = Cmp(), Allocator 
const &alloc = Allocator() );

private:
     Cmp m_cmp;
     template<typename UpIt, typename BufIt>
     void recursion( UpIt start, UpIt end, BufIt buf );
     template<typename UpIt, typename BufIt>
     void merge( UpIt start, BufIt leftBuf, BufIt rightBuf, BufIt bufEnd );
};

template<typename It, typename Cmp, typename Allocator>
merge_sort<It, Cmp, Allocator>::merge_sort( It start, It end, Cmp const 
&cmp, Allocator const &alloc ) :
     m_cmp( cmp )
{
     using namespace std;
     using T = typename iterator_traits<It>::value_type;
     size_t bs = 0;
     // calculate buffer-/stack-size
     for( size_t split = end - start; split > 1; bs += split, split -= 
split / 2 );
     vector<T, Allocator> buf( bs, T(), alloc );;
     recursion( start, end, buf.begin() );
}

template<typename It, typename Cmp, typename Allocator>
template<typename UpIt, typename BufIt>
void merge_sort<It, Cmp, Allocator>::recursion( UpIt start, UpIt end, 
BufIt buf )
{
     using namespace std;
     size_t n = end - start;
     if( n < 2 )
         return;
     copy( start, end, buf );
     size_t right      = n / 2,
            left       = n - right;
     BufIt  leftBuf    = buf,
            leftBufEnd = buf + left,
            rightBuf   = leftBufEnd,
            bufEnd     = buf + n;
     recursion( leftBuf,  leftBufEnd, bufEnd );
     recursion( rightBuf, bufEnd,     bufEnd );
     merge( start, leftBuf, rightBuf, bufEnd );
}

template<typename It, typename Cmp, typename Allocator>
template<typename UpIt, typename BufIt>
void merge_sort<It, Cmp, Allocator>::merge( UpIt start, BufIt leftBuf, 
BufIt rightBuf, BufIt bufEnd )
{
     assert(leftBuf < rightBuf && rightBuf < bufEnd);
     BufIt leftBufEnd = rightBuf;
     for( UpIt wrtBack = start; ; )
         if( m_cmp( *leftBuf, *rightBuf ) )
         {
             *wrtBack++ = *leftBuf;
             if( ++leftBuf == leftBufEnd )
             {
                 // faster for small number of elements than std::copy
                 do
                     *wrtBack++ = *rightBuf;
                 while( ++rightBuf != bufEnd );
                 return;
             }
         }
         else
         {
             *wrtBack++ = *rightBuf;
             if( ++rightBuf == bufEnd )
             {
                 do
                     *wrtBack++ = *leftBuf;
                 while( ++leftBuf != leftBufEnd );
                 return;
             }
         }
}

int main()
{
     using namespace std;
     size_t const                  SIZE = 1'000'000;
     vector<int>                   vSort( SIZE, 0 );
     mt19937_64                    rg;
     uniform_int_distribution<int> uid( numeric_limits<int>::min(), 
numeric_limits<int>::max() );
     for( int &v : vSort )
         v = uid( rg );
     merge_sort( vSort.begin(), vSort.end() );
}

Maybe you would be able to understand what's going on.

[toc] | [prev] | [next] | [standalone]

#71131

Bonita Montero <Bonita.Montero@gmail.com> writes:

>>>> In your experience, what is (roughly) a reasonable threshold (n) in
>>>> terms of convenience of passing from stupid algorithms (bubblesort,
>>>> gnomesort) to better and more complex ones ?
>
>>> Don't use the simpler algorithms. Algthough they might be faster
>>> on a few elements, their runtime doesn't count then because there
>>> 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.

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.

[toc] | [prev] | [next] | [standalone]

#71132

>> Try this on your computer.

> 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). ...

That's not true. You're a liar.

> Third, the OP was not just about bubble sort.

> ... (bubblesort, gnomesort) ...

[toc] | [prev] | [next] | [standalone]

#71144

Bonita Montero <Bonita.Montero@gmail.com> writes:

>>> Try this on your computer.
>
>> 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). ...
>
> 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.

[toc] | [prev] | [next] | [standalone]

#71145

>>> 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). ...

>> 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.

[toc] | [prev] | [next] | [standalone]

#71159

Bonita Montero <Bonita.Montero@gmail.com> writes:

>>>> 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). ...
>
>>> 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:

No apology for accusing me of lying I see.

The fixed code does not alter what I said: the simple sort is faster for
all your test sizes for some data sets -- specifically when the data are
already sorted.  The factor is now smaller (no longer always greater
than 2) but still between 1.5 and 2.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#71165

>> Try the fixed code. The fixed code gives this with gcc on my computer:

> No apology for accusing me of lying I see.
> The fixed code does not alter what I said: the simple sort is faster for
> all your test sizes for some data sets -- specifically when the data are
> already sorted.  The factor is now smaller (no longer always greater
> than 2) but still between 1.5 and 2.

The discussion wasn't about presorted datasets and that's not usual.

[toc] | [prev] | [next] | [standalone]

#71169

On Monday, 6 January 2020 06:40:02 UTC+2, Bonita Montero  wrote:
> >> Try the fixed code. The fixed code gives this with gcc on my computer:
> 
> > No apology for accusing me of lying I see.
> > The fixed code does not alter what I said: the simple sort is faster for
> > all your test sizes for some data sets -- specifically when the data are
> > already sorted.  The factor is now smaller (no longer always greater
> > than 2) but still between 1.5 and 2.
> 
> The discussion wasn't about presorted datasets and that's not usual.

Already sorted or close to sorted data tends to be more likely than
other permutations. But main issue is why you constantly write such
blatant falsehoods? Ben specifically wrote "with sorted data":

Bonita Montero wrote:
> Ben Bacarisse  wrote:
>> Ben Bacarisse  wrote:
>> 
>>> Try this on your computer.
>
>> 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). ...
>
> That's not true. You're a liar.

You are clearly liar yourself, Ben did not lie. 

[toc] | [prev] | [next] | [standalone]

#71170

>> The discussion wasn't about presorted datasets and that's not usual.

> Already sorted or close to sorted data tends to be more likely than
> other permutations.

Give me a URL to a paper that proves this.

[toc] | [prev] | [next] | [standalone]

#71171

On Monday, 6 January 2020 09:59:18 UTC+2, Bonita Montero  wrote:
> >> The discussion wasn't about presorted datasets and that's not usual.
> 
> > Already sorted or close to sorted data tends to be more likely than
> > other permutations.
> 
> Give me a URL to a paper that proves this.

Miserable attempt of hiding being caught being liar noted. 

It is just quite common with real world data that it was entered in sorted order
or that some other part of system already sorted it.
<https://en.wikipedia.org/wiki/Sorting_algorithm#Efficient_sorts>
"Second, the algorithms often perform poorly on already sorted data or almost
sorted data – these are common in real-world data, and can be sorted in O(n)
time by appropriate algorithms." 

[toc] | [prev] | [next] | [standalone]

#71172

On Mon, 2020-01-06, Öö Tiib wrote:
> On Monday, 6 January 2020 09:59:18 UTC+2, Bonita Montero  wrote:
>> >> The discussion wasn't about presorted datasets and that's not usual.
>> 
>> > Already sorted or close to sorted data tends to be more likely than
>> > other permutations.
>> 
>> Give me a URL to a paper that proves this.
...

> It is just quite common with real world data that it was entered in sorted order
> or that some other part of system already sorted it.
> <https://en.wikipedia.org/wiki/Sorting_algorithm#Efficient_sorts>

It's rather obvious if you think about it.  If a sequence of records
doesn't appear at random, it's probably going to be sorted according
to the record's primary key, because it makes sense for the data
source to keep the records in some order.

This has other consequences, too.  A system I once worked with
accepted tens of thousands of network connections/sessions, and stored
them as a std::map.  This worked fine if clients connected one by one,
but if the next gateway (there was such a thing) restarted, it
reestablished the sessions in key order, and performance suffered
because the std::map got rebalanced repeatedly.  We had to add a
workaround for that (I forget what the workaround was).

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.c++

csiph-web