我正在尝试解决 HackerRank 上的问题;“确定 DNA 健康状况。” 在查看了一些讨论后,我决定 Aho-Corasick 算法将是最佳选择。该问题涉及在字符串中搜索具有关联值的各种序列。任务是从给定列表中获取这些序列值对的一个子部分,并找到与输入字符串关联的值。这意味着使用 100000 个序列值对的列表完成 44850 次。我已经实现了这个算法,虽然它比我的第一次尝试快了很多,但它仍然不够快,无法通过这个测试用例。这是我的实现:
构建特里:
def createValueTrie(gs: Array[(String, Int)]): TrieNodeWithVal = {
def recurse(genes: Array[(String, Int)]): Map[Char, TrieNodeWithVal] = {
genes
.groupBy(_._1.head)
.map(x => (x._1, x._2.map(y => (y._1.tail, y._2))))
.map{
case (c, arr: Array[(String, Int)]) => {
val value = arr.filter(_._1.length == 0).foldLeft(0)(_ + _._2)
val filtered = arr.filter(_._1.length > 0)
val recursed = recurse(filtered)
(c, new TrieNodeWithVal(arr.exists(_._1.length == 0), recursed, value))
}
}
}
new TrieNodeWithVal(false, recurse(gs), 0)
}
通过特里搜索:
def findValueMatches(trie: TrieNodeWithVal, sequence: String): Iterator[(String, Long)] = {
sequence.scanRight("")(_ + _).dropRight(1).iterator.flatMap(s => {
Iterator.iterate[(Iterator[Char], Option[TrieNodeWithVal])]((s.iterator, Some(trie))) {
case (it: Iterator[Char], Some(node)) => if (it.hasNext) (it, node(it.next())) else (it, None)
case (it: Iterator[Char], None) => (it, None)
}.takeWhile {
case (_, Some(_)) => true
case _ => false
}.map {
case (_, Some(node)) => node
}.zipWithIndex.withFilter {
case (node, _) => node isWord
}.map {
case (node, i) => (s.slice(0, i), node.value)
}
})
}
Trie 节点类:
class TrieNode(isAWord: Boolean, childs: Map[Char, TrieNode]) {
val isWord = isAWord
val children: Map[Char, TrieNode] = childs
def apply(c: Char): Option[TrieNode] = children.get(c)
override def toString(): String = "(" + children.map(x => (if (x._2.isWord) x._1.toUpper else x._1) + ": " + x._2.toString()).mkString(", ") + ")"
}
class TrieNodeWithVal(isAWord: Boolean, childs: Map[Char, TrieNodeWithVal], valu: Long) extends TrieNode(isAWord, childs) {
val value = valu
override val children: Map[Char, TrieNodeWithVal] = childs
override def toString(): String = "(" + children.map(x => (if (x._2.isWord) x._1.toUpper + "[" + x._2.value + "]" else x._1) + ": " + x._2.toString()).mkString(", ") + ")"
override def apply(c: Char): Option[TrieNodeWithVal] = children.get(c)
}
我知道对于失败案例可以在这里进行更多的边缘构建,但是讨论中的几个人说它会更慢,因为需要为每个查询重建 trie。对于这样的问题,我应该使用一些更有效的集合吗?如何在保持纯粹功能风格的同时加快速度?