Linear counting: Πώς να εκτιμήσεις το πλήθος των διακριτών τιμών

Πώς θα μπορούσαμε να μετρήσουμε το πλήθος των διακριτών τιμών σε ένα σύνολο δεδομένων, αν τα δεδομένα ήταν πραγματικά πάρα πολλά; Μπορεί για παράδειγμα να έχουμε μια υπηρεσία που μετρά τους μοναδικούς χρήστες σε έναν μεγάλο ιστότοπο, ή και σε ολόκληρο το .com/.whatever, ή κάτι τέτοιο.

Η απλοϊκή προσέγγιση

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

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique(values):
    found = set()
    for item in values:
        if item not in found:
            found.add(item)
    return len(found)

print count_unique(nonunique_values) # 5

Δουλεύει. Εντάξει, αλλά τι γίνεται αν τα δεδομένα είναι μοναδικά αναγνωριστικά UUID v4 των 36 χαρακτήρων και αν τα μοναδικά αναγνωριστικά είναι, ας πούμε, δέκα εκατομμύρια; Λοιπόν… το πρόγραμμα εξακολουθεί να υπολογίζει τη σωστή τιμή, αλλά πόση μνήμη θα καταλάβει; Μπορούμε να το υπολογίσουμε. Για απλότητα θα υποθέσουμε ότι αποθηκεύουμε το uuid πραγματικά ως string 36 χαρακτήρων. Ένα uuid καταλαμβάνει έτσι 36 byte και δέκα εκατομμύρια αναγνωριστικά καταλαμβάνουν 360 MB.

Δεν είναι και λίγο, ας το παραδεχτούμε. Αν τα μοναδικά αναγνωριστικά ήταν εκατό εκατομμύρια, θα φτάναμε ήδη σε τάξη μεγέθους gigabyte κατειλημμένης μνήμης. Και μιλάμε ακόμη μόνο για όσα καταλαμβάνουν τα ίδια τα δεδομένα. Πρόσθεσε και κάποιο overhead που καταλαμβάνει η Python/JavaScript και μπορείς να φτάσεις σε gigabyte ακόμη και με δέκα εκατομμύρια αναγνωριστικά:

Αυτό δεν το θέλεις. Πώς να ξεφύγουμε;

Μπορούμε να δοκιμάσουμε να αποθηκεύσουμε αποδοτικότερα τα ίδια τα αναγνωριστικά, μπορούμε να χρησιμοποιήσουμε C αντί για Python, οπότε θα μειώσουμε ριζικά τις απαιτήσεις μνήμης, αλλά και πάλι δεν θα είναι το ιδανικό και ένα τέτοιο πρόγραμμα θα καταλάμβανε ακόμη απίστευτη ποσότητα χώρου. Μένει να αναρωτηθούμε: χρειάζεται πραγματικά να ξέρουμε με απόλυτη ακρίβεια αν οι διακριτές τιμές είναι ακριβώς 9.563.618; Θα συνέβαινε κάτι, αν δουλεύαμε με το πλήθος 9.547.666; Αν η απάντησή σου είναι ότι θα συνέβαινε και ότι το θέλεις ακριβές, τότε ελεύθερα, όπως αγαπάς. Διαφορετικά, ας δούμε μεθόδους για να εκτιμήσουμε το πλήθος των διακριτών τιμών σε ένα σύνολο δεδομένων όσο το δυνατόν ακριβέστερα, ταχύτερα και με ελάχιστες απαιτήσεις μνήμης.

Η συνάρτηση κατακερματισμού – η σωτηρία μας

Θα θεωρήσουμε μια συνάρτηση κατακερματισμού (hash), που παίρνει ως είσοδο ένα string και επιστρέφει ως έξοδο έναν αριθμό n bit. Αν έχεις συνηθίσει περισσότερο σε συναρτήσεις κατακερματισμού που «επιστρέφουν string», φαντάσου απλά ότι αυτό το string μετατρέπεται στη συνέχεια σε αριθμό – δεν έχει τίποτα το ιδιαίτερο. Το πλήθος των bit δείχνει πόσο μεγάλος είναι ο αριθμός. Μια συνάρτηση 8 bit επιστρέφει αριθμό που καταλαμβάνει οκτώ bit και σε οκτώ bit χωράνε 2⁸ διαφορετικές τιμές, συνήθως οι ακέραιοι από το 0 έως το 255. Στη συνέχεια θα δουλεύουμε με συνάρτηση κατακερματισμού 24 bit. Μια τέτοια συνάρτηση επιστρέφει 2²⁴ διαφορετικές τιμές, δηλαδή 16.777.216.

Αντί να αποθηκεύουμε τις ίδιες τις τιμές, θα αποθηκεύουμε τα 24-bit hash τους. Για την αποθήκευση δέκα εκατομμυρίων hash των 24 bit χρειαζόμαστε 30 MB. Αυτό είναι μία τάξη μεγέθους καλύτερο από τα προηγούμενα 360 MB. Ο κώδικας θα μπορούσε να είναι ο εξής:

def nhash(item, n):
    return hash(item) % (2 ** n)

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique_using_nhash(values):
    found = set()
    for item in values:
        checksum = nhash(item, 24)
        if checksum not in found:
            found.add(checksum)
    return len(found)

print count_unique_using_nhash(nonunique_values) # 5

Η συνάρτηση hash είναι εγγενής συνάρτηση της Python και επιστρέφει ακέραιο, ενώ η συνάρτηση nhash δείχνει μια απλοϊκή υλοποίηση συνάρτησης κατακερματισμού n bit· δεν έχει σημασία να καταλάβεις πώς δουλεύει, γιατί ούτως ή άλλως δεν δουλεύει σωστά – το αποτέλεσμά της δεν καταλαμβάνει 24 bit, αλλά αυτό τώρα δεν μας ενδιαφέρει, εδώ μετράει η ιδέα.

Ακολουθεί η συνάρτηση count_unique_using_nhash, που μετρά τις διακριτές τιμές. Διατρέχει όλες τις τιμές, υπολογίζει το hash τους και το αποθηκεύει στη μεταβλητή found, αν η τιμή αυτή δεν υπάρχει ήδη εκεί.

Το πρόβλημα αυτής της προσέγγισης είναι ότι η συνάρτηση κατακερματισμού μπορεί να επιστρέψει το ίδιο checksum για διαφορετικά strings – μπορεί να συμβεί σύγκρουση. Όσο περισσότερες τέτοιες συγκρούσεις συμβαίνουν, τόσο πιο ανακριβές είναι το αποτέλεσμα. Η συνάρτηση count_unique_using_nhash σχεδόν πάντα επιστρέφει μικρότερο πλήθος διακριτών τιμών από το πραγματικό.

Και ποια συνάρτηση κατακερματισμού να διαλέξουμε; Δεν έχει και τόση σημασία, αλλά γενικά συνιστάται κάποια παραλλαγή του MurmurHash.

Χάρτες bit (bitmaps)

Πρόσεχες στο μάθημα προγραμματισμού σε C; Αν ναι, τότε ξέρεις τους χάρτες bit (bitmaps). Πώς θα μπορούσαν να χρησιμοποιηθούν;

Την ιδέα θα την περιγράψουμε με έναν πίνακα. Δεν χρειάζεται να φυλάμε τα υπολογισμένα checksum, μπορούμε να δημιουργήσουμε έναν πίνακα μήκους 2²⁴ και να αρχικοποιήσουμε όλα τα στοιχεία του στο μηδέν. Μετά, όποτε συναντήσουμε κάποιο checksum – που είναι αριθμός! – γράφουμε στον πίνακα, στη θέση checksum, τον αριθμό 1, σημειώνοντας έτσι ότι αυτό το checksum το έχουμε ήδη βρει. Το πλήθος των διακριτών στοιχείων θα είναι τότε περίπου ίσο με το πλήθος των άσσων στον πίνακα. Ο κώδικας θα μπορούσε να είναι ο εξής:

def count_unique_using_array(values):
    # list of length 2^24 initialized to zeros
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Ωστόσο η χρήση πίνακα είναι εδώ πολύ δαπανηρή σε μνήμη, επειδή σε κάθε κελί πρέπει να αποθηκεύουμε είτε ένα είτε μηδέν. Αντί γι' αυτό μπορούμε να χρησιμοποιήσουμε πίνακα bit. Για να το καταλάβεις: ένας ακέραιος αριθμός (integer) μπορεί να αποθηκευτεί π.χ. σε 32 bit. Αν μετατρέψουμε τον αριθμό 354 στο δυαδικό σύστημα, παίρνουμε 101100010. Ο αριθμός 354 θα αποθηκευόταν λοιπόν στον υπολογιστή ως ακέραιος 32 bit (τις λεπτομέρειες τις αφήνουμε, εντάξει;) ως εξής:

00000000 00000000 00000001 01100010

Αυτή είναι μια αρκετά ωραία μορφή που θα μπορούσαμε να αξιοποιήσουμε, έτσι δεν είναι; Εμείς στη συνάρτησή μας θέλουμε να αποθηκεύουμε μόνο άσσους και μηδενικά και μόλις ανακαλύψαμε ότι ένας συνηθισμένος αριθμός δεν είναι τίποτε άλλο από ένας σωρός μηδενικά και άσσοι (όπως περίπου όλα στον υπολογιστή…). Με λίγα λόγια, με τελεστές bit μπορούμε να αποθηκεύσουμε έναν άσσο έτσι ώστε να καταλαμβάνει πραγματικά ένα bit.

Ας επιστρέψουμε στη συνάρτησή μας με τον πίνακα. Αν την ξαναγράφαμε με πίνακες bit, για συνάρτηση κατακερματισμού 24 bit θα μας αρκούσε πίνακας bit μεγέθους 2²⁴ bit, δηλαδή 2 MiB. Αυτό είναι αξιοπρεπής αναβάθμιση!

Με συνάρτηση κατακερματισμού 32 bit, που έχει 2³² διαφορετικές τιμές εξόδου, δηλαδή 4.294.967.296, θα χρειαζόμασταν πίνακα bit μεγέθους μισού giga. Αυτό δεν είναι καθόλου άσχημο, αφού μπορούμε έτσι να μετρήσουμε διακριτές τιμές μέχρι τάξης δισεκατομμυρίων.

Linear Counting

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

Ωστόσο η εκτίμηση που υπολογίζουμε με συναρτήσεις κατακερματισμού μπορεί να βελτιωθεί περαιτέρω. Χρησιμοποιείται μια απλή ιδέα – όσο περισσότερες διακριτές τιμές έχει το σύνολο δεδομένων, τόσο πιθανότερο είναι ότι με τον καιρό θα εμφανίζονται συγκρούσεις. (Σύγκρουση = δύο διαφορετικές είσοδοι έχουν την ίδια έξοδο από τη συνάρτηση κατακερματισμού, το ίδιο checksum.) Τώρα θα κάνουμε λίγους υπολογισμούς, γι' αυτό θα εισαγάγουμε μερικές μεταβλητές:

Θα δουλεύουμε με συνάρτηση κατακερματισμού h των n bit.
Το πλήθος όλων των δυνατών εξόδων της συνάρτησης h είναι έτσι ίσο με 2ⁿ. Αυτό το πλήθος θα το συμβολίσουμε με το γράμμα m, δηλαδή: m=2ⁿ.
Τον πίνακα bit, στον οποίο θα αποθηκεύουμε ποια checksum έχουμε βρει, θα τον συμβολίσουμε με το κεφαλαίο γράμμα A. Ο πίνακας A έχει μήκος m.
Αν περάσουμε από τον αλγόριθμό μας ολόκληρο το σύνολο δεδομένων, κάποιες τιμές στον πίνακα bit θα είναι ίσες με μηδέν και κάποιες με ένα. Εμάς θα μας ενδιαφέρει κυρίως ο λόγος «πλήθος μηδενικών διά το μήκος του πίνακα», που μας δίνει το σχετικό ποσοστό μηδενικών στον πίνακα bit. Στην αρχή ο λόγος αυτός είναι ίσος με 1, επειδή ο πίνακας έχει αρχικοποιηθεί σε μηδενικά. Αν ήταν fifty-fifty, ο λόγος θα ήταν ίσος με το ένα δεύτερο κ.ο.κ. Αυτή την τιμή τη συμβολίζουμε με Z και τη βρίσκουμε ως Z = πλήθος μηδενικών / m.

Σε αυτό το σημείο ισχύει ότι όσο μεγαλύτερη η τιμή Z, τόσο μεγαλύτερη βεβαιότητα έχουμε ότι η εκτίμησή μας για το πλήθος των διακριτών τιμών είναι ακριβής. Αν για παράδειγμα περάσουμε ένα κενό σύνολο δεδομένων, στον πίνακα bit θα μείνουν μόνο μηδενικά και η τιμή Z θα είναι ίση με ένα – έχουμε έτσι πλήρη βεβαιότητα ότι στο σύνολο δεδομένων μας υπάρχουν τόσα διακριτά στοιχεία, όσοι είναι οι άσσοι στον πίνακα bit – μηδέν.

Αν η τιμή Z είναι ίση με 0,99, σημαίνει ότι ο πίνακας bit είναι γεμάτος με άσσους κατά ένα εκατοστό. Το 99% του πίνακα περιέχει μηδενικά. Αυτό είναι ακόμη καλό, είναι πιθανό ότι κατά τον υπολογισμό δεν έγιναν πολλές συγκρούσεις και ίσως χρειαστεί μηδενική ή μόνο ελάχιστη διόρθωση. Αν όμως η τιμή Z είναι ίση με 0,05, μόνο το 5% του πίνακα έμεινε μηδενικό και πιθανότατα κατά τον υπολογισμό συναντήσαμε πάρα πολλές συγκρούσεις – θα χρειαστεί μεγάλη διόρθωση.

Πώς όμως υπολογίζεται αυτή η διόρθωση; Θα βοηθηθούμε από τον λογάριθμο, μια συνάρτηση που έχει αυτή τη μορφή:

Εμάς θα μας ενδιαφέρει το κόκκινο τμήμα στο διάστημα (0, 1]. Αν στον άξονα x βάλουμε την τιμή Z, τότε όσο μεγαλύτερο το Z, τόσο περισσότερο η τιμή y πλησιάζει το μηδέν. Και αντίστροφα – όσο μικρότερο το Z, τόσο μικρότερο θα είναι το y. Την τελική εκτίμηση τη βρίσκουμε πολλαπλασιάζοντας αυτόν τον αριθμό με -m. Πρόσεξε ότι για αρκετά μικρή τιμή Z παίρνουμε αριθμό που είναι ακόμη και μικρότερος από -1 και αν αυτή την τιμή την πολλαπλασιάσουμε με -m, παίρνουμε εκτίμηση μεγαλύτερη από m: εκτιμήσαμε δηλαδή ότι το πλήθος των διακριτών τιμών είναι μεγαλύτερο από το πλήθος όλων των δυνατών checksum που μπορούν να βγουν από τη συνάρτηση κατακερματισμού h.

Ολόκληρος ο τύπος για τον υπολογισμό του πλήθους p των διακριτών τιμών θα ήταν ο εξής:

$p = - m \cdot \ln Z$

Η υλοποίηση (χωρίς πίνακες bit, μόνο με συνηθισμένους πίνακες) θα μπορούσε να είναι η εξής:

from uuid import uuid4
from math import log

number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values

def nhash(item, n):
    return hash(item) % (2 ** n)

def count_unique_using_array(values, n):
    array = [0] * (2 ** n)
    for item in values:
        array[nhash(item, n)] = 1
    return sum(array)

def linear_counting(values, n):
    estimate = count_unique_using_array(values, n)
    m = 2 ** n
    number_of_zeros = m - estimate
    Z = float(number_of_zeros) / m
    # log here is the natural logarithm (base e)
    p = (-m) * log(Z)      
    p = int(round(p))
    print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
          (estimate, m, number_of_zeros, Z, p)
    return p

print "Cardinality: %s" % linear_counting(nonunique_values, 16)

Στη συνάρτηση linear_counting υπολογίζουμε πρώτα την πρώτη εκτίμηση με τον προηγούμενο αλγόριθμο, που χρησιμοποιεί συνάρτηση κατακερματισμού n bit. Έπειτα υπολογίζουμε το ποσοστό των μηδενικών στον πίνακα και κάνουμε τη διόρθωση σύμφωνα με τον τύπο. Ο λογάριθμος στον κώδικα είναι ο φυσικός λογάριθμος. Η μεταβλητή nonunique_values περιέχει number_of_unique_values μοναδικά strings, σε αυτό το παράδειγμα λοιπόν η λίστα nonunique_values περιέχει δέκα χιλιάδες διακριτές τιμές. Ο παράξενος κώδικας στην έκτη γραμμή φροντίζει να υπάρχουν στον πίνακα περισσότερες ίδιες τιμές: απλά στο τέλος της λίστας προσαρτούμε την ίδια τη λίστα, οπότε κάθε τιμή υπάρχει στον πίνακα δύο φορές. Και μετά απλά υπολογίζουμε. Η συνάρτηση θα έπρεπε ιδανικά να επιστρέψει ότι η λίστα περιέχει δέκα χιλιάδες διακριτές τιμές. Έξοδος:

Debug info: estimate=9289, m=65536, number_of_zeros=56247, 
Z=0.858261108398, p=10017
Cardinality: 10017

Επειδή κάθε φορά παράγεται διαφορετική λίστα nonunique_values, τα αποτελέσματα θα διαφέρουν σε κάθε εκτέλεση. Χρησιμοποιήσαμε συνάρτηση κατακερματισμού 16 bit. Βλέπουμε ότι η πρώτη εκτίμηση από τη συνάρτηση count_unique_using_array ήταν ότι η λίστα περιέχει 9289 διακριτές τιμές. Αυτή την εκτίμηση τη βελτιώσαμε με τη διόρθωση σε 10.017, που είναι ήδη αρκετά καλό: η εκτίμησή μας είναι μεγαλύτερη μόνο κατά 0,17%, ενώ πριν ήταν μικρότερη κατά 7,11% – μια αρκετά μεγάλη απόκλιση.

Αν πάρουμε «μεγαλύτερη» συνάρτηση κατακερματισμού, για παράδειγμα 24 bit, θα πάρουμε ακριβέστερο αποτέλεσμα:

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, 
Z=0.999404132366, p=10000
Cardinality: 10000

Ήδη η αρχική εκτίμηση ήταν OK, η βελτίωση έφτασε ακριβώς τις δέκα χιλιάδες. Για επίδειξη μπορούμε να δοκιμάσουμε ένα εκατομμύριο μοναδικά αναγνωριστικά, δηλαδή number_of_unique_values = 1000000. Με συνάρτηση κατακερματισμού 24 bit καταλήγουμε σε αυτά τα αποτελέσματα:

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, 
Z=0.94212192297, p=1000267
Cardinality: 1000267

Όχι άσχημα. Και αν το υλοποιήσουμε ως πίνακα bit, ο πίνακας θα μας φάει μόνο τα προαναφερθέντα δύο megabyte (+ όσα φάει η γλώσσα). Για μένα αρκετά καλό. But we can do better! Much better. Αλλά την επόμενη φορά.

Στο μεταξύ μπορείς να διαβάσεις το άρθρο A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Ή μπορείς να συνεχίσεις με το επόμενο μέρος της σειράς: ο αλγόριθμος min-value.

Κεφάλαια: Linear counting, Min Value, LogLog, HyperLogLog

« Προηγούμενο: Μετατροπή αυτομάτου σε κανονική έκφραση

Επόμενο: Min Value »