见路不走

摘要： 在上一篇博客中，讲到计数排序的稳定性非常重要，主要可以体现在基数排序中(?)。这一篇，就来分析一下基数排序。看《算法导论》中的图： 对329，457，657，839，436，720，355几个数字进行排序，使用基数排序的方法，从最低有效位开始，即首先根据个位排序，得到720，355，436，457，657，329，839。十位、百位以此类推。最终得到排序的结果。对于基数排序，待排的数字必须... 阅读全文

摘要： 介绍线性时间排序算法，主要是为了实现构建后缀数组的倍增算法，倍增算法性能保证的主要依据就是采用了基数排序，通常，基础排序会使用计数排序作为rank排序子过程。这里，基数排序和计数排序都是线性时间排序算法，线性时间排序算法还有桶排序。性对于快速排序等比较排序算法而言，线性时间排序算法，没有比较运算。下面先介绍计数排序。 计数排序的基本原理是：对于任意待排的数字x，确定小于x的元素个数，然后将x直接放在最终输出数组中的特定位置上。如有10个小于x的元素，在最终的输出数组中，x就排第11，如果数组是从0开始，则在索引为10的位置。下图是从《算法导论》摘下来的，可以帮助理解计数排序。 如何确定小于x. 阅读全文

摘要： Cassandra自从出了几次大的宕机的情况之后，很少有大公司在用了，我目前知道的，就是twitter的抓取服务使用的Cassandra来存储抓取数据元信息，而且，国内某搜索引擎公司，也是这么做的。我最近的工作之一，就是改进Cassandra，选它一方面是公司的要求，另一方面，学习空间、提速空间性能都比较大。 经过一段时间的调研，确认了三个改进方向（由于公司的原因，现在我只说第一个）。第一个就是索引压缩的改进，往大了说，就是要对Cassandra的索引进行重新设计。重新设计的思路，下面会慢慢讨论。 对于kv存储引擎的索引，根据key是否有序，分为两种：一种是key如果无序，则可以采用hash的 阅读全文

摘要： 对于后缀数组的了解，要始于一篇论文，论文中，使用后缀数组的方式存储索引，改进词组检索的效果和性能，相对于倒排索引而言，后缀数组在空间占用上会比较大，但是效果却非常好，这个是倒排索引所无法高效应对的，而且，个人的一个猜想，会有越来越多的内存索引是基于后缀数组实现的，或许，已经有了。 从别的地方转来的几个个概念，我就不重复了： 子串：字符串S的子串r[i..j]，i≤j，表示r串中从i到j这一段，也就是顺次排列r[i]，r[i+1]，...，r[j]形成的字符串。 后缀：后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串r的从第i个字符开始的后缀表示为Suffix(i)，也就是Suff 阅读全文

摘要： 说开始学习，有点儿不对。我之前也用过算法，不过很少专门，系统的去看一个算法。都是用到了就找一个，然后了解一下，仅此而已。而且，长时间的使用java语言，我算法方面的思考能力，真的越来越弱了。同时，危机感越来越强。 前几天，我下定决心，要把算法详细的，深入的看一看。我想，在同学，同事们的帮助下，一起讨论，我会很快跟上吧。希望如此。 新的博客，新的开始。立此为证。 阅读全文