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

Groups > comp.lang.c > #147589

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

Show all headers | View raw

Paul <nospam@needed.invalid> writes:

> DFS wrote:
>
>> On 10/19/2019 7:32 PM, already5chosen@yahoo.com wrote:
>>
>>> On Sunday, October 20, 2019 at 1:27:37 AM UTC+3, DFS wrote:
>>
>>
>>> o.k.  I don't know why, but I read your code.
>>> Turned out, you don't have an array of records.  For some reason,
>>> you decided to build an array of pointers to records.  That's quite
>>> different!
>>> Your comparison function should take that into account and to use
>>> double indirection, like that:
>>>
>>> int comparepf(const void *p1, const void *p2)
>>> {
>>>    const struct words *a = *(const struct words **)p1;
>>>    const struct words *b = *(const struct words **)p2;
>>>    if (a->wordpf == b->wordpf)
>>>      return strcmp(a->word, b->word);
>>>    return a->wordpf < b->wordpf ? -1 : 1;
>>> }
>>
>> The qsort now works.
>
> I took your code and messed around a bit with it.
>
> For the prime number idea, you can assign the primes
> according to letter frequency.  The intention being,
> to reduce the amount of storage to hold the prime products.
> The letter "e" is assigned "2", as it's the most frequent.
>
> dichlorodiphenyltrichloroethane   55812442766843314104001446573936360
>
> And since that "broke" my calculator, I used log2 of all
> the prime numbers and addition, to come up with estimates
> of the storage requirements for the "worst word", the one shown.
> I had to figure out the storage requirements, so I could
> figure out how to store the numbers (I wanted to use uint64_t
> initially, but they weren't big enough).
>
> regmax = 7564585 for string dichlorodiphenyltrichloroethane
>
> The number is fixed point, and needs to be shifted >>16 to get
> the size of register needed.  7564585/65536 = 115.4 or 116 bits,
> so two 64 bit uint64_t would do.  I multiply together the
> primes until one uint64_t is full, then multiply the rest
> into a second unit64_t.
>
> I used GMP, and only transferred my two 64 bit accumulators
> to GMP when "most" of the multiplies were finished.  [...]

With a bit more work you might find a fairly simple encoding that
fits in 64 bits and gives a unique value (or very nearly unique)
for every anagram.  Using the 64-bit encoding as a hash value,
put all the words in a big hash table using open addressing for
the codes, and a linked list for wordes with a given code, so
it's just a few compares on 64-bit values to get to the
appropriate anagram family.

Hint:  one such encoding uses a variation of Ben Bacarisse's idea
of using a "histogram" of the number of occurrences of each
letter in the alphabet.

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