Project Euler

[pmav99]

Ναι τα imports είναι οι βιβλιοθήκες. Με την αυστηρή έννοια, δεν είναι εξωτερικές βιβλιοθήκες καθώς περιέχονται στην standard library της Python, αλλά και εξωτερικές να ήταν δε θα είχε κάποια διαφορά.

Το module timeit είναι για να συγκρίνεις την ταχύτητα εκτέλεσης ενός snippet python με ένα άλλο snippet python για να δεις ποιος αλγόριθμος είναι ταχύτερος. Δε νομίζω ότι μπορείς να το χρησιμοποιήσεις για να κάνεις συγκρίσεις με άλλες γλώσσες. Το έκανα για να δούμε ποια μέθοδος θα είναι η ταχύτερη καθώς και τις διαφορές μεταξύ python2/python3/pypy. Επίσης μου επέτρεψε να διαλέξω τον ταχύτερο αλγόριθμο για τη σύγκριση με τη C (αν δεχτούμε ότι μια τέτοια σύγκριση έχει νόημα).

Δεν είμαι ειδικός, οπότε μπορεί να κάνω και λάθος, αλλά νομίζω ότι ο λόγος που έχει νόημα να αφαιρέσεις imports, χρόνο εκκίνησης κτλ είναι γιατί είναι ενα σταθερό overhead. Δε σχετίζονται με τον αλγόριθμο. Είτε 5000 είναι το μήκος της λίστας που γίνεται sort είτε 5000000 o χρόνος αυτός είναι ο ίδιος και όπως φάνηκε άλλωστε, τουλάχιστον για το μέγεθος του προβλήματος, ο χρόνος αυτός είναι ένα σημαντικό τμήμα του συνολικού χρόνου. Ο αντίστοιχος χρόνος στη C φαντάζομαι ότι είναι αμελητέος. Είναι δύσκολο σε τόσο διαφορετικές γλώσσες να μπορέσεις να κάνεις συγκρίσεις.

Η C προφανώς είναι πιο γρήγορη από την Python και αυτό δεν είναι κάτι που χρειάζεται αποδείξεις. Εφόσον δεν το παρατηρούμε στην πράξη, το πιο πιθανό είναι ότι χρησιμοποιούμε πιο αργό αλγόριθμο στη C από αυτόν που χρησιμοποιείται στην Python. Δεν πρέπει να ξεχνάμε ότι πολλά από τα τμήματα της standard library της python είναι υλοποιημένα σε C οπότε δεν είναι και τόσο αργά. Επίσης άλλα compilation flags στη C πιθανότατα θα βελτιώνουν την ταχύτητα εκτέλεσης.

[migf1]

Off topic:
Η Python αν δεν κάνω λάθος χρησιμοποιεί δυναμικές βιβλιοθήκες (αυτές εννοώ εξωτερικές) ενώ η C χρησιμοποιεί στατικές βιβλιοθήκες (εσωτερικές, με την έννοια πως γίνονται linked μέσα στο εκτελέσιμο αρχείο του κάθε προγράμματος). Προφανώς μπορείς να χρησιμοποιήσεις και με τη C δυναμικές βιβλιοθήκες.

Ουσιαστικά ισχύει αυτό που λες κι εσύ, πως δεν μπορούμε να συγκρίνουμε ταχύτητες όταν η μια γλώσσα έχει αυτόνομο εκτελέσιμο αρχείο και η άλλη όχι. Αυτό που είναι σίγουρο είναι πως όλες οι compiled γλώσσες εκτελούνται πολύ ταχύτερα από τις μη compiled, ακόμα κι αν οι τελευταίες χρησιμοποιούν Just In Time compilation (JIT), όπως νομίζω κάνει η pypy.

[pmav99]

Off topic:
Just for the record, ρίξε ένα μάτι και ΕΔΩ

[migf1]

Off topic:

Just for the record, ρίξε ένα μάτι και ΕΔΩ

Περισσότερο για τρικ το βλέπω αυτό, παρά για κανόνα. Ένα που είδα αμέσως είναι πως στη C δηλώνει τα a και b ως double, που σημαίνει πολύ μεγάλοι πραγματικοί αριθμοί, Οπότε τη C την αναγκάζει να λάβει υπόψη της και υποδιαστολές. Αν τις δηλώσει ως long θα είναι πάλι πιο γρήγορη η PyPy? Κι έχω την αίσθηση πως όσο μικρότερο είναι το εύρος των μεταβλητών (int, short, char) τόσο πιο πολύ θα απομυθοποιείται το συγκεκριμένο παράδειγμα

Πάραυτα, έχει ένα point με τα shared libraries (τα dynamic δλδ), αλλά το συγκεκριμένο παράδειγμα είναι ψιλο-χοντρο-μούφα

[pmav99]

Off topic:
Μα καλά το γράφει και στον τίτλο ότι είναι "carefully crafted example". Προφανώς είναι ειδική περίπτωση, αλλά δείχνει ότι είναι δυνατόν να συμβεί. Όπως και αν έχει, ισχύει το γνωστό "για κάθε πρόβλημα υπάρχει το κατάλληλο εργαλείο". Άλλα τα usecases των high-level γλωσσών και άλλα αυτά των low-level.

Αν ασχοληθείς με python, φαντάζομαι θα βρεις ενδιαφέρουσα τη Cython η οποία κάνοντας μερικές δηλώσεις τύπων και προσέχοντας λίγο τον κώδικά σου, σου επιτρέπει να φτάσεις κοντά στην ταχύτητα εκτέλεσης της C (τουλάχιστον για number crunching που το έχω δοκιμάσει). Ένα παράδειγμα μπορείς να βρεις εδω

[migf1]

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

Η λύση μου σε C: https://ideone.com/Zmum3

Δεν είναι γρήγορος ο αλγόριθμος, γιατί δεν μπόρεσα να σκεφτώ κάποιον μαθηματικό τρόπο για να εξετάζω αν 2 αριθμοί έχουν αναγραμματισμένα ψηφία, οπότε τους μετατρέπω πρώτα σε c-strings και χρησιμοποιώ κατόπιν τον αλγόριθμο με το ιστόγραμμα του πίνακα ASCII (που έχω ποστάρει στο άλλο νήμα). Έφτιαξα όμως έτσι τον κώδικα ώστε να μπορείτε να αλλάζετε τη σταθερά NMULS για να ψάχνετε κι άλλα πολλαπλάσια εκτός από το 5 πρώτα

[UnKnown96]

Σήμερα που τα ξανά είδα δοκίμασα να λύσω μερικά...
Κατάφερα τα 1, 5 και 6 προς το παρών...

Εδώ ο κώδικας σε C:

Πρόβλημα 1:

Κώδικας: Επιλογή όλων



#include <stdio.h>

#define TRUE 1
#define FALSE 0

int multipleOf (int number)
{
static int sum = 0;

if (number % 3 == 0 || number % 5 == 0)
{
sum += number;
}

if (number == 999) printf ("The answer is %d\n", sum);

return 0;
}

int main (void)
{
int counter = 0;

do
{
counter++;
multipleOf(counter);
}
while (counter <= 999);

return 0;
}



Πρόβλημα 5:

Κώδικας: Επιλογή όλων



#include <stdio.h>

#define TRUE 1
#define FALSE 0

int evenlyDivisible (int number)
{
int counter, sum = 0;

for (counter = 1; counter <= 20; counter++)
{
if (number % counter == 0) sum++;
}

if (sum == 20)
{
printf ("The answer is %d\n", number);
return TRUE;
}

else return FALSE;
}

int main (void)
{
int evenlyDivisible (int number);
int counter = 0;

do
{
counter++;
}
while ( evenlyDivisible(counter) == FALSE );

return 0;
}



Και πρόβλημα 6:

Κώδικας: Επιλογή όλων



#include <stdio.h>

#define SQUARE(x) (x) * (x)

int main (void)
{
int counter, sum1 = 0, sum2 = 0;

for (counter = 1; counter <= 100; counter++)
{
sum1 += SQUARE(counter);
}

for (counter = 1; counter <= 100; counter++)
{
sum2 += counter;
}

sum2 = SQUARE(sum2);

printf ("The answer is: %d\n", sum2 - sum1);

return 0;
}



Αν και λίγο μπακάλικες οι λύσεις, δουλεύουν...

[stamatiou]

Μήπως έχει λύσει κανένας το 3ο σε C; Επειδή εγώ έχω κάνει αυτό:

Κώδικας: Επιλογή όλων


/*
This is the solution for the 3rd problem of the Euler Project in http://projecteuler.net/problem=3
Articulation:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Solution:
This programm starts from NUMBER and checks if there is a prime divisor for it.
*/

#include <stdio.h>

#define NUMBER 600851475143LL

int is_prime(long long num);

int main(void) {

long long i;

for(i = NUMBER; i >= 2; i--) {
if(is_prime(i)) {
if( (NUMBER % i) == 0) {
printf("%lld\n", i);
return 0;
}
}
}

return 0;
}

// Generates prime numbers less or equal than limit using 0 1 and storing them in ptable
int is_prime(long long num)
{
long long i;

if(num == 2)
return 1;

for( i = 2; i < num; i++) {
if( (num % i) == 0 )
return 0;
}

return 1;
}


Και μου βγάζει έξοδο σωστή για μικρότερα νούμερα αλλά για αυτό που μας δίνει, δε μου βγαίνει ποτέ

[Ilias95]

Μεταφράζοντας την λύση που είχα ποστάρει πολύ παλιότερα από python σε C:

Μορφοποιημένος Κώδικας: Επιλογή όλων

#include <stdio.h>
#include <stdbool.h>

int main(void)   {
    long long number = 600851475143, i = 2;
    
    for (;;) {
        bool divisible = false;
        for (; i < number; i++)
            if (!(number % i)) {
                number = number / i;
                divisible = true;
                break;
            }
        if (!divisible) // number is prime
            break;
    }
    
    printf("%lld\n", number);   
    return 0;
}

Edit:
Αυτό που έγραψες είναι αλγοριθμικά σωστό.
Όμως ο αλγόριθμος που έγραψες για να βρεις αν ένας αριθμός είναι πρώτος, είναι εξαιρετικά αργός για μεγάλα νούμερα εξαιτίας του loop που χρησιμοποιείς, γι' αυτό και θα κάνει πάρα μα πάρα πολύ ώρα μέχρι να τελειώσει η εκτέλεση του προγράμματος σου. Έτσι δεν βλέπεις ποτέ την έξοδο.

Αυτό που πόσταρα παραπάνω δίνει την λύση σε λιγότερο από δευτερόλεπτο.

Edit2:
Έκανα μια μικρή αλλαγή στον κώδικα και το πρόγραμμα έγινε ακόμα πιο γρήγορο.

[stamatiou]

Είναι όντως πολύ αργό, Bruteforce καραμπινάτο
Στη λύση σου όμως δεν καταλαβαίνω τον αλγόριθμο που χρησιμοποιείς. Σε τι αποσκοπεί το:

Κώδικας: Επιλογή όλων

number = number / i;