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

Groups > comp.lang.c > #147541

Re: So here's a fun challenge

Show all headers | View raw

On 11/3/2019 1:02 AM, Ian Collins wrote:
> On 03/11/2019 17:18, DFS wrote:
>> On 11/2/2019 9:35 PM, Ian Collins wrote:
> 
>>> ZZZzN3DyoJU9hOy
>>> ZZZZhpliD
>>> ZzzzgdAwKww
>>> zzZZ4waPKAofj
>>> ZzZYshGXMOzI
>>> zZzyp0NY0
>>> zZzyo7v3
>>> ZzzYLx3l2Nmnc973
>>> zzZydYrs3quxF
>>> ZzZy6FpMdt1Zw
>>>
>>> real    0m4.744s
>>
>>
>> Unbelievably quick.  Nearly 10x faster than mine.  I do have a senior
>> citizen processor (i5-750@2.67GHz).
>>
>>
>> But I see you didn't do a case-insensitive sort.
>>
>>   > ZZZzN3DyoJU9hOy
>>   > ZZZZhpliD
>>
>>
>> 3/4 of the proc time in my code is qsorting, which does untold
>> strcasecmp's - that's where the slowdown is.
>>
> 
> That's odd - the other are in order - Ah!  The order of the tail is 
> reversed ZZZzN3DyoJU9hOy is the last entry.
> 
> Your C version (modulo the windows stuff) gives:
> 
> 1.4832s to create 10000000 random string elements (+ add dupes)
> qsorting... 4.8799s
> program ran in 7.0736s seconds
> 
> So removing dupes appears to be a hot-spot.

on my system

10000000 8 16

  8.07s create array add random string elements
27.69s qsort
  1.95s count unique items
  2.16s remove dupes
40.04s total



Re: count unique and remove dupes:

the section

for(i=0;i<arrsize;i++) {
   while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) i++;

is pretty bad I think.  Since the array is sorted, it needs to break on 
the first strcasecmp > 0.

something like:
for(i=0;i<arrsize;i++) {
   while (i<arrsize-1)
     if(strcasecmp(randoms3[i+1],randoms3[i])>0) i++;break;


The code does N! comparisons, but since the dataset is ordered and 
[almost] unique, it should be close to N comparisons.  That fix should 
shave about 10% off the processing time.

I'll mess with it.

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