Ταχύτητα

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
Απάντηση
Dragon Emperor
Δημοσιεύσεις: 7
Εγγραφή: Παρ Μαρ 13, 2020 3:11 pm

Ταχύτητα

Δημοσίευση από Dragon Emperor »

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

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

int A[1000000];
ενώ εγώ προσωπικά απέφυγα τη χρήση array. Αναρωτιέμαι αν η δέσμευση τόσο μεγάλου χώρου είναι αποδοτική, καθώς τις περισσότερες φορές δεν θα χρειαστεί τόσος χώρος. Γιατί δηλαδή, ακόμη και αν ξέρουν το μέγεθος size, προτιμούν

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

int x[max_size];
αντί

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

int * x = new int[size];
Επίσης, τα vector πόσο γρήγορα είναι σε σχέση με τα array; Ευχάριστω.

kostas1507
Δημοσιεύσεις: 12
Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm

Re: Ταχύτητα

Δημοσίευση από kostas1507 »

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

Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 360
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Ταχύτητα

Δημοσίευση από Κηπουρίδης »

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

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

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

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

Ελπίζω να μη σε μπέρδεψα περισσότερο :)
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/

Dragon Emperor
Δημοσιεύσεις: 7
Εγγραφή: Παρ Μαρ 13, 2020 3:11 pm

Re: Ταχύτητα

Δημοσίευση από Dragon Emperor »

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

stathis
Site Admin
Δημοσιεύσεις: 379
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Ταχύτητα

Δημοσίευση από stathis »

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

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

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

Απάντηση