使用LINQ增加乐趣
经过几次尝试,我想出了一个纯LINQ解决方案,理论上可以成为一行代码。我尝试让它高效,但是功能性的解决方案会导致重复计算,因为你无法保持状态。
我们从一些预处理开始,以便稍后节省重复计算。是的,我知道使用索引可能是一个有问题的做法,但是如果你小心谨慎,它可以快速实现:
var index = 0;
var lookup = original.ToLookup(s => s, s => index++);
庞然大物
var occurrences = userSelect
.Where(lookup.Contains)
.SelectMany((s, i) => lookup[s]
.Select(j => new {
User = userSelect.Skip(i),
Original = original.Skip(j),
Skipped = i
})
.Select(t => t.User.Zip(t.Original, (u, v) => Tuple.Create(u, v, t.Skipped))
.TakeWhile(tuple => tuple.Item1 == tuple.Item2)
)
.Select(u => new {
Word = s,
Start = u.Select(v => v.Item3).Min(),
Length = u.Count()
})
)
.GroupBy(v => v.Start + v.Length)
.Select(g => g.OrderBy(u => u.Start).First())
.GroupBy(v => v.Word)
.Select(g => g.OrderByDescending(u => u.Length).First())
.Select(w => Enumerable.Range(w.Start, w.Length).ToArray())
.ToList();
使用打印
foreach (var occurrence in occurrences) {
Console.WriteLine(
"Maximal match starting with '{0}': [{1}]",
userSelect[occurrence[0]],
string.Join(", ", occurrence)
);
}
提供
Maximal match starting with 'the': [0, 1, 2]
Maximal match starting with 'dog': [3]
Maximal match starting with 'jumps': [4, 5]
很明显,你不会想在生产中使用这段代码,另一种(过程式)解决方案要好得多。然而,这个解决方案的独特之处在于除了lookup
之外完全是纯函数式的。当然,这也可以用函数式的方式编写:
var lookup = original.Select((s, i) => Tuple.Create)
.ToLookup(t => t.Item1, t => t.Item2);
它是如何工作的
在热身阶段,它创建了一个类似于字典的结构,将original
中的每个单词与其在同一集合中出现的索引相关联。稍后将使用此结构从userSelect
中的每个单词创建尽可能多的匹配序列(例如,“the”将导致两个匹配序列,因为它在original
中出现了两次)。
然后:
.Where(lookup.Contains)
这很简单,它会从userSelect
中删除所有不在original
中出现的单词。
.SelectMany((s, i) => lookup[s]
.Select(j => new { User = userSelect.Skip(i), Original = original.Skip(j), Skipped = j })
.Select(t => t.User.Zip(t.Original, (u, v) => Tuple.Create(u, v, t.Skipped)).TakeWhile(tuple => tuple.Item1 == tuple.Item2))
.Select(u => new { Word = s, Start = u.Select(v => v.Item3).Min(), Length = u.Count() })
)
此时,我们已经将userSelect
中的每个匹配单词投影到一个带有Start
和Length
属性的匿名对象中。然而,在匹配长度为N的序列中,还会导致长度为N-1、N-2等的更小的匹配序列。
关键在于意识到对于这些集合中的所有子序列,Start + Length
将是相同的;此外,来自不同集合的子序列将具有不同的Start + Length
之和。因此,让我们利用这一点来简化结果:
.GroupBy(v => v.Start + v.Length)
.Select(g => g.OrderBy(u => u.Start).First())
这仍将为我们留下与
userSelect
中每个单词匹配次数相同的匹配项,就像在
original
中出现的次数一样。因此,让我们将其减少到最长匹配:
.GroupBy(v => v.Word)
.Select(g => g.OrderByDescending(u => u.Length).First())
现在我们有一个对象,如
{ Word = "the", Start = 0, Length = 3 }
。让我们将其转换为
userSelect
中的索引数组:
.Select(w => Enumerable.Range(w.Start, w.Length).ToArray())
最后,将所有这些数组放入同一集合中,任务完成!