我希望优化一个相当简单的算法,目前是 O(n 2).我有一个记录文件,每个记录需要在同一个文件中相互比较.如果两者是'相同'(比较器功能非常复杂),则输出匹配的记录.请注意,可能存在多个彼此匹配的记录,并且没有顺序感 - 仅当匹配为True或False时.
伪代码:
For (outRec in sourceFile) {
Get new filePointer for targetFile //starting from the top of the file for inner loop
For (inRec in targetFile) {
if (compare(outRec, inRec) == TRUE ) {
write outRec
write inRec
}
increment some counters
}
increment some other counters
}
数据没有以任何方式排序,并且没有预处理可以订购数据.
关于如何成为低于O(n 2)的任何想法 ？我正在考虑在代码上应用MapReduce范例,分解外部和内部循环,可能使用链式Map函数.我很确定我已经在Hadoop上找到了代码,但是在我花时间编码之前想要检查替代方案.
建议赞赏!
补充:记录类型.基本上,我需要匹配名称/字符串.匹配类型如下例所示.
1,Joe Smith,Daniel Foster
2,Nate Johnson,Drew Logan
3,Nate Johnson, Jack Crank
4,Joey Smyth,Daniel Jack Foster
5,Joe Morgan …在榆树语言中,我很难解释我的问题......在榆树的这些片段中:我理解签名之类的东西
update : Msg -> Model -> Model
其中参数/输出由箭头分隔,但我如何阅读/理解如下:
Sub Msg
Program Never Model Msg
在:
main : Program Never Model Msg
main =
program
{ init = init
, view = view
, update = update
, subscriptions = subscriptions
}
subscriptions : Model -> Sub Msg
subscriptions model =
Sub.none
我有两个名字和一个地址的"记录"(基本上是CSV字符串).我需要找到彼此相似的记录:基本上名称和地址部分都看起来"相似",好像它们是由人类解释的.
我使用了这篇优秀博客文章中的想法:http : //knol.google.com/k/simple-simhashing#来编写一个简单的SimHash.如果两个或多个字符串的SimHash结果相同,我将该子集的所有记录传递给细粒度的匹配程序,该程序是O(n ^ 2),它将该集的每个记录与每个其他记录进行比较.
对于SimHash部分,我有参数,我可以定义数据报大小(基本上是字符串大小为n的滑动窗口)和用于确定我需要用于SimHash计算的哈希(随机)哈希数的迭代次数.到目前为止,数据报大小为4并使用4个哈希来计算SimHash.我尝试过各种其他组合,但到目前为止这个组合效果最好.
我遇到的问题是这个方法在我拥有的数据集中找到了大约80%的重复项.我知道这是因为我已经验证了整个数据集与上面提到的缓慢的O(n ^ 2)完全匹配.对于小于10 ^ 4的数据集,O(n ^ 2)匹配器是可以的,但很快变得不可行,因为我需要运行大小为10 ^ 8的集合.
关于如何提高SimHash准确性的任何想法,建议或想法,以便更多的"相似"记录被标记为相同的SimHash数字？
编辑:在SimHashing之前,我大写并删除所有![0-9A-Z]字符.应该匹配的事情的例子(拼写错误是有意的):
这里1和2是相似的,3不是.输出应为:1 + 2
我可能会遗漏Scala字符串插值机制的基本内容.我想做的事:
// this could come from a config file, string here to demo
val brown = "BROWN"
val cow = "Moo"
val replaceInMe = "How Now ${brown} ${cow}"
//this does what I eventually want:
val output = s"How Now ${brown} ${cow}"
//But, since the variables 'brown' and 'cow' are defined,
//I really wold like to be able to do something like:
val output = s(replaceInMe)
这甚至可能吗？
编辑:基于下面的第一个答案,它必须将变量replaceInMe作为输入.在这里我将它定义为一个字符串,但它实际上是从配置文件中读取的一行.