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

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

Challenge for Feeb: dealing with large numbers in C

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

Contents

  Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-20 18:12 -0400
    Re: Challenge for Feeb: dealing with large numbers in C Barry Schwarz <schwarzb@delq.com> - 2019-10-20 18:33 -0700
      Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-20 23:16 -0400
        Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-21 13:15 +0100
          Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 14:40 -0400
            Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-22 00:54 +0100
              Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-22 10:05 +0200
              Re: Challenge for Feeb: dealing with large numbers in C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-23 07:18 -0700
            Re: Challenge for Feeb: dealing with large numbers in C Manfred <noname@invalid.add> - 2019-10-26 20:01 +0200
              Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-26 17:50 -0400
                Re: Challenge for Feeb: dealing with large numbers in C Manfred <noname@add.invalid> - 2019-10-28 16:33 +0100
        Re: Challenge for Feeb: dealing with large numbers in C Barry Schwarz <schwarzb@delq.com> - 2019-10-21 07:56 -0700
        Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 16:46 +0100
          Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 14:57 -0400
            Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 20:53 +0100
              Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 16:05 -0400
                Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 21:12 +0100
              Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 20:08 -0400
                Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-22 10:27 +0200
            Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-22 19:45 +0100
              Re: Challenge for Feeb: dealing with large numbers in C Eli the Bearded <*@eli.users.panix.com> - 2019-10-22 19:58 +0000
              Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-23 11:46 -0400
                Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-23 20:02 +0100
                Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 01:38 +0100
                  Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-23 22:10 -0400
                    Re: Challenge for Feeb: dealing with large numbers in C Ike Naar <ike@sdf.lonestar.org> - 2019-10-24 07:24 +0000
                      Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 09:29 -0400
                        Re: Challenge for Feeb: dealing with large numbers in C James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-10-24 08:45 -0700
                          Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 11:56 -0400
                            Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-24 09:13 -0700
                              Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 18:28 +0100
                    Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 10:36 +0100
                    Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 09:26 -0400
                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 18:29 +0100
                        Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 14:38 -0400
                          Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 21:30 +0100
                  Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-24 11:30 +0100
                    Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 20:36 +0100
                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 21:34 +0100
                        Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-24 22:42 +0100
                      Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 18:59 -0400
                        Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-25 02:48 +0100
                        Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-26 04:33 -0700
                          Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 17:21 +0100
                            Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-26 18:47 +0100
                              Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 23:24 +0100
                                Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-27 00:29 +0100
                                  Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-27 01:58 +0100
                                    Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-27 12:02 +0000
                                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 02:08 +0000
                            Re: Challenge for Feeb: dealing with large numbers in C Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-10-26 14:29 -0600
                              Re: Challenge for Feeb: dealing with large numbers in C Keith Thompson <kst-u@mib.org> - 2019-10-26 13:36 -0700
                              Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-26 22:06 +0100
                              Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 23:04 +0100
                            Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-27 12:49 +0100
                              Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-27 18:20 +0000
                                Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-27 22:45 +0100
                                  Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 00:08 +0000
                                Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-27 14:57 -0700
                                  Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 01:08 +0000
                                    Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 01:44 +0000
                                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 02:31 +0000
                                        Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 10:42 +0000
                                          Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 12:45 +0000
                                          Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 17:39 +0000
                                            Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-28 20:31 +0100
                                              Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 20:22 +0000
                                                Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-28 22:07 +0100
                                                  Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 22:22 +0000
                                                    Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-29 10:17 +0100
                                                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 11:21 +0000
                                      Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-28 11:05 -0700
                                        Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 19:26 +0000
                                          Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 21:08 +0000
                                            Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 21:57 +0000
                                              Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 23:59 +0000
                                                Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 00:53 +0000
                                                  Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 01:09 +0000
                                                    Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 01:32 +0000
                                                      Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-28 22:44 -0400
                                                      Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-29 03:05 -0700
                                                        Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 11:12 +0000
                                                        Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-29 04:19 -0700
                                                          Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 11:47 +0000
                                                            Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-29 05:03 -0700
                                                              Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 13:16 +0000
                                                            Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 17:13 +0000
                                                              Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 17:35 +0000
                                                        Re: Challenge for Feeb: dealing with large numbers in C Ike Naar <ike@sdf.lonestar.org> - 2019-10-30 07:19 +0000
                                                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 16:19 +0000
                                                        Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 16:50 +0000
                                                          Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-29 10:03 -0700
                                                            Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 17:13 +0000
                                                            Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-29 10:23 -0700
                                                              Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 22:20 +0000
                                                                Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-30 03:04 -0700
                                                                  Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-30 15:39 +0000
                                                                    Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-30 09:02 -0700
                                                                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-30 19:35 +0000
                                                                    Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-30 14:11 -0700
                                                                      Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-31 03:34 +0000
                                    Re: Challenge for Feeb: dealing with large numbers in C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-04 17:02 -0800
                        Re: Challenge for Feeb: dealing with large numbers in C Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2019-10-26 12:30 -0400
                          Re: Challenge for Feeb: dealing with large numbers in C Robert Wessel <robertwessel2@yahoo.com> - 2019-10-26 12:03 -0500
                            Re: Challenge for Feeb: dealing with large numbers in C Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-10-26 14:25 -0600
                      Re: Challenge for Feeb: dealing with large numbers in C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-24 18:06 -0700
          Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 22:44 +0100
            Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 19:00 -0400
    Re: Challenge for Feeb: dealing with large numbers in C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2019-10-21 10:20 +0800
      Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 12:44 +0100
    Re: Challenge for Feeb: dealing with large numbers in C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2019-10-21 10:24 +0800
      Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-20 23:05 -0400
        Re: Challenge for Feeb: dealing with large numbers in C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2019-10-21 11:32 +0800
    Re: Challenge for Feeb: dealing with large numbers in C Autist <autist69@gmail.com> - 2019-10-29 15:15 +0100

Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6  Next page →

#147168

In comp.lang.c, Bart  <bc@freeuk.com> wrote:
> On 21/10/2019 19:57, DFS wrote:
>> It's not slow, in my opinion.
>> 1.13 seconds to load 370104 words, including calculating the prime 
>> product of each word.
>> 
>> It's quite fast to search: finds 7 anagrams in 3/1000ths of a second.

I would think that the standard alphbetize then compare strings will
start to show good results with being able to filter just based on
length of string before actually comparing the big results.

> For anagrams, there is another neat way, which uses a different kind of 
> hash.
> 
> If U[] is the word list, then create a corresponding list V[] where each 
> entry is a sorted version of each word in U (so "bart" in U becomes 
> "abrt" in V).

This is the standard way to go about finding anagrams with software.
Eg:

https://github.com/bdrupieski/AnagramFinder/blob/master/AnagramListener/src/main/java/anagramlistener/CandidateStatusProcessor.java#L69

https://github.com/mendelmunkis/wordplay/blob/master/wordplay.c#L379

> If you want to find anagrams of S, then search for sorted(S) within V, 
> and read off the actual word in U.
> 
> And a quicker way of doing that is to further sort both U and V, in 
> order of the strings in V. Then it becomes a binary search of sorted(S) 
> within V.

Code I've written, but don't have handy now, further narrows the field by
counting key letters in addition to using the alphbetized letters. No
sense in comparing candidate[i] with candidate[j] if vowels[i] != vowels[j].

In my case, I was inspired by the twitter anagram bots to search for
natural anagrams in public domain text, eg:

https://qaz.wtf/anagramhunt/showpair.cgi?pair=327

(My results are still online, but the code I used to generate them is
long ago moved to hard drive backups. My results include a large number
of boring matches. Things that work only because of poor sentence end
detection (pair=890), things that work only because of typos in the OCR
(pair=923), things that would be caught if my word rearrangement code
understood compound words (pair=1586) -- this category has a lot.

Even with those bad matches, there was a (to me) surprisingly low
percentage of sentences that ever matched.

Elijah
------
which makes me respect the matches found in twitter more

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

#147176

On 10/22/2019 2:45 PM, Bart wrote:
> On 21/10/2019 19:57, DFS wrote:
>> On 10/21/2019 11:46 AM, Bart wrote:
> 
>>>> It's looking like prime products is not the right hash function
>>>> for a table of only 370K entries.
>>> 
>>> No, it would be a very poor, and slow, if multiplying all those 
>>> characters together.
>> 
>> 
>> It's not slow, in my opinion.
>> 
>> 1.13 seconds to load 370104 words, including calculating the prime
>>  product of each word.
>> 
>> It's quite fast to search: finds 7 anagrams in 3/1000ths of a
>> second.
> 
> For anagrams, there is another neat way, which uses a different kind
> of hash.
> 
> If U[] is the word list, then create a corresponding list V[] where
> each entry is a sorted version of each word in U (so "bart" in U
> becomes "abrt" in V).
> 
> If you want to find anagrams of S, then search for sorted(S) within
> V, and read off the actual word in U.


It's a better method than prime product, since it's conceptually simpler 
and you don't run into issues with massive numbers.

You don't have to make a separate list V[] to store the sorted letters 
(though using such a list would be faster).

This code makes one pass thru the dictionary, comparing the sorted 
letters of the search word against the sorted letters of each word in 
the dictionary.

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

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

//bubble sort word in alpha order
char *wsort(char *s, int len)
{
   char t;
   for(int i=0;i<len-1;i++) {
      for(int j=i+1;j<len;j++) {
         if(s[i]>s[j]) {
            t=s[i];
            s[i]=s[j];
            s[j]=t;
         }
      }
   }
}

//trim trailing spaces
void rtrim(char *str, int len)
{
  while(len>0 && isspace(str[len-1])){len--;}
  str[len] = '\0';
}

//read file, find anagrams
int main(int argc, char *argv[])
{
     // w   = word in dictionary
     // ws  = alpha sort of the word
     // s   = search word you want anagrams for
     // ss  = alpha sort of the search word
     // mws = max word size
     // wc  = word count in dict

     int i=0,wc=0,mws=32;
     char w[mws], ws[mws], ss[mws];
     char *s = argv[2];

     strcpy(ss,s);
     wsort(ss,strlen(ss));

     FILE *fw = fopen(argv[1],"r");
     while(fgets(w,sizeof(w),fw)!=NULL) {
         rtrim(w,strlen(w));
         strcpy(ws,w);
         wsort(ws,strlen(ws));
         if(strcmp(ws,ss)==0) {
           if(strcmp(w,s)!=0) {
             printf("%s\n",w);
             i++;
           }
         }
         wc++;
     }

     printf("%d anagram(s) found in %d words\n",i,wc);
     fclose(fw);
     exit(0);
}

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

ptime anagrams words_alpha.txt players
asperly
parleys
parsley
pyrales
replays
sparely
splayer
7 anagram(s) found in 370100 words

Execution time: 0.595 s


ptime is a Windows timing utility.

I used the words_alpha.txt file from words_alpha.zip at
https://github.com/dwyl/english-words

The file has 370099 words.  Not sure why C fgets() is overcounting by 1.






> And a quicker way of doing that is to further sort both U and V, in 
> order of the strings in V. Then it becomes a binary search of
> sorted(S) within V.


That's kind of what I did with the prime products code (never posted the 
final here, though).  I sorted the data by prime product, but instead 
did a linear search.  If the search word was small and the letters close 
to the beginning of the alphabet, it would find anagrams in as fast as 
1/10000th of a second.  If it had to iterate all the numbers, it was 
still real fast:

Searching for anagrams of 'trinitrophenylmethylnitramine'...
0 anagram(s) found in 0.01329s


> (There might be a cluster of identical strings in V, then you just
> need to find the limits of that group, and read off the actual
> anagrams from U.)

Sounds interesting.

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

#147177

On 23/10/2019 16:46, DFS wrote:
> On 10/22/2019 2:45 PM, Bart wrote:

>> For anagrams, there is another neat way, which uses a different kind
>> of hash.

>      int i=0,wc=0,mws=32;
>      char w[mws], ws[mws], ss[mws];
>      char *s = argv[2];
> 
>      strcpy(ss,s);
>      wsort(ss,strlen(ss));
> 
>      FILE *fw = fopen(argv[1],"r");
>      while(fgets(w,sizeof(w),fw)!=NULL) {
>          rtrim(w,strlen(w));
>          strcpy(ws,w);
>          wsort(ws,strlen(ws));
>          if(strcmp(ws,ss)==0) {
>            if(strcmp(w,s)!=0) {
>              printf("%s\n",w);
>              i++;
>            }
>          }
>          wc++;
>      }
> 
>      printf("%d anagram(s) found in %d words\n",i,wc);

> 7 anagram(s) found in 370100 words

> The file has 370099 words.  Not sure why C fgets() is overcounting by 1.

The text file contains the word 'dichlorodiphenyltrichloroethane', which 
I think is 32 letters, requiring a 33-character buffer to include the 
zero terminator.

Your buffer is only 32 characters, so that that line is read in two 
parts, which accounts for the extra line.

This is a peculiarity of fgets. Dealing properly with line buffers that 
can cope with any length line is a third topic to be added to hash 
functions and random number generators, which can get very elaborate to 
do properly.

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

#147182

DFS <nospam@dfs.com> writes:

> You don't have to make a separate list V[] to store the sorted letters
> (though using such a list would be faster).
>
> This code makes one pass thru the dictionary, comparing the sorted
> letters of the search word against the sorted letters of each word in
> the dictionary.

Surely it's faster to count letters?  On my machine a simple letter
counting version takes about 1/4 of the time your program takes.

-- 
Ben.

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

#147184

On 10/23/2019 8:38 PM, Ben Bacarisse wrote:
> DFS <nospam@dfs.com> writes:
> 
>> You don't have to make a separate list V[] to store the sorted letters
>> (though using such a list would be faster).
>>
>> This code makes one pass thru the dictionary, comparing the sorted
>> letters of the search word against the sorted letters of each word in
>> the dictionary.
> 
> Surely it's faster to count letters?  On my machine a simple letter
> counting version takes about 1/4 of the time your program takes.


It doesn't count letters [1]

It sorts the letters of each dictionary word in alpha order and string 
compares that result to the alpha sort of the search word.  If they 
match, and the orig word doesn't match the search word, you found 
yourself an anagram.

search for players anagrams

asperly -> aelprsy  ana
parleys -> aelprsy  ana
parsley -> aelprsy  ana
players -> aelprsy  orig word
pyrales -> aelprsy  ana
replays -> aelprsy  ana
sparely -> aelprsy  ana
splayer -> aelprsy  ana

So 7 anagrams.

Read line, trim spaces, sort letters, do comparison.  I'm thrilled with 
0.6s to process 370K words.  It's why I like C.

The python ver takes 3.5s (only 14 lines of code though)

It would search REALLY fast if I mimicked what I did in the prime 
products version: load the dictionary and the alpha-sorted words into a 
struct, sort on the sorted words, then search that column.  But the 
overall time to run that is gonna be close to 1.5 seconds, based on my 
experience.

Also, my code bubble sorts each word (which is the only sort string 
method I found online).  Can you qsort a single word?  Would it be 
faster than bubble sort?  I haven't tried.

Also, my system is pretty old: i5-750@2.67GHz, 8GB memory


1.  Now that you mention counting, maybe it should count the letters and 
only if the count matches the count of the letters in the search word do 
you sort the dict word and do the comparison.  I'll update the code and 
see what happens.

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

#147186

On 2019-10-24, DFS <nospam@dfs.com> wrote:
> 1.  Now that you mention counting, maybe it should count the letters and 
> only if the count matches the count of the letters in the search word do 
> you sort the dict word and do the comparison.  I'll update the code and 
> see what happens.

If the counts match, the words are anagrams.
No need to sort and compare.

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

#147191

On 10/24/2019 3:24 AM, Ike Naar wrote:
> On 2019-10-24, DFS <nospam@dfs.com> wrote:
>> 1.  Now that you mention counting, maybe it should count the letters and
>> only if the count matches the count of the letters in the search word do
>> you sort the dict word and do the comparison.  I'll update the code and
>> see what happens.
> 
> If the counts match, the words are anagrams.

Incorrect.

> No need to sort and compare.

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

#147192

On 10/24/2019 3:24 AM, Ike Naar wrote:
>> On 2019-10-24, DFS <nos...@dfs.com> wrote:
>>> 1.  Now that you mention counting, maybe it should count the letters and
>>> only if the count matches the count of the letters in the search word do
>>> you sort the dict word and do the comparison.  I'll update the code and
>>> see what happens.
>>
>> If the counts match, the words are anagrams.
>
> Incorrect. 

If you were right about that, it should be trivial to provide a counter example: two words which have exactly the same count of every letter, but which are not anagrams. Can you?

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

#147193

On 10/24/2019 11:45 AM, James Kuyper wrote:
> On 10/24/2019 3:24 AM, Ike Naar wrote:
>>> On 2019-10-24, DFS <nos...@dfs.com> wrote:
>>>> 1.  Now that you mention counting, maybe it should count the
>>>> letters and only if the count matches the count of the letters
>>>> in the search word do you sort the dict word and do the
>>>> comparison.  I'll update the code and see what happens.
>>> 
>>> If the counts match, the words are anagrams.
>> 
>> Incorrect.
> 
> If you were right about that, it should be trivial to provide a
> counter example: two words which have exactly the same count of every
> letter, but which are not anagrams. Can you?


I interpreted it as count of all letters in the word.

He probably meant counts of each letter in the word.

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

#147194

On Thursday, 24 October 2019 16:56:33 UTC+1, DFS  wrote:
> On 10/24/2019 11:45 AM, James Kuyper wrote:
> > On 10/24/2019 3:24 AM, Ike Naar wrote:
> >>> On 2019-10-24, DFS <nos...@dfs.com> wrote:
> >>>> 1.  Now that you mention counting, maybe it should count the
> >>>> letters and only if the count matches the count of the letters
> >>>> in the search word do you sort the dict word and do the
> >>>> comparison.  I'll update the code and see what happens.
> >>> 
> >>> If the counts match, the words are anagrams.
> >> 
> >> Incorrect.
> > 
> > If you were right about that, it should be trivial to provide a
> > counter example: two words which have exactly the same count of every
> > letter, but which are not anagrams. Can you?
> 
> 
> I interpreted it as count of all letters in the word.
> 
> He probably meant counts of each letter in the word.
>
One way to is take two histograms of 26 letters and compare them for
equality. The other way is to go through the first word in the pair,
counting every letter you encounter in the first word, and then counting 
that letter in the second word. If the counts don't match, they are
not anagrams. So you can reject most pairs early. However you also
have to compare the string lengths for equality, otherwise "axe" is
an anagram of "ex".
The histogram method doesn't scale up to big alphabets, the letter 
by letter method doesn't scale up to big words.

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

#147198

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Thursday, 24 October 2019 16:56:33 UTC+1, DFS  wrote:
>> On 10/24/2019 11:45 AM, James Kuyper wrote:
>> > On 10/24/2019 3:24 AM, Ike Naar wrote:
>> >>> On 2019-10-24, DFS <nos...@dfs.com> wrote:
>> >>>> 1.  Now that you mention counting, maybe it should count the
>> >>>> letters and only if the count matches the count of the letters
>> >>>> in the search word do you sort the dict word and do the
>> >>>> comparison.  I'll update the code and see what happens.
>> >>> 
>> >>> If the counts match, the words are anagrams.
>> >> 
>> >> Incorrect.
>> > 
>> > If you were right about that, it should be trivial to provide a
>> > counter example: two words which have exactly the same count of every
>> > letter, but which are not anagrams. Can you?
>> 
>> 
>> I interpreted it as count of all letters in the word.
>> 
>> He probably meant counts of each letter in the word.
>>
> One way to is take two histograms of 26 letters and compare them for
> equality. The other way is to go through the first word in the pair,
> counting every letter you encounter in the first word, and then counting 
> that letter in the second word. If the counts don't match, they are
> not anagrams.

For the program in question, this method loses the advantage of
pre-computing the counts for the string for which anagrams are sought.

> So you can reject most pairs early. However you also
> have to compare the string lengths for equality, otherwise "axe" is
> an anagram of "ex".
> The histogram method doesn't scale up to big alphabets, the letter 
> by letter method doesn't scale up to big words.

Using a flat array for the histogram does not scale, but that's not the
only way to store a histogram.

-- 
Ben.

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

#147187

DFS <nospam@dfs.com> writes:

> On 10/23/2019 8:38 PM, Ben Bacarisse wrote:
>> DFS <nospam@dfs.com> writes:
>>
>>> You don't have to make a separate list V[] to store the sorted letters
>>> (though using such a list would be faster).
>>>
>>> This code makes one pass thru the dictionary, comparing the sorted
>>> letters of the search word against the sorted letters of each word in
>>> the dictionary.
>>
>> Surely it's faster to count letters?  On my machine a simple letter
>> counting version takes about 1/4 of the time your program takes.
>
>
> It doesn't count letters [1]

I know.  I'm saying it's faster to count letters.

> 1.  Now that you mention counting, maybe it should count the letters
> and only if the count matches the count of the letters in the search
> word do you sort the dict word and do the comparison.  I'll update the
> code and see what happens.

Exactly.  I did that and saw a considerable speed-up.  Of course, it
doesn't matter if the slower program is fast enough.

-- 
Ben.

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

#147190

On 10/23/2019 10:10 PM, DFS wrote:

<snip>


> 1.  Now that you mention counting, maybe it should count the letters and 
> only if the count matches the count of the letters in the search word do 
> you sort the dict word and do the comparison.  I'll update the code and 
> see what happens.


I did that update, and the processing time went from 0.6s down to 0.2s. 
Nice.


$ ptime alpha words_alpha.txt players
asperly
parleys
parsley
pyrales
replays
sparely
splayer
7 anagram(s) found in 370099 words

Execution time: 0.204 s


=============================================================
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

//this program finds anagrams for the input word

//usage
//anagrams wordlist searchword

//bubble sort word in alpha order
char *wsort(char *s, int len)
{
   char t;
   for(int i=0;i<len-1;i++) {
      for(int j=i+1;j<len;j++) {
         if(s[i]>s[j]) {
            t=s[i];
            s[i]=s[j];
            s[j]=t;
         }
      }
   }
}
	
//trim trailing spaces	
void rtrim(char *str, int len)
{
  while(len>0 && isspace(str[len-1])){len--;}
  str[len] = '\0';
}

int main(int argc, char *argv[])
{	
     // w   = word in dictionary
     // ws  = alpha sort of the word
     // s   = search word you want anagrams for
     // ss  = alpha sort of the search word
     // mws = max word size
     // wc  = word count in dict

     int i=0,wc=0,mws=33;
     char w[mws], ws[mws], ss[mws];
     char *s = argv[2];

     strcpy(ss,s);
     wsort(ss,strlen(ss));

     FILE *fw = fopen(argv[1],"r");
	while(fgets(w,sizeof(w),fw)!=NULL) {
         rtrim(w,strlen(w));
         if(strlen(w)==strlen(ss)) {
           strcpy(ws,w);
           wsort(ws,strlen(ws));
           if(strcmp(ws,ss)==0) {
             if(strcmp(w,s)!=0) {
               printf("%s\n",w);
               i++;
             }
            }
          }
     wc++;
     }
		
	printf("%d anagram(s) found in %d words\n",i,wc);
	fclose(fw);
	exit(0);
}
=============================================================

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

#147199

DFS <nospam@dfs.com> writes:

> On 10/23/2019 10:10 PM, DFS wrote:
>
> <snip>
>
>> 1.  Now that you mention counting, maybe it should count the letters
>> and only if the count matches the count of the letters in the search
>> word do you sort the dict word and do the comparison.  I'll update
>> the code and see what happens.
>
>
> I did that update, and the processing time went from 0.6s down to 0.2s. Nice.
<cut>
> #include <stdlib.h>
> #include <stdio.h>
> #include <string.h>
>
> //this program finds anagrams for the input word
>
> //usage
> //anagrams wordlist searchword
>
> //bubble sort word in alpha order
> char *wsort(char *s, int len)
> {
>   char t;
>   for(int i=0;i<len-1;i++) {
>      for(int j=i+1;j<len;j++) {
>         if(s[i]>s[j]) {
>            t=s[i];
>            s[i]=s[j];
>            s[j]=t;
>         }
>      }
>   }
> }

You posted the old code.

-- 
Ben.

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

#147206

On 10/24/2019 1:29 PM, Ben Bacarisse wrote:
> DFS <nospam@dfs.com> writes:
> 
>> On 10/23/2019 10:10 PM, DFS wrote:
>>
>> <snip>
>>
>>> 1.  Now that you mention counting, maybe it should count the letters
>>> and only if the count matches the count of the letters in the search
>>> word do you sort the dict word and do the comparison.  I'll update
>>> the code and see what happens.
>>
>>
>> I did that update, and the processing time went from 0.6s down to 0.2s. Nice.
> <cut>
>> #include <stdlib.h>
>> #include <stdio.h>
>> #include <string.h>
>>
>> //this program finds anagrams for the input word
>>
>> //usage
>> //anagrams wordlist searchword
>>
>> //bubble sort word in alpha order
>> char *wsort(char *s, int len)
>> {
>>    char t;
>>    for(int i=0;i<len-1;i++) {
>>       for(int j=i+1;j<len;j++) {
>>          if(s[i]>s[j]) {
>>             t=s[i];
>>             s[i]=s[j];
>>             s[j]=t;
>>          }
>>       }
>>    }
>> }
> 
> You posted the old code.


I posted the right code.

We're getting confused by interchanging 'count the letters' with 'count 
each letter'.

The code I posted 'counts the letters' via strlen(word).

According to a friendly competition I'm having with someone, his count 
of each letter method is much slower than my count of all letters then 
sort and compare method.

count each letter:          real 0.196s
count all letters = strlen: real 0.113s

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

#147213

DFS <nospam@dfs.com> writes:

> On 10/24/2019 1:29 PM, Ben Bacarisse wrote:
>> DFS <nospam@dfs.com> writes:
>>
>>> On 10/23/2019 10:10 PM, DFS wrote:
>>>
>>> <snip>
>>>
>>>> 1.  Now that you mention counting, maybe it should count the letters
>>>> and only if the count matches the count of the letters in the search
>>>> word do you sort the dict word and do the comparison.  I'll update
>>>> the code and see what happens.
>>>
>>>
>>> I did that update, and the processing time went from 0.6s down to 0.2s. Nice.
>> <cut>
>>> #include <stdlib.h>
>>> #include <stdio.h>
>>> #include <string.h>
>>>
>>> //this program finds anagrams for the input word
>>>
>>> //usage
>>> //anagrams wordlist searchword
>>>
>>> //bubble sort word in alpha order
>>> char *wsort(char *s, int len)
>>> {
>>>    char t;
>>>    for(int i=0;i<len-1;i++) {
>>>       for(int j=i+1;j<len;j++) {
>>>          if(s[i]>s[j]) {
>>>             t=s[i];
>>>             s[i]=s[j];
>>>             s[j]=t;
>>>          }
>>>       }
>>>    }
>>> }
>>
>> You posted the old code.
>
> I posted the right code.
>
> We're getting confused by interchanging 'count the letters' with
> 'count each letter'.

Seems an odd confusion to have since I posted letter counting code in
reply to a request from you.  Anyway, glad that's cleared up.

> The code I posted 'counts the letters' via strlen(word).
>
> According to a friendly competition I'm having with someone, his count
> of each letter method is much slower than my count of all letters then
> sort and compare method.

I think you should call the change you've made something else.  Counting
letters is so standard in anagram programs that using those words to
talk about checking the string lengths is just going to add to the
confusion.

> count each letter:          real 0.196s
> count all letters = strlen: real 0.113s

Both the letter sorting and the letter counting versions should use the
same algorithm in other respects.  If you only count letters when the
lengths match, I would expect a fractionally faster run time.

Once you check the string lengths, the benefit of letter counting drops
off.  In my tests it's still faster than sorting the letters in every
word, but it's hard to measure since it's not inherently a slow
operation.

-- 
Ben.

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

#147189

On 24/10/2019 01:38, Ben Bacarisse wrote:
> DFS <nospam@dfs.com> writes:
> 
>> You don't have to make a separate list V[] to store the sorted letters
>> (though using such a list would be faster).
>>
>> This code makes one pass thru the dictionary, comparing the sorted
>> letters of the search word against the sorted letters of each word in
>> the dictionary.
> 
> Surely it's faster to count letters?  On my machine a simple letter
> counting version takes about 1/4 of the time your program takes.

Can you post code for a letter-counting version (that works off an 
external word list), or have you posted one already?

With the OP's sorting version:

(1) The words are read via fgets with line-endings attached, and need to 
be trimmed

(2) Bubble sort is applied to every word in the list

(I don't know if your '1/4' of the time compares times on your machine 
with the OP's reported time, but they appear to be using Tiny C.)

The sort version is missing the simplest optimisations, such as only 
comparing (and therefore sorting) words that are the right length. (Was 
this the letter-counting thing mentioned?)

And also, the program does (1) and (2) (for the words that are 7 letters 
with the above tweak applied), for EACH word that you want to find the 
anagrams of.

To find the anagrams of lots of different words, you would use a 
different approach with a data structure processed in advance or on-demand.

This can be done even when you want to run the program as a 
command-utility which looks for anagrams for one word at a time as this 
does (by preparing files that are processed versions of the word list). 
Then a 'slow' algorithm becomes less important.

This one just illustrates a more practical solution that prime number 
products.

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

#147210

Bart <bc@freeuk.com> writes:

> On 24/10/2019 01:38, Ben Bacarisse wrote:
>> DFS <nospam@dfs.com> writes:
>>
>>> You don't have to make a separate list V[] to store the sorted letters
>>> (though using such a list would be faster).
>>>
>>> This code makes one pass thru the dictionary, comparing the sorted
>>> letters of the search word against the sorted letters of each word in
>>> the dictionary.
>>
>> Surely it's faster to count letters?  On my machine a simple letter
>> counting version takes about 1/4 of the time your program takes.
>
> Can you post code for a letter-counting version (that works off an
> external word list), or have you posted one already?

I didn't want to because I had not fixed any of the issues with the
original.  I just hacked a letter count into the code.  For what it's
worth, I've appended it as the end.

> With the OP's sorting version:
>
> (1) The words are read via fgets with line-endings attached, and need
> to be trimmed

I kept that.  I wanted a direct comparison.  Profiling on Linux showed
that most of the time was spent in wsort so there was clearly room for
improvement.

> (2) Bubble sort is applied to every word in the list

I don't call that bubble sort, but let's not have that discussion again!

> (I don't know if your '1/4' of the time compares times on your machine
> with the OP's reported time, but they appear to be using Tiny C.)

It compared the original (compiled with gcc -O2) with the counting
version (obtained simply by adding -DCOUNTING), both running on the same
Linux laptop.  The numbers a so small that I doubt the ratio is really
accurate (roughly 0.132 vs 0.035 seconds when I tried today).

Code:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#ifdef COUNTING
#define N_LETTERS 26

void wcount(const char *s, unsigned char *c)
{
     memset(c, 0, N_LETTERS);
     while (*s) c[*s++ - 'a']++;
}

int eq_count(const char *s, const unsigned char *c)
{
     unsigned char sc[N_LETTERS];
     wcount(s, sc);
     return memcmp(c, sc, N_LETTERS) == 0;
}

#else

//bubble sort word in alpha order
char *wsort(char *s, int len)
{
  char t;
  for(int i=0;i<len-1;i++) {
     for(int j=i+1;j<len;j++) {
        if(s[i]>s[j]) {
           t=s[i];
           s[i]=s[j];
           s[j]=t;
        }
     }
  }
}

#endif

//trim trailing spaces
void rtrim(char *str, int len)
{
 while(len>0 && isspace(str[len-1])){len--;}
 str[len] = '\0';
}

//read file, find anagrams
int main(int argc, char *argv[])
{
    // w   = word in dictionary
    // ws  = alpha sort of the word
    // s   = search word you want anagrams for
    // ss  = alpha sort of the search word
    // mws = max word size
    // wc  = word count in dict

    int i=0,wc=0,mws=33;
    char w[mws], ws[mws], ss[mws];
    char *s = argv[2];

#ifdef COUNTING
    unsigned char ac[N_LETTERS];
    wcount(s, ac);
#else
    strcpy(ss,s);
    wsort(ss,strlen(ss));
#endif

    FILE *fw = fopen(argv[1],"r");
    while(fgets(w,sizeof(w),fw)!=NULL) {
        rtrim(w,strlen(w));
#ifdef COUNTING
        if (eq_count(w, ac)) {
#else
        strcpy(ws,w);
        wsort(ws,strlen(ws));
        if(strcmp(ws,ss)==0) {
#endif
          if(strcmp(w,s)!=0) {
            printf("%s\n",w);
            i++;
          }
        }
        wc++;
    }

    printf("%d anagram(s) found in %d words\n",i,wc);
    fclose(fw);
    exit(0);
}

-- 
Ben.

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

#147214

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> ...  The numbers a[re] so small that I doubt the ratio is really
> accurate (roughly 0.132 vs 0.035 seconds when I tried today).

These tests had some gcc -fsanitize options turned on which is why they
seemed wrong (slower overall than I remembered) as I typed them!  Plain
gcc -O2 gives 0.08 and 0.02.

-- 
Ben.

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

#147217

On 24/10/2019 21:34, Ben Bacarisse wrote:
> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> 
>> ...  The numbers a[re] so small that I doubt the ratio is really
>> accurate (roughly 0.132 vs 0.035 seconds when I tried today).
> 
> These tests had some gcc -fsanitize options turned on which is why they
> seemed wrong (slower overall than I remembered) as I typed them!  Plain
> gcc -O2 gives 0.08 and 0.02.

OK, thanks.

On my machine, gcc-O3 gives times of approx 80ms, counting, to 160ms 
with the slow sort. But file reading overhead using fgets is most of 
that 80ms (this is Windows).

Note that your letter-counting/histogram is actually just another way of 
sorting the string (you can trivially derive a sorted string from the 
result). (Starting the counts from 1 instead of 0, and ensuring a 0 
count follows the 'z' entry, yields a histogram that can be treated as a 
string.)

This string sort method seems to be O(n).

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

Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6  Next page →

Back to top | Article view | comp.lang.c

csiph-web