数据结构-2-链表

链表简介

首先，链表不需要连续的你内存空间，它通过“指针”将一组零散的内存块串联起来使用；每一个内存块实际上被称作“节点”，每个节点除了数据还有一个记录下一个节点位置的指针，比如指向后记节点叫做next 指向前一个节点地址称作prev；如果是链表的尾部，next 指向的是一个null。

常见的链表有单向链表和双向链表。

单向链表只有数据和指向下一个节点的指针，双向链表包括数据和指向上一个节点和下一个节点的两个指针。

操作复杂度分析

单链表的插入、删除操作的时间复杂度都是 O(1)：比如新增节点，只需要把上一个节点的指针指向加入的数据，并将新节点的指针指向下一个节点即可（删除同理）；

双向链表因为有了前驱指针，在特定情况下性能会更加高效，体现在：

删除：

  • 删除指定值的节点

无论是单向链表还是双向链表，都需要将整个链表遍历一遍，复杂度相等，为 O(n)。

  • 删除指定指针指向的节点

对于单向链表，需要将需要被删除的节点的上一个节点的 next 指针指向被删除的节点的下一个节点，所以需要从头开始遍历，如果某节点的 next 指向需要被删除的那个节点，则将它进行修改，所以复杂度是O(n);

对于双向链表，由于被山粗的节点有前驱指针，可以直接通过前驱指针找到上一个节点，修改其 next 指针，所以复杂度是O(1)；性能有提升了。

相关问题

数组和链表 复杂度对比

时间复杂度 数组 链表
随机访问 O(1) O(n)
插入，删除 O(n) O(1)

时间换空间

当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以
选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。

比如在JAVA中，我经常使用 LinkedHashMap ，其实是一个双向链表实现的，虽然他会比较费内存，但是能够保证顺序。

用链表实现了一个 LRU 缓存

常用的缓存清除策略包括：

  • 先进先出策略 FIFO （ First In ， First Out ）

  • 最少使用策略 LFU （ Least Frequently Used ）

  • 最近最少使用策略 LRU （ Least Recently Used ）

使用链表实现一个LRU缓存淘汰算法：

维护一个有序单向链表，链表内最靠尾部的数据是最早访问的（即将被淘汰的），每当有一个新的数据被访问时，可以从头遍历链表：

  • 如果查找到对应数据，将此数据提取（删除并新增）到链表的头部；
  • 如果没有查找到该数据，则检查此时缓存量是否达到阈值：
    • 如果未满直接插入该数据到链表头部；
    • 如果已经满了就山粗链表尾部节点的数据，将新数据插入到链表头部；

利用 CPU 的缓存机制

CPU 在从内存读取数据的时候，会先把读取到的数据加载到 CPU 的缓存中。而 CPU 每次从内存读取数据并不是只读取那个特定要访问的地址，而是读取一个
数据块 ( 这个大小我不太确定。。 ) 并保存到 CPU 缓存中，然后下次访问内存数据的时候就会先从 CPU 缓存开始查找，如果找到就不需要再从内存中取。这样
就实现了比内存访问速度更快的机制，也就是 CPU 缓存存在的意义 : 为了弥补内存访问速度过慢与 CPU 执行速度快之间的差异而引入。
对于数组来说，存储空间是连续的，所以在加载某个下标的时候可以把以后的几个下标元素也加载到 CPU 缓存这样执行速度会快于存储空间不连续的链表存
储。

数据结构-1-数组

学习闲话

一旦设计到框架的选择，技术选型，或者研究工具底层的时候，往往就需要一些通用的知识，比如数据结构和常用的算法，网络协议，操作系统等等知识，算是无论往哪个方向发展的必经之路了。所以这段时间根据极客时间课程《数据结构与算法之美》 的学习写了这一系列的笔记。后期计划再系统学习网络协议，操作系统等系列课程。

进入主题

基本概念

数据就是在内存中使用连续的内存空间，用于存储一系列相似数据的线性表数据结构。

阅读全文

数据结构-0-疑难杂症

复杂度分析

递归怎么理解

其他疑难杂症

数据结构-0-递归

递归简介

递归需要满足的三个条件：

  • 一个问题可以被拆解成几个子问题
  • 子问题与原问题的解题思路是相同的，只有数据规模不一样
  • 需要有终止条件，当数据规模足够小，能够直接得出结果并返回

写递归代码最关键的是写出递推公式，找到终止条件，剩下将递推公式转化为代码就很简单了。

递归注意事项

  • 递归代码写的不合理的时候会出现 堆栈溢出 的问题：

    ​ 函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。避免出现上述问题的措施：

    ​ 限制递归调用的最大深度（超过指定调用深度就进行报错，需要使用局部变量，需要注意解决线程安全问题）；另外最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。

  • 递归的方法层层嵌套，可能出现对于同样的调用做了多次计算。解决办法：

    ​ 通过一个数据结构（比如散列表）来保存已经求解过的 f(k) 。当递归调用到 f(k) 时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算。

  • 递归要注意是否会出现环的问题，一旦出现 A-B-C-A这种环的存在，就会发生死循环。解决办法：

    1. 有人说可以使用散列表存储一个调用结果，如果存在重复调用就是存在环了。比如调用A的到C（保存到散列表，下同） ,调用C得到B ,抵用B得到A,此时的A已经得到过了，说明存在环。===数据规模大的时候占用空间也很大

    2. 有人说可以步长法判断 : 从起点开始分别以 2x,1x 速度出发两个指针 , 当遇到 null 停止 , 相遇点为 null 时说明没有环 。暂时还没太理解【后续继续补充】

  • 递归的调试是一个问题，像规模比较大、递归层次很深的递归代码，几乎无法使用这种调试方式。解决办法：

    1. 打印日志发现，递归值。
    2. 结合条件断点进行调试。

SpringCloud+mybatis+webmagic Mapper注入报错

项目背景

Springcloud+mybatis+webMagic 获取百度热搜榜、搜狗热搜榜等热搜数据并存储到数据库中。

使用Mybatis Generator自动生成Mapper后放置在Mapper文件夹，并添加了对应的注解支持，service无法自动注入Mapper对象。

相关配置

阅读全文 

1
2
3
title: Thrift应用实例
date: 2019-06-12
tags: [java,分布式]

待完善

Thrift是一个跨语言的服务器部署框架，有自己的跨机器通信框架，也是一个代码生成器，可以生成多种语言的通信过程代码。

阅读全文

使用场景

使用webmagic爬取百度榜单的时候，出现超时错误

报错内容

1
2
3
4
5
6
7
09:15:23.811 [pool-1-thread-1] DEBUG org.apache.http.impl.conn.PoolingHttpClientConnectionManager - Connection released: [id: 0][route: {}->http://top.baidu.com:80][total kept alive: 0; route allocated: 0 of 100; total allocated: 0 of 5]
09:15:23.814 [pool-1-thread-1] WARN us.codecraft.webmagic.downloader.HttpClientDownloader - download page http://top.baidu.com/category?c=513&fr=topbuzz error
java.net.SocketTimeoutException: Read timed out
	at java.net.SocketInputStream.socketRead0(Native Method)
	at java.net.SocketInputStream.socketRead(SocketInputStream.java:116)
	at java.net.SocketInputStream.read(SocketInputStream.java:171)
	at java.net.SocketInputStream.read(SocketInputStream.java:141)

问题分析

因为爬虫框架使用了SocketInputStream 读取网页内容，但是下载的网速很慢，使得超时，设置超时时间如下：

1
2
private Site site = Site.me().setRetryTimes(3).setSleepTime(100).
    setUserAgent("Mozilla/5.0 (Windows NT 6.1; WOW64; rv:53.0) Gecko/20100101 Firefox/53.0").setTimeOut(100000);

并没有什么作用。

实际原因：

网速太差，网速好的时候再运行就OK了。

Tomcat日志的理解

几种log

Tomcat默认使用JULI日志系统

1560220401868

Server、Tomcat Localhost Log 和Tomcat Catalina Log:

  1. catalina.out 是tomcat的标准输出(stdout)和标准出错(stderr).是在tomcat的启动脚本里指定的；一般包括控制台输出。
  2. Localhost log 对应 CATALINA_BASE指向目录的localhost.{yyyy-MM-dd}.log 文件。记录的是应用初始化(listener, filter, servlet)未处理的异常最后被tomcat捕获而输出的日志。
  3. Catalina log 对应 CATALINA_BASE指向目录的localhost.{yyyy-MM-dd}.log 文件。 是tomcat自己运行的一些日志。应用向console输出的日志不会输出到catalina.{yyyy-MM-dd}.log。
  4. Tomcat 默认manager应用日志，文件名manager.日期.log，如果配置了其他的项目应用，如下配置了Demo ，会出现demo.{yyyy-MM-dd}.log日志。

阅读全文

Elastic-6-实例

索引：

1
fund_collective_financing_announcement_a

3个分片

1082个文档

类型 type:

1
2
3
NewsDoc

doc
1
2