Combinations algorithm, λιγο φως?

[yop]

Εχω σπασει λιγο το κεφαλι μου με κατι, λοιπον για να μην μπλεξουμε με ορολογιες κτλ θα το πω σαν προβληματακι σχολειου. Εστω οτι εχουμε Ν δοχεια με 1 εως Ν-1 μπαλακια το καθενα. Θεωρουμε ότι θέλουμε να διαλεξουμε n μπαλακια παίροντας 1 μπαλακι από κάθε ένα από τα n δοχεια (n<=N προφανως). Ψαχνω ποσους διαφορετικους τετοιους συνδιασμους απο n μπαλακια μπορω να εχω. Πχ με νουμερακια, εστω 5 δοχεια το πρωτο με 1 μπαλακι το δευτερο με δυο, το τριτο με ενα, το τεταρτο με ενα, το πεμπτο με δυο. Ποσους διαφορετικους συνδιασμους απο πχ 3 μπαλακια μπορουμε να εχουμε παιρνοντας μεχρι ένα μπαλακι απο καθε δοχειο? Αν τα δοχεια είχαν απο ένα μπαλακι είναι ευκολα τα πραγματα (binomial coefficients, pascal's triangle, πολλες επιλογες απο ετοιμους αλγοριθμους). Δωστε αλγοριθμο, μαθηματικη ερμηνεια, links, source code, ό,τι βολευει τον καθενα θα το φερω εγω στα μετρα μου για να το χρησιμοποιησω. Thanx...

[Evolution_R]

Το μπαλακι που θα επιλεξεις απο καθε δοχειο θα το ξαναβαλεις μεσα για να τραβηξεις παλι η θα το αφησεις εξω .
Δηλαδη αν εχεις 3 δοχεια απο 3 μπαλακια και κανεις μια επιλογη απο το καθενα μετα θα εχεις 3 δοχεια απο 2 μπαλακια η παλι απο 3?
Σε ρωταω γιατι αλλαζει ο μαθηματικος τυπος πες μου και θα σου απαντησω. :039:

[yop]

Πολυ σωστη η παρατηρηση σου... Θα τα ξαναβαλουμε στις προηγουμενες θεσεις τους και παντα μας ενδιαφερουν διαφορετικες διαταξεις.

[Evolution_R]

Ο μαθηματικος τυπος -αν π.χ εχουμε 9 μπαλες και θελουμε να δουμε ποσες 3αδες μπορουν να προκυψουν- ειναι C(9,3)= 9! / 3!(9-3)! = 84
Το ! σημαινει παραγωντικο, δηλαδη 9! = 1*2*3*4*5....
Σε προγραμμα θες να το χρησιμοποιησεις?

[backgroundman]

Για να το φτιάξεις πρόγραμμα αυτό, το καλύτερο είναι να φτιάξεις μια συνάρτηση για το παραγωντικό την οποία θα μπορείς να καλείς όσες φορές θες. Μετά φτιάχνεις τον τύπο και τελείωσες.

Αν είναι να χρησιμοποιήσεις μεγάλους αριθμούς για να μην έχεις πρόβλημα με τη μνήμη καλύτερα για το παραγωντικό να πάρεις το προσεγγιστικό τύπο του Stirling

n! =e^(-n)*n^n*sqrt(2*pi*n)

[Braveheart1980]

Για να το φτιάξεις πρόγραμμα αυτό, το καλύτερο είναι να φτιάξεις μια συνάρτηση για το παραγωντικό την οποία θα μπορείς να καλείς όσες φορές θες. Μετά φτιάχνεις τον τύπο και τελείωσες.

Αν είναι να χρησιμοποιήσεις μεγάλους αριθμούς για να μην έχεις πρόβλημα με τη μνήμη καλύτερα για το παραγωντικό να πάρεις το προσεγγιστικό τύπο του Stirling

n! =e^(-n)*n^n*sqrt(2*pi*n)

Με προλαβες!
Πολυ σωστα τα λετε ολοι σας.
Μπραβο!

ΥΓ Καρα-offtopic αλλα τι θεματα Φ2 ηταν αυτα φιλε backgroundman!

[DarthMoul]

Για να το φτιάξεις πρόγραμμα αυτό, το καλύτερο είναι να φτιάξεις μια συνάρτηση για το παραγωντικό την οποία θα μπορείς να καλείς όσες φορές θες. Μετά φτιάχνεις τον τύπο και τελείωσες.

Αν είναι να χρησιμοποιήσεις μεγάλους αριθμούς για να μην έχεις πρόβλημα με τη μνήμη καλύτερα για το παραγωντικό να πάρεις το προσεγγιστικό τύπο του Stirling

n! =e^(-n)*n^n*sqrt(2*pi*n) Επειδή το n! θα χτυπήσει overflow σχετικά γρήγορα (35! σε float είναι το max), καλύτερα να το υπολογίσεις με ένα for και να φτιάξεις lookup table. Θα αυξήσεις την ταχύτητα καμμιά 50αριά φορές τουλάχιστον.

[yop]

C(9,3)= 9! / 3!(9-3)! = 84Ο παραπανω τυπος ειναι ο γνωστος "Ν choose n (http://mathworld.wolfram.com/Choose.html)" (9 choose 3 οπως το εγραψες), η αλλιώς μία binomial coefficient (http://mathworld.wolfram.com/BinomialCoefficient.html). Με τα παραπανω, για να επιστρεψω στο προβλημα, βρισκουμε ποσες διαφορετικες διαταξεις απο δοχεια εχουμε. Στο θετω και αριθμητικα χωρις πολλους υπολογισμους:
1ο δοχειο 1 μπαλακι
2ο δοχειο 1 μπαλακι
3ο δοχειο 2 μπαλακια
ζηταω συνδιασμους απο 2 μπαλακια.
Με τον αλγοριθμο choose του Evolution_R (σαν να τον ανακαλυψες εσυ το εγραψα... να με θυμηθεις στα Nobel!!!) 3!/(2!*(3-2)!)=3 (διαταξεις {0,1},{0,2},{1,2}), ενω η σωστη απαντηση ειναι 5 γιατι το τελευταιο δοχειο εχει 2 μπαλακια (διαταξεις {0.0 , 1.0},{0.0 , 2.0},{1.0 , 2.1},{0.0 , 2.0},{1.0 , 2.1}) μπροστα απο την τελεια το δοχειο (0...2) και μετα την τελεια το μπαλακι του δοχειου (0...1).Σε προγραμμα θες να το χρησιμοποιησεις? Ναι.Επειδή το n! θα χτυπήσει overflow σχετικά γρήγορα (35! σε float είναι το max), καλύτερα να το υπολογίσεις με ένα for και να φτιάξεις lookup table.Ποσο τεραστιο δικιο εχεις!... Και overflow (ειχα long μεταβλητες στην αρχη ouch!) και σερνεται και ολα τα καλα του κοσμου.
Την εχω ψαξει αρκετα τη δουλεια πριν σας ενοχλησω, sorry που σας τρωω και τον δικο σας χρονο...

[Evolution_R]

Με τον αλγοριθμο choose του Evolution_R (σαν να τον ανακαλυψες εσυ το εγραψα... να με θυμηθεις στα Nobel!!!):)
Δεν καταλαβα καλα τι εννοεις στο παραπανω,θες διαταξη απο δοχεια η απο μπαλακια?
Αν θες μπαλακια ειναι 4 ανα 2 και οχι 3 ανα 2 οπως λες και το αποτελεσμα ειναι 6 οχι 5.
Επειδη οι διαταξεις εχουν πολλες παραμετρους αν θες πες μου ακριβως το προβλημα και αν μπορω ευχαριστως να σε βοηθησω.
Παντως ο τυπος που σου εδωσα ειναι εγγυημενος και οριζεται ως διαταξη χωρις επαναληψη.

[yop]

Παντως ο τυπος που σου εδωσα ειναι εγγυημενος και οριζεται ως διαταξη χωρις επαναληψη.Ειναι οντως εγγυημενος ο τυπος αλλα στο προβλημα μου, δινει διαταξεις απο δοχεια (δεν ξερω αν με καταλαβαινεις, ο τυπος αυτος δινει τους διαφορετικους συνδιασμους n πραγματων απο ένα συνολο Ν>=n ομοιων πραγματων, στην περιπτωση μας τα δοχεια. Εμεις δεν εχουμε Ν ομοια πραγματα, αφου το καθε δοχειο μπορει να περιεχει διαφορετικο αριθμο απο μπαλακια)... Ζηταμε συνδιασμους απο μπαλακια παιρνοντας μεχρι ενα απο καθε δοχειο.Αν θες μπαλακια ειναι 4 ανα 2 και οχι 3 ανα 2 οπως λες και το αποτελεσμα ειναι 6 οχι 5.Παιρνοντας το 4 ανα 2 που μου λες βαζεις μεσα και τον συνδιασμο να παρω τις δυο μπαλες του τελευταιου δοχειου που δεν το θελουμε, απο καθε δοχειο μια μπαλα σε καθε συνδιασμο... Αλλιως δεν θα σας εμπλεκα με δοχεια και μπαλακια!

[Evolution_R]

Ωπα μαλλον μιλαμε για διαταξεις με επαναληψη (και οχι χωρις οπως ειπα εγω παραπανω:072: ). Αν τωρα καταλαβα καλα χρειαζεσαι τον τυπο P=N!/(N-M)! οπου στο παραδειγμα που αναφερεις μας δινει 3!/(3-2)!=6 οπου ειναι το σωστο και οχι 5, επιμενω. Αν και τωρα δεν το βρηκα θα φαω το πληκτρολογιο μεχρι και σημειωσεις 2 χρονων+ εψαξα! :073:
Για δες και πες μου.

[kagelar34]

Και γω τις πέρασα με την πρώτη τις πιθανότητες και δεν θυμάμαι τίποτα από τότε

όσοι τις θυμάστε ...μήπως ξέρετε τις πιθανότητες να κερδίσουμε το τζόκερ με ένα απλό δελτίο των 5+1?

Αν δεν λύθηκε η απορία του παιδιού φροντίστε πρώτα εκείνο και μετά ασχοληθείτε αν θέλετε μ' αυτό...

[Evolution_R]

Tου ΛΟΤΤΟ ειναι 1 στις 13.983.816.
Στο ΤΖΟΚΕΡ ειναι 1 στις 24.435.180
....
Παιζουμε??? :040: :040: :040: :040:

[kagelar34]

Παιζουμε???

ε όχι ιδιαίτερα...αλλά ήθελα να μάθω πόσο μας κοροιδεύουν

[yop]

Πιστεψε με οτι ειναι 5...
Δοχεια τα ονοναζουμε Α(1 μπαλακι),Β(1 μπαλακι),Γ(2 μπαλακια)
Ζηταμε συνδιασμους των δυο μπαλακίων (ωραια λεξη!...), πιθανοι συνδιασμοι:
Α1,Β1
Α1,Γ1
Α1,Γ2
Β1,Γ1
Β1,Γ2
το συνολον 5 (με τους τυπους που μου δινεις, οι οποιοι επαναλαμβανω ειναι σωστοι αλλα δεν καλυπτουν συνολικα το προβλημα, δεν θα βγαλουμε ποτε 5).
Κοιτα το και αν απο τα παραπανω δοχεια ζηταμε τρια μπαλακια, πιθανοι συνδιασμοι:
Α1,Β1,Γ1
Α1,Β1,Γ2
2 συνδιασμοι συνολικα (με τους παραπανω τυπους δεν θα το πετυχεις).
Ασε το πληκτρολογιo στη θεση του plz, γιατι μετα πως θα με βοηθησεις?... :)

[yop]

Τωρα που ειδα τα post του kagelar34: Αυτη ειναι η περιπτωση που χρησιμοποιουνται οι τυποι που μου δινεις, ποσους διαφορετικους συνδιασμους απο 6αδες εχουμε σε μια 36αδα? (ετσι δεν παιζεται το lotto ή ειμαι απο αλλο ανεκδοτο?...) Αυτη τη σκεψη πρεπει να παμε λιγο παραπερα δηλ αν κάποια στοιχεια της 36αδας έχουν και παραπανω επιλογες. Ας πουμε οτι το νουμερο 10 εχει τις επιλογες 10.1 10.2 10.3 10.4 και μονο μια απο αυτες τις επιλογες του δεκα μπορει να βγει στην κληρωση ποσες γινονται τοτε οι επιλογες του λοτο? Thanx kagelar34 την ανοιξαμε την κουβεντα...

[Evolution_R]

Λοιπον το εψαξα με τριγωνο Pascal, το εψαξα με αρχη του περιστερωνα,μεχρι και με την αρχη εγκλεισμου-αποκλεισμου και ΔΕΝ μπορω να το βγαλω 5 ενω πρεπει να ειναι 5 :076: :076: :076: :076: :076: ,το αποτελεσμα ολο 6 μου βγαινει μια λογικη θα ηταν να αφαιρεις την μοναδα απο το αποτελεσμα αλλα το δοκιμασα με μεγαλυτερα νουμερα και δεν μου βγαινει. Θα σου απαντησω αυριο σιγουρα μιας και θα ανεβω στην σχολη οποτε λιγο υπομονη και θα την βρουμε την ακρη, μου εχει κολλησει και το κουμπι DEL στο δοντι... :110:.

[yop]

Η υλοποιηση μου ειναι με τριγωνο Pascal (όπως προτεινε και ο Darth) αλλα τα αποτελεσματα μου ειναι μοκέτα για τον περιστερωνα που λες. Παντως ακριβως με τον ιδιο τροπο ξεκινησα κι εγω (αφου πρεπει να ειναι 6 γιατι μου βγαζει 5?... κτλ) αλλα εγω εβριζα μαθηματικους δεν ετρωγα πληκτρολογια thank god!

[backgroundman]

Δε φταίνε οι μαθηματικοί για το πρόβλημά σου. Το πρόβλημά σου δεν λύνεται με ένα τύπο μόνο. Δεν είναι συνδιασμοί των 4 μπαλακίων ανα 2 γιατι δεν θέλεις να παίρνεις 2 μπαλάκια απο το ίδιο δοχείο. Ούτε διατάξεις είναι γιατι σε μια διάταξη έχουμε Ν διαφορετικά αντικείμενα και παίρνουμε Μ απο αυτά και μας ενδιαφέρει η σειρά που τα πήραμε και ποια είναι αυτά τα αντικείμενα.
Είναι κάτι πιο πολύπλοκο το οποίο θέλει σκέψη.

[DarthMoul]

Ποσο τεραστιο δικιο εχεις!... Και overflow (ειχα long μεταβλητες στην αρχη ouch!) και σερνεται και ολα τα καλα του κοσμου.
Την εχω ψαξει αρκετα τη δουλεια πριν σας ενοχλησω, sorry που σας τρωω και τον δικο σας χρονο... Βρες τον αλγόριθμο που σε βολεύει, και μετά θα το κάνουμε γρήγορο μαζί.

[Evolution_R]

Λοιπον. Καθοτι δεν πηγα στην σχολη λογω ξενυχτιου(ωραια λεξη!)... :040: :040: :040:
Καθισα μαζι με τον πρωινο καφε να βρουμε λυση.
Το προβλημα σου εχει μια σοβαρη παραμετρο που ακυρωνει τους μαθηματικους τυπους που χρησιμοποιουν οι πιθανοτητες. Αυτη ειναι οτι ζητας να μην παρουμε μαζι τα 2 κ***μπαλακια απο το 3 δοχειο.
Αρα κατεληξα σε μια λυση που μου βγαζει το αποτελεσμα αλλα δεν ξερω κατα ποσο στεκει μαθηματικα.
Πρωτα θα παρουμε την περιπτωση να επιλεξουμε τα μπαλακια απο το δοχειο 1 και 2 αρα C(1,1)*C(1,1) -ενα απο το καθενα δηλαδη- αυτο μας δινει 1.
Μετα την περιπτωση να παρουμε το μπαλακι απο το 1 και καποιο απο τα 2 μπαλακια απο το 3 αρα C(2,1)*C(1,1) αυτο μας δινει 2.
Τελος την περιπτωση να παρουμε το 1 μπαλακι απο το δοχειο 2 με ενα απο τα μπαλακια απο το δοχειο 3 αρα C(2,1)*C(1,1) αυτο μας δινει παλι 2.
Οποτε αθροιζοντας τους πιθανους συνδιασμους εχουμε 1+2+2=5 :038: :038:
Αυτη ειναι η μονη λογικη λυση που μπορεσα να βρω αν και αυτο δεν κανει τοτε λυπαμαι αλλα δεν μπορω να βοηθησω :089: .

[backgroundman]

Αυτά που βγάζεις δεν είναι πιθανότητες αλλα επιλογές. Οι πιθανότητες είναι πάντα <= 1.
Το θέμα αυτό δεν έχει να κάνει με πιθανότητες αλλα με δειγματικό χώρο, για αυτό λέγαμε για συνδιασμούς και διατάξεις.

[Evolution_R]

Ναι λαθος μου οι πιθανοι συνδιασμοι ηθελα να πω και οχι πιθανοτητες.

[backgroundman]

Νομίζω οτι το βρήκα :
Έστω οτι οι συνδιασμοί των N ανα 1 είναι C(N,1) που ισούται με Ν τότε αν έχω Κ δοχεία με Μ1,Μ2,Μ3,...,Μν μπάλλες το κάθε δοχείο τότε οι συδιασμοί 2 μπαλλών παίρνοντας 1 μπάλα απο κάθε δοχείο είναι
Α=[C(M1,1)*C(M2,1)]+[C(M1,1)*C(M3,1)]+...+[C(M1,1)*C(Mv,1)]+

[C(M2,1)*C(M3,1)]+[C(M2,1)*C(M4,1)]+...+[C(M2,1)*C(Mv,1)]+...+[C(Mv-1,1)*C(Mv,1)]

A=M1*M2+M1*M3+...+M1*Mv + M2*M3+M2*M4+...M2*Mv + ... + Mv-1*Mv

A= M1*SUM(M2,Mv) + M2*SUM(M3,Mv) + ... + Mv-1*SUM(Mv,Mv).

Εαν έχω M1=1,M2=1,M3=2 τότε βγαίνει Α=1*3+1*2 = 3+2 =5
To δοκίμασα και με Μ1=1,Μ2=2,Μ3=3 και Μ1=1,Μ2=3,Μ3=3 και έβγαλε σωστά αποτελέσματα.

Τώρα αν θές 3άδες απο μπάλλες τότε πας σε τριπλά γινόμενα ανα 3 δοχεία χωρίς να παίρνεις την ίδια 3άδα ποτέ.

[Evolution_R]

Νομίζω οτι το βρήκα :
Έστω οτι οι συνδιασμοί των N ανα 1 είναι C(N,1) που ισούται με Ν τότε αν έχω Κ δοχεία με Μ1,Μ2,Μ3,...,Μν μπάλλες το κάθε δοχείο τότε οι συδιασμοί 2 μπαλλών παίρνοντας 1 μπάλα απο κάθε δοχείο είναι
Α=[C(M1,1)*C(M2,1)]+[C(M1,1)*C(M3,1)]+...+[C(M1,1)*C(Mv,1)]+

[C(M2,1)*C(M3,1)]+[C(M2,1)*C(M4,1)]+...+[C(M2,1)*C(Mv,1)]+...+[C(Mv-1,1)*C(Mv,1)]

A=M1*M2+M1*M3+...+M1*Mv + M2*M3+M2*M4+...M2*Mv + ... + Mv-1*Mv

A= M1*SUM(M2,Mv) + M2*SUM(M3,Mv) + ... + Mv-1*SUM(Mv,Mv).

Εαν έχω M1=1,M2=1,M3=2 τότε βγαίνει Α=1*3+1*2 = 3+2 =5
To δοκίμασα και με Μ1=1,Μ2=2,Μ3=3 και Μ1=1,Μ2=3,Μ3=3 και έβγαλε σωστά αποτελέσματα.

Τώρα αν θές 3άδες απο μπάλλες τότε πας σε τριπλά γινόμενα ανα 3 δοχεία χωρίς να παίρνεις την ίδια 3άδα ποτέ.
Το ιδιο πραγμα λεμε μαλλον...:D

[backgroundman]

Και ο γενικός τύπος αν έχουμε ν δοχεία και θέλουμε να διαλέξουμε r μπάλες τότε

A(r) = M1*M2*...*Mr-1*SUM(Mr,Mv) + M1*M3*...*Mr*SUM(Mr+1,Mv) +...+ M1*Mv-r+2*...*Mv-1*SUM(Mv,Mv) +

M2*M3*...*Mr*SUM(Mr+1,Mv) + M2*M4*...*Mr+1*SUM(Mr+2,Mv) +...+ M2*Mv-r+2*...*Mv-1*SUM(Mv,Mv) +

...
...
... +

Mv-r+1*Mv-r+2*...*Mv-1*SUM(Mv,Mv).

Νομίζω οτι ο τύπος είναι σωστός αν και είναι μεγάλη μπερδεψούρα. Δε ξέρω αν βγαίνει αναγωγικός τύπος απο αυτό το πράγμα αλλα θα το σκεφτούμε και αυτό. Τωρα πώς αυτό θα το κάνεις πρόγραμμα είναι άλλη ιστορία.

[backgroundman]

Το ιδιο πραγμα λεμε μαλλον...:D

Λέμε το ίδιο αν με το C(2,1) εννοείς τους συνδιασμούς των 2 ανα 1.
Επίσης όταν έχεις περισσότερα δοχεία μπερδεύεται το πράγμα γιατι δε πρέπει να πάρεις 2 φορές τον ίδιο συνδιασμό δοχείων, δηλαδή να πάρεις το C(M3,M7) και το C(M7,M3).

Η λογική είναι παρόμοια. Να ρωτήσω επίσης τι σπουδάζεις (αν σπουδάζεις)??

[backgroundman]

O γενικός τύπος Α(r) είχε ένα λαθάκι και έγινε update τώρα είναι σωστός.

[Evolution_R]

Με το C(2,1) εννοω οτι απο τα δυο μπαλακια του 3 περνουμε το ενα.
Αρα απο τα δυο πιθανα ενδεχομενα επιλεγουμε το ενα.
Ειναι σωστο εχω την εντυπωση, απλως γινεται οντως πολυπλοκο αν βαλεις πολλες μεταβλητες.
Βιομηχανικη Πληροφορικη σπουδαζω στην Καβαλα.

[backgroundman]

Έχεις δίκιο είναι το ίδιο με αυτό που λέω εγώ.
Άρα το βρήκες πρώτος, μπράβο :D :D :D
Καλη συνέχεια με τις σπουδές σου, στη πιο όμορφη πόλη της Ελλάδας (προσωπική άποψη).

[yop]

Sorry guys εμεινα στη δουλεια μεχρι αργα χθες κ δεν μπηκα στο internet καθολου. Ο τυπος πρεπει να εναι Ok, το απογευμα θα τον δω κι εγω και θα εχεται feedback

[yop]

Οντως παιζει ο αλγοριθμος (μαλλον επρεπε να ειχα ρωτησει νωριτερα, θα το θυμαμαι αλλη φορα). Εκανα δοκιμη με αυτον:A=M1*M2+M1*M3+...+M1*Mv + M2*M3+M2*M4+...M2*Mv + ... + Mv-1*Mvκαι τα αποτελεσματα ειναι οοολα σωστα.
Απο αυριο θα κοιταξω να κανω implementation και σ'αυτον:A(r) = M1*M2*...*Mr-1*SUM(Mr,Mv) + M1*M3*...*Mr*SUM(Mr+1,Mv) +...+ M1*Mv-r+2*...*Mv-1*SUM(Mv,Mv) +

M2*M3*...*Mr*SUM(Mr+1,Mv) + M2*M4*...*Mr+1*SUM(Mr+2,Mv) +...+ M2*Mv-r+2*...*Mv-1*SUM(Mv,Mv) +

...
...
... +

Mv-r+1*Mv-r+2*...*Mv-1*SUM(Mv,Mv).Τωρα τα προβληματα ειναι ποιο πολυ υλοποιησης γιατι για δεδομενο αριθμο απο μπαλακια (balls) που θα παιρνουμε απο τα δοχεια (containers) που το καθενα εχει Μ[i], i=0,1,2,...,containers-1 μπαλακια ειναι της μορφης:
for(i1=0; i1<containers-(balls-1); i1++)
for(i2=i1+1; i2<containers-(balls-2); i2++)
for(i3=i2+1; i3<containers-(balls-3); i3++)
.
.
.
for(i_n=i_n_minus_1+1; i_n<containers; i_n++)
result=M[i1]*M[i2]*M[i3]*....*M[i_n];
Τα ασχημα νεα ειναι ότι για να έχω μεταβλητο αριθμο απο μπαλακια που θα παρουμε απο τα δοχεια πρεπει ή σε κάθε for να κανω τον ελεγχο if(iteration_depth == balls) κανε τον πολλαπλασιασμο;
με iteration_depth να ειναι το σε ποιο for ειμαι
ή να κανω ενα τεραστιο switch με ολες τις δυνατες επιλογες απο δοχεια που εχω και σε καθε τετοια επιλογη να φτανω σε τετοιο βαθος το for.
Επισης επειδη θα επιστρεφω long μεταβλητη καποια στιγμη κανει overflow συν του οτι ας πουμε το C(13,25) (13 μπαλακια απο 25 δοχεια ολα τα δοχεια απο ενα μπαλακι) ειναι 5.2003e6 και γονατιζει το pc (αν δειτε λιγο τον κωδικα παιζουν 13 for το ενα μεσα στο αλλο με 12 επαναληψεις το εξωτερικο φτανοντας τις 25 επαναληψεις το εσωτερικο (που κανει κ τον πολλαπλασιασμο). Αν θελετε να παγωσετε το pc για κανα διλεπτο να σας στειλω το εκτελεσιμο).
Τουλαχιστον ξερω τωρα που βαδιζω...
Thanx guys με βοηθησατε απιστευτα

[DarthMoul]

Γιατί δεν δουλεύεις με float;

Νομίζω είναι ευκαιρία να παίξουμε λιγάκι με optimizations. Γράψε αυτό που μπορείς, ανέβασε σε ένα zip το source και κάνε ποστ 1-2 μετρήσεις. Μετά θα πειράξουμε το source μαζί και θα ξαναμετρήσουμε με την καινούργια optimized έκδοση.

[backgroundman]

Πιστεύω οτι πρέπει να βρείς ένα πιο αποδοτικό αλγόριθμο για να γλιτώσεις τα πολλαπλά for. Θα το ψάξω λίγο μπας και βρώ τίποτα.

[yop]

Λοιπον...
Εκανα την υλοποιηση με δυο τροπους στον ενα κανω τον ελεγχο για τα ζητουμενα μπαλακια μεσα στα for και με τον αλλο χρησιμοποιω ενα τεραστιο switch. Επισης αν το καθε δοχειο εχει 1 μπαλακι χρησιμοποιω τριγωνο Pascal (δεν δινει σωστα αποτελεσματα για το γενικο προβλημα παρα μονο στην περιπτωση 1 μπαλακι / δοχειο). Η ταχυτητα εκτελεσης δεν επηρεαζεται απο τον αριθμο μπαλακίων/δοχειο αλλα απο τον αριθμο των δοχειων και τα ζητουμενα μπαλακια (αφου ειτε 1*1*1*1*1 ή 2*2*2*2*2 ή ο,τι αλλο πολλαπλασιασουμε τον ιδιο χρονο θα κανουν). Λοιπον αποτελεσματα:
δοχεια, μπαλακια, με if, με switch
20, 12, 2.198 sec, 0.007 sec
21, 13, 2.624 sec, 0.015 sec
22, 13, 8.145 sec, 0.030 sec
Οι μετρησεις γινονται περιπου με τον ιδιο τροπο που χρησιμοποιει ο Darthmoul στα pctestbench (εγω ειχα μεινει στην clock() αλλα σε αλλο ποστ μου τα αλλαξε τα μυαλα...).
Darthmoul θελω να χρησιμοποιησω long αλλα απο λαθος input μπορει να την πατησω. Αλλαξα σε double και θα κανω cast σε long (αν προκυψει υπερχειληση τοτε μυνηματακι λαθους, ευχαριστω για την προτιμηση και καλη σας νυχτα...). Στο θεμα τωρα δεν περιμενα τοοοσο μεγαλες διαφορες αναμεσα στις δυο υλοποιησεις αφου εχουν σχεδον την ιδια λογικη, μπορεις να καταλαβεις τι φταιει? Τελοσπαντων στελνω και sources και σας αφηνω για να συνεχισω να παλευω με τον αλγοριθμο με τα αθροισματα που εχω πιασει να δουμε τι κανει κι αυτος...

[DarthMoul]

Μόλις βρω χρόνο θα το κοιτάξω και θα σου πω. Αν πετύχω σημαντική βελτίωση (πάνω από 10%) θα ανεβάσω και την βελτιστοποιημένη έκδοση για να την δεις. Δεν θα αλλάξω τον αλγόριθμο. Ούτε καν θα γράψω δικό μου κώδικα. Θα επέμβω στον δικό σου, ώστε να φανεί καλύτερα πως θα έπρεπε να γραφτεί. Σε τι μηχανή μέτρησες; Intel ή AMD;

[yop]

Intel

[DarthMoul]

Ξαναέγραψα την calculate_all_fors που φαινόταν λιγάκι προβληματική. Ακριβώς ο ίδιος αλγόριθμος αλλά με άλλη υλοποίηση. Βάλτην στην θέση της δικιάς σου, ξαναμέτρα στην μηχανή σου και πες μας αποτέλεσμα. Με χρόνο και % βελτίωση.

Την δοκίμασα με παραμέτρους 22, 13 και n. Ελπίζω να δουλεύει σωστά.

[yop]

Ξαναέγραψα την calculate_all_fors που φαινόταν λιγάκι προβληματικήΤο λιγακι μου αρεσε...

Input 15,7
original: 2.14 sec
optimized: 0.001 sec
alternative: < msec

Input 20,10
original: 2.984 sec
optimized: 0.033 sec
alternative: 0.008 sec

Input 25,10
original: 30.035 sec
optimized: 0.633 sec
alternative: 0.209 sec

Ενταξει συγκριση δεν υπαρχει μεταξυ original και optimized. Τα αποτελεσματα αν κανετε λιγες δοκιμες που δινει ο optimized δεν ειναι ολα σωστα (δεν προλαβα να δω τι φταει).
Darthmoul με την static δεν θα εχουμε προβλημα αν ξανακαλεσουμε την συναρηση με αλλο input? Επισης αν βαλεις την optimized συναρτηση μεσα στο προγραμμα που εστειλα δεν δινει output στο stdout τις τιμες που υπολογιζονται αλλα μια σταθερη τιμη ασχετη (για να δω οτι κανει σωστους υπολογισμους επαιρνα output μεσα απο την core συναρτηση και μετα την επανεφερα για τις μετρησεις). Σπανια χρησιμοποιω static (πρεπει να ειμαι πολυ σιγουρος πως θα συμπεριφερθει) και ψιλομπερδευτηκα (και σχεδον ποτε δεν χρησιμοποιω recursive συναρτησεις οποτε, δυστυχως για μενα απ'ο,τι φαινεται, την δικια σου υλοποιηση δεν υπηρχε περιπτωση να την γραψω...)

[DarthMoul]

Την δοκίμασα μόνο με 22 και 13 και σύγκρινα το αποτέλεσμα με το δικό σου. Ίσως κάπου να ξέφυγε κάτι, γιατί από τον αλγόριθμο δεν κατάλαβα γρι. Απλώς ξανάγραψα την δικιά σου ωστέ να τρέξει γρήγορα.

Ναι με την static μεταβλητή θα έχεις πρόβλημα αν την ξανακαλέσεις μετά. Αλλά έτσι όπως είναι το πρόγραμμα σου δεν υπάρχει περίπτωση για κάτι τέτοιο, οπότε την χρησιμοποιείς εκ του ασφαλούς.

Εγώ την έβαλα μέσα στο πρόγραμμα σου και δούλεψε μια χαρά. Σε linux με gcc.
Μια χαρά δούλεψε. Θα στο στείλω την δευτέρα να το δεις μαζί με το output.

Μέχρι τότε κοίταξε σε ποιές περιπτώσεις δεν δουλεύει για να το διορθώσουμε. Micro optimization να κάνω; Ίσως κερδίσουμε άλλο ένα 60-70%. Δεν ξέρω. Θα δείξει

ΥΓ. Και εγώ αποφεύγω τις recursive συναρτήσεις. Είναι αργές και πιέζουν πολύ το stack με κίνδυνο overflow. Συνήθως φτιάχνω δικό μου stack και κάνω την αναδρομή μόνος μου, αλλά ήμουν στο γραφείο και είχα ένα 15λεπτο break, οπότε έγραψα αναδρομικά.

[yop]

αλλά ήμουν στο γραφείο και είχα ένα 15λεπτο break, οπότε έγραψα αναδρομικά.μου εμπηξες μαχαιρι στην καρδια εγω παιδευομουν ολοκληρο απογευμα...
Δυστυχως τωρα δεν εχω χρονο, θα σου πω παντως περιπτωσεις που δεν δουλευει σωστα.
GCC κ Linux επισης.

[DarthMoul]

μου εμπηξες μαχαιρι στην καρδια εγω παιδευομουν ολοκληρο απογευμα...
Δυστυχως τωρα δεν εχω χρονο, θα σου πω παντως περιπτωσεις που δεν δουλευει σωστα.
GCC κ Linux επισης.
Έγραψες πολλά περιττά, γι αυτό άργησες. Γέμισες και το icache και όλους του registers και έδεσε το γλυκό. Λίγα και απλά θέλει. Αν είναι απλοϊκά ακόμα καλύτερα. One step at a time and keep it simple.

[yop]

Την δοκίμασα μόνο με 22 και 13 και σύγκρινα το αποτέλεσμα με το δικό σου. Ίσως κάπου να ξέφυγε κάτι, γιατί από τον αλγόριθμο δεν κατάλαβα γρι. Απλώς ξανάγραψα την δικιά σου ωστέ να τρέξει γρήγορα.Αν δωσεις input με y δεν δινει σωστα αποτελεσματα, πχ 7,4,y,2,3 δινει 206 ενω το σωστο ειναι 115. Αν σε 15' ειχες καταλαβει κ τον αλγοριθμο θα μου τον εκοβες τον προγραμματισμο μια και καλη και πως θα εβγαζα το ψωμακι μου μετα?Ναι με την static μεταβλητή θα έχεις πρόβλημα αν την ξανακαλέσεις μετά. Αλλά έτσι όπως είναι το πρόγραμμα σου δεν υπάρχει περίπτωση για κάτι τέτοιο, οπότε την χρησιμοποιείς εκ του ασφαλούς.Σε κανονικη υλοποιηση ομως η συναρτηση λογικο ειναι να ξαναχρειαστει, αυτο ειναι προγραμματακι για tesing αρχικα των αποτελεσματων και μετα για το optimization.Εγώ την έβαλα μέσα στο πρόγραμμα σου και δούλεψε μια χαρά. Σε linux με gcc.Εξακολουθω να μην έχω σωστο ouput. Εκανα buid κ στα win με minigw, borland, m$, και δεν... Εβαλα σκεψου στο header την core με default τιμη για την index παραμετρο 0, copy paste την core στο cpp με τις συναρτησεις υπολογισμου και την καλεσα ακριβως οπως κ τις υπολοιπες. Στο linux δινει stdout output κατι σαν 3.04027e-315 (δεν ειναι ακριβης τιμη απλα η μορφη της γιατι ειμαι σε win τωρα), ενω στα win 1.#QNAN. Anyway αδιαφορο αν βαλω μεσα στην συναρτηση ενα cout πριν το return δεινει τα κανονικα αποτελεσματα που ειναι και αυτα που σου δινω σν feedback.Μέχρι τότε κοίταξε σε ποιές περιπτώσεις δεν δουλεύει για να το διορθώσουμε.Αν δωσεις input y οπως ειπα κ παραπανω.Micro optimization να κάνω; Ίσως κερδίσουμε άλλο ένα 60-70%. Δεν ξέρω. Θα δείξειΑπ' οτι φαινεται μαλλον θα χρησιμοποιησω την alternative που εγραψα που δειχνει να ειναι κ η πιο γρηγορη. Παντως ειμαι περιεργος...ΥΓ. Και εγώ αποφεύγω τις recursive συναρτήσεις. Είναι αργές και πιέζουν πολύ το stack με κίνδυνο overflow.ΣωσταΣυνήθως φτιάχνω δικό μου stack και κάνω την αναδρομή μόνος μου, αλλά ήμουν στο γραφείο και είχα ένα 15λεπτο break, οπότε έγραψα αναδρομικά.Τα ειπαμε, ουτε στα πιο τρελα ονειρα μου...Έγραψες πολλά περιττά, γι αυτό άργησες. Γέμισες και το icache και όλους του registers και έδεσε το γλυκό. Λίγα και απλά θέλει. Αν είναι απλοϊκά ακόμα καλύτερα. One step at a time and keep it simple.Για οποιον δεν ειδε τα sources, YoP 150 lines, Darthmoul 13 lines, απο Δευτερα παραιτουμαι...

[DarthMoul]

Μήπως εννοείς 150 lines;

Κατάλαβα γιατί δεν σου δίνει σωστά αποτελέσματα. Έχεις άλλη έκδοση glibc με διαφορετική υλοποίηση printf. Με τι τυπώνεις το αποτέλεσμα; %f;
Δοκίμασε κάτι άλλο. %LF, %F κλπ...Κοίταξε το manual της printf και θα την βρεις την άκρη.

Από δευτέρα θα κοιτάξω και τα bugs που είπες. Θα προσθέσω και μια αρχικοποίηση κατά συνθήκη στις static μεταβλητές για να γίνει η συνάρτηση γενικής χρήσης. Όταν γίνει αξιόπιστη θα κάνω micro-optimization να δούμε μέχρι που πάει και μετά θα κοιτάξω και την άλλη με τα switch.

[yop]

Ναι 150 (για 2 γραμμες δεν χανω τη δουλεια μου...) το εκανα κ edit. Εχω χρησιμοποιησει κ cout κ printf με ο,τι formating μπορουσα να φανταστω, θα κοιταξω το man. Δεν ειναι κ κανα μεγαλο προβλημα αυτο ουτως ή αλλως απλα την ομορφια μου χαλαει...

[DarthMoul]

Διορθωμένη και overoptimized. Μέτρησε την να δούμε τι ψάρια πιάνει.
Μένει να δούμε τι θα κάνουμε με τις static μεταβλητές. Μπορώ να χρησιμοποιήσω global variables;

[yop]

Μπορώ να χρησιμοποιήσω global variables;Οσες θες...

[DarthMoul]

Οκ. Εδώ έλυσα και το πρόβλημα με τις static variables ώστε να μπορείς να την καλείς επαναληπτικά. Είναι πιο γρήγορη από την δεύτερη έκδοση, οπότε καλύτερα να μετρήσεις με αυτήν.

Keep on coding.

[yop]

Επεστρεψα!!! Παιξαμε με εναν φιλο μαθηματικο και τελικα εχει προβλημα ο αλγοριθμος και την παταμε σε ταχυτητα. Γραψαμε κατι καινουριο που παιζει ποιο γρηγορα απ ολους ως τωρα στελνω κωδικα κ μετρησεις (caf3, switch και του τελευταιου alternative). Παντως αν εχεις ορεξη Darthmoul γραψε δυο λογακια για το πως δουλεψες στο optimization, ωστε να μην έχουμε ενα thread που απλα λυνει ενα προβλημα αλλα που να δινει ποιο γενικες λυσεις. Θα ήθελα να δω κι εγω πως παιρνουμε απλα εναν αλγοριθμο που παιζει και αρχιζουμε και τον επιταχυνουμε. Αν εχεις χρονο θα ήταν ενδιαφερον. Thanks σε ολους που βοηθησαν (δεν θα ειχα καν λυση αν δεν ειχα ανοιξει το thread)...

[DarthMoul]

Για τον αλγόριθμο δεν μπορώ να εκφέρω γνώμη γιατί απλά δεν τον κατάλαβα. Για να πω την αμαρτία μου, ασχολήθηκα ελάχιστα μαζί του. Απλά διάβασα αυτό που έγραψες εσύ στην δικιά σου caf και το ξαναέγραψα έτσι ώστε να τρέχει πιο γρήγορα.

Γενικές αρχές και μεθόδους βελτιστοποίησης θα βρεις στα performance tips που είναι sticky στην αρχή αυτής της κατηγορίας. Ότι δεν είναι εκεί, όπως αυτή η περίπτωση, αποτελούν ιδιάζουσες περιπτώσεις. Ακόμα και αν περιγράψω πως το προσέγγυσα, για να με καταλάβει κάποιος θα πρέπει να γνωρίζει από αρχιτεκτονική μεταγλωττιστών και να έχει πολύ καλή γνώση από τις εσωτερικές λειτουργίες του επεξεργαστή.

Θα κοιτάξω και το καινούργιο που ανεβάζεις και αν έχω κάτι να πω θα επανέλθω.

[DarthMoul]

Δοκίμασα τον κώδικα σου με gcc και icc on opteron και compaq C on alpha. Στην αρχή χωρίς κανένα optimization και μετά άρχισα να ανεβάζω το optimization level του compiler. Σε όλες τις περιπτώσεις δεν είδα την παραμικρή βελτίωση. Άρα έγραψες τον καλύτερο δυνατό κώδικα με αποτέλεσμα οι optimizers των καλύτερων compiler να μην καταφέρουν να κάνουν την παραμικρή βελτίωση. :023:

Πάντως περιθώρια βελτίωσης υπάρχουν πάντα. Ξανάγραψα τον κώδικα σου και στον opteron πήρα ένα 10% ενώ στον Alpha 25%. Μέτρησε το σε Pentium να δούμε πόσο αποδίδει.

[Να Αγαπατε Αλληλους]

για το λοττο που λεγατε πριν ο πατερας μου κερδισε 6αρι και βγηκαν μαζι με αυτον 6τυχεροι αυτο τι πιθανότητα είναι ?κριμα και ημουν τοσο κοντα στο να γινω ο τυπος τα λεφτά του μπαμπά .

[circular]

για το λοττο που λεγατε πριν ο πατερας μου κερδισε 6αρι και βγηκαν μαζι με αυτον 6τυχεροι αυτο τι πιθανότητα είναι ?κριμα και ημουν τοσο κοντα στο να γινω ο τυπος τα λεφτά του μπαμπά .

??? Τι θέλει να πει ο ποιητής? Παρακαλώ να μείνουμε On-topic ;)

[yop]

Μετρησα κι εγω και ο κώδικας που στελνεις είναι 12% κατα μεσο ορο ποιο γρηγορος. :038: Πολυ ωραιο κ απλο αυτο που εκανες το ειχα σκισει λιγο εκει το θεμα. Thanx...
Αν δεις απο που ξεκινησαν οι χρονοι εκτελεσης κ που εφτασαν μαλλον μπορω να πω οτι εγινε καλη δουλεια :023:

[fabia]

καλησπερα παιδια... ειμαι νεο μελος αλλα σας παρακολουθω σαν απισκεπτης εδω και καμποσο καιρο....!!
λοιπον πριν αρχισετε να μου φωναζετε γιατι ανοιξα αυτο το πανπαλαιο τοπικ θα σας πω οτι εχω ενα παρομοιο προβλημα με αυτο του φιλου ΥΟΡ.
θα ηθελα να με βοηθησετε να βρω εναν τυπο για μια ακηση! προσοχη, δεν με ενδιαφερει το αποτελεσμα αλλα ο τυπος...!
λοιπον: εχουμε βαλει σε σειρα 10 δοχεια και θελουμε να παρουμε στα χερια μας 2. θελω να βρω ποσοι συνδυασμοι των 2 υπαρχουν!!!
υπαρχουν ομως 2 κολληματακια...
1) θα πρεπει να υπολογιζει το ιδιο δοχειο μια φορα στον καθε συνδυασμο
π.χ. δοχειο1--δοχειο2------>ναι
δοχειο1--δοχειο5------>ναι
δοχειο1--δοχειο1------>οχι
2) δεν μας ενδιαφερει η σειρα των δοχειων που θα διαλεξουμε, αρκει να διαλεξουμε τον δυνδυασμο αυτο...! τι εννοω...?
π.χ. απο την στιγμη που εχουμε διαλεξει σαν συνδυασμο

δοχειο1--δοχειο5 δεν θελουμε να υπολογιζει και δοχειο5--δοχειο1

αυτο που ζηταμε ειναι ο τυπος και οχι το αποτελεσμα.
οποιος μπορει να με βοηθησει θα ηταν καλο...!(αν καταλαβατε τι ζηταω γιατι και εγω κολλησα λιγο ετσι οπως τα λεω...!!:120: )
{ελπιζω να μην ειμαι offtopic:105: :105: :105: )
:006: :006:

[DarthMoul]

καλησπερα παιδια... ειμαι νεο μελος αλλα σας παρακολουθω σαν απισκεπτης εδω και καμποσο καιρο....!!
λοιπον πριν αρχισετε να μου φωναζετε γιατι ανοιξα αυτο το πανπαλαιο τοπικ θα σας πω οτι εχω ενα παρομοιο προβλημα με αυτο του φιλου ΥΟΡ.
θα ηθελα να με βοηθησετε να βρω εναν τυπο για μια ακηση! προσοχη, δεν με ενδιαφερει το αποτελεσμα αλλα ο τυπος...!
λοιπον: εχουμε βαλει σε σειρα 10 δοχεια και θελουμε να παρουμε στα χερια μας 2. θελω να βρω ποσοι συνδυασμοι των 2 υπαρχουν!!!
υπαρχουν ομως 2 κολληματακια...
1) θα πρεπει να υπολογιζει το ιδιο δοχειο μια φορα στον καθε συνδυασμο
π.χ. δοχειο1--δοχειο2------>ναι
δοχειο1--δοχειο5------>ναι
δοχειο1--δοχειο1------>οχι
2) δεν μας ενδιαφερει η σειρα των δοχειων που θα διαλεξουμε, αρκει να διαλεξουμε τον δυνδυασμο αυτο...! τι εννοω...?
π.χ. απο την στιγμη που εχουμε διαλεξει σαν συνδυασμο

δοχειο1--δοχειο5 δεν θελουμε να υπολογιζει και δοχειο5--δοχειο1

αυτο που ζηταμε ειναι ο τυπος και οχι το αποτελεσμα.
οποιος μπορει να με βοηθησει θα ηταν καλο...!(αν καταλαβατε τι ζηταω γιατι και εγω κολλησα λιγο ετσι οπως τα λεω...!!:120: )
{ελπιζω να μην ειμαι offtopic:105: :105: :105: )
:006: :006:
for (i=0; i<9;i++)
for (j=i+1; j<10; j++)
{
<εντολές>
}