Min Value: Cara menganggar bilangan nilai unik

Dalam artikel sebelum ini tentang Linear Counting, kita telah membincangkan algoritma asas untuk mengira dan menganggar bilangan nilai unik dalam suatu set data. Hari ini kita akan melihat satu lagi algoritma berkebarangkalian yang membolehkan kita menganggar bilangan nilai unik dengan ketepatan yang baik dan keperluan ingatan yang kecil.

Min Value

Dalam artikel ini kita hanya bekerja dengan nombor nyata daripada selang unit (0, 1). Bayangkan suatu set nombor daripada selang ini yang tertabur secara seragam, contohnya set nombor {0.25, 0.5, 0.75}. Nombor yang bersebelahan sentiasa berjarak tepat 0.25 antara satu sama lain (dan juga dari sifar dan dari satu). Bagaimanakah hal ini membantu kita mengira bilangan unsur unik?

Jika saya katakan bahawa kita mempunyai set nombor sebegini yang tertabur secara seragam dalam selang unit, dan jarak antara nombor-nombor ini tepat 0.2 — bolehkah anda mengira bilangan unsur set itu? Sudah tentu, set itu ialah {0.2, 0.4, 0.6, 0.8}, dan kekardinalannya sama dengan empat. Jika input kita ialah nombor yang tertabur secara seragam dalam selang unit dan kita mengetahui jarak antara nombor yang bersebelahan, kita boleh mengira bilangan unsurnya dengan mudah.

Jarak antara nombor yang bersebelahan pula sama dengan unsur minimum set itu — jarak antara unsur bersebelahan dalam set {0.25, 0.5, 0.75} ialah 0.25, dan begitulah seterusnya. Untuk mengira bilangan unsur bagi nombor yang tertabur secara seragam, kita hanya perlu mencari unsur minimum. Kemudian kita boleh mengira bilangan unsur p dengan rumus mudah:

$$p=\frac{1}{m}-1$$

dengan m ialah unsur minimum tersebut.

Kita mencincang lagi…

Baiklah, tetapi bagaimanakah kita boleh menggunakan idea ini jika input kita ialah rentetan atau nilai lain yang tidak memenuhi syarat taburan seragam dalam selang unit? Sekali lagi kita menggunakan fungsi cincang yang sudah biasa kita guna, yang boleh memulangkan nombor nisbah daripada selang unit bagi sebarang input. Membina fungsi cincang sebegini mudah sahaja.

Dengan cara ini kita memperoleh nombor nisbah daripada data, tetapi bagaimanakah kita memastikan bahawa nombor ini tertabur secara seragam? Hal itu tidak mungkin, tetapi kita boleh menggunakan cara lain. Dari sudut pandangan kita, fungsi cincang berkelakuan agak “rawak”. Bagi rentetan yang sangat serupa seperti “kaki”, “kakj” dan “kakk”, fungsi cincang kemungkinan besar memulangkan checksum yang sangat berbeza. Dengan kata lain: jika kita mencincang seribu nilai yang berbeza ke dalam selang unit, sangat tidak mungkin sebahagian besar nombor itu, misalnya, lebih kecil daripada setengah. Sebaliknya, sangat mungkin nombor itu tertabur lebih kurang secara sekata. Semakin banyak data yang kita cincang, semakin sekata taburannya.

Daripada idea ini kita memperoleh algoritma yang mudah: kita meneliti data input, mencincang setiap unsur ke dalam selang unit dan mengingati unsur minimum. Bilangan unsur unik dianggarkan dengan rumus tadi. Pelaksanaan dalam Python:

from uuid import uuid4

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

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values)
    minimum = min(numbers_from_unit_interval)
    return int(1 / minimum) - 1

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Fungsi unit_interval_hash memulangkan nombor perpuluhan daripada selang (0, 1]. Fungsi count_unique_using_minimum mula-mula menukarkan semua nilai input kepada nombor sebegini, mencari minimum dan memulangkan 1 / minimum - 1. Perhatikan bahawa langsung tidak penting berapa banyak nilai yang sama terdapat dalam set data — bagi dua nilai yang sama, fungsi cincang memulangkan nombor nisbah yang sama, dan hal ini tidak menjejaskan minimum yang terhasil. Oleh itu, algoritma ini mengira bilangan unsur unik.

Apakah hasilnya? (Setiap baris ialah kekardinalan yang dianggarkan, manakala kekardinalan sebenar ialah 10 000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Tidaklah begitu baik, bukan? Algoritma ini meneliti sepuluh set ID yang berbeza, dan setiap set mengandungi sepuluh ribu nilai unik. Anggaran yang dikira kebanyakannya jauh tersasar. Jika kita mengambil min anggaran itu, kita memperoleh nilai 18 352. Nilai ini masih jauh tersasar, tetapi lihat pula keperluan ingatannya — keperluan ini malar! Untuk mencari minimum, anda hanya perlu menyimpan satu pemboleh ubah dalam ingatan, iaitu minimum semasa, dan itu sahaja. Jadi ya, anggarannya teruk, tetapi kosnya hampir tiada.

Penambahbaikan

Kita lihat bahawa masalah utama algoritma ini ialah ketidakstabilannya — sekali algoritma ini memberikan anggaran yang agak baik (9362), kali lain anggarannya langsung tersasar (65536). Bagaimanakah kita boleh mengatasinya? Kita boleh membahagikan data input kepada beberapa bahagian, mengira bilangan unsur unik bagi setiap bahagian, dan akhirnya mengambil min bagi semuanya. Kita boleh membahagikan data mengikut aksara pertama ID kita. Jadi, kita mengira bilangan nilai unik secara berasingan bagi ID yang bermula dengan huruf “a”, kemudian bagi ID yang bermula dengan huruf “b”, dan seterusnya. Kodnya:

from uuid import uuid4

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

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    min_values = {}
    for item in values:
        first_char = str(item)[0]
        hashed_value = unit_interval_hash(item, n)
        min_values[first_char] = min(min_values.get(first_char, 1), hashed_value)
    average_minimum = sum(min_values.values()) / len(min_values)
    return (int(1 / average_minimum) - 1) * len(min_values)

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Perubahannya terdapat dalam fungsi count_unique_using_minimum. Dalam pemboleh ubah min_values, kita menyimpan minimum bagi setiap kumpulan. Pada akhirnya kita menjumlahkan semua minimum dan membahagikannya dengan bilangan semua nilai yang disimpan — kita memperoleh min bagi minimum itu. Ungkapan 1/average_minimum memberikan min bilangan nilai unik dalam setiap kumpulan — nilai ini kemudiannya didarab dengan bilangan kumpulan, dan kita memperoleh anggaran bilangan nilai unik dalam set data yang diberikan. Bagaimanakah prestasi kaedah yang diubah suai ini?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Hasilnya masih kurang baik, tetapi pasti lebih baik. Algoritma ini lebih stabil. Kita boleh cuba mengubah suai fungsi itu supaya kumpulan tidak dibentuk mengikut aksara pertama, tetapi, misalnya, mengikut dua aksara pertama ID, seperti berikut:

first_char = str(item)[0:2] # ToDo: choose better name for variable

Hasilnya kemudian seperti berikut:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Nah, hasil ini sudah agak baik, bukan? Jika kita mencuba pula seratus ribu nilai unik, dua aksara pertama dan n = 24, kita memperoleh hasil berikut:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Boleh tahan. Namun, masih ada algoritma yang lebih baik, jangan risau.

Bagaimana pula dengan keperluan ingatan? Kita perlu menyimpan minimum bagi setiap kumpulan, tidak lebih daripada itu. Jika ID kita dalam format heks, maksudnya kita perlu mengingati paling banyak 16^x minimum, dengan x ialah bilangan aksara yang membentuk kunci kumpulan. Satu minimum ialah satu nombor nisbah, iaitu jenis data seperti double atau float.

Catatan akhir: kita boleh membahagikan input kepada beberapa kumpulan kerana input kita ialah ID yang berkelakuan seperti rentetan rawak. Jika input kita bukan rentetan rawak tetapi data dalam format tertentu, kita perlu membahagikannya dengan cara lain. Contohnya, jika setiap ID bermula dengan awalan userid-, pembahagian kepada kumpulan mengikut aksara pertama tentu tidak akan berfungsi dengan baik.