Groups > comp.lang.c > #147504 > unrolled thread

So here's a fun challenge

Started by	DFS <nospam@dfs.com>
First post	2019-11-02 10:53 -0400
Last post	2019-11-04 15:33 -0500
Articles	20 on this page of 27 — 8 participants

Back to article view | Back to comp.lang.c

  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

Page 1 of 2 [1] 2 Next page →

#147504 — So here's a fun challenge

From	DFS <nospam@dfs.com>
Date	2019-11-02 10:53 -0400
Subject	So here's a fun challenge
Message-ID	<NNgvF.21265$hh5.17108@fx07.iad>

- 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 <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <Windows.h>


//usage
//progname N L H
//N = number of array elements to be created
//L = low  end of length of random string
//H = high end of length of random string
//usage example: ./rand 500 4 8

//vars
int i=0, j=0, k=0;
char charset[62] = 
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
short charsetLen = 62;

//program timing
LARGE_INTEGER frequency,master,start,end;
double elapsedtime(LARGE_INTEGER startingtimer)
{
   QueryPerformanceCounter(&end);
   return (end.QuadPart - startingtimer.QuadPart) / 
(double)frequency.QuadPart;
}

//string compare function for qsort
int comparechar( const void *a, const void *b){
		const char **chara = (const char **)a;
     const char **charb = (const char **)b;
     return strcasecmp(*chara, *charb);
}

//get random number from within range
int randNbr(int low, int high) {
	return (low + rand() / (RAND_MAX / (high - low + 1) + 1));
}

//build random string of random length
char *randStr(int randLen) {
	char *randStr = malloc(sizeof(char) * (randLen + 1));
	for(i=0; i<randLen; i++) {
		randStr[i] = charset[randNbr(0,charsetLen-1)];
	}
	randStr[randLen] = '\0';
	return randStr;
}

//copy elements of arrays a and b into existing array c
void combinearrays(int lenA, int lenB, char *a[], char *b[], char *c[]) {
	printf("combining... ");
	memcpy(c     , a, sizeof(char*) * lenA);
	memcpy(c+lenA, b, sizeof(char*) * lenB);
	printf("combined arrays 1 and 2\nnew unsorted array contains %d 
elements\n",lenA+lenB);
}


int main(int argc, char *argv[])
{
	char *dupes[] = {"These","are","the","dupe","values","for","each","array"};
	int dupecnt = sizeof(dupes)/sizeof(dupes[0]);

	//size of array (including dupes)
	int arrsize = atoi(argv[1]) + (2*dupecnt);
	
	//size of random strings.
	int lo = atoi(argv[2]);
	int hi = atoi(argv[3]);
	
	//begin timer
	QueryPerformanceFrequency(&frequency);
	QueryPerformanceCounter(&master);
	QueryPerformanceCounter(&start);
	
	//create and size 3 arrays
	//first 2 are half the size of the 3rd
	//they will later be combined into the 3rd		
	char **randoms1 = malloc(sizeof(char*) * arrsize/2);
	char **randoms2 = malloc(sizeof(char*) * arrsize/2);
	char **randoms3 = malloc(sizeof(char*) * arrsize);
	
	//seed
	srand(time(NULL));

	//populate 2 arrays with random strings of random lengths
	for(j=0;j<arrsize/2-dupecnt;j++) {
		randoms1[j] = randStr(randNbr(lo,hi));
		randoms2[j] = randStr(randNbr(lo,hi));
	}

	//add dupes to each array
	for(i=0;i<dupecnt;i++) {
		k = (arrsize/2)+i-dupecnt;
		randoms1[k] = dupes[i];
		randoms2[k] = dupes[i];
	}	


	//show top and bottom 10
	printf("\n\nItem        Array 1             Array2\n");
	printf("-------------------------------------------------\n");
	for(i=0;i<arrsize/2;i++) {
		if (i<10 || i>(arrsize/2-11)) {
			printf("%-7d  %-18s %-18s \n",i+1, randoms1[i], randoms2[i]);
		}
	}
	
	printf("\n%.4fs to create %d random string elements (+ add 
dupes)\n",elapsedtime(start),arrsize-(2*dupecnt));	
	
	
	//sort - combine the unsorted arrays into one, then qsort large array
	combinearrays(arrsize/2, arrsize/2, randoms1, randoms2, randoms3);
	QueryPerformanceCounter(&start);
	printf("qsorting... ");
	qsort(randoms3, arrsize, sizeof(char*), comparechar);
	printf("%.4fs\n",elapsedtime(start));
	
	//count unique items in existing randoms array
	int cnt=0;
	for(i=0;i<arrsize;i++) {
		while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
	cnt++;
   }

   //same routine as above, but create a new array
   //to hold unique values, then populate it
   printf("removing dupes... ");
   char **finalarr = malloc(sizeof(char*) * cnt);
	cnt=0;
	for(i=0;i<arrsize;i++) {
		while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
	finalarr[cnt] = randoms3[i];
	cnt++;
   }
	printf("removed %d dupes\n",arrsize-cnt);


	//print top and bottom data
	printf("\ncombined data\ndeduped and sorted 
lowercase\n---------------------------------\n");
	for(i=0;i<cnt;i++) {
		if (i<10 || i>(cnt-11)) {
			printf("%-6d  %s\n",i+1, finalarr[i]);
		}	
	}
	
	printf("program ran in %.4fs seconds\n",elapsedtime(master));
		
	//finish
	free(randoms1);
	free(randoms2);	
	free(randoms3);
	free(finalarr);
	printf("Done");
	exit(0);
}
=========================================================================

Sample output

$ ./randclc 10000000 8 16


Item        Array 1             Array2
-------------------------------------------------
1        a6HFMQFrnUP0Cnv7   aQPGz0UPCP8gMZHJ
2        QQ9JS8SEYk         VlcM3nzRa8G
3        GdncBWK1           ttPRBRxWj3Hh
4        HwSrf8sj9OuYg2RX   3FJOvMAx3bl
5        NBntwcDHxL98TNeY   HWVU1Ch9wwh
6        yJhImP3TCUHDLiLX   345zHvrRz2R
7        BYwC64NTlmN        4El6EdqZai1BZH
8        7r455Z0miJ3f       Tfg2QTH1q
9        4aHS68SRsCf0       J1phwTczJCaAOviU
10       0WOmIt0FmTY        G31XXoCWKKU
4999999  rwknQe3j8BmjO3V    5Mp8CqYAGX
5000000  XbyWcSJhTfDBGn     BPJRhlzsy
5000001  These              These
5000002  are                are
5000003  the                the
5000004  dupe               dupe
5000005  values             values
5000006  for                for
5000007  each               each
5000008  array              array

5.2567s to create 10000000 random string elements (+ add dupes)
combining... combined arrays 1 and 2
new unsorted array contains 10000016 elements
qsorting... 32.7348s
removing dupes... removed 8 dupes

combined data
deduped and sorted lowercase
---------------------------------
1       0000rNRsm
2       0002tSS6R
3       0003BwtPP1tcD2u6
4       0003MzJGcgj2
5       0005yUGPLQz
6       0007EkZ8GJ4H
7       0007muvC2x9w
8       000A6GE3
9       000crSt5s4MX
10      000e8OpCeGvKDA
9999999  ZzzYXVSz0Ioz1
10000000  zzZzaWh1kOlETZ
10000001  ZzzzbgJIE5ao
10000002  ZZzzG8RgD3JHA
10000003  ZzZzJHAzGc2J
10000004  ZZZZkpkDNT
10000005  zzzzUF2zlig
10000006  ZZzZUt2Pwr
10000007  ZzZZxYX10BBKh
10000008  zZzZyyIZ
program ran in 42.8977s seconds
Done


==========================================================

So 43 seconds on my Window/MSYS2 system for 10,000,000 elements size 8 
to 16.  3/4 of that run time is qsorting the array.







=========================================================================
For comparison, done in 12 lines of python, plus 2 lines for timing and 
3 for printing
=========================================================================
import sys, random, string, time
masterTime = time.clock()

randoms1,randoms2 = [],[]
lo = int(sys.argv[2])
hi = int(sys.argv[3])

for i in range(int(sys.argv[1])/2):
     randoms1.append(''.join([random.choice(string.ascii_letters + 
string.digits) for x in xrange(random.randint(lo,hi))]))
     randoms2.append(''.join([random.choice(string.ascii_letters + 
string.digits) for x in xrange(random.randint(lo,hi))]))

dupes = ['These','are','the','dupe','values','for','each','array']
for i in range(len(dupes)):
     randoms1.append(dupes[i])
     randoms2.append(dupes[i])

randsorted = sorted(set(randoms1+randoms2),key=str.lower)

for i in range(len(randsorted)):
     if i<10 or i>len(randsorted)-11:
         print("%2d. %s" % (i+1,randsorted[i]))

print("program ran in: %.3g seconds" %(time.clock()-masterTime))
=========================================================================
On my system, this code runs for 37 seconds for 1000000 8 16.
8.6x slower than C, but it took maybe 30 minutes to write and test.

[toc] | [next] | [standalone]

#147510

From	Bart <bc@freeuk.com>
Date	2019-11-02 17:08 +0000
Message-ID	<MKivF.33881$Yl3.11450@fx24.am4>
In reply to	#147504

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

> =========================================================================
> For comparison, done in 12 lines of python, plus 2 lines for timing and 
> 3 for printing
> =========================================================================
> import sys, random, string, time
> masterTime = time.clock()
> 
> randoms1,randoms2 = [],[]
> lo = int(sys.argv[2])
> hi = int(sys.argv[3])
> 
> for i in range(int(sys.argv[1])/2):
>      randoms1.append(''.join([random.choice(string.ascii_letters + 
> string.digits) for x in xrange(random.randint(lo,hi))]))
>      randoms2.append(''.join([random.choice(string.ascii_letters + 
> string.digits) for x in xrange(random.randint(lo,hi))]))
> 
> dupes = ['These','are','the','dupe','values','for','each','array']
> for i in range(len(dupes)):
>      randoms1.append(dupes[i])
>      randoms2.append(dupes[i])
> 
> randsorted = sorted(set(randoms1+randoms2),key=str.lower)
> 
> for i in range(len(randsorted)):
>      if i<10 or i>len(randsorted)-11:
>          print("%2d. %s" % (i+1,randsorted[i]))
> 
> print("program ran in: %.3g seconds" %(time.clock()-masterTime))
> =========================================================================
> On my system, this code runs for 37 seconds for 1000000 8 16.
> 8.6x slower than C, but it took maybe 30 minutes to write and test.

Does the Python not de-dupe?

[toc] | [prev] | [next] | [standalone]

#147511

From	Richard Damon <Richard@Damon-Family.org>
Date	2019-11-02 15:01 -0400
Message-ID	<XnkvF.1114$bC3.644@fx08.iad>
In reply to	#147510

On 11/2/19 1:08 PM, Bart wrote:
> 
> Does the Python not de-dupe?

Lists, which the program is using can store duplicate values, as they
are different because they are at different indexes (Lists have an order).

Sets, which is what the program uses to dedup, do not store duplicate
values, but also does not maintain an order (sets are built on hash tables).

Passing the data through a set before sorting removes all the duplicates.

Lists would be broken if they did not store duplicates.
The sort function would be broken if it eliminated duplicates.

[toc] | [prev] | [next] | [standalone]

#147512

From	Bart <bc@freeuk.com>
Date	2019-11-02 19:38 +0000
Message-ID	<1XkvF.120116$7ei.98248@fx36.am4>
In reply to	#147511

On 02/11/2019 19:01, Richard Damon wrote:
> On 11/2/19 1:08 PM, Bart wrote:
>>
>> Does the Python not de-dupe?
> 
> Lists, which the program is using can store duplicate values, as they
> are different because they are at different indexes (Lists have an order).
> 
> Sets, which is what the program uses to dedup, do not store duplicate
> values, but also does not maintain an order (sets are built on hash tables).
> 
> Passing the data through a set before sorting removes all the duplicates.
> 
> 
> Lists would be broken if they did not store duplicates.
> The sort function would be broken if it eliminated duplicates.

OK, I got the idea that duplicates would be eliminated completely (since 
when I ran the Python, those extra duplicate values still appeared):

- dedupe the combined array
- add the unique vals to a new array that's sized appropriately

[toc] | [prev] | [next] | [standalone]

#147514

From	Richard Damon <Richard@Damon-Family.org>
Date	2019-11-02 16:07 -0400
Message-ID	<PllvF.9314$fL4.4777@fx41.iad>
In reply to	#147512

On 11/2/19 3:38 PM, Bart wrote:
> On 02/11/2019 19:01, Richard Damon wrote:
>> On 11/2/19 1:08 PM, Bart wrote:
>>>
>>> Does the Python not de-dupe?
>>
>> Lists, which the program is using can store duplicate values, as they
>> are different because they are at different indexes (Lists have an
>> order).
>>
>> Sets, which is what the program uses to dedup, do not store duplicate
>> values, but also does not maintain an order (sets are built on hash
>> tables).
>>
>> Passing the data through a set before sorting removes all the duplicates.
>>
>>
>> Lists would be broken if they did not store duplicates.
>> The sort function would be broken if it eliminated duplicates.
> 
> OK, I got the idea that duplicates would be eliminated completely (since
> when I ran the Python, those extra duplicate values still appeared):
> 
> - dedupe the combined array
> - add the unique vals to a new array that's sized appropriately
> 

The line:
randsorted = sorted(set(randoms1+randoms2),key=str.lower)

should create a new list with no duplicates which has been sorted.
It does NOT change the randoms1 or randoms2 to remove the duplicates
from them.

Where are you seeing duplicates

[toc] | [prev] | [next] | [standalone]

#147538

From	DFS <nospam@dfs.com>
Date	2019-11-03 09:29 -0500
Message-ID	<qvBvF.6807$3u6.2802@fx34.iad>
In reply to	#147512

On 11/2/2019 3:38 PM, Bart wrote:

> OK, I got the idea that duplicates would be eliminated completely (since 
> when I ran the Python, those extra duplicate values still appeared):
> 
> - dedupe the combined array
> - add the unique vals to a new array that's sized appropriately

To ensure I had dupes in the final array (before sorting and deduping), 
I added the set of dupes to each array, so when they're combined you have:

randoms1
These
are
the
dupe
values
for
each
array
randoms2
These
are
the
dupe
values
for
each
array

Then it sorts the array and removes one of each dupe from
'These','are','the','dupe','values','for','each','array'

If you saw two of any value from
  'These','are','the','dupe','values','for','each','array'
there's a problem.

comment out the 3rd line from the bottom (use #):
if i<10 or i>len(randsorted)-11:

and de-indent the next line:
print("%2d. %s" % (i+1,randsorted[i]))

and run it and it will show all the final elements.

[toc] | [prev] | [next] | [standalone]

#147516

From	Bart <bc@freeuk.com>
Date	2019-11-02 20:36 +0000
Message-ID	<WMlvF.8956$om6.1434@fx27.am4>
In reply to	#147504

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

[toc] | [prev] | [next] | [standalone]

#147539

From	DFS <nospam@dfs.com>
Date	2019-11-03 09:33 -0500
Message-ID	<_zBvF.2311$yS5.61@fx22.iad>
In reply to	#147516

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.

[toc] | [prev] | [next] | [standalone]

#147564

From	Paul <nospam@needed.invalid>
Date	2019-11-03 20:53 -0500
Message-ID	<qpo0aj$br2$1@gioia.aioe.org>
In reply to	#147539

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

[toc] | [prev] | [next] | [standalone]

#147522

From	Ian Collins <ian-news@hotmail.com>
Date	2019-11-03 14:33 +1300
Message-ID	<h26p2rFa2cqU3@mid.individual.net>
In reply to	#147504

On 03/11/2019 03:53, DFS wrote:
> Sample output
> 
> $ ./randclc 10000000 8 16
> 
> 
> Item        Array 1             Array2
> -------------------------------------------------
> 1        a6HFMQFrnUP0Cnv7   aQPGz0UPCP8gMZHJ
> 2        QQ9JS8SEYk         VlcM3nzRa8G
> 3        GdncBWK1           ttPRBRxWj3Hh
> 4        HwSrf8sj9OuYg2RX   3FJOvMAx3bl
> 5        NBntwcDHxL98TNeY   HWVU1Ch9wwh
> 6        yJhImP3TCUHDLiLX   345zHvrRz2R
> 7        BYwC64NTlmN        4El6EdqZai1BZH
> 8        7r455Z0miJ3f       Tfg2QTH1q
> 9        4aHS68SRsCf0       J1phwTczJCaAOviU
> 10       0WOmIt0FmTY        G31XXoCWKKU
> 4999999  rwknQe3j8BmjO3V    5Mp8CqYAGX
> 5000000  XbyWcSJhTfDBGn     BPJRhlzsy
> 5000001  These              These
> 5000002  are                are
> 5000003  the                the
> 5000004  dupe               dupe
> 5000005  values             values
> 5000006  for                for
> 5000007  each               each
> 5000008  array              array
> 
> 5.2567s to create 10000000 random string elements (+ add dupes)
> combining... combined arrays 1 and 2
> new unsorted array contains 10000016 elements
> qsorting... 32.7348s
> removing dupes... removed 8 dupes
> 
> combined data
> deduped and sorted lowercase
> ---------------------------------
> 1       0000rNRsm
> 2       0002tSS6R
> 3       0003BwtPP1tcD2u6
> 4       0003MzJGcgj2
> 5       0005yUGPLQz
> 6       0007EkZ8GJ4H
> 7       0007muvC2x9w
> 8       000A6GE3
> 9       000crSt5s4MX
> 10      000e8OpCeGvKDA
> 9999999  ZzzYXVSz0Ioz1
> 10000000  zzZzaWh1kOlETZ
> 10000001  ZzzzbgJIE5ao
> 10000002  ZZzzG8RgD3JHA
> 10000003  ZzZzJHAzGc2J
> 10000004  ZZZZkpkDNT
> 10000005  zzzzUF2zlig
> 10000006  ZZzZUt2Pwr
> 10000007  ZzZZxYX10BBKh
> 10000008  zZzZyyIZ
> program ran in 42.8977s seconds
> Done
> 
> 
> ==========================================================
> 
> So 43 seconds on my Window/MSYS2 system for 10,000,000 elements size 8
> to 16.  3/4 of that run time is qsorting the array.
> 
> =========================================================================
> For comparison, done in 12 lines of python, plus 2 lines for timing and
> 3 for printing
> =========================================================================
> import sys, random, string, time
> masterTime = time.clock()
> 
> randoms1,randoms2 = [],[]
> lo = int(sys.argv[2])
> hi = int(sys.argv[3])
> 
> for i in range(int(sys.argv[1])/2):
>       randoms1.append(''.join([random.choice(string.ascii_letters +
> string.digits) for x in xrange(random.randint(lo,hi))]))
>       randoms2.append(''.join([random.choice(string.ascii_letters +
> string.digits) for x in xrange(random.randint(lo,hi))]))
> 
> dupes = ['These','are','the','dupe','values','for','each','array']
> for i in range(len(dupes)):
>       randoms1.append(dupes[i])
>       randoms2.append(dupes[i])
> 
> randsorted = sorted(set(randoms1+randoms2),key=str.lower)
> 
> for i in range(len(randsorted)):
>       if i<10 or i>len(randsorted)-11:
>           print("%2d. %s" % (i+1,randsorted[i]))
> 
> print("program ran in: %.3g seconds" %(time.clock()-masterTime))
> =========================================================================
> On my system, this code runs for 37 seconds for 1000000 8 16.
> 8.6x slower than C, but it took maybe 30 minutes to write and test.

Using a slightly modified version of your code in C++ (vector for 
arrays, string for the strings), the guts of the combine, sot and dedupe 
were:

   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";

Which on my system:
$ g++ -std=c++17 -pedantic -Wextra -Wall -O3 -o fun fun.cpp
$ time ./fun

Item        Array 1             Array2
-------------------------------------------------
       1       UhyZ4Ex6Sjol          xUgSBbJ0d
       2        vqF8i6iQQqf       kJ3hrdvDoTnv
       3        PwaFAx1Q2ZY    8FFoKczj5HB934o
       4      iJdX6dtwAkdta    i9wOo6QOgMlHLeB
       5    QKzTxwXQSn1WH2N     2atg7aVdM6Kobc
       6           SMEB90pQ      DIvaA8Pt99z6a
       7          9MhK1iM50         zsopH4YaDk
       8           3iRmiQMe     Xet5Olerg4GGnU
       9     VPKWiUXc3Epcl2           2QlmL0xP
      10          EKNaYyWJd        wmijocOEe0w
4999991    EeQ08EVZHkm4hlh    Wapv7y34CNNzpAn
4999992     E4KDyvt6FF1MR8        D9QY6eS1HwF
4999993              These              These
4999994                are                are
4999995                the                the
4999996               dupe               dupe
4999997             values             values
4999998                for                for
4999999               each               each
5000000              array              array
1.26085S to create 10000000 random string elements (+ add dupes)
3.19092S to sort
new sorted array contains 10000000 elements
0.10269S to dedup
new deduped array contains 9999992 elements
0000O3l4xIlD
0002cB9eS3
0002lzVaYmpSH
0007yaIw
000Al1GlOkAfP
000b8bsdj
000ir4XI
000j37ftHAU
000j8SlaN
000JDnZUTsut2tLI
ZZZzN3DyoJU9hOy
ZZZZhpliD
ZzzzgdAwKww
zzZZ4waPKAofj
ZzZYshGXMOzI
zZzyp0NY0
zZzyo7v3
ZzzYLx3l2Nmnc973
zzZydYrs3quxF
ZzZy6FpMdt1Zw

real	0m4.744s

-- 
Ian.

[toc] | [prev] | [next] | [standalone]

#147523

From	Ian Collins <ian-news@hotmail.com>
Date	2019-11-03 14:35 +1300
Message-ID	<h26p7kFa2cqU4@mid.individual.net>
In reply to	#147522

On 03/11/2019 14:33, Ian Collins wrote:
Lets try that again...

Using a slightly modified version of your code in C++ (vector for 
arrays, string for the strings), the guts of the combine, sot and dedupe 
were:

   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";

Which on my system:
$ g++ -std=c++17 -pedantic -Wextra -Wall -O3 -o fun fun.cpp
$ time ./fun

Item        Array 1             Array2
-------------------------------------------------
       1       UhyZ4Ex6Sjol          xUgSBbJ0d
       2        vqF8i6iQQqf       kJ3hrdvDoTnv
       3        PwaFAx1Q2ZY    8FFoKczj5HB934o
       4      iJdX6dtwAkdta    i9wOo6QOgMlHLeB
       5    QKzTxwXQSn1WH2N     2atg7aVdM6Kobc
       6           SMEB90pQ      DIvaA8Pt99z6a
       7          9MhK1iM50         zsopH4YaDk
       8           3iRmiQMe     Xet5Olerg4GGnU
       9     VPKWiUXc3Epcl2           2QlmL0xP
      10          EKNaYyWJd        wmijocOEe0w
4999991    EeQ08EVZHkm4hlh    Wapv7y34CNNzpAn
4999992     E4KDyvt6FF1MR8        D9QY6eS1HwF
4999993              These              These
4999994                are                are
4999995                the                the
4999996               dupe               dupe
4999997             values             values
4999998                for                for
4999999               each               each
5000000              array              array
1.26085S to create 10000000 random string elements (+ add dupes)
3.19092S to sort
new sorted array contains 10000000 elements
0.10269S to dedup
new deduped array contains 9999992 elements
0000O3l4xIlD
0002cB9eS3
0002lzVaYmpSH
0007yaIw
000Al1GlOkAfP
000b8bsdj
000ir4XI
000j37ftHAU
000j8SlaN
000JDnZUTsut2tLI
ZZZzN3DyoJU9hOy
ZZZZhpliD
ZzzzgdAwKww
zzZZ4waPKAofj
ZzZYshGXMOzI
zZzyp0NY0
zZzyo7v3
ZzzYLx3l2Nmnc973
zzZydYrs3quxF
ZzZy6FpMdt1Zw

real	0m4.744s

-- 
Ian.

[toc] | [prev] | [next] | [standalone]

#147525

From	DFS <nospam@dfs.com>
Date	2019-11-03 00:18 -0400
Message-ID	<uzsvF.8285$Ys1.3242@fx42.iad>
In reply to	#147523

On 11/2/2019 9:35 PM, Ian Collins wrote:
> On 03/11/2019 14:33, Ian Collins wrote:
> Lets try that again...
> 
> Using a slightly modified version of your code in C++ (vector for 
> arrays, string for the strings), the guts of the combine, sot and dedupe 
> were:
> 
>    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";
> 
> Which on my system:
> $ g++ -std=c++17 -pedantic -Wextra -Wall -O3 -o fun fun.cpp
> $ time ./fun
> 
> Item        Array 1             Array2
> -------------------------------------------------
>        1       UhyZ4Ex6Sjol          xUgSBbJ0d
>        2        vqF8i6iQQqf       kJ3hrdvDoTnv
>        3        PwaFAx1Q2ZY    8FFoKczj5HB934o
>        4      iJdX6dtwAkdta    i9wOo6QOgMlHLeB
>        5    QKzTxwXQSn1WH2N     2atg7aVdM6Kobc
>        6           SMEB90pQ      DIvaA8Pt99z6a
>        7          9MhK1iM50         zsopH4YaDk
>        8           3iRmiQMe     Xet5Olerg4GGnU
>        9     VPKWiUXc3Epcl2           2QlmL0xP
>       10          EKNaYyWJd        wmijocOEe0w
> 4999991    EeQ08EVZHkm4hlh    Wapv7y34CNNzpAn
> 4999992     E4KDyvt6FF1MR8        D9QY6eS1HwF
> 4999993              These              These
> 4999994                are                are
> 4999995                the                the
> 4999996               dupe               dupe
> 4999997             values             values
> 4999998                for                for
> 4999999               each               each
> 5000000              array              array
> 1.26085S to create 10000000 random string elements (+ add dupes)
> 3.19092S to sort
> new sorted array contains 10000000 elements
> 0.10269S to dedup
> new deduped array contains 9999992 elements
> 0000O3l4xIlD
> 0002cB9eS3
> 0002lzVaYmpSH
> 0007yaIw
> 000Al1GlOkAfP
> 000b8bsdj
> 000ir4XI
> 000j37ftHAU
> 000j8SlaN
> 000JDnZUTsut2tLI
> 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.

[toc] | [prev] | [next] | [standalone]

#147526

From	Ian Collins <ian-news@hotmail.com>
Date	2019-11-03 18:02 +1300
Message-ID	<h275bjFa2cqU6@mid.individual.net>
In reply to	#147525

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.

-- 
Ian.

[toc] | [prev] | [next] | [standalone]

#147532

From	Bart <bc@freeuk.com>
Date	2019-11-03 11:19 +0000
Message-ID	<gJyvF.59748$bi1.35166@fx11.am4>
In reply to	#147526

On 03/11/2019 05:02, 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.

What machine are you running?

Mine takes 32 seconds for the original C code but using 'stricmp', 
compiled with gcc-O3. Or 34 seconds using -lucrtbase.

(Even tcc takes 36 seconds, so most execution time must be spent in the 
libraries.)

[toc] | [prev] | [next] | [standalone]

#147533

From	Ian Collins <ian-news@hotmail.com>
Date	2019-11-04 00:33 +1300
Message-ID	<h27s7eFa2cqU8@mid.individual.net>
In reply to	#147532

On 04/11/2019 00:19, Bart wrote:
> On 03/11/2019 05:02, 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.
> 
> What machine are you running?

Ryzen 2700, reasonably quick.

-- 
Ian.

[toc] | [prev] | [next] | [standalone]

#147541

From	DFS <nospam@dfs.com>
Date	2019-11-03 09:39 -0500
Message-ID	<IFBvF.11528$fL4.4596@fx41.iad>
In reply to	#147526

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.

[toc] | [prev] | [next] | [standalone]

#147527

From	Autist <autist69@gmail.com>
Date	2019-11-03 11:16 +0100
Message-ID	<qpm9e1$dsi$1@news.albasani.net>
In reply to	#147522

Here's the whole C++-code:

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

[toc] | [prev] | [next] | [standalone]

#147528

From	Autist <autist69@gmail.com>
Date	2019-11-03 11:29 +0100
Message-ID	<qpma67$cjl$1@news.albasani.net>
In reply to	#147527

>      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() );

If I don't use this MSVC-specific _stricmp, the sorting-time raises
to 15s.

> #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
>      };

[toc] | [prev] | [next] | [standalone]

#147529

From	Ian Collins <ian-news@hotmail.com>
Date	2019-11-03 23:34 +1300
Message-ID	<h27oqcFa2cqU7@mid.individual.net>
In reply to	#147527

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

[toc] | [prev] | [next] | [standalone]

#147531

From	Melzzzzz <Melzzzzz@zzzzz.com>
Date	2019-11-03 11:04 +0000
Message-ID	<YuyvF.26816$LT2.19349@fx21.am4>
In reply to	#147527

On 2019-11-03, Autist <autist69@gmail.com> wrote:
>      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
>      };

There is also strcasecmp for POSIX.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2 [1] 2 Next page →

csiph-web

So here's a fun challenge

Contents

#147504 — So here's a fun challenge

#147510

#147511

#147512

#147514

#147538

#147516

#147539

#147564

#147522

#147523

#147525

#147526

#147532

#147533

#147541

#147527

#147528

#147529

#147531