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

Groups > comp.lang.c > #147564

Re: So here's a fun challenge

Show all headers | View raw

DFS wrote:
> On 11/2/2019 4:36 PM, Bart wrote:
>> On 02/11/2019 14:53, DFS wrote:
>>> - create 2 (equal or unequal sized) arrays of random strings of random
>>>     lengths from low to high, ie 2 to 4, or 8 to 16, etc
>>> - manually add a few of the same values to each array to ensure dupes
>>> - print the top and bottom 10 to show initial data set
>>> - combine the arrays
>>> - case-insensitive sort the arrays (I use qsort but any method is fine)
>>> - dedupe the combined array
>>> - add the unique vals to a new array that's sized appropriately
>>> - print the top and bottom 10 to show final sorted data
>>
>>> #include <Windows.h>
>>
>> (Most people here seem to run Linux.
> 
> I once timed some C programs and Linux ran them 13% faster than Windows. 
>  That's no small feat.
> 
> 
>> But also, adding windows.h can mean processing hundreds of nested 
>> #includes and hundreds of thousands of lines of header code, just to 
>> get a timing function (and which also slows down compilation with gcc).
> 
> Got it.  I noticed the gcc compilation on MSYS2 was very, very slow.
> 
> 
> 
>> clock() will do for most purposes here. Converting to seconds might be 
>> fiddly, but just showing ticks might do.)
> 
> clock() it is then, since I want you guys to be able to run my code as 
> easily as possible.  And I love to time it.
> 
> ----------------------------------------------------------
> double elapsedtime(clock_t begin) {
>     return (double)(clock() - begin) / (double)CLOCKS_PER_SEC;
> }
> 
> clock_t start = clock();
> processing...
> printf("%.4f seconds to process\n",elapsedtime(start);
> ----------------------------------------------------------
> 
> but I don't like what it returns:
> 0.0400
> 0.2350
> 
> (never carries out to 4 digits)
> 
> 
> Windows timer would typically say 0.0396
> 
> 
> 
>>> So 43 seconds on my Window/MSYS2 system for 10,000,000 elements size 8
>>
>> This is 10M elements in total, as each array is half that. Plus the 16 
>> duplicates.
> 
> Yes.  You key in the total array size and the code splits it and builds 
> 2 arrays, then adds the dupes to each array.  When the arrays are 
> combined, you're guaranteed to have 8 dupes.
> 
> 
> 
>>> to 16.  3/4 of that run time is qsorting the array.
>>
>> I got 22 seconds with gcc-O3, and 28 seconds with tcc (presumably, 
>> with a different set of random data), 
> 
> I have an old Intel i5-750@2.67GHz chip.
> 
> 
>> using strcmp not strcasebmp as I've forgotten where that is found.
> 
> Found, as in which header?  string.h.
> 
> stricmp is in there as well; it returns the same values as strcasecmp.
> 
> 
> strcmp('DFS','Bart') = 1
> strcasecmp('DFS','Bart') = 2
> stricmp('DFS','Bart') = 2
> 
> strcmp('Bart','bart') = -1
> strcasecmp('Bart','bart') = 0
> stricmp('Bart','bart') = 0
> 
> 
> 
> tcc | include | string.h
> 
> * This file is part of the w64 mingw-runtime package.
> 
> #ifndef    NO_OLDNAMES
>   char *__cdecl strdup(const char *_Src);
>   int __cdecl strcmpi(const char *_Str1,const char *_Str2);
>   int __cdecl stricmp(const char *_Str1,const char *_Str2);
>   char *__cdecl strlwr(char *_Str);
>   int __cdecl strnicmp(const char *_Str1,const char *_Str,size_t 
> _MaxCount);
>   __CRT_INLINE int __cdecl strncasecmp (const char *__sz1, const char 
> *__sz2, size_t __sizeMaxCompare) { return _strnicmp (__sz1, __sz2, 
> __sizeMaxCompare); }
>   __CRT_INLINE int __cdecl strcasecmp (const char *__sz1, const char 
> *__sz2) { return _stricmp (__sz1, __sz2); }
>   char *__cdecl strnset(char *_Str,int _Val,size_t _MaxCount);
>   char *__cdecl strrev(char *_Str);
>   char *__cdecl strset(char *_Str,int _Val);
>   char *__cdecl strupr(char *_Str);
> #endif
> 
> 
> 
> 
> 
> 
>> But, since the program is already written, what's the challenge; to 
>> try and get it faster? Shorter?
> 
> Both!
> 
> 
>> Note that if you simply printed both random arrays (with duplicates) 
>> to a file, one after the other, then the data is in a form suitable 
>> for the task discussed in the other thread (count number of unique 
>> lines which is likely to involve creating the unique array).
>>
>> However that internal data will not be sorted.
>>
>> (Sorting is not a very interesting task, as it's all been done; just 
>> invoke a sort routine written by someone else, which you are unlikely 
>> to improve on. Sometimes the only way to speed up sorting is to figure 
>> out when when it is not necessary.)
> 
> Yeah, I just used qsort.  I can't say the performance is good or bad, 
> but it did take up 3/4 of the total processing time, probably because 
> string comparisons are inherently slow vs integer comparisons.
> 

There is an #ifdef version of the clock function here.
For some reason, my mingw32 wasn't picking this up, so
I had to remove it and go back to the Windows one.

https://create.stephan-brumme.com/windows-and-linux-code-timing/

*******

I used a seed of 0 so I could reproduce things run after run.
The strcasecmp is the first run with seed(0).

3.6420s to create 10000000 random string elements (+ add dupes)
qsorting... 18.2752s
10000007  zZZzyMTsw4
10000008  zzZzzccKq4CFtwqz
program ran in 24.8913s seconds
Done

Next, I changed the character set, changed to strcmp, and ran it again.

char charset[62] = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz0123456789";

3.7326s to create 10000000 random string elements (+ add dupes)
qsorting... 8.3763s
10000007  zzzzymtsw4
10000008  zzzzzcckq4cftwqz
program ran in 13.5534s seconds
Done

That's the kind of time that might be saved, if you
created an adjunct lower-cased array first and did the run.

*******

And there's a QSort for video cards, and who
knows how much time that would save.

    Paul

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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