朝小闇的博客

海上月是天上月,眼前人是心上人

Prime算法和Kruskal算法都是无向图中最短路径算法,给出例证场景如下:

1

注:代码部分基本上复用博客https://blog.csdn.net/weixin_43312097/article/details/108238521#comments_14014195

Prime算法

简要介绍

  • 最小生成树算法,从顶点的角度出发,适合解决边稠密的连通网;
  • 时间复杂度为n2,以下代码为n3
  • 从已访问顶点开始,每次查找已访问边集合到未访问边集合中的最短未完全访问路径,直到找到n-1条边结束;

主要思想

  1. 将所有顶点划分成已访问和未访问两个集合;
  2. 从已访问集合依次取出一个顶点作为出度;
  3. 从未访问集合依次取出一个顶点作为入度;
  4. 取以该出入度为顶点的边的最小值并记录,将该最小值的入度顶点移动到已访问集合;
  5. 假设共有n个顶点,循环n-1次即找到所有边;
阅读全文 »

Dijkstra算法

简要介绍

  • Dijkstra算法是一种广度优先搜索算法
  • 主要解决赋权值有向图或无向图的单源点最短路径问题
  • 时间复杂度是${n^2}$;
  • 权值必须为正;

主要思想

  1. 设置两个顶点集S和T,集合S中存放已经找到最短路径的顶点,集合T中存放尚未找到最短路径的顶点;
  2. 初始状态下,集合S中只包含源点V,集合T中包含除源点之外的所有顶点,此时源点到各顶点的最短路径为两个顶点所连边上的权值,如果没有边,则最小路径为无穷大(代码中设置为最大正整数);
  3. 依次从集合T中选取到源点V路径最短的顶点${v_i}$放入集合S中;
  4. 修改从源点V到T中顶点的最短路径长度;
  5. 循环上面两项直到顶点集T为空;
阅读全文 »

1.网络层概述

网络层存在于网络中所有主机和路由器中(路由器具有截断的协议栈,没有网络层以上的部分),由数据平面控制平面两部分组成。

数据平面:是网络层中属于每台路由器自身的功能,决定到达路由器输入链路的数据报(网络层分组)如何转发到该路由器某一个具体的输出链路。

控制平面:是网络范围内的逻辑,控制数据报沿着从源主机到目的主机的端到端路径中路由器的路由方式。

如图所示:

  • 过程实例:
    • H1中的网络层取得来自于H1运输层的报文段,并将其封装成数据报,向相邻路由器发送该数据报;
    • 在接收方路由器H2,网络层接收来自相邻路由器R2的数据报,提取出相应报文段并上传给H2运输层;
  • 每台路由器数据平面作用是从其输入链路向其输出链路转发数据报,控制平面作用是协调本地的每台路由器转发动作,使数据报沿着源到目的主机之间的路由器路径进行端到端传输;

image-20201110165452010

阅读全文 »

工作流程

本次数据分析目标是对大量的txt文本匹配查询一系列词汇出现的总频次,并从另一个大型二维数组(第一列元素存储了一系列文件名,需要将第二列和第三列元素相应添加到Excel表格中)中对每个文件名做相应的匹配查询

使用python进行数据分析工作,主要工作流程如下:

  1. a1a2文本中读取内容(中文情感词汇,积极词汇表和消极词汇表)并以键值对形式存入两个大的字典中,键用取出来的词语表示,值则初始化赋值为0,用来对目标文本进行匹配分析对应词语出现次数:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    includesPositive = {}
    includesNegative = {}
    def readNegativeFile(path):
    txt = open(path, 'r', encoding='UTF-8').readlines()
    for key in txt:
    key = key.replace('\n', '')
    print(key)
    includesNegative[key] = 0
    def readNegativeFile(path):
    txt = open(path, 'r', encoding='UTF-8').readlines()
    for key in txt:
    key = key.replace('\n', '')
    print(key)
    includesNegative[key] = 0
阅读全文 »

1.运输层概述

运输层服务过程:在发送端(端系统),运输层将从发送端应用程序进程接收到的报文转换为运输层分组(报文段),进而传递给网络层,网络层将其封装成网络层分组(数据报)并向目的地发送;在接收端(端系统),网络层从数据报中提取运输层报文段,并根据该报文段(应用程序决定使用哪一个运输层协议)上交给运输层。

1.1 运输层和网络层的关系

网络层提供了主机之间的逻辑通信,而运输层为运行在不同主机上的进程之间提供逻辑通信

1.2 因特网运输层概述

因特网提供两种运输层协议:

  • UDP:用户数据报协议,为应用程序提供不可靠、无连接的服务;
  • TCP:传输控制协议,为应用程序提供可靠的、面向连接的服务,除此之外提供附加服务:
    • 可靠数据传输服务,通过使用流量控制、序号、确认和定时器,TCP确保正确地、按序地将数据从发送进程交付给接收进程;
    • 拥塞控制服务,通过调节TCP连接的发送端发送进入网络的流量速率来防止任何一条TCP连接占用过多带宽;
  • UDP和TCP最基本的功能是将两个端系统间IP的交付服务扩展为运行在端系统上的两个进程之间的交付服务,即应用层只考虑进程交互,而不必关心这两个进程的具体位置;
    • 该基本服务被称为运输层的多路复用多路分解
阅读全文 »

SpringBoot

1.创建SpringBoot文件

1.1 官网创建文件并下载,使用IDEA打开

1.2 IDEA创建

  • New Project -> Spring Initializr(本质也是从官网下载的模板格式);
  • 添加 java web 依赖;

2.文件简析

2.1 pom.xml

  • 配置文件,主要有四个部分:

    • 项目元数据信息:创建时输入的Project Metadata部分,也就是Meaven项目的基本元素,包括groupId、artifactId、version、name、description等;
    • parent:继承spring-boot-starter-parent的依赖管理、控制版本和打包等内容;
    • dependencies:项目具体依赖,下面包含了spring-boot-starter-web用于实现HTTP接口(该依赖包含了Spring MVC,且使用Tomcat作为默认嵌入式容器),spring-boot-starter-test是用于编写后续单元测试的依赖包:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    <!--  在这个标签中添加  -->
    <dependencies>
    <!-- 添加依赖,格式为 spring-boot-starter- 这是springboot启动器的标准格式 -->
    <!-- web依赖,tomcat -->
    <dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-web</artifactId>
    </dependency>

    <dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-test</artifactId>
    <scope>test</scope>
    <exclusions>
    <exclusion>
    <groupId>org.junit.vintage</groupId>
    <artifactId>junit-vintage-engine</artifactId>
    </exclusion>
    </exclusions>
    </dependency>
    </dependencies>
    • build:构件配置部分,默认使用了spring-boot-maven-plugin,即打jar包插件;
阅读全文 »

注解

定义

  • Annotation是从JDK5.0开始引入的新技术;
  • Annotation的作用:
    • 可以被其它程序(编译器等)读取;
    • 不是程序本身,可以对程序作出解释(这一点和注释(comment)没什么区别);
  • Annotation格式:
    • 注解是以“@注释名”在代码中存在的,可以添加一些参数值,如:@SuppressWarnings(value=”unchecked”).
  • Annotation在哪里使用:
    • 可以附加在package、class、method、filed等上面,相当于给他们添加了额外的辅助信息,可以通过反射机制编程实现对这些元数据的访问;
阅读全文 »

1.应用层协议原理

  • 研发网络应用程序的核心是写出能够运行在不同端系统和通过网络彼此通信的程序:
    • Web应用程序中,有两个互相通信的不同的程序:运行在用户主机上的浏览器程序和运行在Web服务器主机上的Web服务器程序;
    • P2P文件共享系统,在参与文件共享的社区中的每台主机中都有一个程序;

image-20201013081228922

1.1 网络应用程序体系结构

应用程序体系结构由应用程序研发者设计,规定了如何在各种端系统上组织该应用程序

阅读全文 »

1.什么是因特网

因特网是一种特定的计算机网络(只是其中一种类型);

1.1 具体构成描述

  • 主机(端系统):

    • 接入到因特网的设备被称作主机;
    • 由通信链路和分组交换机连接;
    • 端系统通过ISP接入因特网;
    • 因特网端系统包括:
      • 桌面计算机(桌面PC、Mac和Linux设备);
      • 服务器(Web和电子邮件服务器);
      • 移动计算机(智能手机和平板电脑);
  • 分组:

    • 由发送端系统将数据进行分段,并为每段加上首部字节组成的信息包;
    • 一个分组所经历的一系列通信链路和分组交换机称为通过该网络的路径(path/route);
  • 通信链路:

    • 由不同类型的物理媒体组成,物理媒体包括同轴电缆、光纤等;
    • 不同的链路以不同的速率传输数据;
    • 传输速度以比特/秒(bit/s或bps)为单位;
  • 分组交换机:

    • 自身连接两段小型通信链路,用于连接外部真正的通信链路:

      • 入通信链路用来接收到达的分组;
      • 出通信链路用来转发接收到的分组;
      • 一般所说的路由器链路传输速率就是指出链路传输到通信链路的速率;
    • 两种类型:

      • 路由器(router);
      • 链路层交换机;
    • 作用是将特定的分组转发到特定的链路;

    • 通过时延图观察其构成:

    image-20200929232833820

  • 因特网服务提供商(ISP):

    • 每个ISP自身就是一个由多台分组交换机和多段通信链路组成的网络;
  • 网络协议:

    • 用来控制因特网中信息的接收和发送的规则和标准;
    • 因特网的主要协议统称为TCP/IP;
阅读全文 »

1.简介

  • FFmpeg是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序(——来源于百度百科)

2.下载并配置环境

  • 直接百度进入官网下载即可;
  • 下载完成后将解压后的文件夹重命名为ffmpeg,并且放至自己电脑的环境目录下;
  • 前往配置环境目录PATH,连同ffmpeg目录下的bin目录路径一起粘贴到PATH配置下新的路径即可;
阅读全文 »