Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147257
| From | Paul <nospam@needed.invalid> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: How to use a struct with qsort()? |
| Date | 2019-10-26 15:03 -0400 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <qp25ab$1j1l$1@gioia.aioe.org> (permalink) |
| References | (8 earlier) <l5MqF.242244$iJ2.110801@fx47.iad> <07784ff9-2fee-49e6-8271-22d713294245@googlegroups.com> <bdZqF.216192$TC2.20635@fx43.iad> <qp0vbg$672$1@gioia.aioe.org> <X%XsF.47310$Ku2.37175@fx41.iad> |
DFS wrote:
> On 10/26/2019 4:15 AM, Paul wrote:
>
>
>> I took your code and messed around a bit with it.
>
> <snip>
>
>
>> 370096. electroencephalographically 5d9c0dac6de2d4b7af0469d810
>> 370097. hydroxydesoxycorticosterone 9061cc85898dcac646dab48e48
>> 370098. trinitrophenylmethylnitramine 913f8dd325653c1599e1f3cb98
>> 370099. microspectrophotometrically 9aba287a31028f4509cc30dd1c
>> 370100. hydroxydehydrocorticosterone 510c71bb0a52f66b6c9ac515218
>> 370101. philosophicopsychological 26b6c1941415142b7b83d64fd613
>> 370102. dichlorodiphenyltrichloroethane
>> abfc410e3f54ff5649a0c76b28ee8
>>
>> Searching for anagrams of 'now'...
>> freq 3005590000
>> now 1053825389785134 now/freq 350621.804632
>> own won
>> freq 3005590000
>> now 1053825389995158 now/freq 350621.804702
>> 2 anagram(s) found in 0.000070s
>> Done
>>
>> *******
>
>
> Interesting thoughts!
>
> I've been trying to use gmp (here on Windows) but no luck so far. I did
> get it installed.
>
>
>> What was your original bar bet anyway ?
>
> Well, I was finishing a bottle of Bacardi 151 and web browsing and came
> across https://wordsmith.org/anagram/
>
> It generated so many anagrams so fast I was blown away. So I went
> looking for algorithms. The first one I came across was the
> prime-products, which looked easy to implement. Once I got the code
> written, I saw how fast it was in C. Sorting the data made it much faster.
>
>
> The hosts of wordsmith.org told me:
> "Lots of horsepower we put into our server!"
>
>
>> Time to search for a single item, or time for the whole process ?
>
> Fastest I got on my old Win8.1 system (i5-750@2.67GHz) is 0.00012
> searching for 'cat'
>
>
> Ran it in MSYS2 and it's even faster:
>
> Searching for anagrams of 'cat'...
> act
> 1 anagram(s) found in 0.00001s
>
>
> Searching for anagrams of 'players'...
> asperly parleys parsley pyrales replays sparely splayer
> 7 anagram(s) found in 0.00212s
Searching for anagrams of 'players'...
asperly parleys parsley pyrales replays sparely splayer
7 anagram(s) found in 0.000149s
Done
Searching for anagrams of 'now'...
own won
2 anagram(s) found in 0.000059s
Done
Searching for anagrams of 'cat'...
act
1 anagram(s) found in 0.000051s
Done
I think I need to put my timestamper back the way
it was in one of my other programs. Apparently it's
based on RDTSC or something. To measure short time
periods, you have to be more careful than I've been
so far.
In MinGW32, I was using
gcc -c anagrams2.c
gcc -o anagrams2.exe anagrams2.o -L. -lgmp-10
I'm missing the bit that would statically link "libgcc_s_dw2-1.dll".
I need two DLLs next to anagrams2.exe program.
And a snippet of GMP stuff looks like.
uint64_t pflow = 1; /* multiply buckets */
uint64_t pfhigh = 1; /* do most multiply in INTs... */
uint64_t pftemp = 0; /* before using GMP for final 128 bit multiply output */
mpz_t mpzshift; /* transfer to GMP domain */
mpz_t mpzaccum;
mpz_t mpzoutput;
mpz_init(mpzshift);
mpz_set_str(mpzshift, "0x0000000100000000", 0); /* 32 bit shift of uint64_t */
mpz_init(mpzaccum);
mpz_init(mpzoutput);
/* this part does the transfer of pflow and pfhigh to a single mpz_t mpzoutput */
pftemp = pflow >>32; /* MShalf 21B746 32FEAE4C*/
mpz_set_ui(mpzoutput, pftemp);
mpz_mul(mpzoutput, mpzshift, mpzoutput); /* 21B74600000000 */
mpz_add_ui(mpzoutput, mpzoutput, pflow & 0xFFFFFFFF); /* 21B74632FEAE4C */
if (pfhigh != 1) { /* multiply to output */
pftemp = pfhigh >>32;
mpz_set_ui(mpzaccum, pftemp);
mpz_mul(mpzaccum, mpzshift, mpzaccum);
mpz_add_ui(mpzaccum, mpzaccum, pfhigh & 0xFFFFFFFF);
mpz_mul(mpzoutput, mpzaccum, mpzoutput); /* output is 128bit number */
}
Then the sorting can use the mpz comparison function,
as crafting my own version directly on pflow and pfhigh
buckets is outside my pay scale.
int compar;
compar = mpz_cmp(a->wordpf, b->wordpf);
I won't post the whole thing, for fear of offending the audience.
Oh, yeah, my primes look like this.
int primes[26] = {5,71,41,29,2,47,61,23,11,97,79,31,43,13,7,67,89,19,17,3,37,73,59,83,53,101};
using frequencies from here
http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html
The binary search for the first output word looks like...
int lowindex = 0;
int highindex = wordcnt - 1;
int startindex = -1; /* if anagram present, 0..wordcnt-1 */
int mid = 0;
while (lowindex <= highindex) {
/* printf("low = %6d high = %6d mid = %06d startindex = %06d\n", lowindex, highindex, mid, startindex); */
mid = (highindex - lowindex) / 2 + lowindex;
if ( mpz_cmp(wordrec[mid].wordpf, searchpf) > 0 ) {
highindex = mid - 1;
} else if ( mpz_cmp(wordrec[mid].wordpf, searchpf) == 0 ) {
startindex = mid;
highindex = mid - 1;
} else {
lowindex = mid + 1;
}
}
You can see I am a fan of the "printf" school of thought.
If at first you don't succeed, printf printf printf.
Paul
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 13:35 -0400
Re: How to use a struct with qsort()? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-19 10:22 -0700
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 14:19 -0400
Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-19 19:36 +0100
Re: How to use a struct with qsort()? Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-19 18:44 +0000
Re: How to use a struct with qsort()? Barry Schwarz <schwarzb@delq.com> - 2019-10-19 10:23 -0700
Re: How to use a struct with qsort()? Ike Naar <ike@sdf.lonestar.org> - 2019-10-19 19:09 +0000
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 15:51 -0400
Re: How to use a struct with qsort()? already5chosen@yahoo.com - 2019-10-19 13:09 -0700
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 16:26 -0400
Re: How to use a struct with qsort()? already5chosen@yahoo.com - 2019-10-19 13:51 -0700
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 17:24 -0400
Re: How to use a struct with qsort()? already5chosen@yahoo.com - 2019-10-19 14:49 -0700
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 18:26 -0400
Re: How to use a struct with qsort()? already5chosen@yahoo.com - 2019-10-19 16:32 -0700
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-20 09:22 -0400
Re: How to use a struct with qsort()? Paul <nospam@needed.invalid> - 2019-10-26 04:15 -0400
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-26 09:37 -0400
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-26 15:40 +0100
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-28 19:49 -0400
Re: How to use a struct with qsort()? Paul <nospam@needed.invalid> - 2019-10-29 01:59 -0400
Re: How to use a struct with qsort()? Paul <nospam@needed.invalid> - 2019-10-30 04:54 -0400
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-30 11:54 +0000
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-30 08:58 -0700
Re: How to use a struct with qsort()? Öö Tiib <ootiib@hot.ee> - 2019-11-07 01:10 -0800
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-11-07 10:51 +0000
Re: How to use a struct with qsort()? Paul <nospam@needed.invalid> - 2019-10-26 15:03 -0400
Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 21:50 +0100
Re: How to use a struct with qsort()? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-04 16:02 -0800
Re: How to use a struct with qsort()? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-10-21 11:58 +0000
Re: How to use a struct with qsort()? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-23 04:51 -0700
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-19 23:25 +0100
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-19 15:38 -0700
Re: How to use a struct with qsort()? David Brown <david.brown@hesbynett.no> - 2019-10-20 14:44 +0200
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-22 15:42 -0400
Re: How to use a struct with qsort()? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-23 05:47 -0700
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-23 16:40 +0100
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-23 13:51 -0700
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-23 23:07 +0100
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-23 15:50 -0700
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-24 01:20 +0100
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-23 18:20 -0700
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-24 10:40 +0100
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-24 11:00 -0700
Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-20 00:30 +0100
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-20 00:44 +0100
Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-20 01:27 +0100
Re: How to use a struct with qsort()? Manfred <noname@add.invalid> - 2019-10-25 20:30 +0200
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-25 16:07 -0400
Re: How to use a struct with qsort()? Ike Naar <ike@sdf.lonestar.org> - 2019-10-26 07:27 +0000
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-26 02:11 -0700
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-26 11:06 +0100
Re: How to use a struct with qsort()? Manfred <noname@invalid.add> - 2019-10-26 16:58 +0200
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-26 18:17 -0400
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-26 16:08 -0700
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-26 21:33 -0400
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-26 22:10 -0700
Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-27 01:48 +0100
Re: How to use a struct with qsort()? Manfred <noname@invalid.add> - 2019-10-27 19:29 +0100
Re: How to use a struct with qsort()? Barry Schwarz <schwarzb4aarp@gmail.com> - 2019-10-27 13:09 -0700
csiph-web