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

Groups > comp.lang.c > #147355

Re: How to use a struct with qsort()?

Show all headers | View raw

Paul wrote:
> DFS wrote:
>> On 10/26/2019 10:40 AM, Bart wrote:
>>> On 26/10/2019 14:37, DFS wrote:
>>>> On 10/26/2019 4:15 AM, Paul wrote:
>>>
>>>>> 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.
>>>
>>> Preprocessing the data is the key.
>>>
>>> Your simple tests combine the processing of all the data (like, 
>>> reading in the whole file), with finding anagrams of just one word.
>>>> One kind of preprocessing can just chain together all anagrams anyway,
>>> then it comes down to looking up one word in a dictionary, which can 
>>> be under a millionth of a second. The anagram part should then take 
>>> zero time, following a handful of links.
>>>
>>> (This preprocessing need not be done in the program each time it 
>>> starts; it can be a separate program that generates a special, linked 
>>> version of words_alpha.txt for example.)
>>
>>
>> Yeah, I wondered how you might do that in C.
>>
>> I've of course written various programs that load data, then wait for 
>> keyboard input, and wait for Ctrl+Z to quit, etc.
>>
>>
>>
>>>>> You could, of course,
>>>>> store the entire word file inside the program, and
>>>>> eliminate the preprocessing time :-)
>>>>
>>>> heh!
>>>
>>> (You can do that easily with the right language; one of mine can do 
>>> this:
>>>
>>>      var []ichar words = textinclude "/texts/words_alpha.txt"
>>>
>>>      proc start=
>>>          println words.len
>>>          println words[1]
>>>          println words[$]
>>>      end
>>>
>>> output is:
>>>
>>>      370099
>>>      a
>>>      zwitterionic
>>>
>>> However, it slows down compilation (as it deals with 370,000 string 
>>> expressions). Much faster is to deal with the file as one string and 
>>> then separate into words at runtime.
>>
>> Splitting a big string is faster than fgets() for each line (which 
>> requires ~1 second to read 370K lines, calculate the prime product, 
>> and store it in a struct)?
> 
> I tested the fgets on mine, and it was about 20% of the processing
> time for the input file. So 80% must be my "lousy multiply method"
> for pf.
> 
>    0.047725s to fgets the file       <=== measure(read file), then rewind()
> 
>    0.273223s to load 370103 words    <=== measure(read file and multiply 
> primes)
> 
> I assume, with some work, we could get the time down to zero,
> by placing the entire array and pre-computed prime values
> in the source. But that's cheating, and it'll still take time
> for the loader to load the bloated executable.
> 
> And now that I've fixed my time stamper, the time to do the
> binary search and find the index of the consecutive anagrams,
> is getting damn close to zero. It's likely the printf
> time would be dominant if I included it.
> 
>    Searching for anagrams of 'players'...
>    asperly parleys parsley pyrales replays sparely splayer
>    7 anagram(s) found in 0.000003s <=== binary search time, no printf
>    Done
> 
>   Paul

I switched from GMP to "ttmath", and got a modest improvement
in compute time for the primes. This is probably due to more
details being exposed during compile, and more opportunities to
optimize away stuff.

"ttmath" is just a bunch of header files, and runs under C++.
I didn't use the ASM option, which is for Intel x64 opportunities.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <inttypes.h>
#include <stdint.h>
#include <windows.h>
#include "ttmath/ttmath.h"

/* also requires a DLL for C++ ... */
/* g++ -O2 -c anagrams3.c */
/* g++ -O2 -o anagrams3.exe anagrams3.o -L. */

/* declarations are pretty simple */

ttmath::Int<4> tttemp;  /* four limbs for my 128 bit storage */

//build struct
#define maxletter 32     /* 31 char plus terminator */
#define linecount 370103 /* use test file for benchmarks */
struct words {char word[maxletter]; ttmath::Int<4> wordpf;};
struct words wordrec[linecount];

/* Thanks to operator overloading, tttemp is easier to load up */

     int i;
     int arrindex;
     uint64_t pflow = 1;
     uint64_t pfhigh = 1;
     uint64_t pftemp = 0;

     /* do most math without ttmath */
     for(i=0;i<len;i++) {
         arrindex = (int)(strchr(charset, str[i]) - charset);

         if (pflow > 182641030432767836) {
            pfhigh *= primes[arrindex];
         } else {
            pflow *= primes[arrindex];
         }
     }

     /* save the potential 64 bit x 64 bit = 128 bit multiply for last */
     /* needed a cast to get the math values right */

     if (pfhigh == 1) {
        tttemp = (ttmath::Int<4>) pflow; /* a global passed back to main */
     } else {
        tttemp = (ttmath::Int<4>) pfhigh * (ttmath::Int<4>) pflow;
     }

/* Printing the struct is pretty easy too, base 10 only */

     for(i=0;i<wordcnt;i++) {
         if(i<10 || i>(wordcnt-11)) {
             printf("%d.      %-18s ",i, wordrec[i].word);
             std::cout << wordrec[i].wordpf << std::endl;
         }
     }

/* In the QSort, writing an equivalent to mpz_cmp is easy. */
/* And because all the math is out in the open, the compiler
    can optimize some of it. */

    int compar; /* compare two ttmath 4 limb variables */

    compar = (a->wordpf > b->wordpf) - (a->wordpf < b->wordpf); /* -1,0,+1 */

/* And I don't need the clumsy mpz_cmp for comparisons in binary search */
/* I can use > and == and the 128 bit math is all taken care of for me */

     ttmath::Int<4> searchpf;
     ...
     while (lowindex <= highindex) {
         mid = (highindex - lowindex) / 2 + lowindex;
         if ( wordrec[mid].wordpf > searchpf ) {
             highindex = mid - 1;
         } else if ( wordrec[mid].wordpf == searchpf ) {
             startindex = mid;
             highindex = mid - 1;
         } else {
             lowindex = mid + 1;
         }
     }

And I get a modest improvement in program speed (prime calc part).

The GMP package is OK, with the exception of moving data
into MPZ_t is harder than it needs to be. They could use
some bitshift operations (which perhaps I missed in my
rush to get done).

The disadvantage of the ttmath, is it doesn't automatically
add limbs like GMP does. But if you insist on bounding
your problem (only using a single test file as the only input),
it seems to be a good option.

    Paul

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

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