Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147529
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: So here's a fun challenge |
| Date | 2019-11-03 23:34 +1300 |
| Message-ID | <h27oqcFa2cqU7@mid.individual.net> (permalink) |
| References | <NNgvF.21265$hh5.17108@fx07.iad> <h26p2rFa2cqU3@mid.individual.net> <qpm9e1$dsi$1@news.albasani.net> |
On 03/11/2019 23:16, Autist wrote:
> Here's the whole C++-code:
It certainly isn't mine, which was based on the original C:
#include <stdlib.h>
#include <strings.h>
#include <time.h>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
auto number( const char* str )
{
char* end {};
const auto n {strtol( str, &end, 10 )};
if( end == str || *end != '\0' )
{
std::cerr << "bad number " << str << std::endl;
exit(EXIT_FAILURE);
}
return n;
}
double time()
{
timespec ts;
clock_gettime( CLOCK_MONOTONIC, &ts );
uint64_t result = ts.tv_sec;
result = result*1'000'000'000 + ts.tv_nsec;
return result/1'000'000'000.0;
}
// Get random number from within range.
//
int randNbr(int low, int high)
{
return (low + rand() / (RAND_MAX / (high - low + 1) + 1));
}
constexpr size_t charsetLen {62};
constexpr char charset[charsetLen+1] =
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
//build random string of random length
//
std::string randStr( size_t randLen )
{
std::string randStr;
randStr.reserve(randLen+1);
for( unsigned i=0; i < randLen; i++)
{
randStr.append(1,charset[randNbr(0, charsetLen - 1)]);
}
randStr[randLen] = '\0';
return randStr;
}
struct less
{
bool operator()(const std::string& lhs, const std::string& rhs) const
{
return strcasecmp(lhs.c_str(), rhs.c_str()) < 0;
}
};
int run( int argc, const char** argv )
{
if( argc < 4 )
{
std::cerr << "Usage fun <array size> <min size> <max size>\n";
return EXIT_FAILURE;
}
const auto arraySize {number(argv[1])};
const auto low {number(argv[2])};
const auto high {number(argv[3])};
using Strings = std::vector<std::string>;
auto start {time()};
// Create and size 3 arrays first 2 are half the size of the 3rd.
//
Strings randoms1;
randoms1.reserve(arraySize/2);
Strings randoms2;
randoms2.reserve(arraySize/2);
// seed.
//
srand(time(NULL));
const std::string dupes[] =
{
"These","are","the","dupe","values","for","each","array"
};
const auto dupecnt {std::size(dupes)};
//populate 2 arrays with random strings of random lengths
for ( unsigned j = 0; j < arraySize / 2 - dupecnt; j++)
{
randoms1.emplace_back( randStr(randNbr(low, high)) );
randoms2.emplace_back( randStr(randNbr(low, high)) );
}
//add dupes to each array
for( unsigned i = 0; i < dupecnt; i++ )
{
randoms1.emplace_back( dupes[i] );
randoms2.emplace_back( dupes[i] );
}
//show top and bottom 10
std::cout << "\n\nItem Array 1 Array2\n";
std::cout << "-------------------------------------------------\n";
for( long i = 0; i < arraySize / 2; i++ )
{
if( i < 10 || i > arraySize / 2 - 11 )
{
std::cout << std::setw(7) << i + 1 << ' '
<< std::setw(18) << randoms1[i] << ' '
<< std::setw(18) << randoms2[i] << '\n';
}
}
std::cout << time()-start << "S to create " << arraySize
<< " random string elements (+ add dupes)\n";
start = time();
//sort - combine the unsorted arrays into one, then sort large array
Strings combined;
combined.reserve(arraySize);
combined.insert( combined.end(), randoms1.begin(), randoms1.end() );
combined.insert( combined.end(), randoms2.begin(), randoms2.end() );
std::sort( combined.begin(), combined.end(), less() );
std::cout << time()-start << "S to sort\n";
start = time();
std::cout << "new sorted array contains " << combined.size() << "
elements\n";
combined.erase(std::unique(combined.begin(), combined.end()),
combined.end());
std::cout << time()-start << "S to dedup\n";
std::cout << "new deduped array contains " << combined.size() << "
elements\n";
auto forward = combined.begin();
for( int n = 0; n < 10; ++n, ++forward )
{
std::cout << *forward << '\n';
}
auto reverse = combined.rbegin();
for( int n = 0; n < 10; ++n, ++reverse )
{
std::cout << *reverse << '\n';
}
return EXIT_SUCCESS;
}
int main()
{
const char* data[] = {"fun","10000000","8","16" };
return run( 4, data );
}
--
Ian.
>
> #include <iostream>
> #include <cstddef>
> #include <iterator>
> #include <vector>
> #include <memory>
> #include <random>
> #include <algorithm>
> #include <chrono>
> #include <cstring>
> #include <iomanip>
> #include <cstdint>
>
> using namespace std;
> using namespace chrono;
>
> unique_ptr<string> randStr( size_t minSize, size_t maxSize );
>
> typedef ptrdiff_t ssize_t;
>
> int main( int argc, char **argv )
> {
> char const *dupes[] = { "These", "are", "the", "dupe",
> "values", "for", "each", "array" };
> size_t const dupesSize = size( dupes );
> if( argc != 4 )
> return EXIT_FAILURE;
> size_t nRandomStrings = (size_t)atoi( argv[1] );
> unsigned minStringSize = (unsigned)atoi( argv[2] ),
> maxStringSize = (unsigned)atoi( argv[3] );
> time_point<high_resolution_clock> overallStart =
> high_resolution_clock::now(),
> start = overallStart;
> vector<unique_ptr<string>> randomStringsA,
> randomStringsB;
> vector<string *> randomStringsOut;
> size_t nRandomStringsHalf = nRandomStrings / 2;
> randomStringsA.reserve( nRandomStringsHalf + dupesSize );
> randomStringsB.reserve( nRandomStringsHalf + dupesSize );
> randomStringsOut.reserve( nRandomStringsHalf * dupesSize );
> auto randStr = []( size_t minSize, size_t maxSize ) ->
> unique_ptr<string>
> {
> static char charset[] =
> "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
> static random_device rd;
> static uniform_int_distribution<size_t> charSelect( 0, size(
> charset ) - 1 );
> static uniform_int_distribution<size_t> stringSize;
> unique_ptr<string> str( new string );
> stringSize.param( uniform_int_distribution<size_t>::param_type(
> minSize, maxSize ) );
> str->resize( stringSize( rd ) );
> for( char &c : *str )
> c = charset[charSelect( rd )];
> return move( str );
> };
> for( size_t i = 0; i != nRandomStrings / 2; ++i )
> randomStringsA.emplace_back( move( randStr( minStringSize,
> maxStringSize ) ) ),
> randomStringsB.emplace_back( move( randStr( minStringSize,
> maxStringSize ) ) );
> for( size_t i = 0; i != size( dupes ); ++i )
> randomStringsA.emplace_back( new string( dupes[i] ) ),
> randomStringsB.emplace_back( new string( dupes[i] ) );
> cout << (double)duration_cast<nanoseconds>(
> high_resolution_clock::now() - start ).count() / 1'000'000'000.0 << "s
> to create " << nRandomStrings << " random string elements (+ add dupes)"
> << endl;
> cout << endl << endl << "Item Array 1 Array2" <<
> endl;
> for( size_t i = 0; i != (nRandomStringsHalf > 10 ? 10 :
> nRandomStringsHalf); ++i )
> cout << setw( 7 ) << i << setw( 18 ) << *randomStringsA[i] <<
> setw( 18 ) << *randomStringsB[i] << endl;
> for( size_t i = (ssize_t)(nRandomStringsHalf - 10) >= 0 ?
> nRandomStringsHalf - 10 : 0; i != nRandomStringsHalf; ++i )
> cout << setw( 7 ) << i << setw( 18 ) << *randomStringsA[i] <<
> setw( 18 ) << *randomStringsB[i] << endl;
> for( unique_ptr<string> &upA : randomStringsA )
> randomStringsOut.emplace_back( &*upA );
> for( unique_ptr<string> &upB : randomStringsA )
> randomStringsOut.emplace_back( &*upB );
> auto pStringIgnoreCaseCmp = []( string *a, string *b ) -> int
> {
> #if defined(_MSC_VER)
> // _stricmp seems to be better optimized
> return _stricmp( a->c_str(), b->c_str() );
> #else
> unsigned char *ua = (unsigned char *)a->c_str(),
> *ub = (unsigned char *)b->c_str();
> int result;
> for( size_t i = 0; (result = (int)tolower( ua[i] ) -
> (int)tolower( ub[i] )) == 0; ++i )
> if( ua[i] == 0 )
> return 0;
> return result;
> #endif
> };
> auto pStringIgnoreCaseLess = [pStringIgnoreCaseCmp]( string *a,
> string *b ) -> bool
> {
> return pStringIgnoreCaseCmp( a, b ) > 0;
> };
> auto pStringIgnoreCaseEquals = [pStringIgnoreCaseCmp]( string *a,
> string *b ) -> bool
> {
> return pStringIgnoreCaseCmp( a, b ) == 0;
> };
> cout << "qsorting... " << endl;
> start = high_resolution_clock::now();
> sort( randomStringsOut.begin(), randomStringsOut.end(),
> pStringIgnoreCaseLess );
> cout << (double)duration_cast<nanoseconds>(
> high_resolution_clock::now() - start ).count() / 1'000'000'000.0 << "s"
> << endl;
> cout << "removing dupes... " << endl;
> size_t beforeSize = randomStringsOut.size(),
> afterSize;
> randomStringsOut.erase( unique( randomStringsOut.begin(),
> randomStringsOut.end(), pStringIgnoreCaseEquals ), randomStringsOut.end() );
> cout << "removed " << beforeSize - (afterSize =
> randomStringsOut.size()) << " dupes" << endl;
> for( size_t i = 0; i != (afterSize > 10 ? 10 : afterSize); ++i )
> cout << setw( 6 ) << i << " " << *randomStringsOut[i] << endl;
> for( size_t i = (ssize_t)(afterSize - 10) >= 0 ? afterSize - 10 :
> 0; i != afterSize; ++i )
> cout << setw( 6 ) << i << " " << *randomStringsOut[i] << endl;
> cout << "program ran in "<< (double)duration_cast<nanoseconds>(
> high_resolution_clock::now() - overallStart ).count() / 1'000'000'000.0
> << " seconds" << endl;
> return EXIT_SUCCESS;
> }
>
> Here are the C-times on my Ryzen 7 1800X:
> 3.2637s to create 10000000 random string elements (+ add dupes)
> qsorting... 15.1535s
> program ran in 21.7801s seconds
>
> here are the C++-times on this computer:
> 10.4253s to create 10000000 random string elements (+ add dupes)
> qsorting...
> 8.37202s
> program ran in 19.7365 seconds
>
> The initialization of the strings might be slower because for
> strings which don't fall into the small-string-optimization
> there are two objects allocated on the heap; the string-object
> as well as its buffer.
> The sorting is faster because std::qsort is faster than
> std::sort with its call to a global function.
>
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
So here's a fun challenge DFS <nospam@dfs.com> - 2019-11-02 10:53 -0400
Re: So here's a fun challenge Bart <bc@freeuk.com> - 2019-11-02 17:08 +0000
Re: So here's a fun challenge Richard Damon <Richard@Damon-Family.org> - 2019-11-02 15:01 -0400
Re: So here's a fun challenge Bart <bc@freeuk.com> - 2019-11-02 19:38 +0000
Re: So here's a fun challenge Richard Damon <Richard@Damon-Family.org> - 2019-11-02 16:07 -0400
Re: So here's a fun challenge DFS <nospam@dfs.com> - 2019-11-03 09:29 -0500
Re: So here's a fun challenge Bart <bc@freeuk.com> - 2019-11-02 20:36 +0000
Re: So here's a fun challenge DFS <nospam@dfs.com> - 2019-11-03 09:33 -0500
Re: So here's a fun challenge Paul <nospam@needed.invalid> - 2019-11-03 20:53 -0500
Re: So here's a fun challenge Ian Collins <ian-news@hotmail.com> - 2019-11-03 14:33 +1300
Re: So here's a fun challenge Ian Collins <ian-news@hotmail.com> - 2019-11-03 14:35 +1300
Re: So here's a fun challenge DFS <nospam@dfs.com> - 2019-11-03 00:18 -0400
Re: So here's a fun challenge Ian Collins <ian-news@hotmail.com> - 2019-11-03 18:02 +1300
Re: So here's a fun challenge Bart <bc@freeuk.com> - 2019-11-03 11:19 +0000
Re: So here's a fun challenge Ian Collins <ian-news@hotmail.com> - 2019-11-04 00:33 +1300
Re: So here's a fun challenge DFS <nospam@dfs.com> - 2019-11-03 09:39 -0500
Re: So here's a fun challenge Autist <autist69@gmail.com> - 2019-11-03 11:16 +0100
Re: So here's a fun challenge Autist <autist69@gmail.com> - 2019-11-03 11:29 +0100
Re: So here's a fun challenge Ian Collins <ian-news@hotmail.com> - 2019-11-03 23:34 +1300
Re: So here's a fun challenge Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-03 11:04 +0000
Re: So here's a fun challenge Autist <autist69@gmail.com> - 2019-11-03 14:56 +0100
Re: So here's a fun challenge Autist <autist69@gmail.com> - 2019-11-03 15:36 +0100
Re: So here's a fun challenge nobody@example.org (Scott) - 2019-11-03 17:35 +0000
Re: So here's a fun challenge Ian Collins <ian-news@hotmail.com> - 2019-11-04 08:03 +1300
Re: So here's a fun challenge DFS <nospam@dfs.com> - 2019-11-04 10:07 -0500
Re: So here's a fun challenge nobody@example.org (Scott) - 2019-11-04 16:06 +0000
Re: So here's a fun challenge DFS <nospam@dfs.com> - 2019-11-04 15:33 -0500
csiph-web