Re: Challenge for Feeb: dealing with large numbers in C

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.lang.c
Subject	Re: Challenge for Feeb: dealing with large numbers in C
Date	2019-10-24 20:36 +0100
Organization	A noiseless patient Spider
Message-ID	<877e4uvstq.fsf@bsb.me.uk> (permalink)
References	(4 earlier) <CdnrF.146403$hL1.58740@fx35.iad> <K7IrF.3053334$dw4.575231@fx12.am4> <zB_rF.60706$VU2.40054@fx12.iad> <87y2xbvuzb.fsf@bsb.me.uk> <s3fsF.1855772$HWr.1014722@fx36.am4>

Show all headers | View raw

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.

Thread

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

csiph-web