java - PairWise 匹配数百万条记录

Question

我手头有一道算法题。为了容易解释这个问题，我将使用一个简单的类比。我有一个输入文件

Country,Exports
Austrailia,Sheep
US, Apple
Austrialia,Beef

最终目标:我必须找到国家对之间的共同产品，所以

{"Austrailia,New Zealand"}:{"apple","sheep}
{"Austrialia,US"}:{"apple"}
{"New Zealand","US"}:{"apple","milk"}

过程:

我读入输入并将其存储在 TreeMap > List 中，字符串由于许多重复项而被保留。本质上，我是按国家汇总的。其中 Key 是国家，Value 是它的导出。

{"austrailia":{"apple","sheep","koalas"}}
{"new zealand":{"apple","sheep","milk"}}
{"US":{"apple","beef","milk"}}

我有大约 1200 个键(国家)，值(导出)总数总共是 8000 万。我对每个键的所有值进行排序:

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

这很快，因为只有 1200 个列表需要排序。

for(k1:keys)
   for(k2:keys)
        if(k1.compareTo(k2) <0){ //Dont want to double compare
    List<String> intersectList = intersectList_func(k1's exports,k2's exports);
        countriespair.put({k1,k2},intersectList)
}

这个代码块花了这么长时间。我意识到它是 O(n2) 和大约 1200*1200 的比较。因此，到现在运行了将近 3 个小时..有什么办法，我可以加快或优化它。算法明智是最佳选择，或者是否有其他技术需要考虑。

编辑:由于两个 List 都是预先排序的，intersectList 是 O(n)，其中 n 是 floor(listOne.length,listTwo.length) 的长度，而不是 O(n2)，如下所述

private static List<String> intersectList(List<String> listOne,List<String> listTwo){
        int i=0,j=0;
        List<String> listResult = new LinkedList<String>(); 
        while(i!=listOne.size() && j!=listTwo.size()){
            int compareVal = listOne.get(i).compareTo(listTwo.get(j));
            if(compareVal==0){
                listResult.add(listOne.get(i));
                i++;j++;}               }
            else if(compareVal < 0) i++;
            else if (compareVal >0) j++;   
        }
        return listResult;
    }

11 月 22 日更新我当前的实现仍然运行了将近 18 个小时。 :|

11 月 25 日更新我已经按照 Vikram 和其他一些人的建议运行了新的实现。这个星期五一直在运行。我的问题是，按导出而非国家/地区分组如何节省计算复杂性。我发现复杂性是一样的。正如 Groo 提到的，我发现第二部分的复杂度是 O(E*C^2)，其中 E 是导出，C 是国家。

Answer 1

这可以作为使用 SQL 的自连接在一个语句中完成:

测试数据。首先创建一个测试数据集:

Lines <- "Country,Exports
Austrailia,Sheep
Austrailia,Apple
New Zealand,Apple
New Zealand,Sheep
New Zealand,Milk
US,Apple
US,Milk
"
DF <- read.csv(text = Lines, as.is = TRUE)

sqldf 现在我们有 DF 发出这个命令:

library(sqldf)
sqldf("select a.Country, b.Country, group_concat(Exports) Exports
   from DF a, DF b using (Exports) 
   where a.Country < b.Country
   group by a.Country, b.Country
")

给出这个输出:

      Country     Country     Exports
1  Austrailia New Zealand Sheep,Apple
2  Austrailia          US       Apple
3 New Zealand          US  Apple,Milk

with index 如果速度太慢，请将索引添加到 Country 列(并且一定不要忘记 main. 部分:

sqldf(c("create index idx on DF(Country)",
   "select a.Country, b.Country, group_concat(Exports) Exports
   from main.DF a, main.DF b using (Exports) 
   where a.Country < b.Country
   group by a.Country, b.Country
"))

如果内存不足，则添加 dbname = tempfile() sqldf 参数，以便它使用磁盘。