返回顶部

收藏

快速匹配字符串

更多

假设内存有一个大字符串集,里面含有约1000万个字符串,如何快速知道该字符串集是否含有某个指定的测试字符串 ? (假设内存能放下这么多字符串)方法一:hashCode法方法二:Trie树 http://zh.wikipedia.org/wiki/Trie

HashCode法

def sampleHashMap(strSet: Set[String]): Map[Int, Set[String]]={
   strSet.groupBy{
      s => s.hashCode
   }  
}

def contain(str: String, sampleMap: Map[Int, Set[String]]): Boolean = { 
   sampleMap.getOrElse(str.hashCode, Set[String]()).exists(_ equals str)
}

// 测试
val sampleSet = Set("a","b","c","AA","Archer","Jack");
val sampleMap = sampleHashMap(sampleSet);
println(contain("Archer", sampleMap));  // true 
println(contain("A", sampleMap));    //  false
println(contain("a", sampleMap));   // true

Trie树法

sealed abstract class  Trie {
  def contains(msg: String): Boolean = contains(msg, this)

   @scala.annotation.tailrec
   private def contains(msg: String, trie: Trie): Boolean = (msg, trie) match {  
        case (null, _ ) | (_ , null ) => false
        case (StringCase(head, tail), TrieNode(edges)) => edges.get(head) match {
            case None => false  
            case Some(subTrie) => contains(tail,subTrie)
        }
        case (StringCase(_,_), TrieLeaf()) => false
        case _ => true
    }
}

case class TrieNode(edges: Map[Char, Trie]) extends Trie{
   assert(edges.size > 0)
}
case class TrieLeaf extends Trie

object StringCase{
    def unapply(s: String): Option[(Char, String)] ={ 
      if (s == null || s == "" )  None
      else Some(s.head, s.tail)
    }
}

object Trie{

   def apply(strs: String*): Trie ={
      apply(strs.toSet);
   }

   def apply(strSet: Set[String]) : Trie = {
      if (strSet.size ==0 || strSet == Set("")) TrieLeaf()
      else {
         val char2TrieSet = strSet.filter(_.length > 0).groupBy(_.head).mapValues{
            strs => strs.map(_.tail)
         }.mapValues{
            strs => apply(strs)
         }
         TrieNode(char2TrieSet);
      }  
   }

}

val trie= Trie("abc","ac","b")
println(trie)
assert(trie.contains("") == true);     // true
assert(trie.contains(null) == false);   //false 
assert(trie.contains("a") == true);    // true
assert(trie.contains("b") == true);    // true
assert(trie.contains("ab") == true);   //true
assert(trie.contains("ac") == true);   //true
assert(trie.contains("abc") == true);   //true
assert(trie.contains("acb") == false);   // false
assert(trie.contains("abcd") == false);   //false
assert(trie.contains("bc") == false);   //false

标签:scala

收藏

0人收藏

支持

0

反对

0

»更多 您可能感兴趣的代码
  1. 2017-03-06 13:27:34在maven项目中混合使用java和scala两种jvm语言 by 甄码农
  2. 2015-08-06 10:27:46将 Scala XML 转成 Java DOM by huwei
  3. 2015-08-04 13:40:48Scale 之长整型 bigint by 风云轩
  4. 2015-08-04 13:35:16Scala 时间处理一例 by 睡到自然醒
  5. 2015-08-03 19:46:27Scala Actors by 跳跳虎
  6. 2015-07-10 20:53:17Scala 之 Properties by fengsweat
  7. 2015-07-09 21:21:23Scala Lazy Evaluation by Hugh
  8. 2015-07-04 11:04:16Scala 之 Socket 通讯示例 by 杨洋
  9. 2015-07-03 09:32:17Scala 程序中使用 Map 数据结构 by G.Conanca
  10. 2015-07-02 10:46:02Scala 的 for 和 yield 构造 by 童学芬
  11. 2015-07-02 10:38:23Scala 模式匹配 (Case Classes) by loking
相关聚客文章
  1. Harries 发表 2018-10-16 12:22:30 从Scala(2.10)类型的标签或符号获取Java类的任何方法?
  2. 博主 发表 2016-12-31 04:38:37 hadoop流水账之HBase,Spark和在Spark上操作HBase
  3. 博主 发表 2016-12-31 04:38:37 Java/Scala杂记之一
  4. 博主 发表 2016-12-31 04:38:37 Java/Scala杂记之二
  5. 博主 发表 2016-12-31 04:38:37 Java/Scala杂记之三
  6. 博主 发表 2016-12-31 04:38:37 Java/Scala杂记之三
  7. 博主 发表 2017-01-07 07:34:01 一年一语言之2016
  8. xiaoli.wang 发表 2018-09-10 13:30:56 穷人创业指南,告诉你没钱该如何创业?
  9. 炒饭 发表 2015-06-13 08:32:43 Scala学习(一)——类、对象和变量
  10. 炒饭 发表 2015-06-16 15:48:52 Scala学习(二)——成员,方法和构造方法
  11. 炒饭 发表 2015-06-18 07:42:29 Scala学习(三)——代码块和流程控制
  12. 炒饭 发表 2015-06-18 14:44:34 Scala学习(四)——类型

发表评论