I dont get it... Why is everyone from science schools so obsessed with Perl and Python when we got C?

[ejolson]

You should install British English insane:

Code: Select all

$ wc -l /usr/share/dict/british-english-insane
654276 /usr/share/dict/british-english-insane

That does seem to keep with the general spirit of this project.

[jalih]

You should install British English insane:

Code: Select all

$ wc -l /usr/share/dict/british-english-insane
654276 /usr/share/dict/british-english-insane

That does seem to keep with the general spirit of this project.

Timed my 8th programming language version of anagram program using "/usr/share/dict/british-english-insane" word list:

Code: Select all

real	0m12,970s
user	0m11,876s
sys	0m1,068s

For interpreter that compiles words but does not do any optimizations, except for tail call elimination the result is good enough.

[Heater]

ejolson,

But, but, surely if the input list is assumed to be sorted, we only have to ensure a "stable sort" on those frequency tables to preserve the relative order of the anagrams.

As the C++ manual says:

"Sorts the elements in the range [first,last) into ascending order, like sort, but stable_sort preserves the relative order of the elements with equivalent values."

Does the sort in C do that?

[ejolson]

ejolson,

But, but, surely if the input list is assumed to be sorted, we only have to ensure a "stable sort" on those frequency tables to preserve the relative order of the anagrams.

As the C++ manual says:

"Sorts the elements in the range [first,last) into ascending order, like sort, but stable_sort preserves the relative order of the elements with equivalent values."

Does the sort in C do that?

Quicksort is not a stable sorting algorithm, that's why I use the actual word as a secondary key in the function indcomp when sorting the alphabetical letter lists.

[Heater]

Suggest upgrade to C++

[bensimmo]

bensimmo,

Hmm...

So what we need, with global warming and climate change in mind, is a complete life cycle energy usage analysis from the moment a person starts learning how to program a computer to the moment they finally create a program that computes the correct result.

We can assume they stop running it when they get the correct result for this particular problem.

Of course, for some countries it may reduce global l warming, with the extra heat some people could turn down their heating a fraction.
Or if you use a Pi4, for a specifically shaped heatsink that take slices of bread and you have yourself a toaster.
Compute and do a useful job at the same time.
Seems a win, win.

[Heater]

OK then. I'll use Python in the winter time so that I can turn my heaters down a bit. Or better yet BASIC.

[Musketeer]

Is variable size of int etc. in C still problem today in real usage on some platforms? + Anything else aspiring C learner should note and take care?

[Heater]

The int in C is still defined as it always was, "defined by the implementation".

The int on the Arduino is 16 bits.

On my embedded ARMs and such, 32 bits.

On my PCs 64 bits.

This is correct and as it should be. This is not a problem if you an understand the language.

If you want to write portable code, do not use int. Use the types defined in recent standards like uint32_t, int64_t, etc.

In fact, use them anyway. If you don't want to move your code around, somebody else might.

Always turn on warnings when compiling, -Wall. Always fix all the reported warnings.

Never return pointers to local variables.

[Michiel O.]

Would it be possible to replace the msortchar() function (which looks very slow) with qsort() ?

Yes, that is entirely possible:

$ cat strsort.c

Code: Select all

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

int charcmp(const void *a, const void *b) {
    return *(char *)a - *(char *)b;
    }

int main(void) {
    char s[] = "the quick brown fox etc...";
    qsort(s, strlen(s), sizeof(char), charcmp);
    printf("%s\n", s);
    }

$ cc strsort.c && ./a.out

...bcceefhiknooqrttuwx

[Michiel O.]

You should install British English insane:

Code: Select all

$ wc -l /usr/share/dict/british-english-insane
654276 /usr/share/dict/british-english-insane

I did this with:

$ sudo apt install wbritish-insane

$ wc -l /usr/share/dict/british-english-insane
654276 /usr/share/dict/british-english-insane

[ejolson]

Would it be possible to replace the msortchar() function (which looks very slow) with qsort() ?

Yes, that is entirely possible:

$ cat strsort.c

Code: Select all

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

int charcmp(const void *a, const void *b) {
    return *(char *)a - *(char *)b;
    }

int main(void) {
    char s[] = "the quick brown fox etc...";
    qsort(s, strlen(s), sizeof(char), charcmp);
    printf("%s\n", s);
    }

$ cc strsort.c && ./a.out

...bcceefhiknooqrttuwx

Replacement of the msortchar routine by a call to a character qsort as described above made the C program 24 lines shorter and lead to the following:

Code: Select all

/*  qanagram.c -- Find anagrams in /usr/share/dict/british-english-insane
    Written July 16, 2019 by Eric Olson

    This program is an example of how insane it is to work with
    pointers and C to find anagrams.
*/

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <ctype.h>
#include <string.h>
#include <strings.h>

static char *words,*keys,*cursor;
static char *skipword(){
    for(;*cursor;cursor++){
        if(*cursor=='\n') return ++cursor;
    }
    return 0;
}
static char *getword(){
    do {
        char *r=cursor;
        while(islower(*cursor)) cursor++;
        if(*cursor=='\n'){
            *cursor++=0;
            return r;
        }
    } while(skipword());
    return 0;
}

typedef struct { int p,n; } indtype;
static indtype *ind; static int indmax=0;

static int indcomp(const void *a,const void *b){
    int r;
    r=strcmp(keys+((indtype *)a)->p,keys+((indtype *)b)->p);
    if(r) return r;
    return strcmp(words+((indtype *)a)->p,words+((indtype *)b)->p);
}
static int anacomp(const void *a,const void *b){
    return strcmp(words+ind[((indtype *)a)->p].p,
        words+ind[((indtype *)b)->p].p);
}
static int charcomp(const void *a,const void *b){
    return *(char *)a-*(char *)b;
}
int main(){
    int fd=open("/usr/share/dict/british-english-insane",O_RDONLY);
    struct stat fdstat;
    fstat(fd,&fdstat);
    words=malloc(fdstat.st_size+1);
    read(fd,words,fdstat.st_size);
    words[fdstat.st_size]=0;
    close(fd);
    int lines=2;
    for(char *p=words;*p;p++) if(*p=='\n') lines++;
    ind=malloc(lines*sizeof(indtype));
    cursor=words;
    for(;;){
        char *word=getword();
        if(!word) break;
        ind[indmax].p=word-words;
        int r=cursor-word-1;
        ind[indmax++].n=r;
    }
    keys=malloc(fdstat.st_size+1);
    memcpy(keys,words,fdstat.st_size+1);
    for(int i=0;i<indmax;i++){
        qsort(keys+ind[i].p,ind[i].n,sizeof(char),charcomp);
    }
    qsort(ind,indmax,sizeof(indtype),indcomp);
    int flag=0;
    indtype *ana; int anamax=0;
    ana=malloc(sizeof(indtype)*lines/2);
    for(int i=1;i<indmax;i++){
        if(!strcmp(keys+ind[i-1].p,keys+ind[i].p)){
            if(!flag){
                ana[anamax].p=i-1;
                flag=1;
            }
        } else {
            if(flag){
                ana[anamax++].n=i;
                flag=0;
            }
        }
    }
    if(flag) ana[anamax++].n=indmax;
    qsort(ana,anamax,sizeof(indtype),anacomp);
    for(int i=0;i<anamax;i++){
        int j=ana[i].p;
        printf("%s: %s",words+ind[j].p,words+ind[j+1].p);
        for(j+=2;j<ana[i].n;j++){
            printf(", %s",words+ind[j].p);
        }
        printf("\n");
    }
    return 0;
}

Running on the Raspberry Pi 3B+ using the insane British dictionary leads to

Code: Select all

$ time ./qanagram >qanagram.insane

real    0m1.411s
user    0m1.370s
sys 0m0.041s

$ time ./anagram >anagram.insane

real    0m1.093s
user    0m1.023s
sys 0m0.071s

$ time ./anagram.perl >perl.insane

real    0m13.631s
user    0m13.519s
sys 0m0.111s

$ md5sum *.insane
bec74aa3b31577edbb291aeb7269a4d5  anagram.insane
bec74aa3b31577edbb291aeb7269a4d5  perl.insane
bec74aa3b31577edbb291aeb7269a4d5  qanagram.insane

which shows, in spite of the additional green-house gases, that the original code using merge sort is about 1.3 times faster. Both C programs are noticeably faster than the Perl program and produce the same result.

Has anyone tested the approach described in this post of creating a vector of letter counts rather than sorting?

[Heater]

ejolson,

Has anyone tested the approach described in this post of creating a vector of letter counts rather than sorting?

Grrr.... you are tempting me. I must resist...I must resist....

I'm supposed to be thinking about some particularly exciting SQL.

[DavidS]

Suggest upgrade to C++

Correction :

Suggest downgrade to C++

[Heater]

DavidS,

I do sympathize.

I also constantly marvel at the mind bending insanity of the ever increasingly complex and tortuous C++ syntax and semantics. Not to mention that swamp which is the STL.

It's gotten so bad that even Bjarne Stroustrup himself has noticed. The last time I heard him talk in a, key note, at a C++ conference he was basically pleading with the audience to stop and think about simplicity!

He is probably speaking in vain though, standards bodies and vested interests have a way to steam roller any garbage they like into a standard. Until the whole thing collapses under it's own weight. We have seen it many times before.

However, when I write C++ for myself it generally generates exactly the same code as if I had created the same functionality in C, But I can write it much more clearly.

The only reason for my upgrade suggestion there was that C++ has a very convenient stable sort in it's library which C does not.

[ejolson]

DavidS,

I do sympathize.

I also constantly marvel at the mind bending insanity of the ever increasingly complex and tortuous C++ syntax and semantics. Not to mention that swamp which is the STL.

It's gotten so bad that even Bjarne Stroustrup himself has noticed. The last time I heard him talk in a, key note, at a C++ conference he was basically pleading with the audience to stop and think about simplicity!

He is probably speaking in vain though, standards bodies and vested interests have a way to steam roller any garbage they like into a standard. Until the whole thing collapses under it's own weight. We have seen it many times before.

However, when I write C++ for myself it generally generates exactly the same code as if I had created the same functionality in C, But I can write it much more clearly.

The only reason for my upgrade suggestion there was that C++ has a very convenient stable sort in it's library which C does not.

It's likely that C++ templates could automatically create sort classes which are customized to character and other types that avoid the additional indirection and resulting slowdown that happens when using the qsort function. While templates would increase the size of the resulting binary by including multiple similar-but-different sort routines, with current computers the speed-versus-size tradeoff in the resulting binary usually favors speed. It's interesting that in historical Unix on the PDP-11 where the qsort function originated, the tradeoff almost always favored size.

[Musketeer]

Latest C++ ISO has like 1500 pages.
Latest Java like 775.

[Heater]

I we comparing like for like there.

To be fair to C++ a good half of the standards document is not about the language itself but the standard library.

The amount of libraries that comes with Java as standard is far bigger, I would expect the complete documentation to be much more pages than that.

[jahboater]

Latest C++ ISO has like 1500 pages.
Latest Java like 775.

C++17 is 1602 pages
C18 is 520 pages

[DavidS]

I have a few older books on C++, back when it was a good language, before STL existed (none of the books mention templates at all). Unfortunately C++ took a terrible turn to extreme feature creap.

I have nothing against the C++ that was C with classes and overloading for operators and functions. That was a good language, a true OO language in its pure form. Back then the most complex part of C++ was the Streams classes (those from which the likes of cin and cout are inherited).

From time to time I still use the subset of C++ that was all of C++ not that long ago (only about 30 years ago), of course with modern compilers.

Now if compilers would stop using name mangling, and use the object formats that specify parameter and return types instead (eliminating the need of name mangling).

[Heater]

DavidS,

It's to early and I'm not fully awake yet. Which is probably why I'm going to agree with you, mostly...

I have what I think was Stroustrup's first C++ book still somewhere. It's hardly bigger than the White Book. I was quite happy getting to learn C++ on Windows 3.1. Made some funky 3D rendering with it.

I also have Stroustrup's "Design of C++" which a great work explaining why all the features of C++ are there and why they are implemented that way.

Somewhere along the line the complexity shot through the roof and it went insane. It's impossible to write clear concise code that describes an algorithm without totally obscuring it with horrible syntactic noise and barely comprehensible semantics.

It has been steadily getting worse over the years. Especially recently as they have accelerated the standardization process so that more junk can get it there quicker.

It's telling that I have seen Stroustrup himself struggling to understand why a dozen lines of code on the screen at a conference presentation did not work!

It's telling that famous C++ gurus have jumped ship. Like Scott Meyers and Andrei Alexandrescu.
Last time I heard Scott speak somebody asked a C++ question and he basically said he had figured out how that stuff worked well enough to write the book on it but it is so complex he no longer remembers!
Andrei seems to be into D now a days.

The killer for C++ is it's insistence on backward compatibility with C. Which means adding any new semantic feature has to be a syntactic kludge.

C++ can be used to create looking, expressive, concise code. As it is in the Arduino. But as soon as you add in the STL or find yourself on a large team where everyone has their own ideas it all goes to hell.

The best thing to do if you only have a C compiler is to use it to create a higher level language, or domain specific language, then use that to solve your actual problem.

Enter, Javascript, Python even BASIC...

[Heater]

Hey, what is the problem with name mangling in C++?

One almost never has to even look at mangled names in C++. No more so than one ever has to look at the assembler code it produces.

On the rare occasions when it's useful to be looking at those things then just demangle them: with "objdump -C" or whatever tool. No problem.

If using name mangling were such a bad idea the new LLVM based Clang compiler would not be using it.

[DavidS]

Hey, what is the problem with name mangling in C++?

One almost never has to even look at mangled names in C++. No more so than one ever has to look at the assembler code it produces.

The problem is that it was a kludge to deal with two issues of the time. The two issues are the fact that C-Front translated C++ to C, and that the old linkable object file formats did not have the needed support for specifying parameter types for functions/methods, nor did they have a means to specify to what object a given method or similar belonged.

Of course you know me, I do look at the assembly, as well as the final object in its raw form.

On the rare occasions when it's useful to be looking at those things then just demangle them: with "objdump -C" or whatever tool. No problem.

If using name mangling were such a bad idea the new LLVM based Clang compiler would not be using it.

LLVM still needs to be compatible with the older way, unfortunately. There are targets of GCC, LLVM, and most other compilers that still have to deal with the limmited linkable object formats (so they have to use name mangling).

If doing it without name mangling is so bad: Why do modern linkable object file formats provide a way to do it without name mangling?

[DavidS]

The best thing to do if you only have a C compiler is to use it to create a higher level language, or domain specific language, then use that to solve your actual problem.

Enter, Javascript, Python even BASIC...

All third generation languages (including C), so none is any higer level than C.

You and JS .

I find it interesting that the three that you mention are traditionally interpreted languages (though becoming more and more popular to compile them [JIT] at runtime). What about Pascal, Oberon, Charm, C, BCPL, etc (normally compiled languages).

[jalih]

Has anyone tested the approach described in this post of creating a vector of letter counts rather than sorting?

I tried that approach with 8th to generate map keys instead of sorting word alphabets. It ran about the same speed as my original version. I got a little help from the 8th forums and version below is currently the fastest version for 8th:

Code: Select all

m:new var, anamap
a:new var, anakeys

: s:sort \ s -- s
  a:new swap ' a:push s:each!
  ' n:cmp a:sort
  ( swap s:+ ) "" a:reduce ;

: process-words \ word --
  /^[a-z]+$/ r:match if
    r:str nip dup >r
    s:sort
    anamap @
    over
    m:exists? if
      over m:@ r> a:push 2drop
    else
      swap a:new r> a:push m:!
    then
  then drop ;

: read-and-check-words  \ fname --
  f:slurp ' process-words s:eachline ;

: len>=  \ key --
  anakeys @ swap a:push drop ;

: fetch-ana-list \ key array --
  a:len 2 n:cmp
  1 n:+
  nip
  [ ' drop , ' len>= , ' len>= ]
  swap
  caseof ;

: key-val-cmp          \ key1 key2
  anamap @ swap m:@    \ key1 anamap key2val
  0 a:@ nip            \ key1 anamap val2
  swap rot             \ val2 anamap key1
  m:@ nip              \ val2 key1val
  0 a:@ nip            \ val2 val1
  swap                 \ val1 val2
  s:cmp ;

: sort-keys-by-first-word
  anakeys @ ' key-val-cmp a:sort drop ;

: list-words \ value --
  " " a:join . cr ;
 
: app:main
  0 args "/usr/share/dict/british-english-insane" ?:
  read-and-check-words
  anamap @ ' fetch-ana-list m:each drop
  sort-keys-by-first-word
  anamap @ anakeys @ m:@@ nip ' list-words a:each! drop
  anakeys @ a:len nip "\nAnagrams: %d\n" s:strfmt .
  bye ;
  

Execution time using "/usr/share/dict/british-english-insane" word list:

Code: Select all

real	0m10,689s
user	0m9,992s
sys	0m0,684s