Lấy phần tử ngẫu nhiên từ C# HashSet nhanh chóng

Question

Tôi cần lưu trữ một tập hợp các phần tử. Những gì tôi cần chức năng để

1. remove (duy nhất) các yếu tố và
2. add (bộ) các yếu tố và
3. mỗi đối tượng chỉ phải ở trong các thiết lập một lần và
4. có được một yếu tố ngẫu nhiên từ thiết

tôi đã chọn HashSet (C#) vì nó thể thao nhanh phương pháp để loại bỏ các yếu tố (hashSet.remove (element)), thêm bộ (hashSet.UnionWith (anotherHashSet)) và bản chất của một HashSet đảm bảo rằng không có bản sao, vì vậy yêu cầu 1 đến 3 được thực hiện.

Cách duy nhất tôi tìm thấy để có được một yếu tố ngẫu nhiên là

Object object = hashSet.ElementAt(rnd.Next(hashSet.Count)); 

Nhưng điều này là rất chậm, kể từ khi tôi gọi nó là một lần cho mỗi điểm ảnh của bản đồ của tôi (tạo ra một điền lũ ngẫu nhiên từ nhiều điểm khởi đầu; bản đồ hóa 500x500 tại thời điểm này nhưng tôi muốn đi lớn hơn) và hashset giữ khá nhiều mục. (Một thử nghiệm nhanh cho thấy nó thổi lên đến 5752 mục trước khi thu hẹp lại.)

Hồ sơ (lấy mẫu CPU) cho tôi biết các cuộc gọi ElementAt của tôi chiếm hơn 50%.

Tôi nhận thấy hoạt động 500x500 trên băm lớn không phải là nhiệm vụ dễ dàng, nhưng các thao tác khác (Remove và UnionWith) được gọi thường xuyên là ElementAt, vì vậy vấn đề chính dường như là hoạt động chứ không phải số lượng cuộc gọi.

Tôi mơ hồ hiểu tại sao nhận một yếu tố nhất định từ HashSet là rất tốn kém (khi so sánh với nó từ danh sách hoặc cấu trúc dữ liệu được sắp xếp khác, nhưng tôi chỉ muốn chọn ngẫu nhiên. không có cách nào xung quanh nó? có một cấu trúc dữ liệu tốt hơn cho mục đích của tôi?

Thay đổi tất cả mọi thứ để Lists không giúp vì bây giờ các phương pháp khác trở nên tắc nghẽn và phải mất nhiều thời gian hơn.

đúc HashSet đến một mảng và chọn phần tử ngẫu nhiên của tôi từ đó dự kiến ​​sẽ không giúp đỡ bởi vì trong khi chọn một phần tử ngẫu nhiên từ một mảng là nhanh chóng, đúc hashset vào mảng ở vị trí đầu tiên mất nhiều thời gian hơn chạy hashSet.ElementAt một mình.

Nếu bạn muốn hiểu rõ hơn về những gì tôi đang cố gắng để làm: A link to my question and the answer.

Answer 1

Vấn đề cơ bản là việc lập chỉ mục.

Trong một mảng hoặc danh sách, dữ liệu được lập chỉ mục bởi coördinate của nó - thường chỉ là một chỉ mục int đơn giản. Trong một số HashSet, bạn tự mình chọn chỉ mục - khóa. Tuy nhiên, tác dụng phụ là không có yếu tố "coördinate" - câu hỏi "ở chỉ số 3" không có ý nghĩa. Cách nó thực sự được thực hiện là toàn bộ HashSet được liệt kê, mục sau mục và mục thứ n được trả về. Điều này có nghĩa rằng để có được mục thứ 1000, bạn phải liệt kê tất cả 999 mục trước đó. Điều này đau.

Cách tốt nhất để giải quyết vấn đề này là chọn ngẫu nhiên dựa trên khóa thực tế của HashSet.Tất nhiên, điều này chỉ hoạt động nếu nó hợp lý để chọn các phím ngẫu nhiên giống như vậy.

Nếu bạn không thể chọn khóa ngẫu nhiên theo cách thỏa đáng, bạn có thể muốn giữ hai danh sách riêng biệt - bất cứ khi nào bạn thêm mục mới vào HashSet, hãy thêm khóa của nó vào List<TKey>; sau đó bạn có thể dễ dàng chọn một khóa ngẫu nhiên từ List và theo dõi nó. Tùy thuộc vào yêu cầu của bạn, bản sao có thể không có nhiều vấn đề.

Và tất nhiên, bạn có thể tiết kiệm trên ElementAt enumerations nếu bạn chỉ làm kiểu liệt kê một lúc - ví dụ, trước khi tìm kiếm trên HashSet, bạn có thể chuyển nó sang List. Điều này chỉ có ý nghĩa nếu bạn chọn nhiều chỉ mục ngẫu nhiên cùng một lúc, tất nhiên (ví dụ nếu bạn chọn 5 chỉ số ngẫu nhiên cùng một lúc, bạn sẽ tiết kiệm được khoảng 1/5 thời gian trung bình) - nếu bạn luôn luôn chọn một, sau đó sửa đổi các HashSet và chọn một, nó sẽ không giúp đỡ.

Tùy thuộc vào trường hợp sử dụng chính xác của bạn, bạn cũng có thể xem giá trị SortedSet. Nó hoạt động theo cách tương tự như HashSet, nhưng nó duy trì thứ tự trong các phím. Phần hữu ích là bạn có thể sử dụng phương thức GetViewBetween để có được toàn bộ các khóa - bạn có thể sử dụng điều này khá hiệu quả nếu các khóa của bạn thưa thớt, nhưng cũng cân bằng giữa các phạm vi tùy ý. Trước tiên, bạn chỉ cần chọn một phạm vi ngẫu nhiên, sau đó lấy các mục trong phạm vi với GetViewBetween và chọn một mục ngẫu nhiên trong số đó. Trong thực tế, điều này sẽ cho phép bạn phân vùng kết quả tìm kiếm, và nên tiết kiệm khá nhiều thời gian.

Answer 2

Tôi nghĩ rằng OrderedDictionary có thể phù hợp với mục đích của bạn:

var dict = new OrderedDictionary(); 

dict.Add("My String Key", "My String"); 
dict.Add(12345, 54321); 

Console.WriteLine(dict[0]); // Prints "My String" 
Console.WriteLine(dict[1]); // Prints 54321 

Console.WriteLine(dict["My String Key"]); // Prints "My String" 
Console.WriteLine(dict[(object)12345]); // Prints 54321 (note the need to cast!) 

này đã nhanh chóng thêm và loại bỏ, và O (1) lập chỉ mục. Tuy nhiên, nó chỉ hoạt động với các khóa và giá trị object - không có phiên bản chung.