Làm cách nào để kiểm tra hàm băm của tôi tốt về tải trọng tối đa?

Question

Tôi đã đọc qua các bài báo khác nhau về vấn đề 'Quả bóng và Thùng' và có vẻ như nếu hàm băm hoạt động đúng (tức là nó phân phối ngẫu nhiên) thì phải là/đúng nếu tôi băm n giá trị vào một bảng băm với n khe (hoặc thùng):

1. xác suất mà một thùng rỗng, cho lớn n là 1/e.
2. Số thùng dự kiến ​​trống là n/e.
3. Xác suất rằng thùng có k quả bóng là <= 1/ek! (đã sửa).
4. Xác suất rằng thùng có ít nhất k va chạm là <= ((e/k)**k)/e (đã sửa).

Những giao diện này dễ kiểm tra. Tuy nhiên, kiểm tra max-load (số lượng va chạm tối đa có xác suất cao) thường được ghi nhận một cách mơ hồ.

Hầu hết các văn bản đều cho biết số va chạm tối đa trong bất kỳ thùng là O(ln(n)/ln(ln(n))). Một số người nói là 3*ln(n)/ln(ln(n)). Các giấy tờ khác trộn ln và log - thường không xác định chúng hoặc nêu rõ rằng log là cơ sở nhật ký điện tử và sau đó sử dụng ln ở nơi khác.

là ln đăng nhập để căn e hoặc 2 và là này max-load thức đúng đắn và lớn như thế nào nên n được để chạy một thử nghiệm?

Bài giảng này dường như đề cập đến nó tốt nhất, nhưng tôi không phải là nhà toán học.

http://pages.cs.wisc.edu/~shuchi/courses/787-F07/scribe-notes/lecture07.pdf

BTW, with high probability dường như có nghĩa 1 - 1/n.

Answer 1

Đó là một bài báo/bài giảng hấp dẫn-- làm cho tôi ước tôi đã thực hiện một số lớp thuật toán chính thức.

Tôi sẽ tham gia một số câu trả lời tại đây, dựa trên những gì tôi vừa đọc từ đó và cảm thấy tự do bỏ phiếu cho tôi. Tuy nhiên, tôi sẽ đánh giá cao sự điều chỉnh, thay vì chỉ là một downvote :) Tôi cũng sẽ sử dụng n và N thay thế cho nhau ở đây, đó là một không lớn trong một số vòng kết nối, nhưng vì tôi chỉ sao chép công thức, tôi hy vọng bạn sẽ tha thứ cho tôi.

Đầu tiên, cơ sở của nhật ký. Những con số này được đưa ra dưới dạng ký hiệu big-O, không phải là công thức tuyệt đối. Điều đó có nghĩa là bạn đang tìm kiếm thứ gì đó 'theo thứ tự ln (n)/ln (ln (n))', không phải với kỳ vọng của một câu trả lời tuyệt đối, nhưng nhiều hơn khi n trở nên lớn hơn, mối quan hệ của n với số va chạm tối đa phải theo công thức đó. Các chi tiết của đường cong thực tế mà bạn có thể vẽ sẽ thay đổi theo cách thực hiện (và tôi không biết đủ về các triển khai thực tế để cho bạn biết đường cong 'tốt' là gì, ngoại trừ việc nó nên theo mối quan hệ lớn-O đó). Hai công thức mà bạn đã đăng thực sự tương đương với ký hiệu big-O. 3 trong công thức thứ hai chỉ là một hằng số và có liên quan đến việc triển khai cụ thể. Một triển khai kém hiệu quả sẽ có một hằng số lớn hơn. Với ý nghĩ đó, tôi sẽ chạy thử nghiệm thực nghiệm, bởi vì tôi là một nhà sinh vật học ở tim và tôi được đào tạo để tránh chứng minh cứng và nhanh như là dấu hiệu cho thấy thế giới thực sự hoạt động như thế nào.Bắt đầu với N như một số, nói 100, và tìm thấy thùng rác với số va chạm lớn nhất trong đó. Đó là tải trọng tối đa của bạn cho lần chạy đó. Bây giờ, các ví dụ của bạn nên càng gần với những gì bạn mong đợi người dùng thực sự sử dụng, vì vậy có thể bạn muốn lấy ngẫu nhiên các từ từ một từ điển hoặc một cái gì đó tương tự như đầu vào của bạn.

Chạy thử nghiệm đó nhiều lần, ít nhất 30 hoặc 40. Vì bạn đang sử dụng số ngẫu nhiên, bạn sẽ cần phải thỏa mãn bản thân rằng tải trọng tối đa trung bình bạn đang nhận được gần với 'kỳ vọng' lý thuyết của thuật toán của bạn. Kỳ vọng chỉ là trung bình, nhưng bạn vẫn sẽ cần phải tìm nó, và chặt chẽ hơn của bạn std dev/std err về trung bình đó, bạn càng có thể nói rằng trung bình thực nghiệm của bạn phù hợp với kỳ vọng lý thuyết. Một chạy là không đủ, bởi vì một lần chạy thứ hai sẽ (rất có thể) đưa ra một câu trả lời khác.

Sau đó, tăng N, để nói, 1000, 10000, v.v. Tăng nó theo lôgarit, bởi vì công thức của bạn là logarit. Khi N tăng, tải trọng tối đa của bạn sẽ tăng theo thứ tự ln (n)/ln (ln (n)). Nếu nó tăng với tốc độ 3 * ln (n)/ln (ln (n)), điều đó có nghĩa là bạn đang theo dõi lý thuyết mà chúng đưa ra trong bài giảng đó.

Loại thử nghiệm thực nghiệm này cũng sẽ cho bạn thấy nơi tiếp cận của bạn bị hỏng. Nó có thể là thuật toán của bạn hoạt động tốt cho N < 10 triệu (hoặc một số số khác), nhưng trên đó, nó bắt đầu sụp đổ. Tại sao điều đó có thể? Có lẽ bạn có một số hạn chế đối với 32 bit trong mã của bạn mà không nhận ra nó (ví dụ: sử dụng 'float' thay vì 'double') hoặc một số chi tiết triển khai khác. Những loại chi tiết này cho bạn biết mã của bạn sẽ hoạt động tốt ở đâu trong thực tế và sau đó khi nhu cầu thực tế của bạn thay đổi, bạn có thể sửa đổi thuật toán của mình. Có thể làm cho thuật toán hoạt động cho các bộ dữ liệu rất lớn khiến cho các bộ dữ liệu rất kém hiệu quả, hoặc ngược lại, vì vậy xác định rằng sự cân bằng sẽ giúp bạn mô tả thêm cách bạn có thể điều chỉnh thuật toán của mình cho các tình huống cụ thể. Luôn luôn là một kỹ năng hữu ích để có.

EDIT: một bằng chứng về lý do tại sao các cơ sở của hàm log không quan trọng với ký hiệu lớn-O:

log N = log_10 (N) = log_b (N)/log_b (10)= (1/log_b(10)) * log_b(N) 

1/log_b (10) là một hằng số, và trong ký hiệu lớn-O, hằng số được bỏ qua. Thay đổi cơ sở là miễn phí, đó là lý do tại sao bạn đang gặp phải sự thay đổi như vậy trong các giấy tờ.

Answer 2

Sau một số nghiên cứu và thử nghiệm-và-lỗi, tôi nghĩ rằng tôi có thể cung cấp một cái gì đó một phần cách để trả lời.

1. Để bắt đầu, ln và log dường như tham khảo để đăng nhập cơ sở-e nếu bạn nhìn vào toán học đằng sau lý thuyết này. Nhưng như mmr chỉ ra, đối với O (...) ước tính, nó không quan trọng.

2. max-load có thể được xác định cho bất kỳ xác suất nào bạn muốn. Công thức điển hình sử dụng là

   1-1/n ** c

Hầu hết các giấy tờ về việc sử dụng chủ đề

1-1/n 

Một ví dụ có thể là đơn giản nhất.

Giả sử bạn có bảng băm gồm 1000 vị trí và bạn muốn băm 1000 thứ. Giả sử bạn cũng muốn biết số max-load với xác suất 1-1/1000 hoặc 0.999.

max-load là số lượng giá trị băm tối đa kết thúc bằng nhau - nghĩa là. va chạm (giả sử hàm băm của bạn là tốt).

Sử dụng công thức cho khả năng nhận được chính xác k băm giống hệt đánh giá cao

Pr[ exactly k ] = ((e/k)**k)/e 

sau đó bằng cách tích lũy xác suất chính xác 0..k mục cho đến khi tổng số lớn hơn hoặc bằng 0.999 nói với bạn rằng k là max-load.

ví dụ:

Pr[0] = 0.37 
Pr[1] = 0.37 
Pr[2] = 0.18 
Pr[3] = 0.061 
Pr[4] = 0.015 
Pr[5] = 0.003  // here, the cumulative total is 0.999 
Pr[6] = 0.0005 
Pr[7] = 0.00007 

Vì vậy, trong trường hợp này, max-load là 5.

Vì vậy, nếu hàm băm của tôi hoạt động tốt trên tập hợp dữ liệu thì tôi nên mong đợi số lượng giá trị băm giống hệt nhau (hoặc va chạm) là 5.

Nếu nó không phải là thì đây có thể là do các nguyên nhân sau:

1. Dữ liệu của bạn có giá trị nhỏ (như chuỗi ngắn) mà băm để cùng giá trị. Bất kỳ giá trị băm nào của một ký tự ASCII sẽ chọn 1 trong 128 giá trị băm (có nhiều cách xung quanh điều này. Ví dụ bạn có thể sử dụng nhiều hàm băm, nhưng làm chậm băm và tôi không biết nhiều về điều này).

2. Hàm băm của bạn không hoạt động tốt với dữ liệu của bạn - hãy thử với dữ liệu ngẫu nhiên.

3. Hàm băm của bạn không hoạt động tốt.

Các thử nghiệm khác tôi đã đề cập trong câu hỏi của tôi cũng hữu ích khi thấy hàm băm của bạn đang chạy như mong đợi.

Ngẫu nhiên, hàm băm của tôi hoạt động tốt - ngoại trừ các chuỗi ngắn (1..4 ký tự).

Tôi cũng đã triển khai phiên bản bảng phân tách đơn giản đặt giá trị băm vào vị trí được sử dụng ít nhất từ ​​lựa chọn 2 vị trí. Điều này hơn một nửa số va chạm và có nghĩa là thêm và tìm kiếm bảng băm chậm hơn một chút.

Tôi hy vọng điều này sẽ hữu ích.

Answer 3

Đây là một khởi đầu khó khăn cho giải pháp của vấn đề này liên quan đến phân phối đồng đều và tải trọng tối đa.

Thay vì thùng và quả bóng hoặc bình hoặc hộp hoặc xô hoặc m và n, người (p) và cửa ra vào (d) sẽ được sử dụng làm chỉ định.

Có giá trị kỳ vọng chính xác cho mỗi cửa được cung cấp cho một số lượng người nhất định. Ví dụ, với 5 người và 5 cửa, cửa tối đa dự kiến ​​chính xác là 1.2864 {(1429-625)/625} trên giá trị trung bình (p/d) và cửa tối thiểu chính xác là -0,9616 {(24-625)/625 } bên dưới giá trị trung bình. Giá trị tuyệt đối của khoảng cách cửa cao nhất từ ​​trung bình là lớn hơn một chút so với cửa nhỏ nhất bởi vì tất cả mọi người có thể đi qua một cánh cửa, nhưng không ít hơn 0 có thể đi qua một trong những cánh cửa.Với số lượng người lớn (p/d> 3000), sự khác biệt giữa giá trị tuyệt đối của khoảng cách cửa cao nhất từ ​​cửa trung bình và cửa thấp nhất trở nên không đáng kể.

Đối với một số lẻ cửa, cửa trung tâm về cơ bản là không và không thể mở rộng, nhưng tất cả các cửa khác có thể mở rộng từ các giá trị nhất định đại diện cho p = d. Những giá trị làm tròn cho d = 5 là:

-1,163 -0,495 0 * 0,495 1,163 * chầm chậm tiến tới zero từ -0,12

Từ những giá trị này, bạn có thể tính toán số lượng dự kiến ​​của mọi người đối với bất kỳ số lượng người đi qua mỗi 5 cánh cửa, bao gồm cánh cửa tối đa. Ngoại trừ cánh cửa được đặt giữa, sự khác biệt so với giá trị trung bình có thể mở rộng bằng sqrt (p/d).

Vì vậy, đối với p = 50.000 và d = 5:
Số lượng người mong đợi đi qua cửa tối đa, có thể là bất kỳ trong số 5 cửa, = 1.163 * sqrt (p/d) + p/d. = 1.163 * sqrt (10.000) + 10.000 = 10,116.3 Đối với p/d < 3,000, kết quả từ phương trình này phải được tăng nhẹ.

Với nhiều người hơn, cửa giữa từ từ trở nên gần hơn và gần bằng không từ -0.11968 ở p = 100 và d = 5. Nó luôn luôn có thể được làm tròn lên đến số không và giống như 4 cửa khác có khá khác biệt.

Các giá trị trong vòng 6 cửa là: -1,272 -0,643 -0,202 0,202 0,643 1,272

Đối với 1000 cửa ra vào, các giá trị tương đối như sau: -3,25, -2,95, -2,79 ... 2,79, 2,95, 3,25

Đối với bất kỳ d và p nào, có giá trị kỳ vọng chính xác cho mỗi cửa được đặt hàng. Hy vọng rằng, một xấp xỉ tốt (với một lỗi tương đối < 1%) tồn tại. Một số giáo sư hoặc nhà toán học ở đâu đó phải biết.

Để thử nghiệm phân phối đồng đều, bạn sẽ cần một số phiên đặt hàng trung bình (750-1000 hoạt động tốt) thay vì số lượng người nhiều hơn. Không có vấn đề gì, sự chênh lệch giữa các phiên hợp lệ là rất lớn. Đó là bản chất của sự ngẫu nhiên. Va chạm là không thể tránh khỏi. *

Giá trị dự kiến ​​cho 5 và 6 cửa được tính bằng cách tính toán sức mạnh tuyệt đối bằng cách sử dụng số nguyên 640 bit và tính trung bình sự hội tụ của giá trị tuyệt đối của cửa đối diện tương ứng. Ví d = 5 và p = 170: -6,63901 -2,95905 -0,119342 2,81054 6,90686 (27,36099 31,04095 33,880658 36,81054 40,90686) Ví d = 6 và p = 108: -5,19024 -2,7711 -0,973979 0,734434 2,66716 5,53372 (12,80976 15.2289 17.026021 18.734434 20.66716 23.53372)

Tôi hy vọng rằng bạn có thể phân phối đồng đều dữ liệu của mình.

• Nó gần như đảm bảo rằng tất cả các con trai của George Foreman hoặc một số tình huống tương tự sẽ chiến đấu chống lại hàm băm của bạn. Và kế hoạch ngẫu nhiên phù hợp là công việc của tất cả các lập trình viên giỏi.