Σελίδα 3 από 5

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 11:14
από ST48410
Spiros252 έγραψε:
21 Ιούλ 2018, 11:06

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

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

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

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 11:19
από shrike
Spiros252 έγραψε:
21 Ιούλ 2018, 11:11
shrike έγραψε:
21 Ιούλ 2018, 10:21
Σπύρο, μου φαίνεται λίγο δύσκολο να είναι πιο γρήγορο αυτό που προτείνεις (μια που το θέμα είναι η ταχύτητα σύμφωνα με τον 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 και στο δικό μου μπουζούκι, όχι σε καμιά σούπερ γλώσσα και σε κανένα γρήγορο μηχανάκι).

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 11:24
από ST48410
Μήπως υπάρχει κάποιος λόγος για το ότι οι 2 διαιρέτες είναι πρώτοι αριθμοί;

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 11:26
από shrike
ST48410 έγραψε:
21 Ιούλ 2018, 11:24
Μήπως υπάρχει κάποιος λόγος για το ότι οι 2 διαιρέτες είναι πρώτοι αριθμοί;
ST, δες τον κώδικα που έγραψα πιο πάνω (viewtopic.php?p=167503#p167503).

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

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 11:30
από Spiros252
Εμένα σε 144 ms το βγάζει ο server.

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 11:40
από shrike
Spiros252 έγραψε:
21 Ιούλ 2018, 11:30
Εμένα σε 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.

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 11:47
από 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 />";

?>

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 11:54
από ST48410
τα ms που συγκρίνετε στις λύσεις σας δεν έχουν σχέση με το πόσο γρήγορη είναι η CPU του κάθε μηχανήματος; Είναι συγκρίσιμα του Σπύρου με του shrike;

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 12:01
από shrike
ST48410 έγραψε:
21 Ιούλ 2018, 11:54
τα ms που συγκρίνετε στις λύσεις σας δεν έχουν σχέση με το πόσο γρήγορη είναι η CPU του κάθε μηχανήματος; Είναι συγκρίσιμα του Σπύρου με του shrike;
Σαφώς! Το έγραψα και πιο πάνω άλλωστε που λέω για το "μπουζούκι" μου (που ασφαλώς και δεν έχει καμιά σχέση με τον server που το τρέχει ο Σπύρος).

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

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 12:04
από ST48410
shrike έγραψε:
21 Ιούλ 2018, 12:01
ST48410 έγραψε:
21 Ιούλ 2018, 11:54
τα ms που συγκρίνετε στις λύσεις σας δεν έχουν σχέση με το πόσο γρήγορη είναι η CPU του κάθε μηχανήματος; Είναι συγκρίσιμα του Σπύρου με του shrike;
Σαφώς! Το έγραψα και πιο πάνω άλλωστε που λέω για το "μπουζούκι" μου (που ασφαλώς και δεν έχει καμιά σχέση με τον server που το τρέχει ο Σπύρος).
ε τότε ας τρέξει ο ένας σας την λύση και του άλλου να δείτε χρόνους

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 12:12
από shrike
ST48410 έγραψε:
21 Ιούλ 2018, 12:04
shrike έγραψε:
21 Ιούλ 2018, 12:01
ST48410 έγραψε:
21 Ιούλ 2018, 11:54
τα ms που συγκρίνετε στις λύσεις σας δεν έχουν σχέση με το πόσο γρήγορη είναι η CPU του κάθε μηχανήματος; Είναι συγκρίσιμα του Σπύρου με του shrike;
Σαφώς! Το έγραψα και πιο πάνω άλλωστε που λέω για το "μπουζούκι" μου (που ασφαλώς και δεν έχει καμιά σχέση με τον server που το τρέχει ο Σπύρος).
ε τότε ας τρέξει ο ένας σας την λύση και του άλλου να δείτε χρόνους
Δεν είναι τόσο απλό, τουλάχιστον για μένα. Δεν έχω τρόπο να τρέξω php ή C εδώ που είμαι, κάποια functions που έχει βάλει ο Σπύρος δεν υποστηρίζονται στη γλώσσα που μπορώ να χειριστώ εδώ, οπότε αν το πάω μέσω Τρικάλων για να τα προσομοιώσω τα αποτελέσματα θα είναι τραγικά... :wink

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

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 12:59
από ST48410
shrike έγραψε:
21 Ιούλ 2018, 12:12
ST48410 έγραψε:
21 Ιούλ 2018, 12:04
shrike έγραψε:
21 Ιούλ 2018, 12:01

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

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

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

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 14:36
από Spiros252
Μπορώ αλλά πρέπει κι εγώ να το μετατρέψω στη λογική του shrike και βαριέμαι ..

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

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

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 14:42
από Spiros252
shrike έγραψε:
21 Ιούλ 2018, 12:01

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

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

Δημοσιεύτηκε: 21 Ιούλ 2018, 14:47
από Χαοτικός
Πληροφορικάριοι είσαστε;