程序员的自我修养
Home » 标签 » Java

Trie树

0条评论4,293次浏览

前几天与学弟聊到他最近的面试题中有一题需要计算两个字符串的最长公共子字符串。当时想到了KMP算法可能可以解决,但仔细想想可能是个比较复杂的任务。后来在网上看到有不少人说用trie树来解决。然后我就糊涂了,记忆中trie树貌似只能解决最长公共前缀的问题吧。于是复习一遍Trie树。

简介

Trie树百度百科解释如下:又称单词查找树,字典树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。

Trie树的直观结构如图所示:
trie tree

图中红色的点代表此处有字符串在此结束,上图中共有7个字符串:abc、abcd、abd、b、bcd、efg、hij(百科中的图,空白边就算作j好了)。

Trie树的使用场景

  • 字符串检索,词频统计,搜索引擎的热门查询。
  • 字符串最长公共前缀。
  • 字符串排序。
  • 作为其他数据结构和算法的辅助结构,如后缀树,AC自动机等。

至于“计算两个字符串的最长公共子字符串”这样的需求无法采用trie树实现,就算能实现也需要大量的改变。

阅读全文>>

标签:,

Levenshtein距离

0条评论2,442次浏览

Levenshtein距离,又称为编辑距离,或者成为字符串相似度,意思是一个字符串转换为另一个字符串所需要的最小编辑次数。编辑包含:插入、删除和替换三种操作。例如字符串:yurnom和yunum的编辑距离为2,因为需要插入一个r和将u替换为o两次操作。

Levenshtein算法由俄罗斯科学家Vladimir Levenshtein在1965年提出,该算法现在广泛用于DNA匹配、字符串纠错、实体共指等领域。

算法简介

将2个字符串转换为一个矩阵,为了简单起见,采用字符串heqi和hoi。转换后进行初始化,如下所示:

h e q i
0 1 2 3 4
h 1 A
o 2
i 3

其中数字部分为初始化的值,现计算绿色格子A处的值,其算法为:

  1. 若A所对应的两个字符相同,则左上角蓝色格子的值+0,否则+1,结果记为R1
  2. 选取上方和左方紫色格子中较小的值,并+1,结果记为R2
  3. 选取R1和R2中的较小值为绿色格子A处的值

经过计算可以得出A处的值为0,当A处计算完毕后,其右方和下方的值可以接着进行计算了,如此整个矩阵的值将可全部计算出来。最后矩阵右下方红色格子的值即为两个字符串的编辑距离。

至于为何左方和上方的值加1、左上角的值根据不同的情况加0或1的原因(也就是这么算的原理)比较简单,在此不再详述。

阅读全文>>

标签:,

Java并发编程学习笔记(5)——Fork/Join框架

0条评论12,802次浏览

Fork/Join简介

Fork/Join的核心思想为分治算法:将一个规模较大的问题划分为同样性质但规模较小的若干子问题来求解,然后将子问题的结果汇总并输出最后的结果。Fork/Join框架执行任务时,检查该任务的规模大小,若大于设定的阀值,则划分为更小的子任务,然后继续用框架来执行。若划分后的子问题小于阀值则直接执行,若大于阀值则继续划分成更小的子问题。下图总结了这个概念:
fork-join

核心操作

  • fork操作:把任务分成更小的任务和使用这个框架执行它们。
  • join操作:一个任务等待它创建的任务的结束。

特性

Work-stealing算法,类似Hadoop中的推测执行:一个先完成所有任务的线程会尝试着窃取其它线程中没有完成的任务来执行(任务队列尾部窃取)。这样做的好处是重用利用了并发多线程的优点,并减少了线程间的竞争。

阅读全文>>

标签:,

Java并发编程学习笔记(4)——线程池

0条评论1,521次浏览

从Java5开始,JDK并发API提供了ThreadPoolExecutor类,用来创建线程池。合理的使用线程池,有以下三个好处:

  • 降低资源消耗
  • 提高响应速度
  • 提高线程的可管理性

ThreadPoolExecutor

构造方法

基本构造方法

创建大小固定的线程池

创建大小为1的线程池

常用方法

  • void executeTask(Runnable command),执行Runnable任务
  • void shutdown(),关闭线程池
  • int getPoolSize(),获取线程池大小
  • int getActiveCount(),获取正在运行的线程数量
  • long getCompletedTaskCount(),获取已完成的任务数量
  • Future<T> submit(Callable<T> task),执行Callable任务
  • T invokeAny(Collection<? extends Callable<T>> tasks),执行一组Callable任务,只获取第一个返回结果
  • List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks),执行一组Callable任务,获取全部返回结果

阅读全文>>

标签:,

Java并发编程学习笔记(3)——线程同步进阶

0条评论1,263次浏览

Semaphore

Semaphore是一个控制访问多个共享资源的计数器。当计数器值大于0,代表还有可用资源,线程可以继续访问和使用资源;当计数器的值等于0,代表暂无可用资源,线程必须等待资源的释放。

一个典型的例子就是,有多台打印机,当新的打印任务来时,将检测是否还有可用的打印机,若有则使用,并将可用打印机数量减1;若无则等待;当使用完毕后,释放打印机,将可用打印机数量加1。

使用示例

  • 同Lock一样,Semaphore也可开启公平机制,Semaphore(int permits, boolean fair)
  • acquireUninterruptibly(),与acquire()的区别是:线程中断不会抛出异常
  • tryAcquire(),尝试获取semaphore。如果成功,返回true。如果不成功,返回false值,并不会被阻塞和等待semaphore的释放。

阅读全文>>

标签:,

Java并发编程学习笔记(2)——线程同步基础

0条评论1,141次浏览

synchronized

synchronized关键字用来控制并发访问。每个方法声明为synchronized关键字是一个临界区,Java只允许一个对象执行其中的一个临界区。当synchronized加在静态方法时,代表只有一个执行线程能访问被synchronized关键字声明的静态方法。

synchronized关键字不利于应用程序的性能,所以必须仅在修改共享数据的并发环境下的方法上使用它。应当尽量使用synchronized来保护访问共享数据的代码块,以使得临界区尽可能短。

  • 对于同步方法,锁是当前实例对象
  • 对于静态同步方法,锁是当前对象的Class对象
  • 对于同步方法块,锁是synchronized括号里配置的对象,通常来说会用this;当使用其它对象引用时,代表可以并行的访问。

wait()、notify()、notifyAll()

wait()必须出现在synchronized内,否则会抛出IllegalMonitorStateException异常。当调用wait()后,该线程会睡眠,直到相同对象保护的synchronized代码块中调用notify()或notifyAll()方法才会醒来。在此期间其它线程可以访问synchronized代码块。通常wait()需要配合while循环检查边界条件,否则,当线程唤醒后就会继续执行,而此时可能并不满足线程执行的条件。

阅读全文>>

标签:,

Java并发编程学习笔记(1)——线程基础

0条评论1,154次浏览

写在前面

发现现在学Java的,要是对IO、多线程、并发不熟悉都不好意思出去找工作。现在的新技术日新月异,一味的追求新技术不但沉淀不下多少东西,还得迟早累死。当然不是说不用学新技术,能快速掌握新技术毫无疑问可以增加自己的竞争力,但我觉得打好基础才能以不变应万变,也能更加快速的掌握新技术。其实很多新技术,如Hadoop、HBase等都是前人结合自己的经验写出的框架,真正底层的还是那些基础的东西。

IO、多线程、并发毫无疑问是Java基础中的基础。回想自己做过的项目和产品,要么用的SSH架构,要么是Hadoop这样产品,做开发也快3年了,却一直对IO、多线程、并发不了解,现在开始学习并发编程,并写下学习笔记。

线程基础

创建线程

继承Thread父类

阅读全文>>

标签:,

Java自动适配读取Hdfs和本地文件

1条评论3,068次浏览

开发MR程序通常是在本地跑local MapReduce进行测试,等测试完毕后则将mapred-site.xml放入src下打包成jar放在集群上进行测试。MR若需要读取文件作为数据源,则FileInputFormat.addInputPath(job, new Path(args[0]) );。但有时会出现需要读取Hdfs文件内容但又不能作为数据源输入的场景,比如写HBase MapReduce的时候,输入数据源为HBase的表,但是需要读取Hdfs上某文件的数据来进行操作。

单纯的读取本地文件内容实现起来十分简单,但读取本地文件内容的代码放在集群上是无法使用的。是否有方法能自动适配本地和集群两种模式下的文件读取?通过查找Hadoop API发现可通过FileSystem来实现。具体实现代码如下:

如是本地测试,项目中不包含mapred-site.xml文件(或将其中集群的配置信息注掉),则根据传入的conf则读取本地的文件;反之,添加mapred-site.xml文件,则读取Hdfs上的文件。本地测试时,getResult(conf, "/home/yurnom/data")将读取本地文件or文件夹/home/yurnom/data下面的内容;集群测试时,getResult(conf, "/home/yurnom/data")将读取hdfs://master:9000/home/yurnom/data文件or文件夹下面的内容。

标签:,

Lombok

0条评论4,307次浏览

简介

通过注解形式帮助生成常用的getter、setter等方法,在消除冗长的Java代码上有不错的效果。而且,看起来比较炫酷。

lombok官方网址

原理

没有看过源码,不过想必是通过asm来操控字节码实现的。

对字节码感兴趣的同学可以看看

安装

  • 为何要安装

为了IDE的支持,不然IDE可不知道相应的显示setter、getter方法,编译的时候也不会调用lombok。

  • 安装方式

不同的IDE安装方式不同,详见官网。

此外,我在IntelliJ Idea上安装使用lombok时遇到了一个比较头疼的问题:安装成功了但编译出来的.class文件中却没有相应的方法。若你也遇到了这样的问题,详见

阅读全文>>

分类:Java语言
标签:,

关于Apache Pig

0条评论4,840次浏览

网上关于介绍pig、安装Pig以及pig原理的文章够多了。以下记录一些入门时遇到的一些问题,算是一些实战经验吧。

关于脏数据过滤

Pig除了用FILTER进行按条件过滤数据以外,还有一种脏数据无法处理。如,我的数据共29个字段,以“,”分隔。现在有一部分的数据,缺失了部分字段,导致以“,”分隔后,数组长度小于29。因为不知道到底缺失的是哪个字段,这样的数据已经毫无意义。在Pig中如何过滤掉呢?翻遍了Pig的Document,去各种社区提问也没人能回答。最后尽然在FAQ中看到了答案,可以用ARTIY(*)来进行过滤。如:

关于PigStorage

PigStorage可以自定义分隔符,如PigStorage(','),PigStorage('|')。但上次遇到一个奇葩的csv文件,里面的所有数据全部加上的引号,导致数据大小直接变大了1倍不说,而且以','分隔后的数据全部是"1352288xxxx"这样带着引号无法转换为chararray以外类型的数据。数据样例:

"1","2","3","4"

后来想尝试使用'\",\"'来进行分隔,然后对第一个和最后一个字段进行SUBSTRING处理,结果却报错了。具体错误没保存下来,意思好像是PigStorage只能以char为分隔符。

无奈,只能用shell命令替换掉所有的引号再进行下一步处理。

遇到这样的文件,除了祈祷文件不要太大以外,最好的处理方式是给数据发送方上一课。you see see your po data!!!

阅读全文>>

分类:Apache Pig
标签:
3123
profile
  • 文章总数:81篇
  • 评论总数:247条
  • 分类总数:32个
  • 标签总数:45个
  • 运行时间:1250天

大家好,欢迎来到selfup.cn。

这不是一个只谈技术的博客,这里记录我成长的点点滴滴,coding、riding and everthing!

最新评论
  • Anonymous: :?: :razz: :sad:
  • Anonymous: 牛
  • Anonymous: 楼主你好,我偶尔也会 遇到Reconnect due to socket error: java.nio.channels.ClosedCha...
  • Anonymous: sdfs
  • Anonymous: :arrow: :neutral: :cry:
  • Anonymous: java.io.NotSerializableExcepti on: DStream checkpointing has been enabled but the DStreams with their...
  • wick: HI,请问一下,U,S,V得到 ,怎么得到近似矩阵 (用spark java),谢谢。
  • Michael Whitaker: Thank you for this blog, it was very helpful in troubleshooting my own issues. It seems that no...
  • Anonymous: :mad:
  • Anonymous: :???:
  • Anonymous: :mad: :mad: :mad:
  • 洋流: 哥们,我问个问题,你 把testOnborrow去掉了。。 如果得到的jedis资源...
  • 洋流: 哥们,我问个问题,你 把testOnborrow去掉了。。 如果得到的jedis资源...
  • Anonymous: :razz: :evil: :grin:
  • 张瑞昌: 有很多,比较常见的是 Jacob迭代法,一次迭代O (n^3),迭代次数不清楚 ...
  • Anonymous: :mrgreen:
  • lc277: 你好 我想问下一般删除节点 要多久,要删除的datano de大概用了1t,解除...
  • Anonymous: 你好 我想问下一般删除节点 要多久,要删除的datano de大概用了1t,解除...
  • Anonymous: :smile: :grin: :eek:
  • 李雪璇: 想要完整代码,可以帮 忙发给我吗