Maj*_*jnu 7 .net f# haskell scala clojure
在我学习计算机科学的过程中,我遇到了一些像Prolog这样的函数式语言,但是现在我在过去的10年里只做过像C#,Ruby JavaScript和Java这样的命令式的东西.目前我正在为网上商店创建一个全文搜索引擎,我已经走到了"必要的方式".但是,遇到像Caskjure的Haskell这样的函数式语言时,很明显功能范式非常合适,并且命令式方法不适合这项工作.
所以我们有一个大约1000万条记录的全文索引.每个记录基本上包含一个单词出现,以及它所来自的记录中的id和text位置.
当用户输入搜索字符串时,它将被解析为表达式树.例如,搜索字符串"transformer 100 W"会产生类似的结果
AND('transformer%', OR(NEAR('100', 'W'), NEAR('100', 'watts'), '100W', '0.1kW'))
这里还有一些额外的"情报",但这个问题无关紧要.
然后递归地评估表达式树,并导致一些sql查询,这些查询可以以.NET-DataTables的形式返回多达100,000行.然后将它们读入集合或字典中,并根据谓词应用交叉点和联合,以便找到与整个搜索表达式匹配的所有结果.对于NEAR评估,还比较找到的事件的位置索引.但这一切都是必须完成的,有很多for循环.
此外,还有一个排名功能,可以将找到的单词出现次数加起来.仅作为前缀或模糊匹配(由数据库服务器完成)的单词得分低于精确匹配.
对于每个结果项,我还需要获得匹配的所有单词出现的列表,以便在结果页中突出显示这些单词.
所以大致评估算法是一个像
expression tree, full text index ->
resulting items that match the expressin tree,
each with a ranking sum
and a list of all found word occurrences for this item
我只是在这里给出一个粗略的概述,但我希望你能得到足够的图片.
现在"现实世界"的限制:
由于我需要继续使用.NET,我正在研究Clojure-CLR,F#和Scala for .NET.
我很喜欢Clojure的概念,但是现在我无法评估它是否符合这项工作.阅读F#给了我复杂的感受,因为它似乎想要能够完成所有事情,而我倾向于为给定的任务采用更"纯粹"的数学方法.但也许F#也可以这样做,我还没有意识到这一点.我还没有深入研究过Scala,但它似乎已经很成熟了.
任何见解都会受到欢迎!
pad*_*pad 15
- 整个应用程序(到目前为止)都是用C#编写的,因此与.NET的轻松集成至关重要.
- 大量数据被读入.NET-DataTables,然后需要进行评估和转换.结果应该包含在.NET类型(字典,集合,数组,等等......)中.
F#应该是一个更好的选择.作为Visual Studio中的一流语言,F#与C#的互操作性非常好.
- 表现非常重要.目前我的算法通常需要两秒钟才能进行搜索(不计算sql),这有点好,但应该进行改进.我们的服务器有16个处理器,因此欢迎并行处理.由于我们每秒获得大约一个搜索请求,并且当前实现是单线程的,因此处理器时间仍然可用.
假设您从功能优先且不可变的实现开始,应该很容易并行化您的应用程序.此外,异步工作流程对于像您这样的IO绑定应用程序来说是一种祝福.
- 语言(和编译器)应该是成熟的.
我没有将F#与JVM上的Clojure和Scala进行比较,但F#比Clojure CLR和Scala在.NET上要成熟得多.在选择F#时,您一定会得到微软的长期承诺,并从不断增长的F#社区中获得帮助.
当用户输入搜索字符串时,它将被解析为表达式树.
您可以使用区分联合来表示表达式树.通过在F#3.0中引入查询表达式,您可以轻松地将逻辑转换为SQL查询.您甚至可以通过为您的域定义类似的查询语言来进一步推动它.
阅读F#给了我复杂的感受,因为它似乎想要能够完成所有事情,而我倾向于为给定的任务采用更"纯粹"的数学方法.但也许F#也可以这样做,我还没有意识到这一点.
F#3.0引入了类型提供程序,允许用户以类型安全的方式访问非结构化数据; 您可能需要查看此"F#3.0 - 信息丰富的编程"视频以获取更多见解.如果你想使用F#作为数据挖掘的编程语言,我已经提出了一个相关的问题,并在这里得到了很好的回答.
也就是说,你对F#的第一感觉可能不正确.根据我的经验,您可以随时保持尽可能接近功能和不可变的一面.鉴于您已经有了一个有趣的应用程序,我建议您亲自了解F#是否适合您的语言.
更新:
这是一个F#原型,它展示了这个想法:
/// You start by modeling your domain with a set of types.
/// FullText is a sequence of Records, which is processed on demand.
type Word = string
and Freq = int
and Record = {Occurrences: (Word * Freq) list; Id: string}
and FullText = Record seq
/// Model your expression tree by following the grammar closely.
type Expression =
| Occur of Word
| Near of Word * Word
| And of Expression * Expression
| Or of Expression * Expression
/// Find wether a word w occurs in the occurrence list.
let occur w {Occurrences = xs} = xs |> Seq.map fst |> Seq.exists ((=) w)
/// Check whether two words are near each other.
/// Note that type annotation is only needed for the stub implementation.
let near (w1: Word) (w2: Word) (r: Record): bool = failwith "Not implemented yet"
/// Evaluate an expression tree.
/// The code is succinct and clear thanks to pattern matching.
let rec eval expr r =
match expr with
| Occur w -> occur w r
| Near(w1, w2) -> near w1 w2 r
| And(e1, e2) -> eval e1 r && eval e2 r
| Or(e1, e2) -> eval e1 r || eval e2 r
/// Utility function which returns second element in a 3-tuple
let inline snd3 (_, x, _) = x
/// Get the rank of the record by adding up frequencies on the whole database.
let rank (r: Record) (ft: FullText): Freq = failwith "Not implemented yet"
/// Retrieve all records which match the expression tree.
let retrieve expr fullText =
fullText |> Seq.filter (eval expr)
|> Seq.map (fun r -> r, rank r fullText, r.Occurrences)
|> Seq.sortBy snd3
/// An example query
let query =
And (Occur "transformer%",
Or (Or (Near ("100", "W"), Near ("100", "watts")),
Or (Occur "100W", Occur "0.1kW")))
我很好奇你为什么不考虑LINQ作为选项.它似乎满足您的所有标准.注意我没有使用Scala的经验,因此我无法对此发表评论.
- 整个应用程序(到目前为止)都是用C#编写的,因此与.NET的轻松集成至关重要.
- 大量数据被读入.NET-DataTables,然后需要进行评估和转换.结果应该包含在.NET类型(字典,集合,数组,等等......)中.
这里,LINQ> F#> Clojure-CLR.如果一切都已经在C#中,LINQ将是最容易集成的.在C#-only程序中,Visual Studio对智能感知和函数定义导航等功能的支持似乎要好得多.从C#调用Clojure可能是可怕的 - 理论上它应该可以正常工作,但在实践中,要准备好花几周时间弄清楚为什么事情没有按照你期望的方式工作.它真的被设计成顶级的东西; 你从Clojure那里调用C#,反过来说Clojure-CLR开发人员的优先级列表并不高; 有基本的支持,但你得到你得到的.
- 表现非常重要.目前我的算法通常需要两秒钟才能进行搜索(不计算sql),这有点好,但应该进行改进.我们的服务器有16个处理器,因此欢迎并行处理.由于我们每秒获得大约一个搜索请求,并且当前实现是单线程的,因此处理器时间仍然可用.
LINQ~ = F#> Clojure.我在其他地方读到,对于大多数惯用语编写的算法,LINQ的性能可以比F#略好,但是它们足够接近它应该无关紧要.PLINQ使并行性变得容易.Clojure-CLR的启动时间非常慢,而且运行时开销也会降低速度.
- 语言(和编译器)应该是成熟的.
LINQ> = F#> Clojure.不是说F#是不成熟的,在所有的,但Visual Studio支持滞后有点落后,而且也基于LINQ比F#世界上更多的产品代码(和更多的堆栈溢出的答案).
阅读F#给了我复杂的感受,因为它似乎想要能够完成所有事情,而我倾向于为给定的任务采用更"纯粹"的数学方法.但也许F#也可以这样做,我还没有意识到这一点.
没有一种语言像Haskell那样纯粹纯粹,但就编写非纯代码的难度而言,我将其排名为:LINQ> Clojure> F#> Scala.只能通过调用不纯的方法使LINQ变得不纯洁.Clojure有refs和atoms,F#任何东西都可以指定为mutable,而Scala(根据我的理解)实际上只是带有功能特性的Java.
虽然F#和Scala都支持它们的功能特性是对模式匹配的语言支持.在C#中,您需要某种继承层次结构或b？x:y运算符链以在功能上执行操作(或者如果您使用非功能方法就可以执行其他操作),模式匹配会在不同的情况下进行条件运算原始数据类型的变化更加简洁.这可能在计算精确vs前缀与模糊匹配排名时很有用,但是var alg = x.match == exact ? alg1 : x.match == prefix ? alg2 : alg3在这个简单的情况下,C#中的ab？x:y链将是完全清晰的 - 当匹配变得更加复杂时,语言集成模式匹配变得更加复杂有价值.
有趣的是,我认为你的工具包的一个方面,其中F#比LINQ更有用,不是查询,LINQ本身的名称应该表明它可以处理,而是将搜索字符串解析为表达式树. 这是功能语言和模式匹配真正擅长的领域之一,并且添加FsLex和FsYacc等工具可以为您提供一个良好的开端.
所有这一切,我认为决定归结为你想去的地方.如果您只是想清理搜索算法并完成它,我会建议使用LINQ方法.但是,如果你想要逐个进入一个更加功能导向的整个程序风格(而你的公司愿意付出你承诺的时间),那么可以看看F#选项.无论哪种方式,我都会首先使用LINQ选项,因为这对您来说可能更为直接,并且一旦您开始沿着这条路走下去,就可以帮助指导您的F#更具功能性.
简单地说,这就是你想要的,只需填写你的Near和Equal fetchers的函数,以及你的GetRank和GetStrings函数,并使用下面的代码
static IEnumerable<Record> FetchRecords(this Tree tree) {
return tree.Op == "OR" ? tree.Args.SelectMany(FetchRecords).Distinct() :
tree.Op == "AND" ? tree.Args.Select(FetchRecords).Aggregate((intersect, current) => intersect.Intersect(current)) :
tree.Op == "NEAR" ? FetchValsNear(tree.Args[0].Op, tree.Args[1].Op) :
FetchValsEqual(tree.Op);
}
static IEnumerable<Record> FetchValsEqual(string s) {
throw new NotImplementedException();
}
static IEnumerable<Record> FetchValsNear(string s1, string s2) {
throw new NotImplementedException();
}
static IEnumerable<Tuple<Record, double, string[]>> OrderByRank(this IEnumerable<Record> vals) {
return from val in vals
let rank = GetRank(val)
orderby rank
let strings = GetStringsIn(val)
select Tuple.Create(val, rank, strings);
}
static string[] GetStringsIn(Record val) {
throw new NotImplementedException();
}
static double GetRank(Record val) {
throw new NotImplementedException();
}
class Tree {
public string Op;
public Tree[] Args;
}
struct Record {/*your record here--use struct so Distinct and Intersect above work naturally (or use class and override Equals)*/}
像这样:
foreach (var tuple in myTree.FetchRecords().AsParallel().OrderByRank().Take(30)) {
// add to datagrid or whatever
}
这为您提供了简单的可并行性和懒惰性,因此该GetStringsIn功能仅对您拍摄的记录执行(在本例中为前30个).(注意,AND可以使用此处的任何IntersectAll示例简化选择器).