Tôi có một vấn đề về thuật toán trong tay. Để giải thích điều này một cách dễ dàng, tôi sẽ sử dụng một phép loại suy đơn giản. Tôi có một tập tin đầu vào

Quốc gia, Xuất khẩu
Australia,Cừu
Mỹ, táo
Austrialia, Thịt Bò

Mục tiêu cuối cùng: Tôi phải tìm ra sản phẩm chung giữa các cặp quốc gia, vì vậy

{"Austrailia,New Zealand"}:{"apple","sheep}
{"Áo,Mỹ"}:{"apple"}
{"New Zealand","US"}:{"apple","sữa"}

quá trình:

Tôi đọc dữ liệu đầu vào và lưu nó trong TreeMap > List, chuỗi này đang được giữ lại do có nhiều bản sao. Về cơ bản, tôi tổng hợp theo quốc gia. Trong đó Key là quốc gia và Value là xuất khẩu của quốc gia đó.

{"australia":{"apple","sheep","koalas"}}
{"new zealand":{"táo","cừu","sữa"}}
{"US":{"táo","thịt bò","sữa"}}

Tôi có khoảng 1200 khóa (quốc gia) và tổng số giá trị (xuất khẩu) là 80 triệu. Tôi sắp xếp tất cả các giá trị cho từng khóa:

{"austrailia":{"apple","sheep","koalas"}} -- > {"austrailia":{"apple","koalas","sheep"}}

Việc này nhanh vì chỉ có 1200 danh sách cần sắp xếp.

cho (k1: phím)
   cho (k2: phím)
        if(k1.compareTo(k2) <0){ //Không muốn so sánh gấp đôi
    List intersectList = intersectList_func(xuất của k1, xuất của k2);
        countrypair.put({k1,k2},intersectList)
}

Khối mã này mất quá nhiều thời gian. Tôi nhận ra đó là O(n2) và so sánh khoảng 1200*1200. Vậy là nó đã chạy được gần 3 tiếng rồi..có cách nào để tôi tăng tốc hoặc tối ưu hóa nó không. Thuật toán khôn ngoan là lựa chọn tốt nhất hoặc có những kỹ thuật khác cần xem xét.

biên tập:Vì cả hai Danh sách đều được sắp xếp trước, nên intersectList là O(n), trong đó n là độ dài của tầng(listOne.length,listTwo.length), không phải O(n2), như được giải thích bên dưới

Danh sách tĩnh riêng tư intersectList(List listOne,List listTwo){
        int i=0,j=0;
        Danh sách listResult = new LinkedList(); 
        while(i!=listOne.size() && j!=listTwo.size()){
            int soVal = listOne.get(i).compareTo(listTwo.get(j));
            if(so sánhVal==0){
                listResult.add(listOne.get(i));
                i++;j++;} }
            khác nếu (so sánhVal < 0) i++;
            khác nếu (so sánhVal >0) j++;   
        }
        danh sách trả vềResult;
    }

Cập nhật ngày 22 tháng 11Việc triển khai hiện tại của tôi vẫn chạy được gần 18 giờ. :|

Cập nhật ngày 25 tháng 11Tôi đã chạy triển khai mới theo đề xuất của Vikram và một số người khác. Nó đã chạy vào thứ Sáu tuần này. Câu hỏi của tôi là làm cách nào để tiết kiệm độ phức tạp tính toán bằng cách nhóm theo xuất khẩu thay vì quốc gia. Tôi thấy sự phức tạp là như nhau. Như Groo đã đề cập, tôi thấy rằng độ phức tạp của phần thứ hai là O(E*C^2), trong đó E là xuất khẩu và C là quốc gia.

câu trả lời hay nhất

Điều này có thể được thực hiện trong một câu lệnh dưới dạng tự tham gia bằng SQL:

dữ liệu thử nghiệm. Đầu tiên tạo một tập dữ liệu thử nghiệm:

Dòng <- "Quốc gia, Xuất khẩu
Australia,Cừu
Úc, Táo
New Zealand, Táo
New Zealand,Cừu
New Zealand,Sữa
Mỹ,Táo
Mỹ, Sữa
"
DF <- read.csv(văn bản = Dòng, as.is = TRUE)

sqldf bây giờ chúng tôi có DF Ra lệnh này:

thư viện (sqldf)
sqldf("select a.Country, b.Country, group_concat(Exports) Xuất khẩu
   từ DF a, DF b sử dụng (Xuất khẩu) 
   trong đó a.Quốc gia < b.Quốc gia
   nhóm theo a.Quốc gia, b.Quốc gia
")

đưa ra kết quả này:

      Quốc gia Xuất khẩu Quốc gia
1 Cừu Úc New Zealand, Táo
2 Úc Mỹ Táo
3 Táo, Sữa New Zealand Mỹ

với chỉ số Nếu quá chậm, hãy thêm chỉ mục vào cột Quốc gia (và nhớ đừng quên chủ yếu. phần:

sqldf(c("tạo chỉ mục idx trên DF(Quốc gia)",
   "chọn a.Country, b.Country, group_concat(Xuất khẩu) Xuất khẩu
   từ main.DF a, main.DF b sử dụng (Xuất khẩu) 
   trong đó a.Quốc gia < b.Quốc gia
   nhóm theo a.Quốc gia, b.Quốc gia
"))

Nếu không đủ bộ nhớ, hãy thêm tên db = tempfile() tham số sqldf để nó sử dụng đĩa.

Về java - PairWise khớp với hàng triệu bản ghi, chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/20116667/