Mxn 一日三省吾身,续之或者改之

理解kmp算法

“KMP算法”,常用于在一个文本串S内查找一个模式串P 的出现位置.KMP算法是一种线性时间复杂的字符串匹配算法, 它是对BF算法(Brute-Force,最基本的字符串匹配算法的)改进。对于给的原始串S和模式串P,需要从字符串S中找到字符串P出现的位置的索引。

BF算法与KMP算法的区别

BF算法的时间复杂度O(S.length * T.length),空间复杂度O(1)。

KMP算法的时间复杂度O(S.length + T.length),空间复杂度O(T.length)。

字符串匹配算法必须要回溯。但回溯就影响了效率,回溯是由T串本身的性质决定的,是因为T串本身有前后’部分匹配’的性质。 改进的地方也就是这里,我们从T串本身出发,事先就找准了T自身前后部分匹配的位置,那就可以改进算法。 KMP算法就是利用之前已经部分匹配这个有效信息,保持i 不回溯,通过修改j 的位置,让模式串尽量地移动到有效的位置。

算法流程事例

1.首先,字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位.

2.因为B与A不匹配,搜索词再往后移。

理解threadlocal

ThreadLocal类用来提供线程内部的局部变量。这种变量在多线程环境下访问(通过get或set方法访问)时能保证各个线程里的变量相对独立于其他线程内的变量。

ThreadLocal不能使用原子类型,只能使用Object类型。 threadLocal为每一个线程都提供了变量的副本, 使得每个线程在某一时间访问到的并不是同一个对象, 这样就隔离了多个线程对数据的数据共享。

ThreadLocal是一个线程内部的数据存储类,通过它可以在指定的线程中存储数据,数据存储以后,只有在指定线程中可以获取到存储的数据, 对于其它线程来说无法获取到数据。在日常开发中用到ThreadLocal的地方较少,但是在某些特殊的场景下,通过ThreadLocal可以轻松地实 现一些看起来很复杂的功能,这一点在Android的源码中也有所体现,比如Looper、ActivityThread以及AMS中都用到了ThreadLocal。 具体到ThreadLocal的使用场景,这个不好统一地来描述,一般来说,当某些数据是以线程为作用域并且不同线程具有不同的数据副本的时候, 就可以考虑采用ThreadLocal。比如对于Handler来说,它需要获取当前线程的Looper,很显然Looper的作用域就是线程并且不同线程具有 不同的Looper,这个时候通过ThreadLocal就可以轻松实现Looper在线程中的存取,如果不采用ThreadLocal,那么系统就必须提供一个 全局的哈希表供Handler查找指定线程的Looper,这样一来就必须提供一个类似于LooperManager的类了,但是系统并没有这么做而是选择 了ThreadLocal,这就是ThreadLocal的好处。

ThreadLocal另一个使用场景是复杂逻辑下的对象传递,比如监听器的传递,有些时候一个线程中的任务过于复杂, 这可能表现为函数调用栈比较深以及代码入口的多样性,在这种情况下,我们又需要监听器能够贯穿整个线程的执行过程,这个时候可以怎么做呢? 其实就可以采用ThreadLocal,采用ThreadLocal可以让监听器作为线程内的全局对象而存在,在线程内部只要通过get方法就可以获取到监听器。 而如果不采用ThreadLocal,那么我们能想到的可能是如下两种方法:第一种方法是将监听器通过参数的形式在函数调用栈中进行传递, 第二种方法就是将监听器作为静态变量供线程访问。上述这两种方法都是有局限性的。第一种方法的问题时当函数调用栈很深的时候, 通过函数参数来传递监听器对象这几乎是不可接受的,这会让程序的设计看起来很糟糕。第二种方法是可以接受的,但是这种状态是不具有可扩充性的, 比如如果同时有两个线程在执行,那么就需要提供两个静态的监听器对象,如果有10个线程在并发执行呢?提供10个静态的监听器对象? 这显然是不可思议的,而采用ThreadLocal每个监听器对象都在自己的线程内部存储,根据就不会有方法2的这种问题。

理解handler

android中处理一些费时的操作需要单独启动一个子线程去处理。子线程处理完毕将结果通知给UI主线程更新UI界面。 子线程与UI主线程的通信在android中使用了消息机制来完成,那么是怎么完成的呢?这就和handler机制的原理(android中线程间通信的原理,而不是进程间通信), 简而言之,就是需要两样古老的东西,消息队列、轮询。也就是说,主线程起来以后有一个消息队列,同时和该队列配对的有一个轮询, 而子线程有这个消息队列的引用,那这样,子线程处理完以后就会向主线程的消息队列发消息,主线程轮询自己的队列,发现有未处理的消息就进行处理。 这就是handler的机制。

下面介绍Handler,Message,MessageQueue,Looper的关系:

looper对象拥有message queue,并且负责从message queue中取出消息给handler来处理。同时handler又负责发送message给looper,由looper把message添加到message queue尾部。 handler和looper是来联系在一起的。多个message可以指向同一个handler,多个handler也可以指向同一个looper。

Android分包原理

如果App引用的库太多,方法数超过65536后无法编译。这是因为单个dex里面不能有超过65536个方法。为什么有最大的限制呢, 因为android会把每一个类的方法id检索起来,存在一个链表结构里面。但是这个链表的长度是用一个short类型来保存的, short占两个字节(保存-2的15次方到2的15次方-1,即-32768~32767),最大保存的数量就是65536。新版本的Android系统中修复了这个问题, 但是我们仍然需要对低版本的Android系统做兼容.

解决方法有如下几个: 1.精简方法数量,删除没用到的类、方法、第三方库。 2.使用ProGuard去掉一些未使用的代码 3.复杂模块采用jni的方式实现,也可以对边缘模块采用本地插件化的方式。 4.分割Dex

本文只介绍最后一种方法。

multidex方案配置

dex文件拆成两个或多个,为此谷歌官方推出了multidex兼容包,配合AndroidStudio实现了一个APK包含多个dex的功能。 Android 的 Gradle插件在 Android Build Tool 21.1开始就支持使用multidex了。

Textview超链接实现方式总结

TextView中的超链接可以通过几种方式实现:1.Html.fromHtml,2.Spannable,3.Linkify.addLinks。下面分别进行测试,包括 修改字体样式,下划线样式,点击事件等。

Html.fromHtml方式

TextView,本身就支持部分的Html格式标签。这其中包括常用的字体大小颜色设置,文本链接等。使用起来也比较方便,只需要使用Html类转换一下即可: textView.setText(Html.fromHtml(str));

代码如下:

       
    public class Test10Activity extends Activity {
        TextView textView ;
        @Override
        protected void onCreate(Bundle savedInstanceState) {
            super.onCreate(savedInstanceState);
            setContentView(R.layout.activity_test10);
            textView = (TextView) findViewById(R.id.text);
            String webLinkText = "<a href='https://souly.cn'> html超链接测试</a>" ;
            textView.setText(Html.fromHtml(webLinkText));
        }
    }