Μαθηματικά, άθροιση και time complexity

[defacer]

Let's have some fun.

  

Προσπαθούσα να διαμορφώσω απάντηση στην παρακάτω ερώτηση:

 

"Για τους 3 παρακάτω τρόπους αθροίσματος των στοιχείων ενός πίνακα, σχολιάστε την απόδοσή τους αν ο αριθμός των στοιχείων αυξηθεί 1000 φορές. Τα στοιχεία στους πίνακες είναι όλα θετικά. Εξηγήστε την απάντησή σας και σχολιάστε την ερώτηση. Προτείνετε μια βέλτιστη λύση που διατηρεί την ίδια ακρίβεια του αθροίσματος." (έμφαση δική μου, είναι hint).

 

Περιττό να πω ότι με τέτοια εκφώνηση μπήκα χαλαρός, πολύ σύντομα όμως συνειδητοποίησα ότι τελικά δεν αστειεύονταν. Και η παρακάτω ερώτηση είναι μία από 4 που σα σκοπό έχουν να ρίξουν το πρώτο κόψιμο στους υποψηφίους. Συνειδητοποιώντας ότι αυτό είναι το 1/4 του πρώτου κόσκινου (για να φύγουν δηλαδή τα πολύ χοντρά) ζορίστηκα λίγο, αλλά το ζόρι είναι και καλό γιατί δε σ' αφήνει να επαναπαυθείς. Παρουσιάζω λοιπόν την ερώτηση με hints και απαντήσεις επειδή α) είναι καλό σχολείο και β) παρόλο που βρήκα τις απαντήσεις, υπάρχουν κάποια κενά στην κατανόησή μου τα οποία ίσως κάποιος μπορεί να συμπληρώσει.

 

Όποιος θέλει απαντάει σε ο,τι θέλει, spoilers please να μη το χαλάμε για τους άλλους, επιτρέπεται η συνεργασία, είμαι διαθέσιμος για διευκρινίσεις, καθοδήγηση και extra hints αν κάποιος θέλει.

 

Πάμε λοιπόν!

 

Ο κώδικας είναι C++ αλλά δεν έχει και πάρα πολλή σημασία.

 

double sum1(std::vector<double>& v)
{    
    if (v.empty()) {
        return 0.0;
    }
    for(size_t i = 0; i < v.size() - 1; ++i) {
        std::sort(v.begin()+i, v.end());
        v[i+1] += v[i];
    }
    return v.back();
}

double sum2(std::vector<double>& v)
{    
    if (v.empty()) {
        return 0.0;
    }
    for(size_t i = 0; i < v.size() - 1; ++i) {
        std::partial_sort(v.begin() + i, v.begin() + i + 2, v.end());
        v[i+1] += v[i];
    }
    return v.back();
}

double sum3(std::vector<double>& v)
{    
    std::multiset<double> set(v.begin(), v.end());
    while (set.size() > 1) {
        std::multiset<double>::const_iterator itA = set.begin();
        std::multiset<double>::const_iterator itB = ++set.begin();
        double c = *itA + *itB;
        set.erase(itA, ++itB);        
        set.insert(c);
    }
    return !set.empty() ? *set.begin() : 0.0;
}

Για όσους δεν ξέρουν C++, τα βασικά:

• Η std::sort είναι O(NlogN). Κάνει το προφανές.
• H std::partial_sort με σταθερό άνοιγμα 2 όπως εδώ είναι O(Nlog2). Αυτό που κάνει εδώ είναι ότι σου βρίσκει τα δύο μικρότερα στοιχεία και τα βάζει στη σωστή ταξινομημένη σειρά στις δύο πρώτες θέσεις. Τα υπόλοιπα στοιχεία παραμένουν σε τυχαία σειρά.
• H δημιουργία του std::multiset είναι O(NlogN). Το multiset είναι ταξινομημένο (άρα το .begin() του είναι πάντα το μικρότερο στοιχείο) tree το οποίο επιτρέπει διπλοεγγραφές.
• Όλα τα .begin(), .end(), λειτουργίες με τελεστές [], *, +, ++ είναι Ο(1)
• Η set.erase και set.insert είναι Ο(logN). H συγκεκριμένη erase σβήνει τα δύο στοιχεία του set που μόλις προσθέσαμε.

Θα πρέπει να υπολογίσουμε το complexity και των 3 περιπτώσεων, αλλά πρώτα...

 

Προειδοποίηση: Τα spoilers λένε πράγματα! Μη τα ανοίξετε αν θέλετε να προσπαθήσετε μόνοι σας!

 

Ερώτηση 1: Γιατί τόσος κόπος για ένα απλό άθροισμα; Δε θα μπορούσαμε απλά να κάνουμε ένα loop να τα προσθέσει;

 

Hint

 

 

Έχει κάτι να κάνει με "την ίδια ακρίβεια του αθροίσματος". Και αυτές οι 3 συναρτήσεις... υπάρχει κάτι που το κάνουν με τον ίδιο ακριβώς τρόπο... κάτι που υπό άλλες συνθήκες δε θα είχε σημασία αλλά εδώ υπάρχει κάτι πολύ συγκεκριμένο που το κάνει να έχει...

 

 

 

Απάντηση

 

 

Το σημαντικό είναι ότι προσθέτουμε doubles, μια πράξη η οποία είναι πεπερασμένης ακρίβειας και άρα μπορεί να οδηγήσει σε απώλεια ακρίβειας. Τελείως χοντρικά ένας double μπορεί να κρατήσει 15 σημαντικά ψηφία πληροφορίας, επομένως (για να δώσω ένα χονδροειδές παράδειγμα) προσθέτοντας 1 στο 1e16 το αποτέλεσμα είναι 1e16. Όσους άσους και να προσθέσουμε το αποτέλεσμα δε θα αλλάξει. Αν όμως προσθέταμε πρώτα 100 άσους θα παίρναμε 100, και προσθέτοντας 1e16 σ' αυτό θα είχαμε το σωστό αποτέλεσμα.

 

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

 

 

 

Ερώτηση 2: τι complexity έχει η sum3;

 

Μερική απάντηση

 

• Η δημιουργία του multiset είναι NlogN
• To loop γίνεται Ν - 1 φορές, για ευκολία λέμε Ν
• Οι μόνες λειτουργίες μέσα στο loop που δεν είναι O(1) είναι τα insert και erase
• Τα οποία είναι logk όπου k το τρέχον μέγεθος του συνόλου
• Άρα όλο το loop είναι το άθροισμα Σ από k=1 ως Ν του 2logk

 

 

Απάντηση

 

 

Το άθροισμα Σ[k=1...Ν] 2logk είναι προφανώς ίσο με 2 * Σ[k=1...Ν] logk. Αλλά ξέρουμε πως logx + logy = logxy, οπότε είναι επίσης ίσο με 2 * log(Ν!). To log(N!) μπορεί να προσεγγιστεί με τη μέθοδο του Stirling (και άλλες καλύτερες, αλλά αυτή είναι good enough) ως NlnN - N, άρα είμαστε Ο(2 * (NlnN - N)) και κρατώντας μόνο τον ισχυρότερο παράγοντα, O(NlnN).

 

 

 

Ερώτηση 3: τι complexity έχει η sum2; (για μένα ήταν η ευκολότερη από τις 3)

 

Μερική απάντηση

 

• To loop γίνεται Ν - 1 φορές, για ευκολία λέμε Ν
• H partial_sort είναι Νlog2 όπου Ν ο αριθμός των στοιχείων που θα εξετάσει
• Άρα όλο το loop είναι το άθροισμα Σ από k=1 ως Ν του klog2

 

 

Απάντηση

 

 

Το άθροισμα Σ[k=1...Ν] klog2 είναι προφανώς ίσο με log2 * Σ[k=1...Ν] k. Το τελευταίο είναι απλή αριθμητική πρόοδος με άθροισμα Ν * (Ν + 1) / 2 οπότε είμαστε Ο(log2 * Ν * (Ν + 1) / 2) = O(log2 / 2 * (N^2 + N)) και κρατώντας μόνο τον ισχυρότερο παράγοντα Ο(N^2). Δηλαδή πολύ χειρότερα από την προηγούμενη περίπτωση.

 

 

 

Ερώτηση 4: τι complexity έχει η sum1; (για μένα ήταν η δυσκολότερη από τις 3 και συγκεκριμένα η μοναδική για την οποία δεν έχω δει καν μαθηματική απόδειξη, πόσο μάλλον που να κατανοώ κιόλας)

 

Μερική απάντηση

 

• To loop γίνεται Ν - 1 φορές, για ευκολία λέμε Ν
• H sort είναι ΝlogΝ όπου Ν ο αριθμός των στοιχείων που θα εξετάσει
• Άρα όλο το loop είναι το άθροισμα Σ από k=1 ως Ν του klogk

 

 

Απάντηση

 

Αυτή ήταν εντελώς πέρα από τις δυνατότητές μου στα μαθηματικά και με δυσκολία υπέκυψε στο google-fu. Δεν έχω την παραμικρή ιδέα πώς μπορεί να υπολογιστεί το άθροισμα που δίνεται παραπάνω στο spoiler, αν και βέβαια μπορούσα να κάνω μια πρόβλεψη βάσει της μεγάλης ομοιότητας και μικρής διαφοράς με τη sum2 (και η πρόβλεψη ήταν σωστή).

 

Τελικά βρήκα την απάντηση με googling

 

 

http://en.wikipedia.org/wiki/Summation#Growth_rates

 

όπου δίνεται ως N^2 * logN, δηλαδή για τις ανάγκες της συζήτησης N^2. Αυτό είναι το ίδιο αποτέλεσμα με τη sum1, αν και προφανώς στην πράξη για την ίδια είσοδο η sum1 θα είναι πιο αργή από τη sum2 αφού κάνει περισσότερη δουλειά (η οποία επιπλέον δε χρειάζεται).

 

 

 

Αυτό το αποτέλεσμα δεν είχα ιδέα πώς προκύπτει, χίλια ευχαριστώ tr3quart1sta!

 

Ερώτηση 5: τελικά η βέλτιστη λύση ποιά είναι;

 

Απάντηση

 

Εν συντομία

 

Όπως είπε και ο Aztec, Kahan summation.

 

 

 

Η "the best I could do" απάντηση που έστειλα (στα αγγλικά, σόρι)

 

This question is somewhat ambiguous in its current form. In particular, information that is not provided but which would be helpful in determining the most appropriate answer includes:

 

a. Optimality criteria

Does "optimal" refer to minimization of the running time, the error inherent in fixed-precision floating point summation, or a combination of both? In the latter case, what are the relevant factors for determining the appropriate tradeoff?

 

b. Precise meaning of "same accuracy"

Summation accuracy (i.e. the relative magnitude of the error) cannot remain exactly the same if a different summation algorithm is used because in the general case each algorithm performs a different series of calculations for the same input, and that difference may result in a divergence of the results.

 

In this context we can probably infer that "the same" means "the same or better", but that still leaves open the question: since accuracy is also dependent on the actual input, should "better" be taken in the strict mathematical sense of "there is no possible input for which the algorithm in question produces worse accuracy" or in a more relaxed sense?

 

Since in reality the algorithm is expected to complete in a finite amount of time, the set of possible inputs to it is also finite even if of astronomical size. Given this, should an algorithm that produces more accurate results for a majority of the possible inputs be considered more accurate overall even if it produces less accurate results for (a subset of) the remaining inputs? If so, what are the criteria that decide?

 

The above considarations prevent me from giving a single definitive answer to the stated question. However, we can incorporate them into a longer but still practical answer:

• The well-known Kahan summation algorithm is superior to the "insertion adding" method implemented in Q2 in both accuracy and performance, so in practice it can be unconditionally recommended as an improvement.
• More accurate results than standard Kahan can be obtained at a significant (but linear) runtime cost by enhancing the intermediate error compensation to take into account the three most recently seen input numbers instead of the last two. Alternatively, a simple descending sort of the input before Kahan summation will also produce better results at the cost of asymptotic complexity being degraded from linear to linearithmic -- this is still better than "insertion adding", especially the quadratic naive versions.
• If the platform supports quadruple precision floating point math via the long double type, performing the calculations using that type will be more accurate than Kahan summation and probably faster as well.
• If more information about the distribution of the input is available, recursive pairwise addition may be able to produce results as good as Kahan at a significant fraction of Kahan's running time. Moreover, pairwise addition is trivially parallelizable and therefore can benefit significantly from the parallel execution capabilities of the system (if applicable).

 

Επεξ/σία 22 Ιουνίου 2014 από defacer

[gon1332]

Με το μυαλό που έχω τώρα θα μπορούσα να πω για την πρώτη ερώτηση.

 

Ερώτηση 1: Γιατί τόσος κόπος για ένα απλό άθροισμα; Δε θα μπορούσαμε απλά να κάνουμε ένα loop να τα προσθέσει;

 

Προφανώς τη ξέρεις την απάντηση αλλά ας τεστάρω κι εμένα:

 

 

Μιλάμε για πρόσθεση πραγματικών αριθμών. Όταν αναφερόμαστε σε μία τέτοια πράξη είναι πάρα πολύ πιθανό να μας ενδιαφέρει η ακρίβεια του τελικού αποτελέσματος. Ξέρουμε πως όσο πιο κοντά στο 0 είμαστε, τόσο πιο μεγάλη είναι η ακρίβεια. Όσο πιο μακρία φεύγουμε, η ακρίβεια πέφτει όλο και πιο πολύ. Αυτό σημαίνει πως αν αθροίσουμε δύο μεγάλους αριθμούς, τότε δε θα χάσουμε και τίποτα σε ακρίβεια. Αν όμως αθροίσουμε έναν μεγάλο με έναν μικρό, τότε η ακρίβεια του μικρού θα "χαθεί" στην ανακρίβεια του μεγάλου. Ένα παράδειγμα είναι η πρόσθεση των πραγματικών: 1.34536, 2.131455 και 4.5e20. Ένα γνωστό τέχνασμα για να χάσουμε όσο το δυνατόν λιγότερη ακρίβεια μπορούμε, είναι να ταξινομήσουμε και να προσθέσουμε τους πραγματικούς κατά αύξουσα σειρά. Με αυτόν τον τρόπο, η ακρίβεια θα "χάνεται" σταδιακά με τις πράξεις με πολύ μεγαλύτερους αριθμούς να οδηγούν σε μικρότερη χασούρα ακρίβειας. Στην ουσία αντί να "εκτελέσουμε" την ακρίβεια εν ψυχρώ, τη μειώνουμε σιγά-σιγά ώστε να "φάει" παράλληλα λίγη ανακρίβεια από τους μεγάλους.

 

 

 

Θα κοιτάξω και αύριο τα υπόλοιπα..

[defacer]

Με το μυαλό που έχω τώρα θα μπορούσα να πω για την πρώτη ερώτηση.

 

Βάλε spoilerrrrrrrrrrrrrrrrrrrrr! 

 

Και καληνύχτες. Ολόσωστος είσαι. 

[Kercyn]

 

 

Εγώ είχα βρει μια ωραία ιδέα να προσθέτεις τους αριθμούς ανά δύο και να μικραίνεις το vector στο μισό κάθε φορά μέχρι να μείνει ένα στοιχείο, αλλά μετά είδα το 3 και πάει η ιδέα μου
No fun allowed.

 

Τι άλλο θα είχε μια ολοκληρωμένη απάντηση πέρα απ' αυτά που έχουν οι μερικές απαντήσεις;

 

 

[tr3quart1sta]

Αυτή ήταν εντελώς πέρα από τις δυνατότητές μου στα μαθηματικά και με δυσκολία υπέκυψε στο google-fu. Δεν έχω την παραμικρή ιδέα πώς μπορεί να υπολογιστεί το άθροισμα που δίνεται παραπάνω στο spoiler, αν και βέβαια μπορούσα να κάνω μια πρόβλεψη βάσει της μεγάλης ομοιότητας και μικρής διαφοράς με τη sum2 (και η πρόβλεψη ήταν σωστή).

 

Τελικά βρήκα την απάντηση με googling

 

 

 

http://en.wikipedia.org/wiki/Summation#Growth_rates

 

όπου δίνεται ως N^2 * logN, δηλαδή για τις ανάγκες της συζήτησης N^2.

 

 

 

Ξέρει κανείς να καταλήξει στο αποτέλεσμα αυτό μαθηματικά; Θα ήμουν υπόχρεος!

 

 

 

Αυτο που μαλλον ζητουσε η ασκηση: upper bound και καθαρισες

 

Αυτο που ψαχνεις εσυ(?): Euler-Maclaurin Sum Formula (1) (2)

 

 

[defacer]

Τι άλλο θα είχε μια ολοκληρωμένη απάντηση πέρα απ' αυτά που έχουν οι μερικές απαντήσεις;

Το τελικό αποτέλεσμα.

  

Euler-Maclaurin Sum Formula

Ναι! Αυτό ακριβώς ήθελα!

 

Ξενέρωμα να μη ξέρεις αρκετά μαθηματικά και να χτυπάς τοίχο σε τέτοιες περιπτώσεις.

 

Κρατάω το βασικό συμπέρασμα ότι την επόμενη φορά με τη μία mathexchange...

Προφανώς τη ξέρεις την απάντηση αλλά ας τεστάρω κι εμένα:

 

 

 

Ξαναδιάβασα την απάντησή σου και επειδή δεν το αναφέρεις ρητά είπα να το επισημάνω.

 

Μια σημαντική πληροφορία είναι ότι οι αριθμοί είναι όλοι θετικοί (κλασική περίπτωση που αν δε χρησιμοποιήσεις όλα τα δεδομένα της εκφώνησης κάτι έκανες "λάθος"). Αυτό που θέλουμε είναι να προσθέτουμε πρώτα τις μικρότερες απόλυτες τιμές μεταξύ τους, οπότε αν είχε μέσα και αρνητικούς και ξεκινούσες να προσθέσεις στα τυφλά από τον μικρότερο πάλι θα είχες το ίδιο πρόβλημα.

 

 

[gon1332]

 

 

Αυτο που μαλλον ζητουσε η ασκηση: upper bound και καθαρισες

 

Αυτο που ψαχνεις εσυ(?): Euler-Maclaurin Sum Formula (1) (2)

 

 

Μαθηματικέ Λογισμέ Ι !!!!

 

Το τελικό αποτέλεσμα.

  

Ναι! Αυτό ακριβώς ήθελα!

 

Ξενέρωμα να μη ξέρεις αρκετά μαθηματικά και να χτυπάς τοίχο σε τέτοιες περιπτώσεις.

 

Κρατάω το βασικό συμπέρασμα ότι την επόμενη φορά με τη μία mathexchange...

 

 

 

Ξαναδιάβασα την απάντησή σου και επειδή δεν το αναφέρεις ρητά είπα να το επισημάνω.

 

Μια σημαντική πληροφορία είναι ότι οι αριθμοί είναι όλοι θετικοί (κλασική περίπτωση που αν δε χρησιμοποιήσεις όλα τα δεδομένα της εκφώνησης κάτι έκανες "λάθος"). Αυτό που θέλουμε είναι να προσθέτουμε πρώτα τις μικρότερες απόλυτες τιμές μεταξύ τους, οπότε αν είχε μέσα και αρνητικούς και ξεκινούσες να προσθέσεις στα τυφλά από τον μικρότερο πάλι θα είχες το ίδιο πρόβλημα.

 

 

Μπράβο μου! Δεν το ανέφερα πουθενά. Και έλεγα από μέσα μου χθες: "πρέπει να χώσω και το κατ'απόλυτη τιμή". Τελικά μάλλον βασίστηκα στην κατανόηση μέσω context (κοντά στο 0 - μακριά από το 0). Καλή είναι μία διευκρίνιση.

Τι άλλο θα είχε μια ολοκληρωμένη απάντηση πέρα απ' αυτά που έχουν οι μερικές απαντήσεις;

Asymptotic notation.

[παπι]

 

 

Μα δεν μπρουν να βαλουν κατι που κανει κατι; Τι ειναι αυτες οι ακαταλαβιστικες πιπες με τα Ο σε κατι που δεν κανει τιποτα;

 

Νιωθω στοκος.

 

 

[Aztec]

Ερώτηση 5: τελικά η βέλτιστη λύση ποιά είναι;

 

Answer : none of the three . No reason to bother with any of the previous questions

[defacer]

Updated το αρχικό post με περισσότερες απαντήσεις. Aztec τι θέλει να πει ο ποιητής; Αγνό καλόκαρδο trolling ή κάτι δεν πιάνω?

[Anubis13]

Ενδιαφερουσα ερωτηση, εχεις και τις αλλες?

Ομολογω οτι το complexity του sum1 με μπερδεψε πιο πολυ απο το 3(το οποιο δεν το απεδειξα μαθηματικα)

[Aztec]

 Aztec τι θέλει να πει ο ποιητής; Αγνό καλόκαρδο trolling ή κάτι δεν πιάνω?

 

Εννοείται καλόκαρδο trolling . Εξάλλου είδα πράγματα που έχω να ακουμπήσω πάρα πολλά χρόνια. Θα απαντούσα με τον εξής τρόπο αν οι 5 ερωτήσεις ήταν κάποιο τεστ πρόσληψης και φυσικά η θέση δεν με έκαιγε. Έξω απο τον χορό δηλαδή

 

Η βέλτιστη λύση λοιπόν δεν είναι καμία απο τις τρείς. Και αυτό γιατι και στις τρεις περιπτώσεις για τα n στοιχεία ποτέ δεν εκτελούνται μόνο O(1) operations. Και στις τρεις περιτπώσεις χρησιμοποιείται καποιο sorting όλικο η μερικό . Το καλυτερο sorting complexity που υπάρχει αυτή τη στιγμή είναι Ο(nlogn) . Στην περίπτωση που είχαμε μόνο Ο(1) operations μέσα ή έξω απο την λούπα τοτέ θα είχαμε ουσιαστικά O(n). Η βέλτιστη λύση λοιπόν είναι ...

αυτή του kahan summation algorithm που παίζει σε Ο(n) .

 

Επεξ/σία 22 Ιουνίου 2014 από Aztec

[defacer]

Η βέλτιστη λύση λοιπόν είναι ... .

 

Μη σποιλεριάζεις... 

[defacer]

Η βέλτιστη λύση λοιπόν είναι ...

Έκανα και το τελευταίο μάλλον update του αρχικού post, όπου δίνω και τη δική μου τελική απάντηση.

 

Είναι άραγε σεντόνι? Στοιχηματίστε τώρα! Αποδόσεις: 1.01 και 42 (ναι/όχι).