pdp forum

Γεια σας! Φέτος είναι η πρώτη φορά που συμμετείχα στον ΠΔΠ και, κοιτώντας ορισμένες προτεινόμενες λύσεις για παλιά θέματα, παρατήρησα πως στην αρχή φτιάχνουν αρκετά μεγάλα array π.χ ενώ εγώ προσωπικά απέφυγα τη χρήση array. Αναρωτιέμαι αν η δέσμευση τόσο μεγάλου χώρου είναι αποδοτική, καθώς τις περισσότερες φορές δεν θα χρειαστεί τόσος χώρος. Γιατί δηλαδή, ακόμη και αν ξέρουν το μέγεθος size, προτιμούν αντί Επίσης, τα vector πόσο γρήγορα είναι σε σχέση με τα array; Ευχάριστω.

Στις ενδεικτικές λύσεις ο κώδικας είναι παράδειγμα, δεν πιστεύω πως κερδίζεις χρόνο με αυτόν τον τρόπο, μάλλον χάνεις! Όσον Αφορά τα vector και τα array, εγώ ξέρω (από την java) ότι τα array είναι πιο γρήγορα αλλά αναφερόμενος σε αυτά τα δύο άρθρα (1, 2) μου φαίνεται πως ίσως κάνω λάθος, τουλάχιστον για την C++.

Ο λόγος που στους διαγωνισμούς δηλώνουμε τεράστιους πίνακες εξαρχής είναι αρκετά απλός. Το χρονικό όριο είναι ίδιο και για τα μικρά και για τα μεγάλα testcases. Επομένως δε μας πειράζει να μην είναι τέλειος ο κώδικάς μας για τα μικρά testcases, γιατί έτσι κι αλλιώς αυτά θα τα περάσουμε. Ενώ για τα μεγάλα ο κώδικας αυτός είναι οκ.

Σε κάθε περίπτωση μη σκέφτεσαι καθόλου τέτοιες λεπτομέρειες, όπως και το αν είναι καλύτερο το array ή το vector. Καλύτερο είναι το array (το vector υλοποιείται χρησιμοποιώντας arrays). Βέβαια το vector έχει μερικούς αλγορίθμους υλοποιημένους με πολύ έξυπνο τρόπο. Μπορείς κι εσύ να το πετύχεις με arrays, αλλά αν δεν προσέξεις δε θα τα καταφέρεις τόσο καλά. Οπότε για τέτοιες περιπτώσεις, βολεύουν περισσότερο τα vectors. Αλλά η διαφορά είναι τόσο μικρή, που δεν αξίζει να το σκέφτεσαι, χρησιμοποίησε όποιο αγαπάς.

Και για να γίνω πιο συγκεκριμένος για το τι είναι σημαντικό και τι όχι, δες αυτό το άρθρο: https://discrete.gr/complexity/?el
Στην ουσία ό,τι ρώτησες δεν αλλάζει την πολυπλοκότητα του αλγορίθμου, άρα δε μας πειράζει.

Σαν τελική σημείωση, τα χρονικά όρια που μπαίνουν στους διαγωνισμούς είναι πάντα τέτοια ώστε αν έχεις τη σωστή πολυπλοκότητα να περνάς, όοοοο,τι και να έχεις κάνει (δήλωση μεγάλου array, χρήση vector αντί για array, κλπ κλπ). Αυτά τα πολύ πολύ να στοιχήσουν πχ 0.01 δευτερόλεπτο.

Ελπίζω να μη σε μπέρδεψα περισσότερο

Ευχαριστώ πολύ για τις διαφωτιστικές απαντήσεις!

@DragonEmperor, ο λόγος που χρησιμοποιούσαμε static defined sizes είναι πως είναι πιο γρήγορη η δέσμευση μνήμης με την εκκίνηση ενός προγράμματος (στο heap) απ' ό,τι αν δεσμευτεί αργότερα, π.χ. με malloc().

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

Ωστόσο είναι κάτι που πρέπει να 'χουμε κατά νου όταν πάμε να "ξεζουμίσουμε" το παραμικρό ίχνος performance. Κάτι που εν τέλει είναι σημαντικό στο διαγωνισμό αφού απ' όσο θυμάμαι, μετά το score έχει σημασία η ταχύτητα.