φιζζ - μπαζζ (Google Interview test)

[ST48410]

Μόνο 25.749 αριθμοί από τους 10.000.000 ανήκουν στα ζητούμενα αποτελέσματα.
Δεν έχω κέρδος όταν τους βρίσκω / παράγω κατευθείαν; αντί να διαιρώ 10.000.000 αριθμούς με δυο ή τρεις ;

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

Πως προκύπτει ότι υπάρχουν 25.749 αριθμοί; Εννοώ αν δεν έχεις κάτσει να τους βρεις πρώτα;
Είναι ο πολλαπλασιασμός και η διαίρεση το ίδιο computational intensive;*

* δεν ξέρω αν το λέω σωστά αλλά καταλαβαίνεις τι εννοώ

[shrike]

Σπύρο, μου φαίνεται λίγο δύσκολο να είναι πιο γρήγορο αυτό που προτείνεις (μια που το θέμα είναι η ταχύτητα σύμφωνα με τον Nameless Ghoul). Κυρίως λόγω του sorting που θες να κάνεις συνδυάζοντας 4 πίνακες, ο ένας εκ των οποίων έχει 10.000.000 στοιχεία.

Γιατί βρε; Ποιος πίνακας έχει 10 μύρια; Οι 3 πίνακές μου έχουν 25.749 στοιχεία συνολικά.

Ο τέταρτος, αυτός που έχει όλους τους αριθμούς. Ακόμα κι αν δεν είναι πίνακας, πρέπει να πάρεις σειριακά τα 10 μύρια αριθμούς και να κάνεις συγκρίσεις με τρεις διαφορετικούς πίνακες των 25 χιλιάδων στοιχείων για να βγάλεις τα αποτελέσματα. Με λίγα λόγια... κάηκε το γάλα, εδώ παίζουμε με τα ms. Για να μην πούμε δηλαδή πόσο χρόνο θα χρειαστείς για να σορτάρεις 3 πίνακες των 25-26 χιλιάδων στοιχείων, είτε με ένα απλό bubble ή με pivots κλπ (ξαναλέω, με τα ms παίζουμε, εμένα το πρώτο μού πήρε ~3000, το δεύτερο ~2900 και το τελευταίο κάπου 400-500 για όλη τη διαδικασία, εννοείται με την πανάρχαια VB6 και στο δικό μου μπουζούκι, όχι σε καμιά σούπερ γλώσσα και σε κανένα γρήγορο μηχανάκι).

[ST48410]

Μήπως υπάρχει κάποιος λόγος για το ότι οι 2 διαιρέτες είναι πρώτοι αριθμοί;

[shrike]

Μήπως υπάρχει κάποιος λόγος για το ότι οι 2 διαιρέτες είναι πρώτοι αριθμοί;

ST, δες τον κώδικα που έγραψα πιο πάνω (viewtopic.php?p=167503#p167503).

Έχω την εντύπωση ότι αυτή (πάνω-κάτω) είναι η λύση, σου είπα ότι από το άλλο που έγραψα και μου είπε ο Ghoul ότι είμαι πολύ κοντά, είναι κάπου 5-6 φορές πιο γρήγορο. Ε, πόσο πιο γρήγορο πχια...

[Spiros252]

Εμένα σε 144 ms το βγάζει ο server.

[shrike]

Εμένα σε 144 ms το βγάζει ο server.

Μαζί με την εκτύπωση, ή απλά αποδίδεις την τιμή σε μεταβλητή;
Μπορείς να βάλεις εδώ τον κώδικα;

Παρεμπιπτόντως, βρήκα τρόπο να παρακάμψω το πρόβλημα της γλώσσας που έλεγα για τα strings κλπ...

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

Dim t(624073), v, aa$
For r = 1 To 624072
    If r Mod 947 = 0 Then
        t(r) = " μπαζζ"
    ElseIf r Mod 659 = 0 Then
        t(r) = " φιζζ"
    End If
Next
t(624073) = " φιζζμπαζ": i = 0
For r = 1 To 10 ^ 7
    i = i + 1: If i > 624073 Then i = 1
    If t(i) <> "" Then
        v = r & t(i)
    Else: v = r
    End If
    'Print v
Next

Χωρίς την μετατροπή τού αποτελέσματος σε string (μόνο οι υπολογισμοί δηλαδή + την απόδοση του numeric τμήματος) μού βγαίνει από 310 έως 350ms. Με το νέο condition που πρόσθεσα (If t(i) <> "" Then v = r & t(i) Else v = r) ανεβαίνει κάπου στα 600-650, αλλά πάλι είναι σημαντικά πιο γρήγορο απ' το παλιό μου που ήταν κάπου στα 3000.

[Spiros252]

Βελτιώνω επειδή με το προηγούμενο έκανα αχρείαστες επιπλέον πράξεις:

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

<?php

$lim = pow(10,7); 

for ($n = 1; $r1 <= ($lim - 659); $n++) { 
	$r1 = $n * 659; 
  	$array['1'."$n"] = $r1; 
}

for ($n = 1; $r2 <= ($lim - 947); $n++) { 
	$r2 = $n * 947; 
  	$array['2'."$n"] = $r2;
}

for ($n = 1; $r3 <= ($lim - (659 * 947)); $n++) { 
	$r3 = $n * (659 * 947); 
  	$array['3'."$n"] = $r3;
}


asort($array);
  
foreach ($array as $r => $v) { 	$count++;
	
	if (substr($r,0,1) == 1) { print "| $v | fizz <br />"; }
	if (substr($r,0,1) == 2) { print "| $v | buzz <br />"; }
  	if (substr($r,0,1) == 3) { print "| $v | fizz-buzz <br />"; }

}

print "<br /><br /><br />Σύνολο αποτελεσμάτων: $count <br /><br />";

?>

[ST48410]

τα ms που συγκρίνετε στις λύσεις σας δεν έχουν σχέση με το πόσο γρήγορη είναι η CPU του κάθε μηχανήματος; Είναι συγκρίσιμα του Σπύρου με του shrike;

[shrike]

τα ms που συγκρίνετε στις λύσεις σας δεν έχουν σχέση με το πόσο γρήγορη είναι η CPU του κάθε μηχανήματος; Είναι συγκρίσιμα του Σπύρου με του shrike;

Σαφώς! Το έγραψα και πιο πάνω άλλωστε που λέω για το "μπουζούκι" μου (που ασφαλώς και δεν έχει καμιά σχέση με τον server που το τρέχει ο Σπύρος).

Σπύρο, νομίζω ξέχασες να τυπώσεις τους υπόλοιπους αριθμούς, όσους δεν έχουν fizz, buzz κλπ δίπλα. Αν δεν κάνω λάθος, δηλαδή.

[ST48410]

τα ms που συγκρίνετε στις λύσεις σας δεν έχουν σχέση με το πόσο γρήγορη είναι η CPU του κάθε μηχανήματος; Είναι συγκρίσιμα του Σπύρου με του shrike;

Σαφώς! Το έγραψα και πιο πάνω άλλωστε που λέω για το "μπουζούκι" μου (που ασφαλώς και δεν έχει καμιά σχέση με τον server που το τρέχει ο Σπύρος).

ε τότε ας τρέξει ο ένας σας την λύση και του άλλου να δείτε χρόνους

[shrike]

τα ms που συγκρίνετε στις λύσεις σας δεν έχουν σχέση με το πόσο γρήγορη είναι η CPU του κάθε μηχανήματος; Είναι συγκρίσιμα του Σπύρου με του shrike;

Σαφώς! Το έγραψα και πιο πάνω άλλωστε που λέω για το "μπουζούκι" μου (που ασφαλώς και δεν έχει καμιά σχέση με τον server που το τρέχει ο Σπύρος).

ε τότε ας τρέξει ο ένας σας την λύση και του άλλου να δείτε χρόνους

Δεν είναι τόσο απλό, τουλάχιστον για μένα. Δεν έχω τρόπο να τρέξω php ή C εδώ που είμαι, κάποια functions που έχει βάλει ο Σπύρος δεν υποστηρίζονται στη γλώσσα που μπορώ να χειριστώ εδώ, οπότε αν το πάω μέσω Τρικάλων για να τα προσομοιώσω τα αποτελέσματα θα είναι τραγικά...

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

[ST48410]

Σαφώς! Το έγραψα και πιο πάνω άλλωστε που λέω για το "μπουζούκι" μου (που ασφαλώς και δεν έχει καμιά σχέση με τον server που το τρέχει ο Σπύρος).

ε τότε ας τρέξει ο ένας σας την λύση και του άλλου να δείτε χρόνους

Δεν είναι τόσο απλό, τουλάχιστον για μένα. Δεν έχω τρόπο να τρέξω php ή C εδώ που είμαι, κάποια functions που έχει βάλει ο Σπύρος δεν υποστηρίζονται στη γλώσσα που μπορώ να χειριστώ εδώ, οπότε αν το πάω μέσω Τρικάλων για να τα προσομοιώσω τα αποτελέσματα θα είναι τραγικά...

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

Ο Σπύρος μπορεί να τρέξει το δικό σου να δούμε;

Sorry αν ρωτάω χαζά πράγματα

[Spiros252]

Μπορώ αλλά πρέπει κι εγώ να το μετατρέψω στη λογική του shrike και βαριέμαι ..

Δεν μπορείς να συγκρίνεις τα μηχανήματα.
Την σωστή διαδικασία ψάχνουμε άλλωστε.

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

[Spiros252]

Σπύρο, νομίζω ξέχασες να τυπώσεις τους υπόλοιπους αριθμούς, όσους δεν έχουν fizz, buzz κλπ δίπλα. Αν δεν κάνω λάθος, δηλαδή.

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

[Χαοτικός]

Πληροφορικάριοι είσαστε;