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

From	Paul <nospam@needed.invalid>
Newsgroups	comp.lang.c
Subject	Re: How to use a struct with qsort()?
Date	2019-10-29 01:59 -0400
Organization	Aioe.org NNTP Server
Message-ID	<qp8kgl$mes$1@gioia.aioe.org> (permalink)
References	(10 earlier) <bdZqF.216192$TC2.20635@fx43.iad> <qp0vbg$672$1@gioia.aioe.org> <X%XsF.47310$Ku2.37175@fx41.iad> <EVYsF.972216$893.214391@fx02.am4> <j9LtF.140989$FB1.58070@fx44.iad>

Show all headers | View raw

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

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