Hợp nhất các tập khổng lồ (HashSet) trong Scala

Question

Tôi có hai tập hợp lớn (như trong hàng triệu mục nhập) (HashSet) có một số (< 10%) chồng lên nhau giữa chúng. Tôi cần phải hợp nhất chúng thành một bộ (tôi không quan tâm đến việc duy trì các bộ gốc).

Hiện nay, tôi đang bổ sung thêm tất cả các mục của một bộ để người kia với:

setOne ++= setTwo 

này phải mất vài phút để hoàn thành (sau nhiều nỗ lực hashCode chỉnh() trên các thành viên).

Bất kỳ ý tưởng nào về cách tăng tốc mọi thứ?

Answer 1

Bạn có thể có được hiệu suất tốt hơn một chút với Parallel Collections API trong Scala 2.9.0+:

setOne.par ++ setTwo 

hoặc

(setOne.par /: setTwo)(_ + _) 

Answer 2

Có một vài điều bạn có thể muốn thử:

• Sử dụng phương pháp sizeHint để giữ bộ của bạn ở kích thước mong muốn.
• Gọi useSizeMap(true) trên đó để giảm kích thước bảng băm tốt hơn.

Dường như với tôi rằng tùy chọn thứ hai cho kết quả tốt hơn, mặc dù cả hai đều hiển thị các cải tiến đối với các thử nghiệm tại đây.

Answer 3

Bạn có thể cho tôi biết thêm một chút về dữ liệu bên trong các bộ không? Lý do tôi hỏi là vì điều này, bạn thường muốn một thứ gì đó chuyên biệt. Dưới đây là một số điều có thể được thực hiện:

• Nếu dữ liệu được sắp xếp, bạn có thể đi bộ để kết hợp, tương tự với những gì được thực hiện bằng cách phối hợp. Thao tác này khá song song tầm thường vì bạn có thể phân vùng một tập hợp dữ liệu và sau đó phân vùng tập dữ liệu thứ hai bằng cách sử dụng tìm kiếm nhị phân để tìm ranh giới chính xác.
• Nếu dữ liệu nằm trong một phạm vi số nhất định, bạn có thể sử dụng bitet và chỉ cần đặt bit bất cứ khi nào bạn gặp phải số đó.
• Nếu một trong các tập dữ liệu nhỏ hơn bộ kia, bạn có thể đặt nó trong bộ băm và lặp lại nhanh hơn tập dữ liệu khác, kiểm tra xem có ngăn chặn hay không.

Tôi đã sử dụng chiến lược đầu tiên để tạo ra một tập khổng lồ khoảng 8 triệu số nguyên từ khoảng 40 nghìn tập nhỏ hơn trong khoảng một giây (trên phần cứng mạnh mẽ, ở Scala).