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

Groups > comp.lang.c > #147516

Re: So here's a fun challenge

Show all headers | View raw

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.

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

clock() will do for most purposes here. Converting to seconds might be 
fiddly, but just showing ticks might do.)


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

> 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), using strcmp not strcasebmp as I've 
forgotten where that is found.

But, since the program is already written, what's the challenge; to try 
and get it faster? Shorter?

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

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