[Παράλληλα και Διανεμημένα Συστ.] Εργασία 4

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[Admins]

Για αλλαγή του public name σας, επικοινωνήστε με έναν από τους Admins.

[vlad]

Όσοι κάνατε το Pagerank ήσασταν ΟΚ με γράφο μέχρι και 1.000.000 κόμβων? Από 50.000 και πάνω το λάπτοπ μου κρασάρει λόγω μνήμης ( οκ, δεν το λες και τέρας ) , αλλά και ο Διάδης δεν τα πάει καλύτερα. Μπορεί να είναι σπάταλος ο αλγόριθμος, αλλά μήπως το ζητούμενο είναι μη υλοποιήσιμο;

Βρες γιατι crushαρει.

[TrueForce]

Όσοι κάνατε το Pagerank ήσασταν ΟΚ με γράφο μέχρι και 1.000.000 κόμβων? Από 50.000 και πάνω το λάπτοπ μου κρασάρει λόγω μνήμης ( οκ, δεν το λες και τέρας ) , αλλά και ο Διάδης δεν τα πάει καλύτερα. Μπορεί να είναι σπάταλος ο αλγόριθμος, αλλά μήπως το ζητούμενο είναι μη υλοποιήσιμο;

Ειναι υλοποιήσιμο, απλά μάλλον σπαταλάς μνήμη χωρίς να χρειάζεται. Δεν πιστεύω να έβαλες μέσα κανα πίνακα 1.000.000x1.000.000 ...;

[spira mirabilis]

Όσοι κάνατε το Pagerank ήσασταν ΟΚ με γράφο μέχρι και 1.000.000 κόμβων? Από 50.000 και πάνω το λάπτοπ μου κρασάρει λόγω μνήμης ( οκ, δεν το λες και τέρας ) , αλλά και ο Διάδης δεν τα πάει καλύτερα. Μπορεί να είναι σπάταλος ο αλγόριθμος, αλλά μήπως το ζητούμενο είναι μη υλοποιήσιμο;

Ειναι υλοποιήσιμο, απλά μάλλον σπαταλάς μνήμη χωρίς να χρειάζεται. Δεν πιστεύω να έβαλες μέσα κανα πίνακα 1.000.000x1.000.000 ...;

Με κατάλαβες  Ας πούμε έχω έναν πίνακα που για κάθε κόμβο έχει με ποιους κόμβους συνδέεται και τη δέσμευση μνήμης την κάνω στην αρχή. Θα μπορούσα να το κάνω με realloc, αλλά τότε δεν ξέρω τί θα γίνει με τον χρόνο. Και ο αρχικός μου γράφος με τις συνδέσεις που τον διαβάζω από αρχείο είναι επίσης nxn, με 1 στους συνδεδεμένους γράφους. Αυτόν τί να το κάνω; Δυο στήλες με τα ζευγάρια;

[TrueForce]

Οι γραφοι που έχει στο internet έχουν αυτή τη μορφή:

[κομβος]TAB[κομβος]

δηλαδή έχεις μόνο μία στήλη που περιέχει όλες τις συνδέσεις και μόνο.

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

Φυσικά αυτό είναι απλά ένας τρόπος υλοποίησης. Feel free να πειραματιστείς και αλλιώς. Απλά το NxN προφανώς θα είναι τεράστιο και δεν μπορείς να το χρησιμοποιήσεις.

[spira mirabilis]

Οι γραφοι που έχει στο internet έχουν αυτή τη μορφή:

[κομβος]TAB[κομβος]

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

[Professional Hater]

Tο σκριπτάκι σε matlab έδινε τετραγωνικό πίνακα 

Βέβαια στο σκριπτάκι ο πίνακας είναι τύπου sparse (=αραιός). Φαντάζομαι θα έχει τη σημασία του, χωρίς να ξέρω. 

[TrueForce]

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

[Professional Hater]

Αν κατάλαβα καλά, εσύ προτείνεις έναν μονοδιάστατο πίνακα n θέσεων, που η κάθε θέση του είναι άλλος πίνακας (pointer δηλαδή) o οποίος έχει τα outgoing links του συγκεκριμένου κόμβου. Δηλαδή αν ο γ κόμβος έχει λινκς προς τους α,β,κ (και οι αλλοι κομβοι δεν εχουν λινκς) θα έχουμε το παρακάτω,

[α][β][γ][δ][ε][ζ][η][θ][ι][κ][λ][μ][ν]
        [α]
        [β]
        [κ]


Σωστά?

[TrueForce]

Ναι, κάτι τέτοιο. Θα σου πρότεινα μάλιστα να χρησιμοποιήσεις ένα struct που θα έχει μέσα για κάθε κόμβο 1) τις συνδέσεις του και 2) των αριθμό των συνδέσεών του(μέγεθος του πίνακα) αντί να έχεις χύμα τους πινακες στο προγραμμα. Το να είναι το struct global βόλεψε. Άλλωστε δεν έχεις να κάνεις με κορτέση που θα σε κράξει γι αυτο. :Ρ

[Professional Hater]

Μμμμ πολύ καλή ιδέα μπράβο σου!

Κάτι βασικό βέβαια που δεν έχω καταλάβει είναι το εξής:
τον γράφο πώς θα τον φτιάξω? Θα πάρω στοιχεία από κάπου ή όλα θα είναι εικονικά και τυχαία? ('Η πρέπει να καταλάβω την surfer? μακάρι να μην είναι το τελευταίο! )

[TrueForce]

Μπορείς να αποθηκεύσεις τον πίνακα που σου επιστρέφει ο surfer με αυτή τη μορφή. Οι γράφοι που υπάρχουν στο διαδίκτυο τους αποθηκεύουν με αυτή τη μορφή. Απλά (μάλλον) πρέπει να χρησιμοποιήσεις τον κώδικα του matlab για συγκρίνεις τα αποτελέσματά σου(να κάνεις plot τις διαφορές). Τον surfer παντως δε χρειαζεται να τον καταλαβεις, dont worry. Το μονο που χρειάζεται να ξέρεις είναι πως σου επιστρέφει έναν πίνακα με τις συνδέσεις.

Ρωτήστε σισμάνη και πιτσιάνη για να σας ανεβάσουν καναν γράφο στο ethmmy ή να σας δώσουν κάποιο link.

[Professional Hater]

Ευχαριστώ πολύ γενικά! Αλλά θα συνεχίσω να ρωτάω

Για να μετατρέψουμε τον τετραγωνικό πίνακα του matlab (ο οποίος είναι εν γένει 1,000,000 Χ 1,000,000) στη μορφή που προτείνεις και μου αρέσει, θα πρέπει κάπως να τον περάσουμε στη C. Και μόνο που τον περνάμε δεν θα δημιουργήσει το πρόβλημα που τέθηκε στην αρχή?

PS: Μήπως έχεις και κανα λινκ εύκαιρο για αυτό?

Οι γραφοι που έχει στο internet έχουν αυτή τη μορφή:

[κομβος]TAB[κομβος].

[TrueForce]

Όλα έτοιμα τα θέλετε...;

Code:

	for i=1:n
		for j=1:n
			if (G(i,j)==1) 
				fprintf(FILE, '%d\t%d\n', j, i);
			end
		end
	end

ο surfer θα σου τρέξει σε κανα χρόνο για 1kk κόμβους. Βάλε κανα μέγεθος 100 ή χιλίων κόμβων το πολύ.

[Professional Hater]

Ευχαριστώ!

PS:

Όλα έτοιμα τα θέλετε...;

Κακά τα ψέματα.... ναι

[Jeik]

Μπορεί να λέω βλακείες, αλλά μήπως υπάρχει λάθος στον τύπο που δίνει για το PageRank;

Συγκεκριμένα, μήπως στο d*Σ _{j ε Βi} το Bi δεν πρέπει να είναι οι κόμβοι με τους οποίους συνδέεται ο i, αλλά οι κόμβοι που συνδέονται στον i; Το ρωτάω γιατί έτσι μου φαίνεται πιο σωστό, αλλά επίσης γιατί διαφορετικά το άθροισμα που υπάρχει στον παρονομαστή μπορεί να μηδενιστεί αν κάποιος κόμβος δεν έχει κανένα link προς άλλη σελίδα(έχει μόνο εισερχόμενες συνδέσεις και όχι εξερχόμενες).