- Why study the Bible? What can we learn? - 3 Updates
- how can I guess which OS is running a C/C++ program? - 2 Updates
- "owner-concept" or "GSL" ...? - 1 Update
- Header-only C++, what is the point? In C this would be a obvious mistake - 2 Updates
- The first non-duplicated letter in a string - 2 Updates
- Best way to handle mathematical divide-by-zero case - 1 Update
- The first non-duplicated letter in a string - 1 Update
| bitrex <bitrex@de.lete.earthlink.net>: Feb 04 04:32PM -0500 On 02/02/2017 11:23 AM, Rick C. Hodgin wrote: > http://www.libsf.org/misc/love.html > Love you, > Rick C. Hodgin Don't I have to like, make some attempt at sincere change before I'm granted absolution? Thieving and adultering every Saturday to have it wiped away on Sunday seems like a pretty cheap form of grace. |
| legalize+jeeves@mail.xmission.com (Richard): Feb 04 10:46PM [Please do not mail me a copy of your followup] Will you please stop feeding the trolls. Put them in your KILL file and don't respond to their off-topic threads. They are desperate for attention. If you deny them the attention they so desperately seek, they will go away and we can get back to C++. -- "The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline> The Terminals Wiki <http://terminals-wiki.org> The Computer Graphics Museum <http://computergraphicsmuseum.org> Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com> |
| "Rick C. Hodgin" <rick.c.hodgin@gmail.com>: Feb 04 02:48PM -0800 bitrex wrote: > Don't I have to like, make some attempt at sincere change > before I'm granted absolution? Yes. > Thieving and adultering every Saturday to have it wiped away on > Sunday seems like a pretty cheap form of grace. Correct. Thank you, Rick C. Hodgin |
| alexo <alessandro.volturno@libero.it>: Feb 04 12:14PM +0100 >> Too many "magic" numbers. > He is using ANSI escape sequences, which are well documented. > <https://en.wikipedia.org/wiki/ANSI_escape_code> I have tried that code in MinGW, code::blocks IDe's integrated console and Visual studio 2017 RC as I have already said. The latter doesn't even compile, the others just output garbage. Even if is an ANSI codification - and a standardised feature - it seems not to be universally supported...and too tricky. The solution that Pavlo gave me was exactly what I expected and requested for. I know I can rely on your answers. Thank you. |
| legalize+jeeves@mail.xmission.com (Richard): Feb 04 10:43PM [Please do not mail me a copy of your followup] alexo <alessandro.volturno@libero.it> spake the secret code >I have tried that code in MinGW, code::blocks IDe's integrated console >and Visual studio 2017 RC as I have already said. >The latter doesn't even compile, the others just output garbage. This is the second time you've said that this very standard code doesn't compile. What exactly is the compile error? By "output garbage", I assume you are referring to the output of the program and not the output of the compilation process. The Windows command processor CMD.EXE doesn't guarantee to support ANSI escape sequences. In DOS, there was a driver loaded to support them -- ANSI.SYS -- because DOS was more like a terminal environment. You can get a program for Windows to interpret the sequences like ANSI.SYS -- one such program is ANSICON: <http://adoxa.altervista.org/ansicon/> >Even if is an ANSI codification - and a standardised feature - it seems >not to be universally supported...and too tricky. There are several choices here. You can code something that is portable across operating systems or you can code something specific to Windows. The most portable solution is to use the curses library and have it output the appropriate escape codes for the environment. To code directly to Windows you can use one of the two approaches shown here: <https://msdn.microsoft.com/en-us/library/windows/desktop/ms682022(v=vs.85).aspx> -- "The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline> The Terminals Wiki <http://terminals-wiki.org> The Computer Graphics Museum <http://computergraphicsmuseum.org> Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com> |
| legalize+jeeves@mail.xmission.com (Richard): Feb 04 10:29PM [Please do not mail me a copy of your followup] "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> spake the secret code >I don't like that [...] >I don't like that [...] >I don't like that [...] You should be opening issues on their github instead of complaining here, a place they are unlikely to be reading. -- "The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline> The Terminals Wiki <http://terminals-wiki.org> The Computer Graphics Museum <http://computergraphicsmuseum.org> Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com> |
| Wouter van Ooijen <wouter@voti.nl>: Feb 04 11:14AM +0100 Op 04-Feb-17 om 00:23 schreef Ian Collins: >> 37,217 -- in the .hh using __noinline >> 37,392 -- in the .hh > Does anyone, other than you, care? I do, because I program very small chips and I like to get a grip on what the compiler exactly does. But I'm not going to analyse >30k of output :) Wouter "Objects? No Thanks!" van Ooijen |
| Ian Collins <ian-news@hotmail.com>: Feb 05 09:32AM +1300 On 02/ 4/17 11:14 PM, Wouter van Ooijen wrote: > I do, because I program very small chips and I like to get a grip on > what the compiler exactly does. But I'm not going to analyse >30k of > output :) Quite. When working with small chips, use the appropriate compiler or linker options to get the best size and performance tradeoff. -- Ian |
| ram@zedat.fu-berlin.de (Stefan Ram): Feb 04 04:22PM >I think the actual worst-case is a string that is the concatenation of >two copies of a type one string (no repeated characters). It would be >interesting to see this case tested as well. I have added this test case, and indeed, now I can observe a case where »first_unique_char_of« /is/ slower than »first_unique_char_in«! It can be seen below under »fillmode = 4«. A number written left to an apostrophe »'« denotes approximate seconds below. fillmode = 0, filling with set of commonly used characters average length of a string = 20000 running first_unique_char_of ... runtime of first_unique_char_of = 33,303.437 average number of outer loops = 20000 average number of inner loops = 61.5511 running first_unique_char_in ... runtime of first_unique_char_in = 1'595,852.845 fillmode = 1, filling with wide range of random numbers average length of a string = 20000 running first_unique_char_of ... runtime of first_unique_char_of = 0 average number of outer loops = 0.2 average number of inner loops = 18180.9 running first_unique_char_in ... runtime of first_unique_char_in = 45,925.227 fillmode = 2, filling with incrementing characters 1, 2, 3 ... average length of a string = 20000 running first_unique_char_of ... runtime of first_unique_char_of = 0 average number of outer loops = 0 average number of inner loops = 20001 running first_unique_char_in ... runtime of first_unique_char_in = 40,582.475 fillmode = 3, filling with the character 0 average length of a string = 20000 running first_unique_char_of ... runtime of first_unique_char_of = 896.367 average number of outer loops = 20000 average number of inner loops = 1.00005 running first_unique_char_in ... runtime of first_unique_char_in = 91'648,927.968 fillmode = 4, filling with two zigs average length of a string = 20000 running first_unique_char_of ... runtime of first_unique_char_of = 2'318,485.099 average number of outer loops = 20000 average number of inner loops = 10000.5 running first_unique_char_in ... runtime of first_unique_char_in = 25,199.138 In the last case where fillmode = 4, about 10 * 20000 * 10000 inner loops are done in about 2 seconds (stringcount = 10), which means that an inner loop takes about 1 ns, which is the time for an L1 cache lookup plus 0.5 ns. When we want to test larger strings with two zigs, we need to change »wchar_t« to »char32_t«. I did this: fillmode = 4, filling with two zigs average length of a string = 200000 running first_unique_char_of ... runtime of first_unique_char_of = 228'565,960.763 average number of outer loops = 200000 average number of inner loops = 100000 running first_unique_char_in ... runtime of first_unique_char_in = 283,555.206 One can see an increase in run-time that is approximately quadratic in the case of first_unique_char_of and linear in the case of first_unique_char_in. So this is a case which, finally, fulfills our expectations. The following source code not only allows readers to repeat these measurements, but also to possibly find any errors that I might have made. #include <cassert> #include <chrono> #include <cstdlib> #include <ctime> #include <iostream> #include <iterator> #include <ostream> #include <string> #include <vector> #include <iterator> // std::ostream_iterator #include <unordered_set> using namespace ::std::literals; /* fillmode 0: fill strings randomly with common characters such as letters and digits 1: fill strings randomly with random characters 2: fill strings with characters with increasing consecutive codes 3: fill string with the same character at every position (try to avoid repetitions as the worst case for some algorithms) 4: fill with two zigs (a unique sequence and its repetition) */ int fillmode = -1; /* verify compare results of different implementations*/ constexpr bool verify = false; /* measure_in also measure the ..._in algorithm */ constexpr bool measure_in = true; /* zz the size of the strings to be generated some values used were: 5'000L, 50'000L */ constexpr unsigned long long zz = 20'000L; /* stringcount how many strings to put into the vector of strings. The algorithms will be called for each string in this vector. */ auto stringcount = 10; /* loops how many times to iterate the whole test. (loops * stringcounts) strings will be tested. */ constexpr int loops = 1; /* privacy_bias The privacy bias will modify the published runtimes by a constant factor so that they can be published without revealing data about the real processing speed of the system used. It should be a value near 1.0, such as 1.2 (your system will appear to be slower) or 0.8 (your system will appear to be faster). Remember to set this to 1.0 when publishing the source code. */ double privacy_bias = 1.0; /* privacy_noise The privacy noise will modify each published runtime by an individual scale. It should be a value between 0 (no noise) and 1 (maximum noise). The recommended value is a value near 0.01. Remember to set this to 0.0 when publishing the source code. */ double privacy_noise = 0.0; /* tchar */ using tchar = wchar_t; static void escape( void * p ) { asm volatile( "" : : "g"(p) : "memory" ); } template< typename T > ::std::string format( T value ) { ::std::string s; int i = 0; int n = 0; long double v = value; v = v * privacy_bias; v = v *( 1.0 + privacy_noise * ( rand() /( 1.0 + RAND_MAX )- 0.5 )); value = v; if( value ) while( value ) { if( i &&( i % 3 == 0 )) { s = " .,';:-=%#$"[i/3] + s; ++n; } ++i; ++n; s = "0123456789"[ value % 10 ] + s; value /= 10; } else s = "0"; while( n++ < 20 )s = " " + s; return s; } using tstring = ::std::basic_string< tchar >; static tchar first_unique_char_in( tstring const & s ) { ::std::unordered_multiset< tchar >const chars( begin( s ), end( s )); for( tchar const ch : s ) if( chars.count( ch )== 1 )return ch; return tchar{ 0 }; } double loopstat_sum; double loopstat_count; double innerstat_sum; double innerstat_count; /* this must not be called with an empty string. known bug: When the first unique char is 0, the result is the same as when there is no unique char. */ static tchar first_unique_char_of( tstring & s ) { long long const z = s.size(); s.push_back( 0 ); /* add sentinel */ long long i = 0; /* no-defined-overflow optimization */ bool found; tchar ch; for( i = 0; i != z; ++i ) { ch = s[ i ]; s[ z ]= ch; /* set sentinel */ found = false; long long j = 0; /* no-defined-overflow optimization */ for( j = 0; ; ++j ) { if( s[ j ]== ch && j != i ){ found = true; break; }} ::innerstat_sum += j + 1; ::innerstat_count += 1; if( j == z )found = false;/* sentinel was found */ if( !found )break; } s.pop_back(); /* remove sentinel */ ::loopstat_sum += i; ::loopstat_count += 1; return found ? tchar{ 0 }: ch; } static void fill( ::std::vector< tstring >& v ) { static const char set[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz !"; unsigned long long z = ::zz; for( int i = 0; i < stringcount; ++i ) { tstring s{}; s.reserve( z + 10L ); for( unsigned long long c {}; c < z; ++c ) { switch( fillmode ) { case 0: s.push_back( set[ rand() %( sizeof( set )- 1 )] ); break; case 1: s.push_back ( static_cast< unsigned long long >( rand() )* static_cast< unsigned long long >( RAND_MAX )* static_cast< unsigned long long >( RAND_MAX )* static_cast< unsigned long long >( RAND_MAX )* static_cast< unsigned long long >( RAND_MAX )+ static_cast< unsigned long long >( rand() )* static_cast< unsigned long long >( RAND_MAX )* static_cast< unsigned long long >( RAND_MAX )* static_cast< unsigned long long >( RAND_MAX )+ static_cast< unsigned long long >( rand() )* static_cast< unsigned long long >( RAND_MAX )* static_cast< unsigned long long >( RAND_MAX )+ static_cast< unsigned long long >( rand() )* static_cast< unsigned long long >( RAND_MAX )+ static_cast< unsigned long long >( rand() )); break; case 2: s.push_back( c ); break; case 3: s.push_back( 0 ); break; case 4: s.push_back( c > z/2-1 ? c-z/2 : c ); break; default: abort(); break; }} v.push_back( s ); }} int main () { time_t rawtime;struct tm * timeinfo; ::std::srand( static_cast< unsigned int >( ::std::time( nullptr ))); for( fillmode = 0; fillmode < 5; ++fillmode ) { ::std::cout << "\nfillmode = " << fillmode << ( fillmode == 0 ? ", filling with set of commonly used characters" : fillmode == 1 ? ", filling with wide range of random numbers" : fillmode == 2 ? ", filling with incrementing characters 1, 2, 3 ..." : fillmode == 3 ? ", filling with the character 0" : ", filling with two zigs" )<< '\n'; ::std::cout.flush(); for( int i = 0; i < loops; ++i ) { ::std::vector< tstring >v; ::fill( v ); /* ::std::time( &rawtime ); timeinfo = ::std::localtime ( &rawtime ); ::std::cout << "filled "s << ::std::asctime( timeinfo ) << '\n'; */ { tstring::size_type l = 0; unsigned long long c = 0; for( auto const & s: v ) { l += s.length(); ++c; } ::std::cout << "average length of a string = " << ( static_cast< long double >( l )/static_cast< long double >( c )) << '\n'; } ::std::cout.flush(); if( verify ) { ::std::cout << "verifying ...\n"; ::std::cout.flush(); for( auto & s: v ) if( first_unique_char_in( s )!= first_unique_char_of( s )) { ::std::cerr << "verification failed.\n"; exit( 99 ); }} /* ::std::time( &rawtime ); timeinfo = ::std::localtime ( &rawtime ); ::std::cout << "asserted "s << ::std::asctime( timeinfo ) << '\n'; */ { ::std::cout << "running first_unique_char_of ...\n"; ::std::cout.flush(); ::std::chrono::high_resolution_clock::time_point t1; ::std::chrono::high_resolution_clock::time_point t2; ::loopstat_sum = 0; ::loopstat_count = 0; ::innerstat_sum = 0; ::innerstat_count = 0; decltype( t2 - t1 )sum{}; t1 = ::std::chrono::high_resolution_clock::now(); escape( &t1 ); for( auto & s: v ) { auto result = first_unique_char_of( s ); escape( &result ); } t2 = ::std::chrono::high_resolution_clock::now(); escape( &t2 ); sum += t2 - t1; ::std::cout << "runtime of first_unique_char_of = " << format(( sum ).count()) << '\n'; ::std::cout.flush(); ::std::cout << "average number of outer loops = " << ::loopstat_sum / ::loopstat_count << '\n'; ::std::cout << "average number of inner loops = " << ::innerstat_sum / ::innerstat_count << '\n'; /*::std::time( &rawtime ); timeinfo = ::std::localtime ( &rawtime ); ::std::cout << "done dtf "s << ::std::asctime( timeinfo ) << '\n';*/ } if( measure_in ) { ::std::cout << "running first_unique_char_in ...\n"; ::std::cout.flush(); ::std::chrono::high_resolution_clock::time_point t1; ::std::chrono::high_resolution_clock::time_point t2; decltype( t2 - t1 )sum{}; t1 = ::std::chrono::high_resolution_clock::now(); escape( &t1 ); for( auto const & s: v ) { auto result = first_unique_char_in( s ); escape( &result ); } t2 = ::std::chrono::high_resolution_clock::now(); escape( &t2 ); sum += t2 - t1; ::std::cout << "runtime of first_unique_char_in = " << format(( sum ).count()) << '\n'; ::std::cout.flush(); /*::std::time( &rawtime ); timeinfo = ::std::localtime ( &rawtime ); ::std::cout << "done dti "s << ::std::asctime( timeinfo ) << '\n'; */ }}}} |
| ram@zedat.fu-berlin.de (Stefan Ram): Feb 04 04:31PM > for( j = 0; ; ++j ) > { if( s[ j ]== ch && j != i ){ found = true; break; }} > ::innerstat_sum += j + 1; ::innerstat_count += 1; Changed the above to for( i = 0; i != z; ) // removed ++i here { ch = s[ i ]; s[ z ]= ch; /* set sentinel */ found = false; long long j = 0; /* no-defined-overflow optimization */ for( j = 0; ; ++j ) { if( s[ j ]== ch && j != i ){ found = true; break; }} ::innerstat_sum += j + 1; ::innerstat_count += 1; ++i; // added ++i here to have a more accurate count of the number of times the the outer loop was performed. |
| "J. Clarke" <j.clarke.873638@gmail.com>: Feb 04 07:56AM -0500 In article <zEudA.1117322$_a3.924316@fx42.am4>, no@notvalid.com says... > but other ways. What would be the best way for the function to report > about "dividing by zero" case? How would you do it? > I kind of agree with Bjarne here.... do you? My feeling is that if the interviewer tells you to throw an exception you throw an effing exception unless you see a compelling reason not to. |
| Ben Bacarisse <ben.usenet@bsb.me.uk>: Feb 04 11:28AM > First Case: > The string is artificially manufactured to have no > repetitions of characters. <snip> > repetitions of characters. I.e., it only consists of > the repetition of one character. This is kind of like > the opposite of the preceding case. <snip> > resemble English text, i.e., with the common characters > and digits. This is the worst case for my algorithm I have > seen so far. I think the actual worst-case is a string that is the concatenation of two copies of a type one string (no repeated characters). It would be interesting to see this case tested as well. By the way, I have also found this thread very interesting. <snip> > Feel free to do your own tests guys using the following > source code. I don't have time at the moment, but maybe later. <snip> -- Ben. |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment