flyingcr

flyingcr 查看完整档案

成都编辑电子科技大学  |  计算机 编辑  |  填写所在公司/组织 blog.csdn.net/xiaoqiu_cr 编辑
编辑

欢迎关注我的公众号:小秋的博客
CSDN博客:https://blog.csdn.net/xiaoqiu_cr
github:https://github.com/crr121
联系邮箱:rongchen633@163.com
有什么问题可以给我留言噢~

个人动态

flyingcr 赞了文章 · 2020-09-15

布隆过滤器你值得拥有的开发利器

在程序的世界中,布隆过滤器是程序员的一把利器,利用它可以快速地解决项目中一些比较棘手的问题。如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。

布隆过滤器(Bloom Filter)是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。

阅读更多关于 Angular、TypeScript、Node.js/Java 、Spring 等技术文章,欢迎访问我的个人博客 ——全栈修仙之路

一、布隆过滤器简介

当你往简单数组或列表中插入新数据时,将不会根据插入项的值来确定该插入项的索引值。这意味着新插入项的索引值与数据值之间没有直接关系。这样的话,当你需要在数组或列表中搜索相应值的时候,你必须遍历已有的集合。若集合中存在大量的数据,就会影响数据查找的效率。

针对这个问题,你可以考虑使用哈希表。利用哈希表你可以通过对 “值” 进行哈希处理来获得该值对应的键或索引值,然后把该值存放到列表中对应的索引位置。这意味着索引值是由插入项的值所确定的,当你需要判断列表中是否存在该值时,只需要对值进行哈希处理并在相应的索引位置进行搜索即可,这时的搜索速度是非常快的。

bf-array-vs-hashtable.jpg

根据定义,布隆过滤器可以检查值是 “可能在集合中” 还是 “绝对不在集合中”。“可能” 表示有一定的概率,也就是说可能存在一定为误判率。那为什么会存在误判呢?下面我们来分析一下具体的原因。

布隆过滤器(Bloom Filter)本质上是由长度为 m 的位向量或位列表(仅包含 0 或 1 位值的列表)组成,最初所有的值均设置为 0,如下图所示。

bf-bit-vector.jpg

为了将数据项添加到布隆过滤器中,我们会提供 K 个不同的哈希函数,并将结果位置上对应位的值置为 “1”。在前面所提到的哈希表中,我们使用的是单个哈希函数,因此只能输出单个索引值。而对于布隆过滤器来说,我们将使用多个哈希函数,这将会产生多个索引值。

bf-input-hash.jpg

如上图所示,当输入 “semlinker” 时,预设的 3 个哈希函数将输出 2、4、6,我们把相应位置 1。假设另一个输入 ”kakuqo“,哈希函数输出 3、4 和 7。你可能已经注意到,索引位 4 已经被先前的 “semlinker” 标记了。此时,我们已经使用 “semlinker” 和 ”kakuqo“ 两个输入值,填充了位向量。当前位向量的标记状态为:

bf-input-hash-1.jpg

当对值进行搜索时,与哈希表类似,我们将使用 3 个哈希函数对 ”搜索的值“ 进行哈希运算,并查看其生成的索引值。假设,当我们搜索 ”fullstack“ 时,3 个哈希函数输出的 3 个索引值分别是 2、3 和 7:

bf-input-hash-2.jpg

从上图可以看出,相应的索引位都被置为 1,这意味着我们可以说 ”fullstack“ 可能已经插入到集合中。事实上这是误报的情形,产生的原因是由于哈希碰撞导致的巧合而将不同的元素存储在相同的比特位上。幸运的是,布隆过滤器有一个可预测的误判率(FPP):

bf-fpp.jpg

  • n 是已经添加元素的数量;
  • k 哈希的次数;
  • m 布隆过滤器的长度(如比特数组的大小)。

极端情况下,当布隆过滤器没有空闲空间时(满),每一次查询都会返回 true 。这也就意味着 m 的选择取决于期望预计添加元素的数量 n ,并且 m 需要远远大于 n

实际情况中,布隆过滤器的长度 m 可以根据给定的误判率(FFP)的和期望添加的元素个数 n 的通过如下公式计算:

bf-bit-vector-length.jpg

对于 m/n 比率表示每一个元素需要分配的比特位的数量,也就是哈希函数 k 的数量可以调整误判率。通过如下公式来选择最佳的 k 可以减少误判率(FPP):

bf-hash-fn-count.jpg

了解完上述的内容之后,我们可以得出一个结论,当我们搜索一个值的时候,若该值经过 K 个哈希函数运算后的任何一个索引位为 ”0“,那么该值肯定不在集合中。但如果所有哈希索引值均为 ”1“,则只能说该搜索的值可能存在集合中。

二、布隆过滤器应用

在实际工作中,布隆过滤器常见的应用场景如下:

  • 网页爬虫对 URL 去重,避免爬取相同的 URL 地址;
  • 反垃圾邮件,从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱;
  • Google Chrome 使用布隆过滤器识别恶意 URL;
  • Medium 使用布隆过滤器避免推荐给用户已经读过的文章;
  • Google BigTable,Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。

除了上述的应用场景之外,布隆过滤器还有一个应用场景就是解决缓存穿透的问题。所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据,这样每次服务调用都会到数据库中进行查询,如果这类请求比较多的话,就会导致数据库压力增大,这样缓存就失去了意义。

利用布隆过滤器我们可以预先把数据查询的主键,比如用户 ID 或文章 ID 缓存到过滤器中。当根据 ID 进行数据查询的时候,我们先判断该 ID 是否存在,若存在的话,则进行下一步处理。若不存在的话,直接返回,这样就不会触发后续的数据库查询。需要注意的是缓存穿透不能完全解决,我们只能将其控制在一个可以容忍的范围内。

三、布隆过滤器实战

布隆过滤器有很多实现和优化,由 Google 开发著名的 Guava 库就提供了布隆过滤器(Bloom Filter)的实现。在基于 Maven 的 Java 项目中要使用 Guava 提供的布隆过滤器,只需要引入以下坐标:

<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>28.0-jre</version>
</dependency>

在导入 Guava 库后,我们新建一个 BloomFilterDemo 类,在 main 方法中我们通过 BloomFilter.create 方法来创建一个布隆过滤器,接着我们初始化 1 百万条数据到过滤器中,然后在原有的基础上增加 10000 条数据并判断这些数据是否存在布隆过滤器中:

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterDemo {
    public static void main(String[] args) {
        int total = 1000000; // 总数量
        BloomFilter<CharSequence> bf = 
          BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
        // 初始化 1000000 条数据到过滤器中
        for (int i = 0; i < total; i++) {
            bf.put("" + i);
        }
        // 判断值是否存在过滤器中
        int count = 0;
        for (int i = 0; i < total + 10000; i++) {
            if (bf.mightContain("" + i)) {
                count++;
            }
        }
        System.out.println("已匹配数量 " + count);
    }
}

当以上代码运行后,控制台会输出以下结果:

已匹配数量 1000309

很明显以上的输出结果已经出现了误报,因为相比预期的结果多了 309 个元素,误判率为:

309/(1000000 + 10000) * 100 ≈ 0.030594059405940593

如果要提高匹配精度的话,我们可以在创建布隆过滤器的时候设置误判率 fpp:

BloomFilter<CharSequence> bf = BloomFilter.create(
  Funnels.stringFunnel(Charsets.UTF_8), total, 0.0002
);

在 BloomFilter 内部,误判率 fpp 的默认值是 0.03:

// com/google/common/hash/BloomFilter.class
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
  return create(funnel, expectedInsertions, 0.03D);
}

在重新设置误判率为 0.0002 之后,我们重新运行程序,这时控制台会输出以下结果:

已匹配数量 1000003

通过观察以上的结果,可知误判率 fpp 的值越小,匹配的精度越高。当减少误判率 fpp 的值,需要的存储空间也越大,所以在实际使用过程中需要在误判率和存储空间之间做个权衡。

四、简易版布隆过滤器

为了便于大家理解布隆过滤器,我们来看一下下面简易版布隆过滤器。

package com.semlinker.bloomfilter;

import java.util.BitSet;

public class SimpleBloomFilter {
    private static final int DEFAULT_SIZE = 2 << 24;
    private static final int[] seeds = new int[]{7, 11, 13, 31, 37, 61};

    private BitSet bits = new BitSet(DEFAULT_SIZE);
    private SimpleHash[] func = new SimpleHash[seeds.length];

    public SimpleBloomFilter() {
        // 创建多个哈希函数
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    /**
     * 添加元素到布隆过滤器中
     *
     * @param value
     */
    public void put(String value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    /**
     * 判断布隆过滤器中是否包含指定元素
     *
     * @param value
     * @return
     */
    public boolean mightContain(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    public static void main(String[] args) {
        SimpleBloomFilter bf = new SimpleBloomFilter();
        for (int i = 0; i < 1000000; i++) {
            bf.put("" + i);
        }
        // 判断值是否存在过滤器中
        int count = 0;
        for (int i = 0; i < 1000000 + 10000; i++) {
            if (bf.mightContain("" + i)) {
                count++;
            }
        }
        System.out.println("已匹配数量 " + count);
    }

    /**
     * 简单哈希类
     */
    public static class SimpleHash {
        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        public int hash(String value) {
            int result = 0;
            int len = value.length();
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i);
            }
            return (cap - 1) & result;
        }
    }
}

在 SimpleBloomFilter 类的实现中,我们使用到了 Java util 包中的 BitSet,BitSet 是位操作的对象,值只有 0 或 1 ,内部维护了一个 long 数组,初始只有一个 long,所以 BitSet 最小的容量是 64 位。当随着存储的元素越来越多,BitSet 内部会动态扩容,最终内部是由 N 个 long 值来存储。默认情况下,BitSet 的所有位都是 0。

五、总结

本文主要介绍的布隆过滤器的概念和常见的应用场合,在实战部分我们演示了 Google 著名的 Guava 库所提供布隆过滤器(Bloom Filter)的基本使用,同时我们也介绍了布隆过滤器出现误报的原因及如何提高判断准确性。最后为了便于大家理解布隆过滤器,我们介绍了一个简易版的布隆过滤器 SimpleBloomFilter。

六、参考资源

本人的全栈修仙之路订阅号,会定期分享 Angular、TypeScript、Node.js/Java 、Spring 相关文章,欢迎感兴趣的小伙伴订阅哈!

full-stack-logo

查看原文

赞 54 收藏 32 评论 1

flyingcr 关注了专栏 · 2020-09-15

全栈修仙之路

聚焦全栈,专注分享 Angular、TypeScript、Node.js/Java 、Spring 技术栈等全栈干货。 欢迎小伙伴们关注公众号全栈修仙之路,一起升级打怪。

关注 7083

flyingcr 发布了文章 · 2019-08-12

动态规划

重温动态规划~

今天刷leetcode:<u>198. House Robber</u>时用到了动态规划,看的是一个小哥哥的视频讲得灰常的清晰明了,推荐!!!<u>basketwangCoding</u>,看他的视频突然想到了算法分析课DQ老师当时给我们讲动态规划的场景,当时感觉这种思路so amazing

由于刷题的时候发现很多地方都用到了动态规划,但是自己总是想不到,可能还缺一点火候吧,所以打算再看看书,梳理梳理它的思想原理

接下来是《算法导论第三版》的读书笔记

什么是动态规划

维基百科的解释:

动态规划(英语:Dynamic programming,简称DP)通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有<u>重叠</u>子问题和<u>最优</u>子结构(英语:Optimal substructure)性质的问题,动态规划方法所耗时间往往远少于朴素解法。

最优子结构:一个问题的最优解包含其子问题的最优解

所以如果我们需要寻找原问题的最优解,那么我们就需要考察最优解中用到的所有子问题的最优解

动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。

通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题<u>一次</u>,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

所以总结一下就是:

  • 动态规划适用于子问题有重叠依赖的情况,并且尝试寻找最优解
  • 动态规划的子问题一般只会计算一次,然后会将每个子问题的解存储下来,以便 下次使用
  • 动态规划一般用于求解最优化问题(最大or最长or最短等等),那么这个时候你就可以考虑用动态规划了,这类问题一般都会有很多的可行解,每一个可行解都有潜力成为那个最优的解,而我们的任务就是找到那个真正的最优的解

这里在提一下分治算法,分治算法和动态规划很像,都是通过组合子问题的解来求原问题,但是分治法的子问题之间是没有重叠的,也就是分治法的子问题之间互不相交,通过递归的求解子问题,再将他们的解组合起来,如果你觉得比较抽象的话,可以想想归并算法,归并算法算是一个比较典型的分治算法了,归并排序可以移步:快速排序-归并排序-插入排序,分治法由于子问题都不相交,所以它会重复的求解一些公共的子子问题,相对于动态规划来说增加了计算开销

如何设计一个动态规划算法

我们可以参考如下4个步骤

  • 最优解有什么样的特点(题目的限定条件?)
  • 选定某一个状态进行递归定义最优解
  • 计算最优解(通常采用自底向上)

动态规划实例问题一:钢条切割问题

图片描述

下面按照算法导论里面的讲解画了一个自己的思路,抽象派。。。(看不懂的话可以直接参考算法导论里面的讲解15.1)

图片描述

图片描述

上面的这种算法采用自顶向下的思路,依次递归求解每个子问题,但是这种方式会重复计算大量的子问题,当n足够大时,会出现指数时间的增长

带备忘的自顶向下法

所以下面基于上面的方式进行了一个优化:以空间换时间

通过一个辅助空间来存储子问题的解,从而避免重复计算,我们也叫作“带备忘的自顶向下法(top-down with memoization)”

带备忘的自顶向下法会在计算子问题的过程中将计算结果保存下来,下次计算子问题的时候先检查是否已经保存过此解,如果保存过就直接返回保存的值,否则再计算

有自顶向下就肯定有自底向上

自底向上:自底向上一般需要提前规划好子问题的规模,使得任何子问题都只依赖于“更小的”子问题的解,所以我们需要将子问题按照规模排序,从小到大依次求解。当求解一个子问题时,它所依赖的更小的子问题已经求解出来了,每个子问题只用求解一次(并且也只会遇到一次)(就像是一个不断向上攀登金字塔的过程,每走一步都是一个脚印,并且绝不会回头

通常来说自底向上方法比自顶向下方法具有更小的时间复杂性系数

带备忘的自顶向下法

图片描述

这里的备忘的自顶向下的方法有几个思想我们可以借鉴:

采用一个辅助数组用来存储每个子问题的解,并且数组的初始值设置为负无穷这也是一种设置未知值得常用手段

递归求解时先判断辅助数组里面是否有值,如果有就直接返回

如果没有那么就按照正常递归求解,然后最后将结果保存到辅助数组里面

图片描述

算法导论上还举了一个动态规划的例子:矩阵连乘,貌似有丢丢复杂,就没仔细看了,直接找了DQ老师的PPT温习了一遍

动态规划实例问题二:矩阵连乘问题

首先了解什么是矩阵连乘问题:通过使用合适的加括号的方式,使得最后矩阵连乘积的乘法次数最少

完整题目:

给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。

由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。

若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积

  • 对于 p × q 矩阵 Aq × r 矩阵 BA × B 需要多少次乘法计算?p × q × r次乘法计算
  • 例如: AB 分别是 20 × 100, 100 × 10 矩阵, 则乘法总数为 20 × 100 × 10 = 20000

图片描述

再来个例子~

图片描述

通过上面的例子可以看出加括号的顺序对运算次数的影响之大,所以我们的任务就是为了找到一个最优的加括号的顺序,来使得最后的乘法次数最少

接下来开始入手,我们先将问题一般化

图片描述

下面我们按照算法导论中的“动态规划四部曲”来一步一步的分析

  • 分析最优解的结构特征

    特征:如果A[i:j]是最优次序,那么它所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的

满足最优子结构性质:最优解包含着其子问题的最优解

  • 建立递归关系

图片描述

  • 计算最优解的值通常采用自底向上

图片描述

图片描述

动态规划实现:

图片描述

什么时候该用动态规划来做

看了上面两个例子我们大概对动态规划的问题有了一些了解,那到底什么时候应该派出动态规划这样的杀手锏呢

首先观察这个问题是否具有最优子结构的性质最优解包含着其子问题的最优解

其次观察子问题之间是否有重叠

如果满足了上述条件,那么毫不犹豫用动态规划(算法导论里面还有提到贪心算法)

那么我们在实际过程中如何发觉原问题与子问题的关系呢?也就是如何挖掘最优子结构的性质

  • 首先先随机做出一个选择:比如我们切钢条,不知道第一刀切到哪,那么我们就随机选择一个位置切割,再比如我们划分矩阵链,不知道第一个划分位置在哪,我们也随机选择一个位置。那么做出的第一个选择,会产生多个待解的子问题

    还有一个重要的是我们不知道最优解到底是什么,那么我们就假设我们第一次的选择就是最优解,那么我们接下来的任务就是如何刻画这个最优解的子问题空间

  • 然后再继续寻找子问题的最优解,这样一步一步寻找就会找到一个通用的递归关系

还需要注意的是:尽量保证子问题空间简单,在必要时才扩展

比如我们前面切钢条,本来我们划分的是两个子问题:如果随机切一刀,那么必然会产生两部分:长度为i和长度为n-i,那么我们对于两部分又要分别去找最优切割方案,如果我们换个思路,就能将两个子问题空间缩小为1个子问题空间

图片描述

但是这种思路不能用于矩阵乘积,因为一旦超过了3个矩阵那么有需要重新寻找最优的划分位置,所以那道题只能是两个子问题空间A[i,k]和A[k,j]

估算动态规划的时间复杂度

我们可以根据子问题的个数以及每个子问题需要考虑的选择数来粗略估计时间复杂度

对于钢条那题r(n) = max(p(i) + r(n - i)) 其中i ∈ [1,n]

也就是一共有n个子问题,而对于每个子问题又有 n-i种选择 ,所以大概的时间复杂度为O(n^2)

对于矩阵那题,

图片描述

算法导论后面还讲了一pa拉烧脑的,比如子问题图中存在环怎么办,以及最长公共子序列,最优二叉搜索树。。。我没有继续看下去了,有兴趣的可以找来仔细研读研读今天小秋就浅尝辄止到这啦~


欢迎关注:小秋的博客(包含Java后台开发,算法,数据结构,分布式,计算机网络等),小秋会时不时的分享自己的学习心得给大家

码字不易,点个赞吧:+1:Related image

查看原文

赞 0 收藏 0 评论 0

flyingcr 收藏了文章 · 2019-08-11

海量数据中寻找中位数

题目

只有2G内存的pc机,在一个存有10G个整数的文件,从中找到中位数,写一个算法。

思路一:外排序(排序-归并)

什么是外排序

外排序就是由于数据量太大不能一次性加载到内存,所以需要先暂时用外存储器(硬盘)将数据存起来,然后依次读入一部分数据到内存,排序之后,生成临时文件存储到硬盘,最后再对这些临时文件进行一个归并,得到最后的排序结果(在合并的过程中虽然不需要多大内存,但是会产生频繁的IO操作,频繁的读磁盘和写磁盘)

《编程之法》中的例子:

假定现在有20个数据的文件A:{5 11 0 18 4 14 9 7 6 8 12 17 16 13 19 10 2 1 3 15},但一次只能使用仅装4个数据的内容,所以,我们可以每趟对4个数据进行排序,即5路归并,具体方法如下述步骤:

  • 我们先把“大”文件A,分割为a1,a2,a3,a4,a5等5个小文件,每个小文件4个数据

    • a1文件为:5 11 0 18
    • a2文件为:4 14 9 7
    • a3文件为:6 8 12 17
    • a4文件为:16 13 19 10
    • a5文件为:2 1 3 15
  • 然后依次对5个小文件分别进行排序

    • a1文件完成排序后:0 5 11 18
    • a2文件完成排序后:4 7 9 14
    • a3文件完成排序后:6 8 12 17
    • a4文件完成排序后:10 13 16 19
    • a5文件完成排序后:1 2 3 15
  • 最终多路归并,完成整个排序

    • 整个大文件A文件完成排序后:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

本题思路:先通过外排序进行排序再寻找中位数

先将这10G的数据等分成5份存储到硬盘中,然后依次读入一份到内存里面,进行排序,然后将这5份数据进行归并得到最后的排序结果,然后找出中位数第5G大

思路二:堆排序(转换为求前5G大的元素)

我们知道利用堆排序处理海量数据的topK是非常合适不过了,因为它不用将所有的元素都进行排序,只需要比较和根节点的大小关系就可以了,同时也不需要一次性将所有的数据都加载到内存;对于海量数据而言,要求前k小/大的数,我们只需要构建一个k个大小的堆,然后将读入的数依次和根节点比较就行了(当然这里的前提是内存需要存的下k个数)

最大堆求前n小,最小堆求前n大。

1、前k小:构建一个k个数的最大堆,当读取的数大于根节点时,舍弃;当读取的数小于根节点时,替换根节点,重新塑造最大堆,然后继续读取,最后读取完所有的数据之后,最大堆中的数就是最小k个数

2、前k大:构建一个k个数的最小堆,当读取的数小于根节点时舍弃;当读取的数大于根节点时,替换根节点,重新塑造最小堆,然后继续读取,读取完所有的数据之后,最小堆中的数就是最大k个数

所以我们本题采用堆排序来求中位数

对于10G的数据,它的中位数就是第5G个元素,按常理来说我们需要构建一个5G大小的堆,但是允许的内存只有两个G,所以我们先构建一个1G大小的大顶堆,然后求出第1G个元素(根节点),然后利用该元素构建一个新的1G大小的堆,求出第2G大的元素,依次类推,求出第5G大的元素

每次构建一个堆求第几G大的元素,都需要重新遍历完所有10G的数据,相当于要遍历5 * 10G次,这需要频繁的IO操作,需要不断的从硬盘中读取数据

思路三:分而治之:基于二进制位映射分割

基于二进制位将10G数据映射到不同的文件中,利用快速排序的分割思想寻找中位数。

依次读入一部分数据到内存,根据数据的最高位将数据映射到不同的文件中,然后判断中位数可能存在于于哪个文件然后再继续对哪个文件进行分割,知道能够将数据读入内存直接排序

图片描述

该方法相对于外排序和堆排序可以减少磁盘IO的次数,每次可以丢弃一部分数据不再进行读取和写入操作

通过快排的partition思想,时间复杂度为:o(nlogn) ≈ 10G

思路四:基数排序(计数排序)

什么是计数排序(线性时间排序)

前提条件:待排序的数组的n个元素都在(0,k)区间内,k为某个正整数

基本思想:对于n个元素的每个元素x, 找到小于x的元素个数有m个,那么x在最后的排序数组里面的第m+1个位置上

所以关键之处就在于如何寻找小于某个元素的个数

我们首先需要新建一个辅助数组C[0....k]用来统计每个元素出现的次数(并且是按照顺序进行统计)

A[0,...n-1] : 待排序数组

B[0,....n-1]:输出结果

C[0,....k-1]:辅助数组(A[i] <= k-1)

计数排序的伪代码

图片描述

计数排序的优点

具有顺序稳定性:具有相同值的元素在输出数组的顺序与原数组的相对顺序顺序一致

不改变原数组:并没有对原数组进行移动交换比较等操作

适用

计数排序要求待排序数组的每个数都在0-k的范围内,所以一般适用输入范围在一个较小的范围内,可以有重复的数,并且不会改变重复的数的输入顺序

时间复杂度和空间复杂度

时间复杂度:O(n + k)

当 k = O(n)(当桶的数量和原数据的数量趋于相同) ,时间复杂度为O(n)

空间复杂度:O( n + K)

需要一个长度为k的数组存储原数组每个数出现的次数,同时需要一个长度为n的数组存储排序结果

什么是基数排序

基数排序是分别按照最低位到最高位(或者从高位到低位)依次进行排序,如果有d位,那么就需要进行d轮排序

基数排序的分类

最高位优先(Most Significant Digit first)法,简称MSD法:先按k1排序分组,同一组中记录,关键码k1相等,再对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd对各子组排序后。再将各组连接起来,便得到一个有序序列。

最低位优先(Least Significant Digit first)法,简称LSD法:先从kd开始排序,再对kd-1进行排序,依次重复,直到对k1排序后便得到一个有序序列。

基于计数的基数排序

图片描述

时间复杂度和空间复杂度

时间复杂度:O(d * (n + k) )

其中d为最大的数字的位数,k为每位数的取值范围(相当于桶的个数)

空间复杂度:O(n + k)

需要一个长度为k的数组存储原数组每个数出现的次数,同时需要一个长度为n的数组存储排序结果

计数排序、基数排序与其他对比排序算法的比较

计数排序/基数排序通过构建辅助空间保存出现的次数,时间复杂度可以达到θ(n)

其他排序算法比如快速排序,堆排序等,是基于原址排序,不用构建辅助空间,充分利用硬件的缓存以及输入数据的特征,当主存容量有限的情况下,采用排序算法优于计数排序和基数排序

本题思路:基于计数排序的基数排序

由于基数排序需要构建一个辅助空间用来存储每一位对应0-9的数有哪些,所以对于每一个轮回都需要两部分同样大小的内存,对于本题来说内存只有2G,那么一次最多能读取1G的数据,因为还需要1G的内存作为辅助空间

1、依次读取1G的数据到内存,根据最低位映射到对应的桶里,直到读取完10G数据

2、根据次低位将第一轮的排序结果重新映射,知道轮回到最高位

3、依次统计每个桶累加次数,若最高位为6的累加次数为4G,最高位为7的累加次数为6G,那么中位数一定在最高位为7的桶中,在为7的桶中寻找底1G大的数据即为中位数

思路五:桶排序

什么是桶排序

思路:将待排序树组按照某种规则分别分到有限的桶里面,然后在针对每个桶里面的数据进行排序(可以继续递归采用桶排序也可以采用其他比较排序算法),然后将桶里面的数据依次放回到原数组

图片描述

图片描述

适用范围

1、输入数据大约成均匀分布在某个范围内

时间复杂度和空间复杂度

时间复杂度

对n个关键字进行桶排序的时间复杂度分为两个部分:

(1) 将n个元素依次按照某种映射关系映射到对应的桶里,时间复杂度为O(n)

(2) 对于每个桶采用某种比较排序算法进行单独排序,其时间复杂度为 ∑ O(ni*logni) 。其中ni 为第i个桶的数据量。

性能提升:可以从第二部分的时间复杂度下手,即减少对每个桶的排序时间,可以减少每个桶里面的数,或者也可以通过增加桶的数量,当然当桶的数量增加时也会影响空间复杂度

空间复杂度

O(k):需要数组大小为k的空间存储桶

桶排序与基数排序和计数排序的对比

1、最开始桶排序和基数排序都是将数字分配到有限的桶中,不同点是桶排序需要继续针对每一个桶进行排序,而对于基数排序来说不用进一步对每个桶里面的数据进行排序,而是统计每个桶中数的个数,直接映射到本次轮回的排好序的数据(不是最后的结果)然后继续参与下一轮的排序(如果是LSD,那么下一轮就是根据次低位进行分组排序)

2、桶排序适合均匀分布的相对比较密集的数据,基数排序适合比较稀疏的数据(可以是间隔很大的数据)

3、计数排序相对于桶排序来说,桶的数量比较多,同时计数排序需要统计每个桶里面的个数,而桶排序需要对每个桶进行排序

桶排序的应用

假设数据有500万,其值在0-1000的整数,利用桶排序实现

(1)确定桶的个数:由于这里数据的值的范围比较小,所以这里构建1001个桶(如果值的范围为0-10亿那么就不能用10亿个桶,空间复杂度太高,并且一般没有那么大的内存)

(2)可以自定义一个映射函数将数据映射到这1001个桶中

(3)依次将数据从桶中取出就是一个有序队列,并且还能知道每个桶中有多少个数

本题思路:桶排序

假设这10G数据都是32位的无符号整数,那么每个数的值域为(0,2 ^ 32 -1)

(1)我们不可能创建2^32个桶,空间复杂度太大,所以我们创建2 ^16个桶

(2)由于我们的内存只有2G,所以一次读取2G数据,按照某种映射关系映射到对应的桶里面

(3)依次统计每个桶里面的数据,找到中位数的范围,在针对范围中的数据进行排序,找到中位数的具体位置

思路六:bitmap位图算法

bitmap就是适用一个bit位代表一个数,所有bit位为1的下标就是排好序的数组(当然也可以用2个bit为代表一个数,或者多个)

图片描述
位图的特点

1) 存储空间的选择受最大值的影响

bitmap的应用

1)查找:先将所有数据映射到bitmap里面,然后判断目标数是否在bitmap里面

2)判断重复:依次将数据放入bitmap里面,若已经放入(该bit位为1),那么就重复

3)找出不重复的数:使用2-bitmap,00表示为出现,01表示出现1次,10表示出现多次,当遍历完所有数据之后,筛选出bit位为00的下标;或者使用两个1-bitmap,如果重复就放入另外一个bitmap,那么另外一个bitmap为1的位都是重复的数

本题思路:使用位图法

假设10G数据都为无符号整数(范围为0-2^32),考虑到可能原数据中可能有重复,所以我们采用两个bit位来表示一个整数,00表示为出现,01表示出现1次,10表示出现多次

所需要的内存为

图片描述

对于10G的数据我们只需要1G的内存就能够表示出来所有的数据,可见bitmap的压缩性之强

我们依次读取10G数据,然后转换为位图表示,去掉所有bit位为00的位置,找到中间下标就是中位数

参考资料:

快速排序中的分割算法的解析与应用

五种常用的算法设计技巧之二:分治算法

海量数据处理之BitMap

https://blog.csdn.net/randyji...

http://blog.sina.com.cn/s/blo...

https://www.cnblogs.com/hapji...

http://www.mojuedu.com/datams...

《编程之法面试和算法心得》

《算法导论第三版》

https://www.byvoid.com/zhs/bl...

https://www.jb51.net/article/...

https://blog.csdn.net/xiajun0...

查看原文

flyingcr 发布了文章 · 2019-07-27

海量数据中寻找中位数

题目

只有2G内存的pc机,在一个存有10G个整数的文件,从中找到中位数,写一个算法。

思路一:外排序(排序-归并)

什么是外排序

外排序就是由于数据量太大不能一次性加载到内存,所以需要先暂时用外存储器(硬盘)将数据存起来,然后依次读入一部分数据到内存,排序之后,生成临时文件存储到硬盘,最后再对这些临时文件进行一个归并,得到最后的排序结果(在合并的过程中虽然不需要多大内存,但是会产生频繁的IO操作,频繁的读磁盘和写磁盘)

《编程之法》中的例子:

假定现在有20个数据的文件A:{5 11 0 18 4 14 9 7 6 8 12 17 16 13 19 10 2 1 3 15},但一次只能使用仅装4个数据的内容,所以,我们可以每趟对4个数据进行排序,即5路归并,具体方法如下述步骤:

  • 我们先把“大”文件A,分割为a1,a2,a3,a4,a5等5个小文件,每个小文件4个数据

    • a1文件为:5 11 0 18
    • a2文件为:4 14 9 7
    • a3文件为:6 8 12 17
    • a4文件为:16 13 19 10
    • a5文件为:2 1 3 15
  • 然后依次对5个小文件分别进行排序

    • a1文件完成排序后:0 5 11 18
    • a2文件完成排序后:4 7 9 14
    • a3文件完成排序后:6 8 12 17
    • a4文件完成排序后:10 13 16 19
    • a5文件完成排序后:1 2 3 15
  • 最终多路归并,完成整个排序

    • 整个大文件A文件完成排序后:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

本题思路:先通过外排序进行排序再寻找中位数

先将这10G的数据等分成5份存储到硬盘中,然后依次读入一份到内存里面,进行排序,然后将这5份数据进行归并得到最后的排序结果,然后找出中位数第5G大

思路二:堆排序(转换为求前5G大的元素)

我们知道利用堆排序处理海量数据的topK是非常合适不过了,因为它不用将所有的元素都进行排序,只需要比较和根节点的大小关系就可以了,同时也不需要一次性将所有的数据都加载到内存;对于海量数据而言,要求前k小/大的数,我们只需要构建一个k个大小的堆,然后将读入的数依次和根节点比较就行了(当然这里的前提是内存需要存的下k个数)

最大堆求前n小,最小堆求前n大。

1、前k小:构建一个k个数的最大堆,当读取的数大于根节点时,舍弃;当读取的数小于根节点时,替换根节点,重新塑造最大堆,然后继续读取,最后读取完所有的数据之后,最大堆中的数就是最小k个数

2、前k大:构建一个k个数的最小堆,当读取的数小于根节点时舍弃;当读取的数大于根节点时,替换根节点,重新塑造最小堆,然后继续读取,读取完所有的数据之后,最小堆中的数就是最大k个数

所以我们本题采用堆排序来求中位数

对于10G的数据,它的中位数就是第5G个元素,按常理来说我们需要构建一个5G大小的堆,但是允许的内存只有两个G,所以我们先构建一个1G大小的大顶堆,然后求出第1G个元素(根节点),然后利用该元素构建一个新的1G大小的堆,求出第2G大的元素,依次类推,求出第5G大的元素

每次构建一个堆求第几G大的元素,都需要重新遍历完所有10G的数据,相当于要遍历5 * 10G次,这需要频繁的IO操作,需要不断的从硬盘中读取数据

思路三:分而治之:基于二进制位映射分割

基于二进制位将10G数据映射到不同的文件中,利用快速排序的分割思想寻找中位数。

依次读入一部分数据到内存,根据数据的最高位将数据映射到不同的文件中,然后判断中位数可能存在于于哪个文件然后再继续对哪个文件进行分割,知道能够将数据读入内存直接排序

图片描述

该方法相对于外排序和堆排序可以减少磁盘IO的次数,每次可以丢弃一部分数据不再进行读取和写入操作

通过快排的partition思想,时间复杂度为:o(nlogn) ≈ 10G

思路四:基数排序(计数排序)

什么是计数排序(线性时间排序)

前提条件:待排序的数组的n个元素都在(0,k)区间内,k为某个正整数

基本思想:对于n个元素的每个元素x, 找到小于x的元素个数有m个,那么x在最后的排序数组里面的第m+1个位置上

所以关键之处就在于如何寻找小于某个元素的个数

我们首先需要新建一个辅助数组C[0....k]用来统计每个元素出现的次数(并且是按照顺序进行统计)

A[0,...n-1] : 待排序数组

B[0,....n-1]:输出结果

C[0,....k-1]:辅助数组(A[i] <= k-1)

计数排序的伪代码

图片描述

计数排序的优点

具有顺序稳定性:具有相同值的元素在输出数组的顺序与原数组的相对顺序顺序一致

不改变原数组:并没有对原数组进行移动交换比较等操作

适用

计数排序要求待排序数组的每个数都在0-k的范围内,所以一般适用输入范围在一个较小的范围内,可以有重复的数,并且不会改变重复的数的输入顺序

时间复杂度和空间复杂度

时间复杂度:O(n + k)

当 k = O(n)(当桶的数量和原数据的数量趋于相同) ,时间复杂度为O(n)

空间复杂度:O( n + K)

需要一个长度为k的数组存储原数组每个数出现的次数,同时需要一个长度为n的数组存储排序结果

什么是基数排序

基数排序是分别按照最低位到最高位(或者从高位到低位)依次进行排序,如果有d位,那么就需要进行d轮排序

基数排序的分类

最高位优先(Most Significant Digit first)法,简称MSD法:先按k1排序分组,同一组中记录,关键码k1相等,再对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd对各子组排序后。再将各组连接起来,便得到一个有序序列。

最低位优先(Least Significant Digit first)法,简称LSD法:先从kd开始排序,再对kd-1进行排序,依次重复,直到对k1排序后便得到一个有序序列。

基于计数的基数排序

图片描述

时间复杂度和空间复杂度

时间复杂度:O(d * (n + k) )

其中d为最大的数字的位数,k为每位数的取值范围(相当于桶的个数)

空间复杂度:O(n + k)

需要一个长度为k的数组存储原数组每个数出现的次数,同时需要一个长度为n的数组存储排序结果

计数排序、基数排序与其他对比排序算法的比较

计数排序/基数排序通过构建辅助空间保存出现的次数,时间复杂度可以达到θ(n)

其他排序算法比如快速排序,堆排序等,是基于原址排序,不用构建辅助空间,充分利用硬件的缓存以及输入数据的特征,当主存容量有限的情况下,采用排序算法优于计数排序和基数排序

本题思路:基于计数排序的基数排序

由于基数排序需要构建一个辅助空间用来存储每一位对应0-9的数有哪些,所以对于每一个轮回都需要两部分同样大小的内存,对于本题来说内存只有2G,那么一次最多能读取1G的数据,因为还需要1G的内存作为辅助空间

1、依次读取1G的数据到内存,根据最低位映射到对应的桶里,直到读取完10G数据

2、根据次低位将第一轮的排序结果重新映射,知道轮回到最高位

3、依次统计每个桶累加次数,若最高位为6的累加次数为4G,最高位为7的累加次数为6G,那么中位数一定在最高位为7的桶中,在为7的桶中寻找底1G大的数据即为中位数

思路五:桶排序

什么是桶排序

思路:将待排序树组按照某种规则分别分到有限的桶里面,然后在针对每个桶里面的数据进行排序(可以继续递归采用桶排序也可以采用其他比较排序算法),然后将桶里面的数据依次放回到原数组

图片描述

图片描述

适用范围

1、输入数据大约成均匀分布在某个范围内

时间复杂度和空间复杂度

时间复杂度

对n个关键字进行桶排序的时间复杂度分为两个部分:

(1) 将n个元素依次按照某种映射关系映射到对应的桶里,时间复杂度为O(n)

(2) 对于每个桶采用某种比较排序算法进行单独排序,其时间复杂度为 ∑ O(ni*logni) 。其中ni 为第i个桶的数据量。

性能提升:可以从第二部分的时间复杂度下手,即减少对每个桶的排序时间,可以减少每个桶里面的数,或者也可以通过增加桶的数量,当然当桶的数量增加时也会影响空间复杂度

空间复杂度

O(k):需要数组大小为k的空间存储桶

桶排序与基数排序和计数排序的对比

1、最开始桶排序和基数排序都是将数字分配到有限的桶中,不同点是桶排序需要继续针对每一个桶进行排序,而对于基数排序来说不用进一步对每个桶里面的数据进行排序,而是统计每个桶中数的个数,直接映射到本次轮回的排好序的数据(不是最后的结果)然后继续参与下一轮的排序(如果是LSD,那么下一轮就是根据次低位进行分组排序)

2、桶排序适合均匀分布的相对比较密集的数据,基数排序适合比较稀疏的数据(可以是间隔很大的数据)

3、计数排序相对于桶排序来说,桶的数量比较多,同时计数排序需要统计每个桶里面的个数,而桶排序需要对每个桶进行排序

桶排序的应用

假设数据有500万,其值在0-1000的整数,利用桶排序实现

(1)确定桶的个数:由于这里数据的值的范围比较小,所以这里构建1001个桶(如果值的范围为0-10亿那么就不能用10亿个桶,空间复杂度太高,并且一般没有那么大的内存)

(2)可以自定义一个映射函数将数据映射到这1001个桶中

(3)依次将数据从桶中取出就是一个有序队列,并且还能知道每个桶中有多少个数

本题思路:桶排序

假设这10G数据都是32位的无符号整数,那么每个数的值域为(0,2 ^ 32 -1)

(1)我们不可能创建2^32个桶,空间复杂度太大,所以我们创建2 ^16个桶

(2)由于我们的内存只有2G,所以一次读取2G数据,按照某种映射关系映射到对应的桶里面

(3)依次统计每个桶里面的数据,找到中位数的范围,在针对范围中的数据进行排序,找到中位数的具体位置

思路六:bitmap位图算法

bitmap就是适用一个bit位代表一个数,所有bit位为1的下标就是排好序的数组(当然也可以用2个bit为代表一个数,或者多个)

图片描述
位图的特点

1) 存储空间的选择受最大值的影响

bitmap的应用

1)查找:先将所有数据映射到bitmap里面,然后判断目标数是否在bitmap里面

2)判断重复:依次将数据放入bitmap里面,若已经放入(该bit位为1),那么就重复

3)找出不重复的数:使用2-bitmap,00表示为出现,01表示出现1次,10表示出现多次,当遍历完所有数据之后,筛选出bit位为00的下标;或者使用两个1-bitmap,如果重复就放入另外一个bitmap,那么另外一个bitmap为1的位都是重复的数

本题思路:使用位图法

假设10G数据都为无符号整数(范围为0-2^32),考虑到可能原数据中可能有重复,所以我们采用两个bit位来表示一个整数,00表示为出现,01表示出现1次,10表示出现多次

所需要的内存为

图片描述

对于10G的数据我们只需要1G的内存就能够表示出来所有的数据,可见bitmap的压缩性之强

我们依次读取10G数据,然后转换为位图表示,去掉所有bit位为00的位置,找到中间下标就是中位数

参考资料:

快速排序中的分割算法的解析与应用

五种常用的算法设计技巧之二:分治算法

海量数据处理之BitMap

https://blog.csdn.net/randyji...

http://blog.sina.com.cn/s/blo...

https://www.cnblogs.com/hapji...

http://www.mojuedu.com/datams...

《编程之法面试和算法心得》

《算法导论第三版》

https://www.byvoid.com/zhs/bl...

https://www.jb51.net/article/...

https://blog.csdn.net/xiajun0...

查看原文

赞 8 收藏 6 评论 0

flyingcr 发布了文章 · 2019-07-27

海量数据中寻找中位数

题目

只有2G内存的pc机,在一个存有10G个整数的文件,从中找到中位数,写一个算法。

思路一:外排序(排序-归并)

什么是外排序

外排序就是由于数据量太大不能一次性加载到内存,所以需要先暂时用外存储器(硬盘)将数据存起来,然后依次读入一部分数据到内存,排序之后,生成临时文件存储到硬盘,最后再对这些临时文件进行一个归并,得到最后的排序结果(在合并的过程中虽然不需要多大内存,但是会产生频繁的IO操作,频繁的读磁盘和写磁盘)

《编程之法》中的例子:

假定现在有20个数据的文件A:{5 11 0 18 4 14 9 7 6 8 12 17 16 13 19 10 2 1 3 15},但一次只能使用仅装4个数据的内容,所以,我们可以每趟对4个数据进行排序,即5路归并,具体方法如下述步骤:

  • 我们先把“大”文件A,分割为a1,a2,a3,a4,a5等5个小文件,每个小文件4个数据

    • a1文件为:5 11 0 18
    • a2文件为:4 14 9 7
    • a3文件为:6 8 12 17
    • a4文件为:16 13 19 10
    • a5文件为:2 1 3 15
  • 然后依次对5个小文件分别进行排序

    • a1文件完成排序后:0 5 11 18
    • a2文件完成排序后:4 7 9 14
    • a3文件完成排序后:6 8 12 17
    • a4文件完成排序后:10 13 16 19
    • a5文件完成排序后:1 2 3 15
  • 最终多路归并,完成整个排序

    • 整个大文件A文件完成排序后:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

本题思路:先通过外排序进行排序再寻找中位数

先将这10G的数据等分成5份存储到硬盘中,然后依次读入一份到内存里面,进行排序,然后将这5份数据进行归并得到最后的排序结果,然后找出中位数第5G大

思路二:堆排序(转换为求前5G大的元素)

我们知道利用堆排序处理海量数据的topK是非常合适不过了,因为它不用将所有的元素都进行排序,只需要比较和根节点的大小关系就可以了,同时也不需要一次性将所有的数据都加载到内存;对于海量数据而言,要求前k小/大的数,我们只需要构建一个k个大小的堆,然后将读入的数依次和根节点比较就行了(当然这里的前提是内存需要存的下k个数)

最大堆求前n小,最小堆求前n大。

1、前k小:构建一个k个数的最大堆,当读取的数大于根节点时,舍弃;当读取的数小于根节点时,替换根节点,重新塑造最大堆,然后继续读取,最后读取完所有的数据之后,最大堆中的数就是最小k个数

2、前k大:构建一个k个数的最小堆,当读取的数小于根节点时舍弃;当读取的数大于根节点时,替换根节点,重新塑造最小堆,然后继续读取,读取完所有的数据之后,最小堆中的数就是最大k个数

所以我们本题采用堆排序来求中位数

对于10G的数据,它的中位数就是第5G个元素,按常理来说我们需要构建一个5G大小的堆,但是允许的内存只有两个G,所以我们先构建一个1G大小的大顶堆,然后求出第1G个元素(根节点),然后利用该元素构建一个新的1G大小的堆,求出第2G大的元素,依次类推,求出第5G大的元素

每次构建一个堆求第几G大的元素,都需要重新遍历完所有10G的数据,相当于要遍历5 * 10G次,这需要频繁的IO操作,需要不断的从硬盘中读取数据

思路三:分而治之:基于二进制位映射分割

基于二进制位将10G数据映射到不同的文件中,利用快速排序的分割思想寻找中位数。

依次读入一部分数据到内存,根据数据的最高位将数据映射到不同的文件中,然后判断中位数可能存在于于哪个文件然后再继续对哪个文件进行分割,知道能够将数据读入内存直接排序

图片描述

该方法相对于外排序和堆排序可以减少磁盘IO的次数,每次可以丢弃一部分数据不再进行读取和写入操作

通过快排的partition思想,时间复杂度为:o(nlogn) ≈ 10G

思路四:基数排序(计数排序)

什么是计数排序(线性时间排序)

前提条件:待排序的数组的n个元素都在(0,k)区间内,k为某个正整数

基本思想:对于n个元素的每个元素x, 找到小于x的元素个数有m个,那么x在最后的排序数组里面的第m+1个位置上

所以关键之处就在于如何寻找小于某个元素的个数

我们首先需要新建一个辅助数组C[0....k]用来统计每个元素出现的次数(并且是按照顺序进行统计)

A[0,...n-1] : 待排序数组

B[0,....n-1]:输出结果

C[0,....k-1]:辅助数组(A[i] <= k-1)

计数排序的伪代码

图片描述

计数排序的优点

具有顺序稳定性:具有相同值的元素在输出数组的顺序与原数组的相对顺序顺序一致

不改变原数组:并没有对原数组进行移动交换比较等操作

适用

计数排序要求待排序数组的每个数都在0-k的范围内,所以一般适用输入范围在一个较小的范围内,可以有重复的数,并且不会改变重复的数的输入顺序

时间复杂度和空间复杂度

时间复杂度:O(n + k)

当 k = O(n)(当桶的数量和原数据的数量趋于相同) ,时间复杂度为O(n)

空间复杂度:O( n + K)

需要一个长度为k的数组存储原数组每个数出现的次数,同时需要一个长度为n的数组存储排序结果

什么是基数排序

基数排序是分别按照最低位到最高位(或者从高位到低位)依次进行排序,如果有d位,那么就需要进行d轮排序

基数排序的分类

最高位优先(Most Significant Digit first)法,简称MSD法:先按k1排序分组,同一组中记录,关键码k1相等,再对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd对各子组排序后。再将各组连接起来,便得到一个有序序列。

最低位优先(Least Significant Digit first)法,简称LSD法:先从kd开始排序,再对kd-1进行排序,依次重复,直到对k1排序后便得到一个有序序列。

基于计数的基数排序

图片描述

时间复杂度和空间复杂度

时间复杂度:O(d * (n + k) )

其中d为最大的数字的位数,k为每位数的取值范围(相当于桶的个数)

空间复杂度:O(n + k)

需要一个长度为k的数组存储原数组每个数出现的次数,同时需要一个长度为n的数组存储排序结果

计数排序、基数排序与其他对比排序算法的比较

计数排序/基数排序通过构建辅助空间保存出现的次数,时间复杂度可以达到θ(n)

其他排序算法比如快速排序,堆排序等,是基于原址排序,不用构建辅助空间,充分利用硬件的缓存以及输入数据的特征,当主存容量有限的情况下,采用排序算法优于计数排序和基数排序

本题思路:基于计数排序的基数排序

由于基数排序需要构建一个辅助空间用来存储每一位对应0-9的数有哪些,所以对于每一个轮回都需要两部分同样大小的内存,对于本题来说内存只有2G,那么一次最多能读取1G的数据,因为还需要1G的内存作为辅助空间

1、依次读取1G的数据到内存,根据最低位映射到对应的桶里,直到读取完10G数据

2、根据次低位将第一轮的排序结果重新映射,知道轮回到最高位

3、依次统计每个桶累加次数,若最高位为6的累加次数为4G,最高位为7的累加次数为6G,那么中位数一定在最高位为7的桶中,在为7的桶中寻找底1G大的数据即为中位数

思路五:桶排序

什么是桶排序

思路:将待排序树组按照某种规则分别分到有限的桶里面,然后在针对每个桶里面的数据进行排序(可以继续递归采用桶排序也可以采用其他比较排序算法),然后将桶里面的数据依次放回到原数组

图片描述

图片描述

适用范围

1、输入数据大约成均匀分布在某个范围内

时间复杂度和空间复杂度

时间复杂度

对n个关键字进行桶排序的时间复杂度分为两个部分:

(1) 将n个元素依次按照某种映射关系映射到对应的桶里,时间复杂度为O(n)

(2) 对于每个桶采用某种比较排序算法进行单独排序,其时间复杂度为 ∑ O(ni*logni) 。其中ni 为第i个桶的数据量。

性能提升:可以从第二部分的时间复杂度下手,即减少对每个桶的排序时间,可以减少每个桶里面的数,或者也可以通过增加桶的数量,当然当桶的数量增加时也会影响空间复杂度

空间复杂度

O(k):需要数组大小为k的空间存储桶

桶排序与基数排序和计数排序的对比

1、最开始桶排序和基数排序都是将数字分配到有限的桶中,不同点是桶排序需要继续针对每一个桶进行排序,而对于基数排序来说不用进一步对每个桶里面的数据进行排序,而是统计每个桶中数的个数,直接映射到本次轮回的排好序的数据(不是最后的结果)然后继续参与下一轮的排序(如果是LSD,那么下一轮就是根据次低位进行分组排序)

2、桶排序适合均匀分布的相对比较密集的数据,基数排序适合比较稀疏的数据(可以是间隔很大的数据)

3、计数排序相对于桶排序来说,桶的数量比较多,同时计数排序需要统计每个桶里面的个数,而桶排序需要对每个桶进行排序

桶排序的应用

假设数据有500万,其值在0-1000的整数,利用桶排序实现

(1)确定桶的个数:由于这里数据的值的范围比较小,所以这里构建1001个桶(如果值的范围为0-10亿那么就不能用10亿个桶,空间复杂度太高,并且一般没有那么大的内存)

(2)可以自定义一个映射函数将数据映射到这1001个桶中

(3)依次将数据从桶中取出就是一个有序队列,并且还能知道每个桶中有多少个数

本题思路:桶排序

假设这10G数据都是32位的无符号整数,那么每个数的值域为(0,2 ^ 32 -1)

(1)我们不可能创建2^32个桶,空间复杂度太大,所以我们创建2 ^16个桶

(2)由于我们的内存只有2G,所以一次读取2G数据,按照某种映射关系映射到对应的桶里面

(3)依次统计每个桶里面的数据,找到中位数的范围,在针对范围中的数据进行排序,找到中位数的具体位置

思路六:bitmap位图算法

bitmap就是适用一个bit位代表一个数,所有bit位为1的下标就是排好序的数组(当然也可以用2个bit为代表一个数,或者多个)

图片描述
位图的特点

1) 存储空间的选择受最大值的影响

bitmap的应用

1)查找:先将所有数据映射到bitmap里面,然后判断目标数是否在bitmap里面

2)判断重复:依次将数据放入bitmap里面,若已经放入(该bit位为1),那么就重复

3)找出不重复的数:使用2-bitmap,00表示为出现,01表示出现1次,10表示出现多次,当遍历完所有数据之后,筛选出bit位为00的下标;或者使用两个1-bitmap,如果重复就放入另外一个bitmap,那么另外一个bitmap为1的位都是重复的数

本题思路:使用位图法

假设10G数据都为无符号整数(范围为0-2^32),考虑到可能原数据中可能有重复,所以我们采用两个bit位来表示一个整数,00表示为出现,01表示出现1次,10表示出现多次

所需要的内存为

图片描述

对于10G的数据我们只需要1G的内存就能够表示出来所有的数据,可见bitmap的压缩性之强

我们依次读取10G数据,然后转换为位图表示,去掉所有bit位为00的位置,找到中间下标就是中位数

参考资料:

快速排序中的分割算法的解析与应用

五种常用的算法设计技巧之二:分治算法

海量数据处理之BitMap

https://blog.csdn.net/randyji...

http://blog.sina.com.cn/s/blo...

https://www.cnblogs.com/hapji...

http://www.mojuedu.com/datams...

《编程之法面试和算法心得》

《算法导论第三版》

https://www.byvoid.com/zhs/bl...

https://www.jb51.net/article/...

https://blog.csdn.net/xiajun0...

查看原文

赞 8 收藏 6 评论 0

flyingcr 发布了文章 · 2019-07-22

机器人的运动范围

题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?

思路一:回溯法

public class Solution {
  public int movingCount(int threshold, int rows, int cols) {
        int count = 0;
        boolean[] isVisited = new boolean[rows * cols];
        count = movingCountCore(threshold, rows, cols, isVisited,0,0,count);
        return count;

    }
    public int movingCountCore(int threshold,int rows,int cols,boolean[] isVisited,int row,int col,int count){
        if(row >= 0 && row < rows && col >= 0 && col < cols && !isVisited[row * cols + col] && getDigitSum(row) + getDigitSum(col) <= threshold){
            isVisited[row * cols + col] = true;
            count = 1 + movingCountCore(threshold,rows,cols,isVisited,row,col + 1,count)
                    + movingCountCore(threshold,rows,cols,isVisited,row-1,col ,count)
                    + movingCountCore(threshold,rows,cols,isVisited,row+1,col,count)
                    + movingCountCore(threshold,rows,cols,isVisited,row,col - 1,count);
        }
        return count;

    }

    public int getDigitSum(int num){
        int sum = 0;
        while (num > 0 ){
            sum += num % 10;
            num = num / 10;
        }
        return sum;
    }
}

参考

《剑指offer纪念版》

查看原文

赞 0 收藏 0 评论 0

flyingcr 发布了文章 · 2019-07-22

矩阵中的路径

[TOC]

题目描述

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
    
    }


}

思路

采用回溯法,从矩阵的第一个节点开始搜索,一旦搜索到和字符串的字符相等,那么又从该节点的上,下,左,右节点进行搜索是否和下一个字符相等,如果搜索完上下左右都不相等,那么就回退到上一个字符,重新继续搜索

 public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        if(matrix == null || matrix.length == 0 || str == null || str.length == 0 || rows * cols != matrix.length)
            return false;
        boolean[] isVisited = new boolean[rows * cols];
        int pathLen = 0;
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(hasPathCore(matrix,rows,cols,i,j,str,isVisited,pathLen))
                    return true;
            }

        }
        return false;
    }
    public boolean hasPathCore(char[] matrix,int rows,int cols,int row,int col,char[] str,boolean[] isVisited,int pathLen){
        boolean flag = false;
        int index = row * cols + col;
        if(row >= 0 && row < rows && col >= 0 && col < cols && !isVisited[index] && matrix[index] == str[pathLen]){
            pathLen++;
            isVisited[index] = true;
            if(pathLen==str.length)
                return true ;
            flag = hasPathCore(matrix,rows,cols,row,(col + 1),str,isVisited,pathLen) ||
                   hasPathCore(matrix,rows,cols,row,(col - 1),str,isVisited,pathLen) ||
                   hasPathCore(matrix,rows,cols,row+1,col,str,isVisited,pathLen) ||
                   hasPathCore(matrix,rows,cols,row-1,col,str,isVisited,pathLen) ;
            if(!flag){
                pathLen--;
                isVisited[index] = false;
            }
        }
        return flag;
    }

补充:回溯法(退一步海阔天空)

什么是回溯法

采用试错的思想,分步去解决问题,在分步解决问题的过程中发现现有的分步答案是错的,那么就放弃或者回退到上一步甚至上几步,然后通过其他分步去继续寻找答案。

回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:

  • 找到一个可能存在的正确的答案
  • 在尝试了所有可能的分步方法后宣告该问题没有答案
    在最坏的情况下,回溯法会导致一次复杂度为指数时间的计算。

回溯法的特点

1、按照选优条件深度优先搜索

2、当发现并不是最优或者达不到目标时,退回一步重新搜索

3、能进则进,进不了则换,换不了则退

参考

《剑指offer纪念版》

《趣学算法》

查看原文

赞 0 收藏 0 评论 0

flyingcr 发布了文章 · 2019-07-22

滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

思路一

图片描述

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size){
        ArrayList<Integer> list = new ArrayList<>();
        if(num == null || num.length == 0 || size == 0)return list;
       
        for(int i = 0; i < num.length - size + 1; i++){
            int tempMax = num[i];
            for(int j = 1;j < size;j++){
                if(num[i+j] > tempMax) tempMax = num[i+j];
            }
            list.add(tempMax);

        }
        return list;

    }
}

时间复杂度:O(kn),k为滑动窗口的大小,n为数组的长度

思路二

使用一个双端队列保存有可能成为窗口最大值的数据

这里之所以采用双端队列是因为,当即将进入窗口的数据大于队列中的值,那么队列中的值会依次从尾部进行删除,如果队列头部的数字已经滑出窗口,那么也需要将队列的头部删除,所以我们需要在队列的头部和尾部都进行删除操作,所以需要一个双端队列

图片描述

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
         ArrayList<Integer> windowMax = new ArrayList<>();
        // 条件检查
        if (num == null || size < 1 || num.length < 1|| size > num.length) {
            return windowMax;
        }
        Deque<Integer> indexQueue = new LinkedList<>();
        /**
         *         窗口还没有被填满时,找最大值的索引
         */
        for (int i = 0; i < size && i < num.length; i++) {
            // 如果索引对应的值比之前存储的索引值对应的值大或者相等,就删除之前存储的值
            while (!indexQueue.isEmpty() && num[i] >= num[indexQueue.getLast()]) {
                indexQueue.removeLast();
            }
            //  添加索引
            indexQueue.addLast(i);
        }
        // 窗口已经被填满了
        for (int i = size; i < num.length; i++) {
            // 第一个窗口的最大值保存
            windowMax.add(num[indexQueue.getFirst()]);
            // 如果新加入窗口的的值比队列中的值大,就删除队列的值
            while (!indexQueue.isEmpty() && num[i] >= num[indexQueue.getLast()]) {
                indexQueue.removeLast();
            }
            // 删除队列中已经滑出窗口的数据对应的下标
            if (!indexQueue.isEmpty() && indexQueue.getFirst() <= (i - size)) {
                indexQueue.removeFirst();
            }
            // 可能的最大的下标索引入队
            indexQueue.addLast(i);
        }
        // 最后一个窗口最大值入队
        windowMax.add(num[indexQueue.getFirst()]);
        return windowMax;
    }
}
查看原文

赞 2 收藏 1 评论 0

flyingcr 发布了文章 · 2019-07-19

包含min函数的栈

题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

思路一:不改变原栈的顺序,时间复杂度为O(n)

idea:本题需要重新自定义push,pop,top,min方法,使得能够通过min方法随时得到当前栈中的最小元素。

首先如果我们不考虑这是一个栈,而是一个普通的数组,那么就很简单,我们只需要定义一个数minNumber存储当前数组中的最小值。遍历整个数组,如果当前数小于最小值min,那么就更新最小值,否则就继续遍历。

那么我们能不能将这种思想转换到栈中呢?首先我们必须清楚栈的特点:“先进后出,后进先出”。如果我们依次将栈中的元素弹出来和minNumber比较,如果小于最小值minNumber,就更新minNumber,否则就继续弹出。这种思想事实上是可以借鉴的。但是有个问题是当我们把最小值找到了,但是这个时候栈也空了。所以我们就需要一个辅助栈来暂时存储弹出来的数,将栈里面的数弹空了,最小值也找到了,那么就将辅助栈里面的数又重新压入原来的栈中。这样两次出栈和入栈的过程也不会改变原来栈中的顺序。

图片描述

import java.util.Stack;
 
public class Solution {
    
      //创建两个栈对象,一个用于存储原栈数据,一个用于暂时辅助存储数据
      Stack<Integer> stack = new Stack<Integer>();
      Stack<Integer> subStack = new Stack<Integer>();
 
    
    public void push(int node) {
        stack.push(node);
        
    }
    
    //pop操返回栈顶元素的同时会remove栈顶元素
    public void pop() {
        int p = stack.pop();
        
    }
    
    //这里返回栈的顶部元素,但是不会remove栈顶元素
    public int top() {
        int topNumber = stack.peek();
        return topNumber;
        
    }
    
    public int min() {
        int minNumber = Integer.MAX_VALUE;
        //依次取出栈里面的数直到栈为空
        while(stack.isEmpty() != true){
            //得到栈顶元素
            int number = stack.pop();
            if(minNumber > number){
                minNumber = number;
            }
            //弹出一个,压入一个
            subStack.push(number);
        }
        //最后将辅助栈中的元素再重新压入原来的栈里
        while(subStack.isEmpty() != true){
            stack.push(subStack.pop())
        }
        
        return minNumber;
        
    }
}

思路二

利用辅助栈存储栈中对应元素的最小值,使得辅助栈的栈顶永远是最小值,从而可以以o(1)的时间复杂度获取到最小值

图片描述

package code;

import javax.activation.MailcapCommandMap;
import java.util.Stack;

public class Stacke1 {

    Stack stack = new Stack<Integer>();
    Stack subStack = new Stack<Integer>();
    public void push(int node) {
        stack.push(node);
        //这里的短路或不能调换位置
        if(subStack.isEmpty() || node < (int)subStack.peek()){
            subStack.push(node);
        } else {
            subStack.push(subStack.peek());
        }
    }

    public void pop() {
        stack.pop();
        subStack.pop();
    }

    public int top() {
        return (int) stack.peek();
    }

    public int min() {
        return (int)subStack.peek();
    }

}
查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 20 次点赞
  • 获得 3 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 3 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2019-01-31
个人主页被 678 人浏览