Project Euler

[UnKnown96]

3 γραμμές;;;
30 θες να πεις έτσι..;

[migf1]

Σε python; 3 (βρήκα και με 2, ακόμα και με 1 ... βέβαια επειδή δεν την ξέρω τη γλώσσα δεν ξέρω αν είναι ολοκληρωμένα... ολοκληρωμένα δείχνουν πάντως).

[migf1]

Νάτες...

2 γραμμές:

Spoiler: show

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


names = open("names.txt").read().replace('"','').split(",")
print sum( (i+1) * sum( 1+ord(c)-ord("A") for c in n ) for i,n in enumerate(sorted(names)) )


1 γραμμή:

Spoiler: show

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


sum(map(lambda x: (x[0]+1)*sum(map(lambda c: ord(c)-64,x[1])),enumerate(sorted(open("names.txt").read().replace('"','').split(",")))))


Ας τις τσεκάρεις όποιος έχει installed python.

[pmav99]

Δουλεύουν.

Το πρώτο είναι περίπου ισοδύναμο (αλλά πιο γρήγορο) με αυτό:

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

tot = 0
for i, name in enumerate(sorted(names)):
for char in name:
tot += (i + 1) * (1 + ord(char) - ord("A"))

print tot

To '1 - ord("Α")' είναι σταθερή ποσότητα (=64) οπότε δε χρειάζεται να υπολογίζεται μέσα στο loop αλλά το άφησα για να είναι πιο κοντά στο πρωτότυπο.

[migf1]

Δουλεύουν.

Το πρώτο είναι περίπου ισοδύναμο (αλλά πιο γρήγορο) με αυτό:

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

tot = 0
for i, name in enumerate(sorted(names)):
for char in name:
tot += (i + 1) * (1 + ord(char) - ord("A"))

print tot

To '1 - ord("Α")' είναι σταθερή ποσότητα (=64) οπότε δε χρειάζεται να υπολογίζεται μέσα στο loop αλλά το άφησα για να είναι πιο κοντά στο πρωτότυπο.

Αν η python μπορεί να βγάλει ανεξάρτητα εκτελέσιμα αρχεία, απλά από περιέργεια θα μπορούσες να κάνεις time -p τα παραπάνω με το εκτελέσιμο του κώδικα C που έχω δώσει στο ideone.com? Κατά προτίμηση εκείνου με τις λιγότερες συναρτήσεις.

Για να τα κάνεις compile, κι αν υποθέσουμε πως έχεις σώσει τον κώδικα ως "euler22.c", γράψε στο τερματικό σου:

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

gcc -O3 euler22.c -o euler22

και μετά:

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

time -p euler22

(τρέξτο 5-6 φορές για να υπολογίσεις χοντρικά με το μάτι τον μέσο όρο του: real time)

Προφανώς θα πρέπει να κάνεις το ίδιο και για το εκτελέσιμο της python.

Είμαι πολύ περίεργος να δω αν και πόση διαφορά υπάρχει σε ταχύτητα εκτέλεσης.

[pmav99]

ok περίμενε. Θα το τρέξω και με pypyγια να είναι ακόμη πιο γρήγορο.

Off topic:
linux δεν έχεις?

[migf1]

ok περίμενε. Θα το τρέξω και με pypyγια να είναι ακόμη πιο γρήγορο.

Off topic:
linux δεν έχεις?

Off topic:
Έχω, kubuntu... αλλά το έχω σε ένα laptop που "πεθαίνει" συνέχεια, και το χω αφήσει "πεθαμένο" τώρα γιατί μου είχε σπάσει τα νεύρα κάθε τρεις και λίγο.

[pmav99]

Λοιπόν το benchmarking τελείωσε.

Παραθέτω τους καλύτερους χρόνους user από 5 τρεξίματα.

1liner

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

real 0m0.058s
user 0m0.050s
sys 0m0.007s

2liner

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

real 0m0.056s
user 0m0.043s
sys 0m0.010s

pyeuler (από εδώ)

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

real 0m0.054s
user 0m0.040s
sys 0m0.010s

slow (το ισοδύναμο που έγραψα)

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

real 0m0.063s
user 0m0.053s
sys 0m0.007s

C (η time όμως έβγαζε το warning "sh: pause: command not found" που δε ξέρω πως επηρεάζει την ταχύτητα εκτέλεσης).

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

real 0m0.078s
user 0m0.070s
sys 0m0.007s

Πόρισμα. Η python είναι πιο γρήγορη από τη C!!! (μάλλον απλά ο κώδικας της c θέλει λίγη βελτιστοποίηση...)

Με το pypy τελικά δεν έτρεξα τον κώδικα, γιατί βγαίνει πολύ πιο αργή με την time. Δε ξέρω γιατί. Χρησιμοποιώντας το στάνταρ τρόπο σύγκρισης ταχύτητας εκτέλεσης της python (module timeit) η pypy είναι δύο φορές πιο γρήγορη από την κλασσική python (cpython) γεγονός αναμενόμενο όπου υπάρχουν for loops.

CPython : 10 loops, best of 3: 22 msec per loop
pypy : 100 loops, best of 3: 9.79 msec per loop

[migf1]

Σβήσε τη γραμμή system("pause"); στο τέλος από τον κώδικα της C (από εδώ: http://ideone.com/t1Mcv)
είναι για windows και περιμένει να πατήσεις ένα πλήκτρο, αυτό μάλλον τον καθυστερεί.

ΥΓ. Μόλις κατέβασα Python για Windows να το μετρήσω κι εγώ εδώ πέρα.

[pmav99]

To ίδιο

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

real 0m0.073s
user 0m0.070s
sys 0m0.000s