separate-chaining

You are currently browsing articles tagged separate-chaining.

Trong bài bảng băm, chúng ta đã nghiên cứu cách thiết kế bảng băm và ba phương pháp giải quyết xung đột cơ bản: xích ngăn cách (chaining), băm địa chỉ mở (open addressing) và băm hoàn hảo (perfect hashing). Bài này chúng ta sẽ phân tích kĩ hơn phương pháp xích ngăn cách. Cụ thể chúng ta sẽ tìm câu trả lời cho các câu hỏi:

  1. Chiều dài trung bình của các danh sách trong bảng băm là bao nhiêu?
  2. Chiều dài danh sách dài nhất trong bảng băm là bao nhiêu?

Câu trả lời cho câu hỏi đầu tiên sẽ cho chúng ta biết, khi chúng ta tìm kiếm một khóa thì trung bình chúng ta sẽ mất bao nhiêu thời gian. Câu trả lời cho câu hỏi thứ hai sẽ cho chúng ta biết trong trường hợp xấu nhất, chúng ta sẽ mất bao nhiêu thời gian để tìm kiếm một khóa.

Nhắc lại các khái niệm cơ bản: Gọi $n$ là số phần tử ta muốn lưu trữ trong bảng băm; các phần tử này xuất phát từ một tập gốc $\mathcal{U}$. Bảng băm của chúng ta có kích thước $m$. Để băm vào bảng, ta sử dụng một hàm $h(x)$; hàm băm này được chọn ngẫu nhiên từ một họ hàm băm $\mathcal{H}$. Bằng cách chọn ngẫu nhiên như vậy, $h(x)$ thỏa mãn:

$ \mathrm{Pr}_{h \in \mathcal{H}}[h(x) = h(y) ] \sim \frac{1}{m} \quad \forall x \not= y \qquad (1)$

Dấu $\sim$ ở đây có nghĩa là "tỉ lệ với",i.e, $\mathrm{Pr}_{h \in \mathcal{H}}[h(x) = h(y) ] = \frac{c}{m}$ với một hằng số $c$ nào đó.

Điểm quan trọng nhất mà bạn đọc cần nhớ ở đây: chúng ta không có bất kì giả sử nào về dữ liệu (i.e chúng ta sẽ không giả sử dữ liệu đầu vào là ngẫu nhiên). Tất cả các phân tích ngẫu nhiên ở đây đến từ việc chọn hàm băm ngẫu nhiên. Do đó, nếu ta có định sẵn một hàm băm thì tất cả các phân tích dưới đây đều vô nghĩa.

Chiều dài trung bình của một xích trong bảng

Nhắc lại hệ số tải:

Hệ số tải (load factor) $\alpha$ được định nghĩa như sau:

$\alpha = \frac{n}{m} \qquad (2)$

 

Cố định một khóa $x$. Gọi $\ell(x)$ là biến ngẫu nhiên chiều dài của danh sách lưu khóa $x$. Gọi $I_{x,y}$ là biến ngẫu nhiên $0/1$ trong đó $I_{x,y} = 1$ nếu $y$ được băm vào cùng ô với $x$ và $0$ nếu ngược lại.

$ I_{x,y} = \begin{cases} 1, & \mbox{if } h(x) = h(y)\\ 0, & \mbox{otherwise } \end{cases} \qquad (3)$

Do $I_{x,y}$ là biến ngẫu nhiên $0/1$, ta có:

$ E[I_{x,y}] = \mathrm{Pr}[h(x) = h(y)] \sim \frac{1}{m}$

Ngoài ra, ta có thể biểu diễ $\ell(x)$ dưới dạng các biến $I_{x,y}$ như sau:

$ \ell(x) = \sum_{y \in S} I_{x,y}$

Do đó, theo tính tuyến tính của kì vọng:

$ E[\ell(x)] = \sum_{y \in S} E[I_{x,y}] \sim \sum_{y \in S}\frac{1}{n} = \frac{n}{m} = \alpha \qquad (4)$

Như vậy, chiều dài trung bình của một xích trong bảng băm tỉ lệ với hệ số tải $\alpha$.


Để phân tích chiều dài của danh sách dài nhất, ta sẽ xem xét mô hình ném bóng vào rổ (balls into bins) dưới đây. Mô hình này sẽ tương ứng với trường hợp hệ số tải $\alpha = 1$.

Mô hình ném bóng vào rổ

Một người ném ngẫu nhiên $n$ quả bóng vào $n$ cái rổ. Hỏi trong rổ đầy nhất có bao nhiêu quả bóng?

 

Trước khi trả lời câu hỏi trên, chúng ta sẽ xem xét một vài câu hỏi đơn giản hơn để có một cách nhìn sâu hơn về bài toán này.

Remark: Một số bạn có lẽ quen với cách kí hiệu số tổ hợp $C^k_n = \frac{n!}{k!(n-k)!}$. Trong bài này mình dùng kí hiệu ${n \choose k}$ để nhất quán với các kí hiệu của Wikipedia.

Câu hỏi 1: Xác suất để rổ 1 có ít nhất một quả bóng là bao nhiêu?

Trả lời: Xác suất khi ném ngẫu nhiên một quả bóng không vào rổ 1 là $1 - \frac{1}{n}$. Do đó, xác suất khi ta ném ngẫu nhiên (độc lập) $n$ quả bóng mà không quả nào vào rổ 1 là $(1-\frac{1}{n})^n$. Sử dụng xấp xỉ $(1-1/x)^x \sim e^{-1}$, ta có xác suất không quả bóng nào vào rổ 1 là $1/e$. Như vậy, xác suất để rổ 1 có ít nhất 1 quả bóng là $P_1 = 1 - 1/e \sim 0.632$.

Câu hỏi 2: Xác suất để rổ 1 có đúng $k$ quả bóng là bao nhiêu?

Trả lời: Do xác suất khi ném ngẫu nhiên một quả bóng vào rổ 1 là $\frac{1}{n}$, xác suất đúng $k$ quả bóng vào rổ 1 khi ta ném $n$ quả bóng ngẫu nhiên là:

$P_2 = {n \choose k}(\frac{1}{n})^k(1-\frac{1}{n})^{n-k} \leq {n \choose k}(\frac{1}{n})^k \leq (\frac{e}{k})^k \qquad (5)$

Ở trên, ta sử dụng xấp xỉ (xem Wikipedia):

$(\frac{n}{k})^k \leq {n \choose k} \leq (\frac{en}{k})^k \qquad (6)$

Câu hỏi 3: Xác suất để rổ 1 có ít nhất $k$ quả bóng là bao nhiêu?

Trả lời: Để tìm cận trên cho xác suất ở câu hỏi 3, ta chỉ cần quan tâm đến $k$ quả bóng vào rổ $1$ còn $n-k$ quả bóng còn lại thì ta không quan tâm nó vào rổ nào. Do ta có $n \choose k$ cách chọn $k$ quả bóng từ $n$ quả bóng, xác suất để rổ 1 có ít nhất $k$ quả bóng tối đa là:

$P_3 = {n \choose k} (\frac{1}{n})^k \leq (\frac{e}{k})^k \qquad (7)$

Câu hỏi 4: Xác suất để tồn tại một rổ bất kì trong số $n$ rổ có ít nhất $k$ quả bóng là bao nhiêu?

Trả lời: Từ câu hỏi 3, ta suy ra xác suất trong câu hỏi 4 tối đa là:

$P_4 = n(\frac{e}{k})^k \qquad (8)$

Bây giờ chúng ta có thể trả lời một số câu hỏi thú vị hơn về mô hình này.

Lemma 1: Với xác suất $1 - \frac{1}{n}$, mọi rổ đều có không quá $3\frac{\ln n}{\ln\ln n}$ quả bóng.

 
Chứng minh: Ta sẽ chứng minh phiên bản dễ hơn một chút: với xác suất $1-\frac{1}{n}$, mọi rổ có không quá $3\ln n$ quả bóng. Cách chứng minh ta sẽ trình bày có thể áp dụng (bằng một sửa đổi nhỏ) để chứng minh Lemma 1. Chi tiết coi như bài tập cho bạn đọc.

Ta sẽ tìm xác suất để tồn tại một rổ có ít nhất $k = 3\ln n$ quả bóng. Áp dụng câu hỏi 4 với $k = 3\ln$, ta có:

$P_4 \leq n(\frac{1}{3\ln n})^{3\ln n} \leq n(\frac{1}{3^{3\ln n}}) = \frac{n}{n^{3\ln 3}} \leq \frac{1}{n} \qquad (8)$

Do đó, xác suất để mọi rổ có tối đa $3\ln n$ quả bóng là $1 - \frac{1}{n}$.


Lemma 1 cho chúng ta biết, nếu sử dụng xích ngăn cách khi hệ số tải $\alpha = 1$, với xác suất cao, danh sách dài nhất có tối đa $O(\frac{\ln}{\ln \ln n})$ phần tử. Câu hỏi còn lại là với xác suất cao, danh sách dài nhất có ít nhất bao nhiêu phần tử?

Lemma 2: Với xác suất $1 - \frac{1}{n}$, tồn tại một rổ có ít nhất $\frac{\ln n}{\ln\ln n}$ quả bóng.

 

Chứng minh Lemma 2 khó hơn Lemma 1 rất nhiều. Bạn đọc quan tâm có thể tham khảo thêm tại [1] (Lemma 5.12).

Kết hợp Lemma 1 và 2, ta suy ra với xác suất $1 - 1/n$, danh sách dài nhất có $\Theta(\frac{\ln n}{\ln\ln n})$ phần tử.

Remark: Nếu ta ném $n$ quả bóng vào $m$ cái rổ khi $n \gg m$ thì với xác suất cao, rổ đầy nhất sẽ có khoảng $\frac{n}{m} + \sqrt{\frac{n\log m}{m}}$ quả bóng. Chi tiết xem thêm tại [3].


Trong bài bảng băm phần xích ngăn cách, chúng ta có nói đến một phương pháp sử dụng hai hàm băm $h(x)$ và $g(x)$. Khi băm khóa $x$ vào bảng, ta sẽ kiểm tra hai danh sách $T[h(x)]$ và $T[g(x)]$. Danh sách nào ngắn hơn thì ta sẽ đặt $x$ vào danh sách đó. Phương pháp này gọi là băm chọn một trong hai và người đầu tiên nghiên cứu phương pháp này có lẽ là Karp, Luby and Heide [7]. Điều ngạc nhiên là với sửa đổi nhỏ như vậy, với xác suất cao, danh sách dài nhất chỉ có khoảng $O(\log \log n)$ phần tử, nhỏ hơn $O(\frac{\ln n}{ \ln \ln n})$ rất nhiều. Sau đây chúng ta sẽ phân tích kĩ hơn về phương pháp này.

Chọn một trong hai

Trong mô hình ném bóng vào rổ, khi ném một quả bóng, thay ném ngẫu nhiên vào rổ bất kì, ta sẽ chọn ra ngẫu nhiên 2 rổ và đặt quả bóng vào rổ có ít bóng hơn. Câu hỏi mà chúng ta quan tâm là:

Trong rổ đầy nhất có bao nhiêu quả bóng?

 
Ta sẽ chứng minh:

Lemma 3: Với xác suất cao, rổ đầy nhất có $\Theta(\log\log n)$ quả bóng.

 

Chứng minh một cách đầy đủ Lemma 3 không hề đơn giản. Phương pháp chứng minh hay sử dụng cho bài toán này là quy nạp theo lớp (layered induction) (Xem thêm tại [1], Theorem 14.1). "Chứng minh" mình sẽ trình bày dưới đây ([5]) đã đơn giản hóa rất nhiều và hi vọng sẽ cho bạn đọc một cách nhìn về bài toán. "Chứng minh" này không phải là một chứng minh toán học đầy đủ.

Chứng minh: Gọi chiều cao của một quả bóng là $i$ nếu quả bóng đó là quả bóng thứ $i$ được đưa vào rổ (chứa nó). Do rổ có ít nhất $i$ quả bóng sẽ chứa ít nhất một quả bóng có chiều cao ít nhất là $i$, ta có:

Nhận xết: Số quả bóng có chiều cao $\geq i$ nhiều hơn số rổ có ít nhất $i$ quả bóng

Gọi $N_i$ là số rổ có ít nhất $i$ quả bóng và đặt $\alpha_i = \frac{N_i}{N}$. Một quả bóng có chiều cao ít nhất $i+1$ khi và chỉ khi ta chọn được hai rổ có ít nhất $i$ quả bóng. Xác suất đó là $\alpha_i^2$. Do đó:

$\mathrm{Pr}[\mbox{ balls have height } \geq i+1] \leq \alpha^2_i\qquad (9)$

Do $\mathrm{Pr}[\mbox{ balls have height } \geq i+1] = \alpha_{i+1}$, ta có công thức đệ quy:

$\alpha_{i+1} \leq \alpha^2_i\qquad (10)$

Do ta chỉ có tối đa $N/2$ rổ có ít nhât $2$ quả bóng, suy ra $\alpha_2 \leq 1/2$. Giải công thức đệ quy $(10)$ ta được $\alpha_{i} = \frac{1}{2^{2^{i-1}}}$. Ta chọn $i$ sao cho $\alpha_i \sim 1/n$ (tương đương với $N_i \sim 1$), ta suy ra $i = \log \log n$ (dpcm).

Tham khảo

[1] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York, NY, USA, 2005.
[2] Shuchi Chawla. Lecture note on balanced allocation. University of Wisconsin, 2007.
[3] Martin Raab and Angelika Steger. "Balls into Bins" - A Simple and Tight Analysis. In RANDOM '98, Springer-Verlag, 159-170, 1998.
[4] Michael Mitzenmacher. The Power of Two Choices in Randomized Load Balancing. Parallel and Distributed Systems, IEEE Transactions on 12.10 (2001): 1094-1104.
[5] Anupam Gupta. Notes on The Power of Two Choices, CMU.
[6] Udi Wieder. Balls-and-Bins made simpler. Windows on Theory blog post, Accessed May/2016.
[7] Richard M. Karp, Michael Luby, and Friedhelm Meyer auf der Heide. Efficient PRAM simulation on a distributed memory machine. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing (STOC '92). ACM, New York, NY, USA, 318-326, 1992.

Tags: , , , , ,

« Older entries