So sánh 10 triệu thực thể

Question

Tôi phải viết chương trình so sánh 10'000'000 + Đối tượng với nhau. Các thực thể về cơ bản là các hàng phẳng trong một tệp cơ sở dữ liệu/csv.

Thuật toán so sánh phải khá linh hoạt, dựa trên công cụ quy tắc trong đó người dùng cuối nhập quy tắc và mỗi đối tượng được đối sánh với mọi thực thể khác.

Tôi đang suy nghĩ về cách tôi có thể chia công việc này thành các khối lượng công việc nhỏ hơn nhưng tôi chưa tìm thấy bất kỳ điều gì. Kể từ khi các quy tắc được nhập bởi người dùng cuối, sắp xếp trước DataSet có vẻ không thể.

Điều tôi đang cố gắng làm bây giờ phù hợp với toàn bộ Số liệu trong bộ nhớ và xử lý từng mục. Nhưng đó không phải là hiệu quả cao và đòi hỏi xấp xỉ. 20 GB bộ nhớ (được nén).

Bạn có ý tưởng làm cách nào để chia nhỏ khối lượng công việc hoặc giảm kích thước của nó không?

Cảm ơn

Answer 1

Nếu quy tắc của bạn ở mức trừu tượng cao nhất (ví dụ: bất kỳ chức năng so sánh không xác định nào), bạn không thể đạt được mục tiêu của mình. 10^14 hoạt động so sánh sẽ chạy theo độ tuổi.

Nếu các quy tắc không hoàn toàn nói chung tôi thấy 3 giải pháp để tối ưu hóa các trường hợp khác nhau:

• nếu so sánh là bắc cầu và bạn có thể tính toán hash (ai đó đã khuyến cáo này), làm điều đó. Phát ban cũng có thể phức tạp, không chỉ các quy tắc của bạn =). Tìm hàm băm tốt và nó có thể giúp ích trong nhiều trường hợp.

• nếu các đối tượng có thể sắp xếp, hãy sắp xếp chúng. Vì mục đích này, tôi khuyên bạn không nên phân loại tại chỗ, nhưng xây dựng một mảng các chỉ mục (hoặc ID) của các mục. Nếu so sánh của bạn có thể được chuyển thành SQL (vì tôi hiểu dữ liệu của bạn nằm trong cơ sở dữ liệu), bạn có thể thực hiện điều này ở phía DBMS hiệu quả hơn và đọc các chỉ mục được sắp xếp (ví dụ 3,1,2, có nghĩa là mục có ID = 3 là thấp nhất, với ID = 1 là ở giữa và với ID = 2 là lớn nhất). Sau đó, bạn chỉ cần so sánh các phần tử liền kề.

• nếu mọi thứ có giá trị, tôi sẽ cố gắng sử dụng một số phân loại hoặc bẻ cong heuristical. Tôi có nghĩa là tôi sẽ tạo ra băm mà không nhất thiết phải xác định duy nhất các yếu tố bằng nhau, nhưng có thể chia tập dữ liệu của bạn trong các nhóm giữa đó chắc chắn không có một cặp yếu tố bằng nhau. Sau đó, tất cả các cặp bằng nhau sẽ nằm trong các nhóm bên trong và bạn có thể đọc từng nhóm một và thực hiện tính toán hàm phức tạp thủ công trong nhóm không 10 000 000, nhưng ví dụ 100 phần tử. Cách tiếp cận phụ khác là phân loại heuristical với mục đích tương tự để đảm bảo rằng các yếu tố bằng nhau không nằm trên các đầu khác nhau của tập dữ liệu. Sau đó bạn có thể đọc từng phần tử một và so sánh với 1000 phần tử trước đó, ví dụ (đã đọc và lưu trong bộ nhớ). Tôi sẽ giữ trong bộ nhớ cho ví dụ 1100 yếu tố và miễn phí lâu đời nhất 100 mỗi lần mới 100 đến. Điều này sẽ tối ưu hóa DB của bạn đọc. Việc thực hiện điều này cũng có thể có trong trường hợp quy tắc của bạn có chứa các quy tắc như (Attribute1 = Value1) AND (...) hoặc quy tắc như (Attribute1 < Value2) AND (...) hoặc bất kỳ quy tắc đơn giản nào khác. Sau đó, bạn có thể tạo cụm sao đầu tiên theo tiêu chí này và sau đó so sánh các mục trong các cụm được tạo.

Nhân tiện, quy tắc của bạn sẽ xem xét tất cả 10 000 000 phần tử bằng nhau? Bạn có muốn nhận 10^14 cặp kết quả không? Trường hợp này chứng minh rằng bạn không thể giải quyết nhiệm vụ này trong trường hợp chung. Hãy thử thực hiện một số hạn chế và giả định.

Answer 2

Tôi sẽ tạo mã băm từ mỗi thực thể. Bạn có thể phải loại trừ các id từ thế hệ băm và sau đó kiểm tra cho bằng. Nếu bạn có băm, bạn có thể đặt tất cả mã băm theo thứ tự bảng chữ cái. Có tất cả các thực thể theo thứ tự có nghĩa là nó khá dễ dàng để kiểm tra đôi.

Answer 3

Bạn đang tìm kiếm thuật toán phân loại phù hợp nhất, loại a, cho điều này? Tôi nghĩ rằng Divide và Concur có vẻ tốt. Nếu thuật toán có vẻ tốt, bạn có thể có nhiều cách khác để thực hiện phép tính. Xử lý song song đặc biệt bằng cách sử dụng MPICH hoặc một cái gì đó có thể cung cấp cho bạn một điểm đến cuối cùng.

Nhưng trước khi quyết định cách thực thi, bạn phải suy nghĩ xem thuật toán có phù hợp trước không.

Answer 4

Tôi sẽ cố gắng suy nghĩ về phân cấp quy tắc. Ví dụ: quy tắc A là "Màu" và quy tắc B là "Hình dạng".

Nếu bạn lần đầu tiên chia đối tượng theo màu, hơn không cần phải so sánh Vòng tròn màu đỏ với hình tam giác màu xanh lam.

Điều này sẽ giảm số lần so sánh bạn sẽ cần thực hiện.

Answer 5

Nếu bạn muốn so sánh từng thực thể với tất cả các thực thể hiệu quả hơn, bạn cần phải nhóm dữ liệu, có rất ít lý do để so sánh những thứ hoàn toàn không liên quan (so sánh Quần áo với con người không có ý nghĩa), tôi nghĩ quy tắc của bạn sẽ cố gắng để nhóm dữ liệu.

để bạn cần phải nhóm dữ liệu, hãy thử một số thuật toán phân cụm như K-Means.

Đồng thời xem, Apache Mahout