Thread: Python --> C

Originally Posted by jeffcobb

C++ may be a good choice for him b/c some of the things he is doing with data structures is already done in the STL so he may find that to be a better middle-ground between pain and pleasure...

That would mean skipping an understanding of basic low level mm, etc. Also, you are to an extent trading the inefficiencies of one generic interface for another. To be honest, I love perl and I love C but using the STL data structures is a drag compared to the perl equivalents, probably that side of C++ will not seem like "fun" compared to python either.

Might be better to consider as an option later if s/he really doesn't like C. Or if s/he really can't do without OOP.

I was more thinking of (and this is a difference between Perl and Python IMO) the same black-box solution way of thinking that pervades Python can be represented by the algorithm part of the STL. I think the OPs stated motivation was simply to make it go faster, not necessarily wanting to get down to the nuts and bolts of the solution but I may have missed something.

Thanks for the many replies.

I have attached 2 files for testing. One takes 4.9 seconds on Python and contains only triplets of numbers.

The other takes 5.48 seconds and contains triplets as well as quadruplets. This is a more general version of the problem if anybody wants to try. The Python code doesn't worry about the length and it can find intersections of varying length.


As for C or C++ or something else. Here is what I think:

I use Python because it interfaces well with the software I primarily use it for. There is also a C++ DK I could use. Python is fine for many things but regularly I run into very computing intensive problems and speed is quite critical. I'm not afraid of "getting my hands dirty". In fact, I may enjoy it, but in the end what counts is results. I always thought of C as a very fast language that can also be a foundation for C++. But I'm not a programmer and don't really know.

If you are curious at all and you wrote the Python you posted (or at least understand it enough to attempt a port to another language, you are as much a programmer as anyone here. Curiosity about how stuff works is what got many of us here. We may argue and occasionally fight like cats and dogs but at the end of the day, that curiosity is what binds us all.

Welcome to the dark side Macha. Today you have take a step towards a greater reality

I think I understand what you mean. In my dayjob I use a software that is considered "hard" by many people because it goes down to the basics and seemingly simple tasks can become quite involved. But it opens a completely different perspective and great powertool to solve problems.

OK, so with your kind help I'll do a few C steps and get this thing running and see how I get along on the darker side. I printed out Sebastanis code, got some coffee and will study that in a bit more in detail now.

My quick hack code. It only deals with the 3-tuple case containing at least 2 common members.
Generalising it for n-tuple and x-common is an exercise for the reader

It's attached, so you have a chance to roll your own code without peeking (if you want to)

The full results for the 4.9 are attached, so you can see if they match your own results.

Code:

$ ./a.out 
Elapsed time:From=246045, To=283909, Elapsed=37864
Num tuples=2028, num results=3042
0 1: 0 1 15 -> 0 15 14
0 3: 0 1 15 -> 1 16 15
0 1327: 0 1 15 -> 714 1 0
1 26: 0 15 14 -> 14 15 29
1 1376: 0 15 14 -> 714 0 14
2 3: 1 2 16 -> 1 16 15
2 5: 1 2 16 -> 2 17 16
2 1329: 1 2 16 -> 715 2 1
3 28: 1 16 15 -> 15 16 30
4 5: 2 3 17 -> 2 17 16

About 40mSec - but that's just for the calculation.

C++ is actually pretty cool but I'm very dubious of the value of Sebastiani's example. I think it will take you the better part of the week just to understand most of the (largely pointless, in context) syntax.

Your "searchlist" function from post #1 is just a set of nested loops. You don't need more that one or two simple functions to do this here either. Your parameters would be a pointer to the head of a 2D int array (ie an array of triples) and an int indicating the number of triples in the array. The return value would be a pointer to a similar array, so the prototype:

Code:

int **searchlist (int **triples, int size);

The use of vectors, templates, etc here is totally superfluous (unless your goal is to just learn inappropriate uses for C++ syntax). It is certainly not more efficient if that is what you are after.

Originally Posted by MK27

C++ is actually pretty cool but I'm very dubious of the value of Sebastiani's example. I think it will take you the better part of the week just to understand most of the (largely pointless, in context) syntax.

Your "searchlist" function from post #1 is just a set of nested loops. You don't need more that one or two simple functions to do this here either. Your parameters would be a pointer to the head of a 2D int array (ie an array of triples) and an int indicating the number of triples in the array. The return value would be a pointer to a similar array, so the prototype:

Code:

int **searchlist (int **triples, int size);

The use of vectors, templates, etc here is totally superfluous (unless your goal is to just learn inappropriate uses for C++ syntax). It is certainly not more efficient if that is what you are after.

Well, it may be true in this particular case that writing it in C would be relatively straightforward and quite efficient (certainly more so than C++), but in *general*, at least, C++ is a much better language to work with, IMO (insomuch that you can choose whether to write high or low level code, depending on the situation, performance constraints, etc). Moreover, the "pointless syntax" you refer to just so happens to be rather close to what would be used in a Python program (most notably the level of abstraction), so I'm not really sure where you're going with that. I can only guess that it is your lack of familiarity of the language and the development processes used by C++ programmers (which are quite different than those used to develop C programs) that drives such a skewed perspective. The fact is, with an sufficient set of boiler-plate code (which most C++ programmers have at their disposal), the effort needed to write this sort of program would be minimal (comparable to what the OP originally posted in Python), not to mention that it could be done *generically*, in such a way that it could be packaged into classes of increasing complexity. Try doing that with your beloved C!

That said, I do respect the language (hell, it was the first one I learned to program with*, and was my language of choice for a number of years), but it's just too primitive (in my opinion, at least) to develop truly robust software. The nice thing about C++ is that you can still write C-style code where absolutely necessary, so you really can have your cake and eat it too, so to speak.

*Little known fact: Salem, in fact, was my first mentor (poor fellow!).

Originally Posted by Salem

About 40mSec - but that's just for the calculation.

Well, I know just what to do about this:

"Mom! Salem's showing off again!!"

I can't get my fingers to even start a program, that fast.



@Sebastiani: You didn't get what the OP really wanted to do. He's not trying to mimic the development process, or algorithmic design of the Python program - far from it. He wants just the functionality - that's the key word. Your program might be great - but just not appropriate, right now. Macha is looking for something fast and simple, so a beginner in C, (or C++), can tailor it to his problem.

That's a project / makefile problem (specific to your IDE).

Just open a console and type
gcc foo.c

I'm gonna take it nice and slow now.

I started by writing something that creates pairs of triplets.

How does this look, any comments?

Code:

/* 
 * File:   main.c
 * Author: Me
 *
 * Created on 24 May 2010, 13:57
 */

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

void main() {
    int datalist[][3] = {
        {0,1,2},
        {3,4,5},
        {2,1,5},
        {2,7,2},
        {4,5,9}
        };
    int size = sizeof(datalist)/sizeof(*datalist);
    int i,j;
    for(i=0;i < size;i++)
    {
        for(j=0;j<size;j++)
        {
            if(i != j)
            {
             printf("trips %d,%d:  (%d,%d,%d),(%d,%d,%d)\n",
             i,j,
             datalist[i][0],datalist[i][1],datalist[i][2],
             datalist[j][0],datalist[j][1],datalist[j][2] );
            };
        }
        printf(" \n");
    }


   
}

Next, I will try to read in data from a file.

Edit: I think that works by just adding #include "primlist.txt" in the datalist array

The code below appears to work and find intersecting triplets but I am sure I wrote really bad C.

What can I do to make it better?

Code:

/* 
 * File:   main.c
 * Author: Me
 *
 * Created on 24 May 2010, 13:57
 */

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

struct trip{ int a; int b; int c; };

int compare(struct trip t0, struct trip t1){
    int ra, rb, rc, r;
    ra = (t0.a == t1.a) || (t0.a == t1.b) || (t0.a == t1.c);
    rb = (t0.b == t1.a) || (t0.b == t1.b) || (t0.b == t1.c);
    rc = (t0.c == t1.a) || (t0.c == t1.b) || (t0.c == t1.c);
    r = (ra && rb) || (ra && rc) || (rb && rc);
    return r;
}
void main() {
    int datalist[][3] = {
    #include "primlist.txt"
    };
    int size = sizeof(datalist)/sizeof(*datalist);
    int i,j,c;
    for(i=0;i < size;i++)
    {
        for(j=0;j<size;j++)
        {
            if(i != j)
            {
            struct trip t0;
            t0.a = datalist[i][0];
            t0.b = datalist[i][1];
            t0.c = datalist[i][2];
            struct trip t1;
            t1.a = datalist[j][0];
            t1.b = datalist[j][1];
            t1.c = datalist[j][2];
            c = compare(t0,t1);
            if ( c == 1){
                printf("trips %d,%d:  (%d,%d,%d),(%d,%d,%d)\n",
                i,j,
                datalist[i][0],datalist[i][1],datalist[i][2],
                datalist[j][0],datalist[j][1],datalist[j][2] );
             };
            };
        }
    }
printf("Finished\n");
}

Are 1,3 and 3,1 regarded as separate matches (does symmetry count?)

My inner loop started from i+1, not zero.

> int compare(struct trip t0, struct trip t1)
Not so good - you're passing two structures by value, which is a lot of extra copying of data (compared to the amount of work done).
Passing two pointers to structures would be better.

Passing pointers to two array positions would be better still, since that saves having to create the trip structs in the first place.

Oh, and watch the void main - not good.