Có nhiều trường hợp việc tạo số ngẫu nhiên là hữu ích – trò chơi máy tính là một ví dụ điển hình, phân tích thống kê, mật mã và nhiều thứ khác Show Việc tạo ra mỗi số ngẫu nhiên thường có thể được coi là một sự kiện duy nhất. Đó là, nó không liên quan đến các sự kiện trong quá khứ hoặc tương lai. Nếu chúng ta tưởng tượng tung một con xúc xắc, thì mỗi lần tung xúc xắc là một sự kiện duy nhất và có cơ hội bằng nhau để trở thành bất kỳ số hợp lệ nào bất kể tất cả các lần tung xúc xắc trước đó Tuy nhiên, trong một số trường hợp, chúng tôi muốn hạn chế các số ngẫu nhiên của mình. Một ràng buộc phổ biến đảm bảo rằng số chính xác không bao giờ được tạo nhiều hơn một lần. Ví dụ: nếu chúng tôi mô phỏng một cỗ bài được xáo trộn hoặc chọn các bài hát từ danh sách phát, chúng tôi muốn đảm bảo rằng mỗi bài được chọn chính xác một lần Trong hướng dẫn này, chúng ta sẽ tìm hiểu về một số kỹ thuật để dễ dàng cho phép chúng ta tạo các số ngẫu nhiên sao cho mỗi số chỉ được tạo một lần 2. Lịch sử ghi âmCách dễ nhất để đạt được điều này là ghi lại tất cả các sự kiện trong quá khứ và so sánh bất kỳ số mới nào với tập hợp đó. Bằng cách này, chúng tôi có thể chắc chắn rằng mọi số được tạo chưa bao giờ được nhìn thấy trước đây  Chúng ta có thể thấy rõ rằng điều này sẽ không bao giờ trả về cùng một số hai lần – mỗi khi chúng ta yêu cầu một số mới, nó sẽ tiếp tục lặp lại cho đến khi chọn ngẫu nhiên một số chưa từng thấy trước đó, ghi lại trong lịch sử và chỉ trả lại số đó Tuy nhiên, nó sẽ rất kém hiệu quả về cả thời gian và bộ nhớ sử dụng. Số đầu tiên được tạo sẽ là số duy nhất vì chúng tôi chưa từng thấy số nào trước đây. Tuy nhiên, vào thời điểm chúng tôi tạo số 100, chúng tôi hiện đang lưu trữ 99 giá trị trước đó, chúng tôi phải kiểm tra xem có bất kỳ số nào trong số 99 số đó khớp với số chúng tôi vừa tạo hay không và chúng tôi cần tiếp tục tạo số cho đến số mới này Khi chúng tôi đạt đến giới hạn số lượng chúng tôi đang tạo, quá trình này sẽ ngày càng chậm hơn. Trên thực tế, thuật toán hoạt động trong thời gian O(2n). Nếu chúng tôi đang cố gắng tạo 100 số duy nhất trong phạm vi 1-100, số cuối cùng sẽ phải là số duy nhất chưa được nhìn thấy, có thể mất một khoảng thời gian không xác định để tạo 3. Các số trước khi xáo trộnKết quả của thuật toán trước đây của chúng tôi là bộ sưu tập lịch sử là một danh sách các số được xáo trộn hoàn toàn. Vì điều này, một giải pháp thay thế chúng ta có là đảo ngược thuật toán. Trước tiên, chúng tôi có thể tạo một danh sách các số được xáo trộn, sau đó việc tạo các số ngẫu nhiên của chúng tôi được thực hiện bằng cách lấy số tiếp theo từ danh sách này Ngay lập tức chúng ta có thể thấy rằng việc tạo từng số sẽ hiệu quả. Nó chỉ lấy số tiếp theo từ một danh sách, đó là phép toán O(1). Tuy nhiên, chúng tôi có chi phí trả trước đắt đỏ khi tạo danh sách được xáo trộn. Trên thực tế, nếu chúng tôi đang tạo ra một số lượng giá trị tương đối nhỏ từ một tập hợp lớn hơn, thì chi phí trả trước này sẽ chi phối 4. Xáo trộn trong quá trình tạoCho đến nay, chúng tôi đã thấy hai thuật toán, một thuật toán có chi phí trả trước đáng kể và cách tạo số hiệu quả, trong khi thuật toán kia không có chi phí trả trước nhưng rất tốn kém để tạo số. Tuy nhiên, chúng ta có thể kết hợp những thứ này để không tốn chi phí trả trước mà vẫn hiệu quả trong việc tạo số Chúng tôi thực hiện việc này bằng cách xáo trộn các số khi chúng tôi tạo các số ngẫu nhiên, thay vì thực hiện trước. Điều này được thực hiện bằng cách theo dõi số lượng số chúng tôi đã tạo cho đến nay và đối với mỗi số mới, chúng tôi chọn một số ngẫu nhiên từ tập hợp chưa sử dụng, hoán đổi nó thành tập hợp đã sử dụng rồi trả lại Điều này có vẻ phức tạp hơn trước đó, vì vậy hãy thực hiện theo cách của chúng tôi bằng cách tạo một vài số ngẫu nhiên và xem nó hoạt động như thế nào Để bắt đầu, chúng tôi tạo một danh sách các số và đặt số lượng của chúng tôi trỏ đến cuối danh sách Bây giờ chúng ta sẽ tạo số ngẫu nhiên đầu tiên. Chúng tôi chọn một chỉ số ngẫu nhiên giữa 0 và số lượng của chúng tôi – 10. Trong trường hợp này, chúng tôi đã chọn "1". Bây giờ, chúng tôi giảm số lượng của mình - sao cho nó chỉ còn 1 điểm cuối - và sau đó hoán đổi chỉ mục đã tạo của chúng tôi cho chỉ mục mà bộ đếm của chúng tôi đang trỏ tới. Sau đó, chúng tôi trả lại số mà bộ đếm của chúng tôi đang trỏ đến Vì vậy, bây giờ chúng tôi đã tạo số ngẫu nhiên đầu tiên của mình - “2” - và chúng tôi còn lại chín số để chọn Vì vậy, hãy làm điều đó một lần nữa. Lần này, chúng tôi chọn ngẫu nhiên "5", vì vậy chúng tôi sẽ giảm số lượng của mình, hoán đổi các giá trị của chúng tôi và trả lại chúng Điều quan trọng cần lưu ý là thứ tự chúng tôi tạo chỉ mục và giảm số lượng của chúng tôi đảm bảo rằng chúng tôi có thể chọn bất kỳ số nào còn lại. Ví dụ: hãy tưởng tượng chỉ số ngẫu nhiên tiếp theo của chúng tôi là “7” Sau đó, chúng tôi sẽ giảm số lượng, hoán đổi chỉ mục được tạo ngẫu nhiên “7” cho mục tiêu bộ đếm mới của chúng tôi là “7”, sau đó trả lại giá trị “8” hiện có trong chỉ mục này cho người gọi Cuối cùng, chúng ta sẽ rơi vào tình huống chúng ta chọn cùng một chỉ số ngẫu nhiên như trước đây. Nhưng điều đó không sao vì chỉ mục đó hiện có một số khác - mà chúng tôi chưa sử dụng - trong đó, vì vậy việc sử dụng số đó vẫn sẽ tạo ra một số duy nhất Ví dụ: nếu bây giờ chúng tôi chọn lại chỉ mục “1” một cách ngẫu nhiên. Điều này thực sự chứa số “10” – bởi vì nó đã được hoán đổi khi nó được sử dụng lần đầu tiên. Vì vậy, lần này, chúng tôi sẽ hoán đổi số “10” vào đúng vị trí - hiện đang chứa số "7" - và sau đó trả lại số "10". Vì vậy, chúng tôi đã tạo thành công một số duy nhất khác Vì vậy, bây giờ chúng tôi có một thuật toán sẽ tạo ra các số ngẫu nhiên duy nhất trong thời gian O(1), nhưng không có chi phí trả trước cao cho việc xáo trộn các số trước 5. Chúng ta có thể làm tốt hơn không?Cho đến nay, chúng ta đã thảo luận về một thuật toán sẽ tạo ra các số ngẫu nhiên duy nhất trong thời gian O(1), điều này thật tuyệt vời. Tuy nhiên, nó vẫn cần phải sử dụng bộ nhớ đáng kể. Nó yêu cầu một mảng đủ lớn cho mọi số chúng tôi có thể tạo và bộ đếm cho số lượng chúng tôi đã tạo cho đến nay Trong các trường hợp nhỏ, việc sử dụng bộ nhớ này là không đáng kể. Ví dụ: nếu chúng ta chỉ muốn tạo các số để biểu thị các quân bài, thì chúng ta cần bộ nhớ để lưu 53 (52 quân bài + bộ đếm) số. Sử dụng các số 32 bit để thuận tiện, lớn hơn nhiều so với mức cần thiết, sẽ dẫn đến 212 byte bộ nhớ Tuy nhiên, thay vào đó, nếu chúng ta muốn có thể tạo bất kỳ số nguyên 32 bit nào thì sao? . Điều này có nghĩa là chúng ta cần (232+1)*4 byte bộ nhớ, tức là ~16GB Vì vậy, làm thế nào để chúng ta tránh điều này? . Điều này có nghĩa là chúng ta không thể sử dụng thuật toán thứ hai hoặc thứ ba mà chúng ta đã thấy ở đây. Chúng tôi có thể sử dụng cái đầu tiên vì nó chỉ lưu trữ các số được tạo. Điều đó có nghĩa là việc sử dụng bộ nhớ của chúng tôi bị giới hạn bởi tập hợp số chúng tôi đã tạo, không phải tập hợp số chúng tôi có thể tạo từ Có một số tùy chọn thay thế có thể được sử dụng – ví dụ: tạo hàm băm mật mã của bộ đếm. Tuy nhiên, các thuật toán này tốt nhất chỉ là giả ngẫu nhiên, có thể sẽ đủ tốt cho hầu hết các mục đích sử dụng. Chúng tôi cũng không thể đảm bảo rằng các số này là duy nhất nếu chúng tôi không có lịch sử về những gì chúng tôi đã tạo trước đó 6. Bản tóm tắtỞ đây, chúng ta đã thấy một số thuật toán có thể tạo các số ngẫu nhiên duy nhất từ tập hợp mong muốn, với các tùy chọn tối ưu hóa cho việc sử dụng bộ nhớ, thời gian thực thi và độ phức tạp của mã Trong hầu hết các trường hợp này, chúng tôi giả định rằng chúng tôi có nguồn số ngẫu nhiên thực sự - ví dụ: /dev/random trên Linux có nhóm entropy cơ bản, do đó ngẫu nhiên hơn đáng kể so với nhiều lựa chọn khác. Tuy nhiên, chúng sẽ hoạt động hoàn toàn tốt bất kể chất lượng của nguồn số ngẫu nhiên như thế nào – điểm khác biệt duy nhất là chất lượng của đầu ra sẽ liên quan trực tiếp đến chất lượng của đầu vào Vì vậy, lần tới khi bạn cần sử dụng các số ngẫu nhiên và đảm bảo chúng không lặp lại, tại sao không xem xét một trong số này tác giả dưới cùng Nếu bạn có một vài năm kinh nghiệm trong Khoa học máy tính hoặc nghiên cứu và bạn muốn chia sẻ kinh nghiệm đó với cộng đồng, hãy xem Nguyên tắc đóng góp của chúng tôi |
