标签搜索
.png)
搜索到
21
篇与
的结果
-
fast git Gitgit命令获取git仓库git init将当前目录转换为Git仓库该命令将创建一个名为 .git 的子目录，这个子目录含有你初始化的 Git 仓库中所有的必须文件，这些文件是 Git 仓库的骨干。 但是，在这个时候，我们仅仅是做了一个初始化的操作，你的项目里的文件还没有被跟踪。git clone当你执行 git clone 命令的时候，默认配置下远程 Git 仓库中的每一个文件的每一个版本都将被拉取下来。$ git clone 克隆仓库指令 （指定名称）文件状态工作目录里的文件无非就是两种状态：已跟踪与未跟踪状态，已跟踪的文件是指那些被纳入了版本控制的文件，在上一次快照中有它们的记录，在工作一段时间后， 它们的状态可能是未修改，已修改或已放入暂存区。简而言之，已跟踪的文件就是 Git 已经知道的文件。当我们初次克隆某仓库的时候，仓库中的所有文件都是已跟踪文件未修改状态，仓库中的文件一旦发生修改，状态将更改为已修改，在工作时，我们可以将已修改文件放入暂存区，状态更改为暂存，然后我们可以一次性提交所有已经暂存的修改。上图就是文件的生命周期图。git status查看文件状态，状态信息中包含所在的分支以及当前所在分支与远程仓库中对应的分支是否存在偏离 如果文件发生了改变，则在下面则会出现Untracked files的列表，提醒我们没有追踪的文件git add使用命令 git add 开始跟踪一个文件。只要在 Changes to be committed 这行下面的，就说明是已暂存状态。 如果此时提交，那么该文件在你运行 git add 时的版本将被留存在后续的历史记录中。 你可能会想起之前我们使用 git init 后就运行了 git add 命令，开始跟踪当前目录下的文件。 git add 命令使用文件或目录的路径作为参数；如果参数是目录的路径，该命令将递归地跟踪该目录下的所有文件。git add是一个多功能的命令，可以使用他对已修改文件进行暂存如若在暂存后再次修改了该文件，则该文件会同时出现在暂存与未暂存区域，这时我们直接提交提交的是第一次暂存的版本，如若要使用当前的版本需要再次add后再提交将这个命令理解为“精确地将内容添加到下一次提交中”git ignore一般我们总会有些文件无需纳入 Git 的管理，也不希望它们总出现在未跟踪文件列表。 通常都是些自动生成的文件，比如日志文件，或者编译过程中创建的临时文件等。 在这种情况下，我们可以创建一个名为 .gitignore 的文件，列出要忽略的文件的模式。范例： # 忽略所有的 .a 文件 *.a # 但跟踪所有的 lib.a，即便你在前面忽略了 .a 文件 !lib.a # 只忽略当前目录下的 TODO 文件，而不忽略 subdir/TODO /TODO # 忽略任何目录下名为 build 的文件夹 build/ # 忽略 doc/notes.txt，但不忽略 doc/server/arch.txt doc/*.txt # 忽略 doc/ 目录及其所有子目录下的 .pdf 文件 doc/**/*.pdfgit diff此命令比较的是工作目录中当前文件和暂存区域快照之间的差异。 也就是修改之后还没有暂存起来的变化内容。若要查看已暂存的将要添加到下次提交里的内容，可以用 git diff --staged 命令。 这条命令将比对已暂存文件与最后一次提交的文件差异请注意，git diff 本身只显示尚未暂存的改动git commit提交命令，执行后会启动你选择的文本编辑器来输入提交说明。Note 启动的编辑器是通过 Shell 的环境变量 EDITOR 指定的，一般为 vim 或 emacs。 当然也可以按照 起步 介绍的方式， 使用 git config --global core.editor 命令设置你喜欢的编辑器。默认的提交消息包含最后一次运行 git status 的输出，放在注释行里，另外开头还有一个空行，供你输入提交说明。 你完全可以去掉这些注释行，不过留着也没关系，多少能帮你回想起这次更新的内容有哪些。另外，你也可以在 commit 命令后添加 -m 选项，将提交信息与命令放在同一行提交后它会告诉你，当前是在哪个分支（master）提交的，本次提交的完整 SHA-1 校验和是什么（463dc4f），以及在本次提交中，有多少文件修订过，多少行添加和删改过。每一次运行提交操作，都是对你项目作一次快照，以后可以回到这个状态，或者进行比较。git commit 加上 -a 选项，Git 就会自动把所有已经跟踪过的文件暂存起来一并提交，从而跳过 git add 步骤git rmgit rm --cached README可以将指定文件从暂存区中移除，但是不会从本地删除，如果本地删除只需要直接 git rm-f即可，这是一种安全特性，用于防止误删尚未添加到快照的数据，这样的数据不能被 Git 恢复。git mvgit mv 被改文件名 文件名相当于执行三句$ mv README.md README $ git rm README.md $ git add README 如此分开操作，Git 也会意识到这是一次重命名，所以不管何种方式结果都一样。 两者唯一的区别在于，git mv 是一条命令而非三条命令，直接使用 git mv 方便得多。 不过在使用其他工具重命名文件时，记得在提交前 git rm 删除旧文件名，再 git add 添加新文件名。git log查看提交历史git log 有许多选项可以帮助你搜寻你所要找的提交， 下面我们会介绍几个最常用的选项。其中一个比较有用的选项是 -p 或 --patch ，它会显示每次提交所引入的差异（按 补丁 的格式输出）。 你也可以限制显示的日志条目数量，例如使用 -2 选项来只显示最近的两次提交，该选项除了显示基本信息之外，还附带了每次提交的变化。 当进行代码审查，或者快速浏览某个搭档的提交所带来的变化的时候，这个参数就非常有用了。 你也可以为 git log 附带一系列的总结性选项。 比如你想看到每次提交的简略统计信息，可以使用 --stat 选项，另一个非常有用的选项是 --pretty=。 这个选项可以使用不同于默认格式的方式展示提交历史。 这个选项有一些内建的子选项供你使用。 比如 oneline 会将每个提交放在一行显示，在浏览大量的提交时非常有用。 另外还有 short，full 和 fuller 选项，它们展示信息的格式基本一致，但是详尽程度不一。当 oneline 或 format 与另一个 log 选项 --graph 结合使用时尤其有用。 这个选项添加了一些 ASCII 字符串来形象地展示你的分支、合并历史：$ git log --pretty=format:"%h %s" --graph * 2d3acf9 ignore errors from SIGCHLD on trap * 5e3ee11 Merge branch 'master' of git://github.com/dustin/grit |\ | * 420eac9 Added a method for getting the current branch. * | 30e367c timeout code and tests * | 5a09431 add timeout protection to grit * | e1193f8 support for heads with slashes in them |/ * d6016bc require time for xmlschema * 11d191e Merge branch 'defunkt' into local总结Table 2. git log 的常用选项 选项 说明 -p 按补丁格式显示每个提交引入的差异。 --stat 显示每次提交的文件修改统计信息。 --shortstat 只显示 --stat 中最后的行数修改添加移除统计。 --name-only 仅在提交信息后显示已修改的文件清单。 --name-status 显示新增、修改、删除的文件清单。 --abbrev-commit 仅显示 SHA-1 校验和所有 40 个字符中的前几个字符。 --relative-date 使用较短的相对时间而不是完整格式显示日期（比如“2 weeks ago”）。 --graph 在日志旁以 ASCII 图形显示分支与合并历史。 --pretty 使用其他格式显示历史提交信息。可用的选项包括 oneline、short、full、fuller 和 format（用来定义自己的格式）。 --oneline --pretty=oneline --abbrev-commit 合用的简写。撤销操作git commit --amend这个命令可能用在我们提交信息错误或者有文件忘记提交时进行使用我们使用这个命令就可以再次进行提交，此时我们这次提交会将上次提交的基础上再次进行提交并且将修改信息加到本次提交上，也就是将提交补全，补全后之前提交将不再存在git reset xxxgit reset命令可以取消对某文件的暂存git checkout撤销修改，将文件退回为之前的样子请务必记得 git checkout -- 是一个危险的命令。 你对那个文件在本地的任何修改都会消失——Git 会用最近提交的版本覆盖掉它。 除非你确实清楚不想要对那个文件的本地修改了，否则请不要使用这个命令。在 Git 中任何 已提交 的东西几乎总是可以恢复的。 甚至那些被删除的分支中的提交或使用 --amend 选项覆盖的提交也可以恢复 （阅读 数据恢复 了解数据恢复）。 然而，任何你未提交的东西丢失后很可能再也找不到了。远程操作git remote add运行 git remote add 添加一个新的远程 Git 仓库，同时指定一个方便使用的简写git remote add jx xxxxxxxxgit fetch这个命令会访问远程仓库，从中拉取所有你还没有的数据。 执行完成后，你将会拥有那个远程仓库中所有分支的引用，可以随时合并或查看git pushgit push 分支 服务器将本地分支内容推送到上游，当你的本地版本并不是最新时，这条命令将不起作用git remote rename改远程仓库名git remote remove删除远程仓库 -
java期末速成 javajdk jre jvm.java-------->.class----jvm---->机器语言编写源文件 编译源文件生成字节码 加载运行字节码java语句执行顺序 顺序 选择 循环 异常处理基本语法方法格式权限修饰符 返回值声明 方法名称(参数列表){ 方法中封装的逻辑功能; return 返回值; }--权限修饰符--注释//单行注释 /* 多行注释 */ /** 文档注释 **/标识符举例java变量java是一个强类型语言 必须先声明类型后使用java数据类型分两大类 基本数据类型与引用类型引用数据类型：string 数组 接口 类按照声明位置进行定义分为局部变量与成员变量变量的类型转换boolean类型不参与转换自动类型转换容量小的类型自动转换成容量大的类型byte,short,int -> float -> long ->doublebyte short int之间不会互相转换 三者计算时会转化成int类型强制类型转换容量大的类型转换成容量小的类型时需要加上强制转换符变量的作用域在类体内定义的变量称为成员变量 作用域是整个类在一个方法或方法内代码块中定义的变量称为局部变量常量量前加一个final变量赋值注意事项：float a = 133f long a = 22220202l char c = '羊'数组数组初始化方式不允许在前面的[]里写元素个数动态两种int[][] arr = new int[3][]; arr[0] = new int[3] int [][] arr2 = new int[3][2] arr[0][0] = 33静态一种int arr4[][] = new int[][]{{1,2,3},{2,3,4}}arr.length 得到数组长度输入输出scanner类型#输入 Scanner s = new Scanner(System.in); s.nextInt(); s.nextLine(); s.nextfloat(); scanner.next(); #输出 System.out.println("XX");system.out. print() 普通输出 printf()格式化输出 println()换行输出类与对象封装继承多态我们进行一次举例public class Student { private String username; public String getUsername{ return username; } #这个函数存在而不使用直接赋值的意义就是因为username这个变量是私有的 public void setUsername(String username){ this.username = username; } } class Test { public static void main(String[] args) { Student student=new Student(); student.setUsername("张三"); student.getUsername(); System.out.println(); } }类的实例化通过new语句进行创建类的定义格式[修饰符] class 类名 [extends 父类名] [implements 接口名]{ //类体 包括类的成员变量与成员方法 }继承基类object没有选择继承的时候默认继承object，有很多自带方法继承格式public class Parent { private int age; public int getAge() { return age } public void setAge(int age) { this.age = age; } #有参 public Parent(int age){ this.age = age; } #无参 public Parent(){ } public void myprint(){ system.out.println("我是父类的myprint方法"); } } class Son extents Parent{ public static void main(String[]args) { Son son = new son(); son.age = 3; } }类的重写对相同的函数进行再次声明就可以进行重写类的封装将类的某些信息隐藏在内部，不允许直接访问而是提供get set方法public class Person { private intn age; private string name; public String getName(){ return name; } public int getAge(){ return age; } public void setName(String name){ this.name = name; } public void setAge(int age){ this.age = age; } }构造方法 重点构造方法定义主要用来创建对象时 初始化对象的 总与new一起使用在创建对象的运算符中 一个类可以有 多个构造函数 可根据参数个数不同或者参数类型不同区分 即构造函数的重载方法的重载重写重载重写区别this关键字在构造方法中指该构造器所创建的新对象也就是对应对象的属性也可以使用this关键字调出对象本身例如在一个对象的setAge中调用getAge注意：this只能在类的非静态方法中使用 静态方法与静态的代码块中不能出现this 原因 static方法在类加载时就已经存在了 但是对象在创建时才在内存中生成super关键字super关键字主要存在于子类方法中用于子类调用父类的方法例如子类重写了父类的一个方法 但是又想重新调用一次父类的方法就使用super关键字static关键字静态 的关键字静态变量静态方法静态代码块使用了static后的方法变成类方法 不需要new就能直接调用final关键字final修饰的类不能被继承final修饰的方法不能被重写 但是可以直接用final修饰的基本类型变量不可变 但是引用类型变量引用不可改变 但是引用对象的内容可以改变抽象类在class前加一个abstract来修饰抽象方法要在子类里进行实现 不然不正确接口将class替换为interface即可接口里所有定义的方法实际上都是抽象的public abstract变量只能为public static final类型的public abstract void add(); 等效于 void add();抽象类与接口的区别接口要被子类实现 抽象类要被子类继承接口中变量全为公共静态常量 抽象类中可有普通变量接口中全为方法的声明 抽象类中可以有方法的实现接口中不可以有构造函数 抽象类中可以有构造函数接口可多实现 而抽象类必须被单继承接口中方法全为抽象方法 而抽象类中可以有非抽象方法内存机制栈存放局部变量 不可以被多个线程共享系统自动分配空间连续 速度快堆存放对象 可以被多个线程共享每个对象都有锁空间不连续 速度慢 灵活方法区存放类的信息：代码 静态变量 字符串 常量等可以被多个线程共享空间不连续 速度慢 灵活垃圾回收机制程序员不能调用垃圾回收器 但是可以通过system.gc()建议回收未引用的会被回收finallize方法 每个对象都有这个方法 用来释放对象区域资源 一般不去调用递归算法递归头 什么时候不调用自己递归体 什么时候调用自己异常机制：try catch finally catch的顺序 先小后大声明抛出异常：throws手动抛出异常：throw自定义异常： 首先继承Exception 或者它的子类容器：Collection接口： List -》ArrayList LinkedList Vector Set-》HashSet 内部使用HashMap实现Map接口： 采用 key value存储数据 HashMap线程不安全 效率高 HashTable线程安全 效率低Iterator接口：遍历容器中元素泛型：Collections： 包含排序查找的工具类字符串比较中 == 与 equal的区别==：比较的是两个字符串内存地址（堆内存）的数值是否相等，属于数值比较；equals()：比较的是两个字符串的内容，属于内容比较。多态多态体现为一个事物的多种形态 例如 父类引用变量可以指向子类对象isinstanceof 向上转型 将子类对象赋值给父类变量 向下转型 将父类对象赋值给子类变量注解也叫元数据 用于描述数据的数据基本注解：@Override 重写 在重写的方法前加入即可@SuppressWarnings 压制警告 在警告内容前加入 可以让我们暂时忽略特定的警告自定义注解[public] @interface 注解名 { 数据类型 成员变量名（）[default 初始值] }注解跟类一样 会被编译为 注解名.class的字节码文件成员变量名后面的（）必不可少反射机制一段程序在运行过程中 接受一个对象作为形参 该对象的编译时类型与运行时类型不一致 但是程序又需要调用该对象运行时的类中的方法这就需要引用反射机制 保证在程序运行过程中可以知道任意对象的运行时类型可以构造任意类的对象可以调用任意对象的属性和方法其实就是在运行时获取对象的属性与方法，例如对象.getClass内部类将一个类作为成员放在另一个类或者方法的内部嵌套类内部类可以分为 非静态内部类和静态内部类非静态内部类 是指 在非静态类的方法内访问某个变量时 先找局部变量 再找内部类的属性 最后找外部类的属性如果局部变量 内部类属性 外部类三者名字相同静态内部类是用static修饰的内部类都称为静态内部类静态内部类是一个普通类 可以包含静态成员 也可以包含非静态成员静态内部类不能访问外部类的实例成员 只能访问外部类的类成员lambda表达式当接口中只有一个抽象方法 匿名内部类的语法过于频繁这种接口叫做函数式接口表达式 ： （形参列表）->{代码块}形参列表：如果形参列表中只有一个参数 形参列表的圆括号也可以忽略异常处理基本语法try{ 执行语句 }catch (ExceptionType e) { 异常处理 }finally{ 无论是否发生异常都会执行的语句 }创建Exception通过继承Exception来创建异常public class CustomException extends Exception{ public CustomException(String message){ super(message) } }throw/throws用于手动抛出异常 需要使用public void processAge(int age) { if (age < 0) { throw new IllegalArgumentException("Age cannot be negative"); } // 其他处理逻辑 }throwspublic String readFile(String fileName) throws IOException { // 读取文件内容的逻辑 }输入输出操作InputStreamInputStream是用于从各种源（如文件、网络连接等）读取字节流的抽象类。它定义了一系列用于读取字节的方法。你可以使用InputStream来读取二进制数据，比如图片、音频或视频文件。OutputStream是用于向各种目标（如文件、网络连接等）写入字节流的抽象类。它定义了一系列用于写入字节的方法。你可以使用OutputStream来写入二进制数据，比如将数据写入文件或通过网络发送。Reader是用于从各种源（如文件、网络连接等）读取字符流的抽象类。它定义了一系列用于读取字符的方法。你可以使用Reader来读取文本数据，比如读取文本文件中的内容。Writer是用于向各种目标（如文件、网络连接等）写入字符流的抽象类。它定义了一系列用于写入字符的方法。你可以使用Writer来写入文本数据，比如将数据写入文本文件。// 使用FileReader读取文件 FileReader fileReader = new FileReader("file.txt"); int data = fileReader.read(); // 读取一个字符 while (data != -1) { System.out.print((char)data); data = fileReader.read(); } fileReader.close(); // 使用FileWriter写入文件 FileWriter fileWriter = new FileWriter("file.txt"); fileWriter.write("Hello, world!"); fileWriter.close();System.in、System.out 和 System.errSystem.in、System.out和System.err是Java中的三个标准I/O流。System.in：标准输入流，通常对应于键盘输入。你可以使用它来从控制台读取用户的输入。System.out：标准输出流，通常对应于控制台输出。你可以使用它向控制台输出信息。System.err：标准错误流，也通常对应于控制台输出。与System.out不同的是，它主要用于输出错误信息。泛型java 中泛型标记符：E - Element (在集合中使用，因为集合中存放的是元素)T - Type（Java 类）K - Key（键）V - Value（值）N - Number（数值类型）？ - 表示不确定的 java 类型Collection \<E>Collection 是 Java 集合框架中所有集合类的根接口。它代表了一组对象，这些对象通常称为元素。Collection 接口的主要特点包括：存储一组对象：Collection 是一个容器，可以存储多个对象，这些对象可以是任何类型，包括基本类型的封装类、自定义对象等。无序性：Collection 不保证元素的顺序，即它们不一定按照插入的顺序进行存储和访问。允许重复元素：Collection 允许存储重复的元素，即相同的对象可以被添加多次。常见实现类：Java 中常见的 Collection 实现类包括 List、Set 和 Queue 接口的各种实现类，如 ArrayList、LinkedList、HashSet 等。Map<K,V>Map 接口代表了一种映射关系，它将键映射到值。Map 中的键是唯一的，而值则可以重复。Map 接口的主要特点包括：键值对存储：Map 存储的是键值对，每个键都映射到一个值。通过键可以快速查找对应的值。键的唯一性：Map 中的键是唯一的，每个键最多只能与一个值关联。值的重复性：Map 中的值可以重复，即不同的键可以映射到相同的值。常见实现类：Java 中常见的 Map 实现类包括 HashMap、TreeMap、LinkedHashMap 等。
-
数据结构 树树的前中后序遍历前序遍历 根左右 每次左右可以展开时进行替换中序遍历 左根右后序遍历 左右根前中后序转化前中后序转化看遍历方式决定的顺序结构例如前序遍历的第一个元素一定是根节点 中序遍历的根节点的两边就是左右子树树与二叉树的转化树要变成二叉树，那就将树中的所有兄弟结点进行链接，然后每一层与上一层的连接只留下第一个结点的连接二叉树要变成树，那就反方向来一次，将除了第一个结点的其他结点与根节点连接上，然后将兄弟结点连接，这时候二叉树就变回了原来的树森林与二叉树的转化森林转化为二叉树，森林是由若干个树组成的，可以理解为森林中的每棵树都是兄弟，我们先把森林中的每棵树转化成二叉树，然后将从第二个树起的每个结点作为上一个结点的右孩子二叉树想转化成森林，先要看他可不可以转化，直接看根节点有没有右孩子，有就可以转化，先递归的将每个拥有右节点的根节点都断开 然后将二叉树再转化成树就成了森林树与森林的遍历树的遍历树的遍历很简单，分为先根遍历与后根遍历森林的遍历森林的遍历也分为两种，分别是前序遍历与后序遍历，森林的前序遍历与二叉树的中序遍历相同，森林的后序遍历与二叉树的中序遍历相同图图的表示邻接矩阵typedef struct { Vertextype vexs[MAXVEX]; EdgeType arc[MAXVEX][MAXVEX]; int numNodes, numEdges; }MGraph;邻接表int EdgeType; typedef struct { int adjvex; EdgeType info; struct EdgeNode *next; }EdgeNode; typedef struct { VertexType data; EdgeNode *firstedge; }VertexNode,AdjList[MAXVEX]; typedef struct { Adjlist adjList; int numNodes,numEdges; }AdjList;深度优先搜索深度优先搜索也叫DFS，这种搜索如其名，深度优先，在走之前先确定一个方向，比如先访问最左边的，那就持续往前走，在未遇到过的结点的路中选择最左边的即可//邻接矩阵 #define MAXVEX 9 Boolean visited[MAXVEX] void DFS(MGraph G,int i) { int j; visited[i] = True; printf("%c",G.vexs[i]) for(j = 0;j < MAXVEX;j++) { if(G.arc[i][j] == 1 && visited[i] == False) { DFS(G,j); } } } void DFSTraverse(MGraph G) { int i; for(i = 0;i < G.numvertexes;i++) { visited[i] = False; } for(i = 0;i < G.numvertexes;i++) { if(!visited(i)) { DFS(G,i); } } }//邻接表 void DFS(GraphAdjList GL,int i) { EdgeNode *p; visited[i] = True; printf("%c",GL->adjlist[i].data); p = GL->adjlist[i].firstedge; while(p) { if(!visted[p->adjvex]) { DFS(GL,p->adjvex); } p = p->next; } } void DFSTraverse(GraphAdjlist GL) { int i; for(i = 0;i < GL->numvexes;i++) { visited[i] = False; } for(i = 0;i < GL->numvexes;i++) { if(!visited[i]) { DFS(GL,i); } } }广度优先搜索广度优先搜索，也叫BFS核心思想是一层一层访问结点，使用的是一个栈来作为辅助存储，从入栈第一个节点开始，每次出栈一个结点，就将这个结点邻接的所有未访问顶点入栈，由此来遍历所有顶点void BFSTraverse(MGraph G) { int i; Queue Q; for(i = 0;i < G->numvexes;i++) { visited[i] = False; } InitQueue(Q); for(i = 0;i < G->numvexes;i++) { if(!visited[i]) { visited[i] = True; printf("%c",G->vex[i]) EnQueue(&Q,i); while(!EmptyQueue(Q)) { DeQueue(&Q,&i); for(j = 0;j < G->numvexes;j++) { if(G.arc[i][j]&&!visited[j]) { printf("%c",G->vex[j]); EnQueue(&Q,j); } } } } } }最小生成树prim算法简介prim算法的核心就是迭代，从一个顶点开始构建生成树，每次讲代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。实现思想创建两个数组，一个是标记是否加入的数组isjoin，一个是计算各节点加入最小生成树的最低代价的数组lowcost 在此之前先选取第一个结点，对此结点的相邻边进行遍历，将有权边加入到lowcost中供选择 第一轮循环遍历各个结点，找出lowcost最低的并且未加入树的顶点，将相邻结点加入isjoin数组中并开启下一轮遍历，更新还未加入的各个顶点的lowcost值不断循环直至所有顶点都纳入为止因为要进行n-1轮的循环，每次循环2n次总时间复杂度是O($n^2$)即O($|V|^2$)kruskal算法简介kruskal算法的核心就是全局里去找，每次选择一条权值最小的边，使这条边的两头连通（若原本已经连通则不选）直到所有顶点都连通实现思想初始时先将各条边按照权值进行排序然后使用并查集方法检查是否已连通，若未连通则将新节点加入，一共要执行e轮，美伦判断两结点是否属于同一集合，需要O($log_2e$)最短路径BFS求无权图的单源最短路径简介直接进行广度优先遍历使用两个数组，一个记录最短路径值，一个记录到这个顶点的直接前驱只能用无权图迪杰斯特拉算法简介dijkstra算法是一种一步一步找出最短路径的方法，核心思路就是从初始点开始，一步一步从已确定路径中选取最短的路径作为新的最短路径，并加入新已确定顶点，然后执行多次实现我们选用三个数组，分别是标记各顶点是否已找到最短路径的finals，最短路径长度的dist，以及记录路径上的前驱的path也就是我们每次将可到达的结点找出来，从可获取路径中找到最短路径，并将其前驱记录，标记出结点时间复杂度为O($n^2$)即O($|V|^2$)如果用于负权值带权图，则迪杰斯特拉算法可能会失效弗洛伊德算法简介Floyd算法是求出每一对顶点之间的最短路径使用动态规划思想，将问题的求解分为多个阶段对于个顶点的图G,求任意一对顶点Vi一>Vj之间的最短路径可分为如下几个阶段：初始：不允许在其他顶点中转，最短路径是？0:若允许在Vo中转，最短路径是？1:若允许在Vo、V1中转，最短路径是？2:若允许在Vo、V1、V2中转，最短路径是？......n-1:若允许在Vo、V1、V2.Vn-1中转，最短路径是？例如这样，左边的矩阵就是初始时，不中转获得的个顶点建最短路径长度，右边的矩阵是初始时中转点的记录，因为不中转，所以是-1若允许在V0中转，则新加一编辑 如此经历n轮递推woc，大道至简，本身以为是只有一个节点做中转的情况，但是仔细一想，它并不是单源的算法，而是点到点的算法，并且也从来不是每次加一个这么简单，他是考虑了所有的结点 就好比是需要经过 0 2 4 6才能到这个点，在查找时0->2是最小值不需要中转,0->4是经过2的中转，0到6是经过4的中转，但是到4的中转前已经中转过2了,所以这种算法已经考虑了所有的情况DAG简介有向无环图简称DAG 图DAG描述表达式相同部分可以合并节省存储空间顶点中不能出现重复的操作数，标出来各个运算符的生效顺序，注意分层拓扑排序简介拓扑排序就是找到做事的先后顺序每个AOV网可能有一个或者多个拓扑排序实现①从AOV网中选择一个没有前驱（入度为0）的顶点并输出。②从网中删除该顶点和所有以它为起点的有向边。③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。使用三个数组进行实现分别是 记录当前顶点入度的数组indegree 记录拓扑序列的数组print 保存度为零的顶点栈s逆拓扑排序将拓扑排序中的入度更换成出度即可，使用邻接表不适合实现逆拓扑排序，应该使用逆邻接表或者邻接矩阵查找查找的衡量方法为平均查找长度顺序查找基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置。若查找到表的另一端，仍未找到符合给定条件的元素，则返回查找失败的信息。折半查找基本思想就是二分法散列表基本概念散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这些情况为冲突，这些发生碰撞的不同关键字称为同义词。散列表建立了关键字和存储地址之间的一种直接映射关系。散列函数不同，散列表不同直接定址法就是直接使用线性函数确定地址，一般不常见除留余数法确定一个数m，所有的数对设定的数m进行取余，取余后进行散列表的排序解决冲突办法如果有重复则将其使用向后推移并记录查找次数的方法进行储存，成为开放定址法，也可使用链表进行存储，称为拉链法查找长度散列表的查找长度取决于三个因素：散列函数、处理冲突的方法和装填因子。装填因子a=表中记录数n/散列表长度m。散列表的平均查找长度依赖于散列表的装填因子α，不直接依赖于n或m。α越大，表示装填的记录越“满”，发生冲突的可能性就越大。排序插入排序直接排序实际上就是进行比较后一步步替换空间复杂度为O(1)时间复杂度为O($n^2$)-->两个嵌套for循环（平均）稳定性 稳定 （遇到相同数字，相对位置保持不变）每次向后移动一次即一趟排序希尔排序希尔排序是通过一个常数d作为增量，然后对于相隔d个增量的记录作为子表进行排序，经过几次排序，使得整个表格基本有序后，对全体进行一次排序即可因为同样使用常数个辅助单元，所以空间复杂度为o(1)时间复杂度依赖于增量d，一般来说是不确定的，所以一般我们不去考虑最后两个相同数字的相对位置也不能保证，所以稳定性也是不稳定的交换排序冒泡排序不做解释，一一交换空间 O(1)时间O($n^2$)快速排序快速排序是选取一个固定数，通常为第一个数，将小于这个数的跟不小于这个数的值进行排序，然后依次进行，是一个递归的过程所以空间复杂度是O($log_2n$)时1间复杂度是O($nlog_2n$)稳定性为不稳定快速排序是所有内部排序算法中平均性能最优的算法但是并不适用于本身就已经有了一定顺序的序列进行排序选择排序简单选择排序就是遍历每个元素，在遍历到第i个元素时，选择从i到n的所有元素中最小的一个，将其与第i个元素进行交换空间复杂度为O(1)时间复杂度为O($n^2$)稳定性为不稳定堆排序对于二叉树的排序结果，我们可以根据根节点存放的是最大结点还是最小结点将堆分为大根堆与小根堆对于大根堆小根堆的构造，都是从$n/2$开始进行的对于堆的删除操作，就是将栈顶元素输出后再次进行构造对于堆的插入操作，我们将其放入栈尾，再次进行构造空间复杂度O(1)时间复杂度O($nlog_2n$)稳定性 不稳定归并排序归并排序是将两个或两个以上的有序表组成一个新的有序表例如二路归并排序，就是将元素两两组合并进行排序空间复杂度是O(n)时间复杂度是O($nlog_2n$)稳定性 为稳定基数排序不基于比较与移动进行排序，而是基于关键字各位的大小进行排序空间效率 O(r)时间复杂度O(d(n+r))稳定性 稳定各种排序算法的比较插帽龟跟统计鸡是很稳定的插帽龟在选冒插的时候，恩慌了恩老说快归堆问题树的度为树中最大的度，例如二叉树的度为2树中的指针域，看图理解即可含有n个结点的树含有n+1个空链域，n-1个非空链域，可以从画图理解，从第一个结点为2个空域，每增加一个结点，空域增加一个前后缀表达式前缀表达式首先先看，前缀表达式是从后往前算，遇到数字一个个放入栈中，遇到符号则拿出栈顶的元素进行计算，后进先算后缀表达式先入先出，从前往后进行计算，也就是通过队列进行实现二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树。二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：非空左子树的所有键值小于其根结点的键值。非空右子树的所有键值大于其根结点的键值。左、右子树都是二叉搜索树。二叉链表用二叉链表存储哈夫曼树，有m个叶子结点，问哈夫曼树中总共多少个空指针域：2m，叶子节点数*2数据的物理存储结构主要包括链式存储与顺序存储二叉排序树插入新节点时间复杂度为O(n)，因为最差情况为单链以链表为栈的存储结构出栈时以链表为栈的存储结构出栈时必须判空，不需要判定满栈顺序线性表插入脑残数据的最小单位是数据项归并排序落单丢掉substr(str,int,int)意思是str的第int开始的int个字符层次遍历初始堆无法保证得到一个有序的序列，因为堆的兄弟结点之间无序创建邻接表的时间复杂度无向图中有n个结点e条边，建立该图邻接表的平均时间复杂度为O(n+e)深度为k的完全二叉树中最少有$2^{k-1}$个结点如上一趟排序结束后不一定能选出一个元素在其最终位置上的排序算法希尔排序，可能没有元素在最终位置上连通图是无向图连通图一定是无向图，所以深度优先遍历连通图一定能够访问到所有的顶点链式栈的栈顶元素删除删除栈顶元素操作序列 top = top->next初始化堆筛选法建初始堆必须从第$\frac{n}{2}$个元素开始进行筛选，因为第$\frac{n}{2}$个元素都有孩子结点(对于所有的完全二叉树来讲都是这样)新建元素x = (类型)malloc(sizeof(元素)）
-
动手学深度学习 深度学习环境安装在之前做数据分析就已经安装过anaconda，所以不安装miniconda安装完成之后，由于国内的pip太慢，所以要更换镜像源上海交通大学 Linux 用户组 软件源镜像服务 (sjtu.edu.cn)然后经过一些配置之后安装git也弄过了国内git速度巨慢无比，加速在此GitHub Proxy 代理加速 (ghproxy.com)数学基础学习了高等数学中的微积分模块与对于梯度的学习，链式法则，补习了线代范式内容，后续会更新数学笔记课程环境搭建已搭建成功准备工作数据操作张量张量表示一个由数值组成的数组，这个数组可能有多个维度。 具有一个轴的张量对应数学上的向量（vector）； 具有两个轴的张量对应数学上的矩阵（matrix）； 具有两个轴以上的张量没有特殊的数学名称。一维张量 对应向量二维张量 对应矩阵三维以及以上不命名重要函数reshape要想改变一个张量的形状而不改变元素数量和元素值，可以调用reshape函数。 例如，可以把张量x从形状为（12,）的行向量转换为形状为（3,4）的矩阵。 这个新的张量包含与转换前相同的值，但是它被看成一个3行4列的矩阵。 要重点说明一下，虽然张量的形状发生了改变，但其元素值并没有变。 注意，通过改变张量的形状，张量的大小不会改变。x = torch.arange(12) x X = x.reshape(3, 4) Xtensor([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]) tensor([[ 0, 1, 2, 3], [ 4, 5, 6, 7], [ 8, 9, 10, 11]])我们不需要通过手动指定每个维度来改变形状。 也就是说，如果我们的目标形状是（高度,宽度）， 那么在知道宽度后，高度会被自动计算得出，不必我们自己做除法。 在上面的例子中，为了获得一个3行的矩阵，我们手动指定了它有3行和4列。 幸运的是，我们可以通过-1来调用此自动计算出维度的功能。 即我们可以用x.reshape(-1,4)或x.reshape(3,-1)来取代x.reshape(3,4)。zeros,ones,randn有时，我们希望使用全0、全1、其他常量，或者从特定分布中随机采样的数字来初始化矩阵。 我们可以创建一个形状为（2,3,4）的张量，其中所有元素都设置为0。代码如下：torch.zeros((2, 3, 4)) torch.ones((2, 3, 4))tensor([[[0., 0., 0., 0.], [0., 0., 0., 0.], [0., 0., 0., 0.]], [[0., 0., 0., 0.], [0., 0., 0., 0.], [0., 0., 0., 0.]]]) tensor([[[1., 1., 1., 1.], [1., 1., 1., 1.], [1., 1., 1., 1.]], [[1., 1., 1., 1.], [1., 1., 1., 1.], [1., 1., 1., 1.]]])有时我们想通过从某个特定的概率分布中随机采样来得到张量中每个元素的值。 例如，当我们构造数组来作为神经网络中的参数时，我们通常会随机初始化参数的值。 以下代码创建一个形状为（3,4）的张量。 其中的每个元素都从均值为0、标准差为1的标准高斯分布（正态分布）中随机采样。torch.randn(3, 4)tensor([[ 0.7277, -1.3848, -0.2607, 0.9701], [-2.3290, -0.3754, 0.2457, 0.0760], [-1.2832, -0.3600, -0.3321, 0.8184]])运算张量可以直接通过运算符直接按元素计算x = torch.tensor([1.0, 2, 4, 8]) y = torch.tensor([2, 2, 2, 2]) x + y, x - y, x * y, x / y, x ** y (tensor([ 3., 4., 6., 10.]), tensor([-1., 0., 2., 6.]), tensor([ 2., 4., 8., 16.]), tensor([0.5000, 1.0000, 2.0000, 4.0000]), tensor([ 1., 4., 16., 64.]))还可以通过函数连结在一起，连结时选择参数，按照轴0还是轴1，按照轴0就是按行结合，1是按照列结合X = torch.arange(12, dtype=torch.float32).reshape((3,4)) Y = torch.tensor([[2.0, 1, 4, 3], [1, 2, 3, 4], [4, 3, 2, 1]]) torch.cat((X, Y), dim=0), torch.cat((X, Y), dim=1)(tensor([[ 0., 1., 2., 3.], [ 4., 5., 6., 7.], [ 8., 9., 10., 11.], [ 2., 1., 4., 3.], [ 1., 2., 3., 4.], [ 4., 3., 2., 1.]]), tensor([[ 0., 1., 2., 3., 2., 1., 4., 3.], [ 4., 5., 6., 7., 1., 2., 3., 4.], [ 8., 9., 10., 11., 4., 3., 2., 1.]]))还可以通过逻辑运算符来获得特殊张量X == Ytensor([[False, True, False, True], [False, False, False, False], [False, False, False, False]])在某些情况下，即使形状不同，我们仍然可以通过调用 广播机制（broadcasting mechanism）来执行按元素操作。 这种机制的工作方式如下(就是逐行去逐列进行计算)：1.通过适当复制元素来扩展一个或两个数组，以便在转换之后，两个张量具有相同的形状；2.对生成的数组执行按元素操作。a = torch.arange(3).reshape((3, 1)) b = torch.arange(2).reshape((1, 2)) a, b a + b(tensor([[0], [1], [2]]), tensor([[0, 1]])) tensor([[0, 1], [1, 2], [2, 3]])索引跟切片与普通列表大差不差，所以不对其再进行论述节省内存一些操作可能会导致新结果分配新的内存，在对大量数据进行操作时，会占用很大的存储空间，故采用方法进行规避before = id(Y) Y = Y + X id(Y) == beforeFalse综上，这样加合的习惯会带来不小的麻烦，我们采取原地操作执行原地操作非常简单。 我们可以使用切片表示法将操作的结果分配给先前分配的数组如果在后续计算中没有重复使用X， 我们也可以使用X[:] = X + Y或X += Y来减少操作的内存开销。数据预处理在学习中，我们要使用pandas预处理原始数据，并将原始数据转换为张量格式首先我们无论自己手动编写，还是外界下载，要得到一个CSV格式的文件通过pandas的read_csv函数对数据进行格式转化pandas.read_csv(文件)处理缺失值在数据处理中，会有一些值由于某种原因缺失，这种情况下我们要对其进行一定的处理。通常用的有两种方法，插值法和删除法， 其中插值法用一个替代值弥补缺失值，而删除法则直接忽略缺失值。 在这里，我们将考虑插值法。例如这样的一个表 NumRooms Alley Price 0 NaN Pave 127500 1 2.0 NaN 106000 2 4.0 NaN 178100 3 NaN NaN 140000通过位置索引iloc，我们将data分成inputs和outputs， 其中前者为data的前两列，而后者为data的最后一列。 对于inputs中缺少的数值，我们用同一列的均值替换“NaN”项。inputs, outputs = data.iloc[:, 0:2], data.iloc[:, 2] inputs = inputs.fillna(inputs.mean()) print(inputs) NumRooms Alley 0 3.0 Pave 1 2.0 NaN 2 4.0 NaN 3 3.0 NaN对于inputs中的类别值或离散值，我们将“NaN”视为一个类别。 由于“巷子类型”（“Alley”）列只接受两种类型的类别值“Pave”和“NaN”， pandas可以自动将此列转换为两列“Alley_Pave”和“Alley_nan”。 巷子类型为“Pave”的行会将“Alley_Pave”的值设置为1，“Alley_nan”的值设置为0。 缺少巷子类型的行会将“Alley_Pave”和“Alley_nan”分别设置为0和1。inputs = pd.get_dummies(inputs, dummy_na=True) print(inputs) NumRooms Alley_Pave Alley_nan 0 3.0 1 0 1 2.0 0 1 2 4.0 0 1 3 3.0 0 1现在inputs和outputs中的所有条目都是数值类型，它们可以转换为张量格式。import torch X, y = torch.tensor(inputs.values), torch.tensor(outputs.values) X, y(tensor([[3., 1., 0.], [2., 0., 1.], [4., 0., 1.], [3., 0., 1.]], dtype=torch.float64), tensor([127500, 106000, 178100, 140000]))线性代数数学知识之前已经了解了表示标量向量矩阵的方法,接下来不算总结，仅为摘要书上内容线性代数计算的实现1.矩阵转置.t例子:A = torch.arange(20).reshape(5, 4) Atensor([[ 0, 1, 2, 3], [ 4, 5, 6, 7], [ 8, 9, 10, 11], [12, 13, 14, 15], [16, 17, 18, 19]])A.Ttensor([[ 0, 4, 8, 12, 16], [ 1, 5, 9, 13, 17], [ 2, 6, 10, 14, 18], [ 3, 7, 11, 15, 19]])2.降维.sum对于向量，降维就是访问sumx = torch.arange(4, dtype=torch.float32) x, x.sum()(tensor([0., 1., 2., 3.]), tensor(6.))默认情况下，调用求和函数会沿所有的轴降低张量的维度，使它变为一个标量。 我们还可以指定张量沿哪一个轴来通过求和降低维度。 以矩阵为例，为了通过求和所有行的元素来降维（轴0），可以在调用函数时指定axis=0。 由于输入矩阵沿0轴降维以生成输出向量，因此输入轴0的维数在输出形状中消失。A_sum_axis0 = A.sum(axis=0) A_sum_axis0, A_sum_axis0.shape(tensor([40., 45., 50., 55.]), torch.Size([4]))指定axis=1将通过汇总所有列的元素降维（轴1）。因此，输入轴1的维数在输出形状中消失。A_sum_axis1 = A.sum(axis=1) A_sum_axis1, A_sum_axis1.shape(tensor([ 6., 22., 38., 54., 70.]), torch.Size([5]))3.平均值.meanA.mean()(tensor(9.5000), tensor(9.5000))4.非降维求和sum_A = A.sum(axis=1, keepdims=True) sum_Atensor([[ 6.], [22.], [38.], [54.], [70.]]).cumsumA.cumsum(axis=0)tensor([[ 0., 1., 2., 3.], [ 4., 6., 8., 10.], [12., 15., 18., 21.], [24., 28., 32., 36.], [40., 45., 50., 55.]])5.点积采用按元素乘的和即可y = torch.ones(4, dtype = torch.float32) x, y, torch.dot(x, y)(tensor([0., 1., 2., 3.]), tensor([1., 1., 1., 1.]), tensor(6.))torch.sum(x * y)tensor(6.)6.矩阵-向量积.mv在代码中使用张量表示矩阵-向量积，我们使用mv函数。 当我们为矩阵A和向量x调用torch.mv(A, x)时，会执行矩阵-向量积。 注意，A的列维数（沿轴1的长度）必须与x的维数（其长度）相同。A.shape, x.shape, torch.mv(A, x)(torch.Size([5, 4]), torch.Size([4]), tensor([ 14., 38., 62., 86., 110.]))7.矩阵-矩阵乘法.mmB = torch.ones(4, 3) torch.mm(A, B)tensor([[ 6., 6., 6.], [22., 22., 22.], [38., 38., 38.], [54., 54., 54.], [70., 70., 70.]])矩阵-矩阵乘法可以简单地称为矩阵乘法，不应与”Hadamard积(就是同位置简单相乘)”混淆。8.范式线性代数中最有用的一些运算符是范数（norm）。 非正式地说，向量的范数是表示一个向量有多大。 这里考虑的大小（size）概念不涉及维度，而是分量的大小。.abs().sum()L1范式的使用torch.abs(u).sum()tensor(7.).normL2范式的使用u = torch.tensor([3.0, -4.0]) torch.norm(u)tensor(5.)线性回归首先是书上基础的概念它在回归的各种标准工具中最简单而且最流行。 线性回归基于几个简单的假设： 首先，假设自变量x和因变量y之间的关系是线性的， 即y可以表示为x中元素的加权和，这里通常允许包含观测值的一些噪声； 其次，我们假设任何噪声都比较正常，如噪声遵循正态分布。线性模型线性模型很简单，就是加权和，是各个参数经过加权后再加上偏置得到的值，主要是对于参数与权重的确定，而偏置是对其准确性的调整损失函数损失函数（loss function）能够量化目标的实际值与预测值之间的差距。 通常我们会选择非负数作为损失，且数值越小表示损失越小，完美预测时的损失为0。 回归问题中最常用的损失函数是平方误差函数。解析解线性回归刚好是一个很简单的优化问题。 与我们将在本书中所讲到的其他大部分模型不同，线性回归的解可以用一个公式简单地表达出来， 这类解叫作解析解（analytical solution）。像线性回归这样的简单问题存在解析解，但并不是所有的问题都存在解析解。 解析解可以进行很好的数学分析，但解析解对问题的限制很严格，导致它无法广泛应用在深度学习里。随机梯度下降解析解并不好寻找，我们用到一种名为梯度下降（gradient descent）的方法， 这种方法几乎可以优化所有深度学习模型。 它通过不断地在损失函数递减的方向上更新参数来降低误差。梯度下降最简单的用法是计算损失函数（数据集中所有样本的损失均值） 关于模型参数的导数（在这里也可以称为梯度）。 但实际中的执行可能会非常慢：因为在每一次更新参数之前，我们必须遍历整个数据集。 因此，我们通常会在每次需要计算更新的时候随机抽取一小批样本， 这种变体叫做小批量随机梯度下降。然后用已经学习的线性回归模型就能对目标进行预测。向量化加速在训练我们的模型时，我们经常希望能够同时处理整个小批量的样本（如利用小批量样本实现随机梯度下降）。 为了实现这一点，需要我们对计算进行矢量化， 从而利用线性代数库，而不是在Python中编写开销高昂的for循环。正态分布与平方损失正态分布与线性回归密切相关，本次研究针对于对于噪声分布的假设，服从正态分布的噪声很理想化，均值为0，似然就是对于预测值的接近，最大似然值就是对于预测值的估计反向传播反向传播依靠计算图实现，见深度学习入门鱼书p146理论知识到这里softmax回归前面我们学习了线性回归，线性回归主要用于对于问题的预测，输出一个结果值，但问题往往不止这一种，我们每天也在处理很多分类的问题，要的结果是哪一种。所以本节学习softmax回归模型分类问题对于分类问题，我们要的结果是输出一个类别统计学家很早以前就发明了一种表示分类数据的简单方法：独热编码（one-hot encoding）。 独热编码是一个向量，它的分量和类别一样多。 类别对应的分量设置为1，其他所有分量设置为0。例如(1,0,0,)(0,1,0)(0,0,1)这三个向量分别代表三个类别为了估计所有可能类别的条件概率，我们需要一个有多个输出的模型，每个类别对应一个输出。 为了解决线性模型的分类问题，我们需要和输出一样多的仿射函数（affine function）。 每个输出对应于它自己的仿射函数。 在我们的例子中，由于我们有4个特征和3个可能的输出类别， 我们将需要12个标量来表示权重（带下标的w）， 3个标量来表示偏置（带下标的b）。 下面我们为每个输入计算三个未规范化的预测（logit）：o1、o2和o3。$$ \begin{split}\begin{aligned} o_1 &= x_1 w_{11} + x_2 w_{12} + x_3 w_{13} + x_4 w_{14} + b_1,\\ o_2 &= x_1 w_{21} + x_2 w_{22} + x_3 w_{23} + x_4 w_{24} + b_2,\\ o_3 &= x_1 w_{31} + x_2 w_{32} + x_3 w_{33} + x_4 w_{34} + b_3. \end{aligned}\end{split} $$与线性回归一样，softmax回归也是一个单层神经网络。运算对于softmax的运算，我们要介绍的是softmax函数$$ \hat{\mathbf{y}} = \mathrm{softmax}(\mathbf{o})\quad \text{其中}\quad \hat{y}_j = \frac{\exp(o_j)}{\sum_k \exp(o_k)} $$这个公式y_hat代表的是正确的概率分布，取幂的目的是为了让数保持非负数，为了确保最终输出的概率值总和为1，我们再让每个求幂后的结果除以它们的总和。$$ \operatorname*{argmax}_j \hat y_j = \operatorname*{argmax}_j o_j. $$如上，我们进行求最大输出值，输出可能最大的概率。尽管softmax是一个非线性函数，但softmax回归的输出仍然由输入特征的仿射变换决定。 因此，softmax回归是一个线性模型（linear model）。损失函数损失函数的确定也十分重要，我们使用极大似然估计法，求对数似然来作为损失函数$$ -\log P(\mathbf{Y} \mid \mathbf{X}) = \sum_{i=1}^n -\log P(\mathbf{y}^{(i)} \mid \mathbf{x}^{(i)}) = \sum_{i=1}^n l(\mathbf{y}^{(i)}, \hat{\mathbf{y}}^{(i)}), $$最后得出损失函数$$ l(\mathbf{y}, \hat{\mathbf{y}}) = - \sum_{j=1}^q y_j \log \hat{y}_j. $$这个损失函数通常被称为交叉熵损失，能够表示出不确定性程度，比较直观的反应分类损失，使用交叉熵还因为它有一个特性是其他损失函数不容易替代的，就是交叉熵更强烈的惩罚错误的输出。如果有非常错误的输出，它的值就会变化很大，反馈很强，并且导数更大。损失函数的导数寻找损失函数的导数是一个很重要的问题$$ \begin{split}\begin{aligned} l(\mathbf{y}, \hat{\mathbf{y}}) &= - \sum_{j=1}^q y_j \log \frac{\exp(o_j)}{\sum_{k=1}^q \exp(o_k)} \\ &= \sum_{j=1}^q y_j \log \sum_{k=1}^q \exp(o_k) - \sum_{j=1}^q y_j o_j\\ &= \log \sum_{k=1}^q \exp(o_k) - \sum_{j=1}^q y_j o_j. \end{aligned}\end{split} $$$$ \partial_{o_j} l(\mathbf{y}, \hat{\mathbf{y}}) = \frac{\exp(o_j)}{\sum_{k=1}^q \exp(o_k)} - y_j = \mathrm{softmax}(\mathbf{o})_j - y_j. $$由此得出该导数，以便于后续计算由于softmax常用于分类，对于图片的分类需要采用图像数据集，在此插入图像分类数据集的相关知识图像分类数据集首先引入数据集所需要的准备工作(代码用课上的)%matplotlib inline import torch import torchvision from torch.utils import data from torchvision import transforms from d2l import torch as d2l d2l.use_svg_display()接下来读取数据集# 通过ToTensor实例将图像数据从PIL类型变换成32位浮点数格式， # 并除以255使得所有像素的数值均在0～1之间 trans = transforms.ToTensor() mnist_train = torchvision.datasets.FashionMNIST( root="../data", train=True, transform=trans, download=True) mnist_test = torchvision.datasets.FashionMNIST( root="../data", train=False, transform=trans, download=True)Fashion-MNIST中包含的10个类别，分别为t-shirt（T恤）、trouser（裤子）、pullover（套衫）、dress（连衣裙）、coat（外套）、sandal（凉鞋）、shirt（衬衫）、sneaker（运动鞋）、bag（包）和ankle boot（短靴）。 以下函数用于在数字标签索引及其文本名称之间进行转换。创建函数可视化样本def show_images(imgs, num_rows, num_cols, titles=None, scale=1.5): #@save """绘制图像列表""" figsize = (num_cols * scale, num_rows * scale) _, axes = d2l.plt.subplots(num_rows, num_cols, figsize=figsize) axes = axes.flatten() for i, (ax, img) in enumerate(zip(axes, imgs)): if torch.is_tensor(img): # 图片张量 ax.imshow(img.numpy()) else: # PIL图片 ax.imshow(img) ax.axes.get_xaxis().set_visible(False) ax.axes.get_yaxis().set_visible(False) if titles: ax.set_title(titles[i]) return axes为了使我们在读取训练集和测试集时更容易，我们使用内置的数据迭代器，而不是从零开始创建。 回顾一下，在每次迭代中，数据加载器每次都会读取一小批量数据，大小为batch_size。 通过内置数据迭代器，我们可以随机打乱了所有样本，从而无偏见地读取小批量。batch_size = 256 def get_dataloader_workers(): #@save """使用4个进程来读取数据""" return 4 train_iter = data.DataLoader(mnist_train, batch_size, shuffle=True, num_workers=get_dataloader_workers())现在我们定义load_data_fashion_mnist函数，用于获取和读取Fashion-MNIST数据集。 这个函数返回训练集和验证集的数据迭代器。 此外，这个函数还接受一个可选参数resize，用来将图像大小调整为另一种形状。def load_data_fashion_mnist(batch_size, resize=None): #@save """下载Fashion-MNIST数据集，然后将其加载到内存中""" trans = [transforms.ToTensor()] if resize: trans.insert(0, transforms.Resize(resize)) trans = transforms.Compose(trans) mnist_train = torchvision.datasets.FashionMNIST( root="../data", train=True, transform=trans, download=True) mnist_test = torchvision.datasets.FashionMNIST( root="../data", train=False, transform=trans, download=True) return (data.DataLoader(mnist_train, batch_size, shuffle=True, num_workers=get_dataloader_workers()), data.DataLoader(mnist_test, batch_size, shuffle=False, num_workers=get_dataloader_workers()))下面，我们通过指定resize参数来测试load_data_fashion_mnist函数的图像大小调整功能。train_iter, test_iter = load_data_fashion_mnist(32, resize=64) for X, y in train_iter: print(X.shape, X.dtype, y.shape, y.dtype) breaksoftmax从零实现准备工作import torch from IPython import display from d2l import torch as d2l batch_size = 256 train_iter, test_iter = d2l.load_data_fashion_mnist(batch_size) num_inputs = 784 num_outputs = 10 W = torch.normal(0, 0.01, size=(num_inputs, num_outputs), requires_grad=True) b = torch.zeros(num_outputs, requires_grad=True)实现softmax由三个步骤组成：对每个项求幂（使用exp）；对每一行求和（小批量中每个样本是一行），得到每个样本的规范化常数；将每一行除以其规范化常数，确保结果的和为1。softmax函数def softmax(X): X_exp = torch.exp(X) partition = X_exp.sum(1, keepdim=True) return X_exp / partition # 这里应用了广播机制模型定义def net(X): return softmax(torch.matmul(X.reshape((-1, W.shape[0])), W) + b)损失函数(一行代码实现交叉熵好牛)def cross_entropy(y_hat, y): return - torch.log(y_hat[range(len(y_hat)), y]) cross_entropy(y_hat, y)分类精度def accuracy(y_hat, y): #@save """计算预测正确的数量""" if len(y_hat.shape) > 1 and y_hat.shape[1] > 1: y_hat = y_hat.argmax(axis=1) cmp = y_hat.type(y.dtype) == y return float(cmp.type(y.dtype).sum())累加类class Accumulator: #@save """在n个变量上累加""" def __init__(self, n): self.data = [0.0] * n def add(self, *args): self.data = [a + float(b) for a, b in zip(self.data, args)] def reset(self): self.data = [0.0] * len(self.data) def __getitem__(self, idx): return self.data[idx]实现def train_epoch_ch3(net, train_iter, loss, updater): #@save """训练模型一个迭代周期（定义见第3章）""" # 将模型设置为训练模式 if isinstance(net, torch.nn.Module): net.train() # 训练损失总和、训练准确度总和、样本数 metric = Accumulator(3) for X, y in train_iter: # 计算梯度并更新参数 y_hat = net(X) l = loss(y_hat, y) if isinstance(updater, torch.optim.Optimizer): # 使用PyTorch内置的优化器和损失函数 updater.zero_grad() l.mean().backward() updater.step() else: # 使用定制的优化器和损失函数 l.sum().backward() updater(X.shape[0]) metric.add(float(l.sum()), accuracy(y_hat, y), y.numel()) # 返回训练损失和训练精度 return metric[0] / metric[2], metric[1] / metric[2]训练函数def train_ch3(net, train_iter, test_iter, loss, num_epochs, updater): #@save """训练模型（定义见第3章）""" animator = Animator(xlabel='epoch', xlim=[1, num_epochs], ylim=[0.3, 0.9], legend=['train loss', 'train acc', 'test acc']) for epoch in range(num_epochs): train_metrics = train_epoch_ch3(net, train_iter, loss, updater) test_acc = evaluate_accuracy(net, test_iter) animator.add(epoch + 1, train_metrics + (test_acc,)) train_loss, train_acc = train_metrics assert train_loss < 0.5, train_loss assert train_acc <= 1 and train_acc > 0.7, train_acc assert test_acc <= 1 and test_acc > 0.7, test_acc小批量随机梯度下降lr = 0.1 def updater(batch_size): return d2l.sgd([W, b], lr, batch_size)简洁实现import torch from torch import nn from d2l import torch as d2l batch_size = 256 train_iter, test_iter = d2l.load_data_fashion_mnist(batch_size)初始化# PyTorch不会隐式地调整输入的形状。因此， # 我们在线性层前定义了展平层（flatten），来调整网络输入的形状 net = nn.Sequential(nn.Flatten(), nn.Linear(784, 10)) def init_weights(m): if type(m) == nn.Linear: nn.init.normal_(m.weight, std=0.01) net.apply(init_weights);损失函数loss = nn.CrossEntropyLoss(reduction='none')优化算法trainer = torch.optim.SGD(net.parameters(), lr=0.1)onehot 独热就像手写数字识别中的 0 1 0 0 0 0 0 0 0 0一样，只有正确值赋值1而其他赋值0的方式就是onehot表示多层感知机前面咱们使用过单层的感知机了，多层感知机就是在原有的基础上，加入隐藏层，从而克服线性隐藏层的限制，要做到这一点，最简单的方法是将许多全连接层堆叠在一起。 每一层都输出到上面的层，直到生成最后的输出。 通常缩写为MLP。要实现数值稳定性数值稳定性在深度学习中是十分重要的在进行反向传播求梯度时，根据链式法则，我们知道，梯度计算的结果是有许多的矩阵与一个梯度向量的乘积，会受到数值下溢的影响，引起梯度爆炸或梯度消失，原理很简单，就是过多的概率相乘带来的结果，不稳定的梯度带来的风险很大梯度消失参数更新过小，导致模型无法学习sigmoid函数就是导致梯度消失的常见原因，由于sigmoid函数是饱和函数，在输入很大或很小时其梯度都会消失。导致模型梯度被切断梯度爆炸参数更新过大，破坏了模型的稳定收敛与模型消失相反，但同样让人烦恼，模型爆炸也是一种不可避免的问题对称性神经网络设计中的另一个问题是其参数化所固有的对称性。在这种情况下，我们可以对第一层的权重进行重排列， 并且同样对输出层的权重进行重排列，可以获得相同的函数。在基于梯度的迭代（例如，小批量随机梯度下降）之后， W1的所有元素仍然采用相同的值。 这样的迭代永远不会打破对称性，我们可能永远也无法实现网络的表达能力。 隐藏层的行为就好像只有一个单元。 请注意，虽然小批量随机梯度下降不会打破这种对称性，但暂退法正则化可以。模型初始化在模型训练中，我们想努力使训练更稳定，目标就是要让梯度值在合理的范围内。可使用的方法有：把乘法变加法归一化合理的权重初始和激活函数权重初始化在合理值区间里随机初始参数训练开始的时候更容易有数值不稳定远离最优解的地方损失函数表面可能很复杂最优解附近表面会比较平Xavier初始不能同时满足前一层与后一层的方差＝1，采用折中的办法这节，我学不懂，等以后会概率论了再说吧只听懂了一点就是激活函数的由来假设我有一个线性函数等于ax+b，我要实现通过这个函数，让我的均值与方差保持不变，可以求解得到a=1,b=0。由此达到relu函数为什么好用了。检查激活函数使用泰勒展开检查 可以发现各个激活函数的合理性环境与分布偏移模型的数据来源，数据精度是很重要的问题，我们在训练模型的时候一定关注这些问题，当数据分布改变时，模型部署可能会出现灾难性的失败。分布偏移类型
-
torch进阶 Torch进阶损失函数函数方式定义的损失函数易于定义，直接写个函数就ok不过我们也可以以类定义以类方式定义损失函数虽然以函数定义的方式很简单，但是以类方式定义更加常用以类定义损失函数时，我们继承自nn.Module类，将其作为神经网络的一层看待，也可以利用自动求导例如我们要实现Dice Loss(分割领域常见的损失函数)$DSC = \frac{2|X \bigcap Y|}{|X| + ||Y}$我们的实现代码class DiceLoss(nn.Module): def __init__(self,weight): super(DiceLoss,self).__init__() def forward(self,inputs,targets,smooth=1): inputs = F.sigmoid(inputs) inputs = input.view(-1) targets = targets.view(-1) intersection = (inputs*targets).sum() dice = (2.*intersection + smooth)/(inputs.sum() + targets.sum() + smooth) return 1 - dice动态调整学习率学习率的大小会影响模型调优，我们使用scheduler方法来实现动态调整策略pytorch中的lr_scheduler已经提供给了我们动态调整的方法我们可以使用help(torch.optim.lr_scheduler)来查看他们的使用方法使用示例如下# 选择一种优化器 optimizer = torch.optim.Adam(...) # 选择上面提到的一种或多种动态调整学习率的方法 scheduler1 = torch.optim.lr_scheduler.... scheduler2 = torch.optim.lr_scheduler.... ... schedulern = torch.optim.lr_scheduler.... # 进行训练 for epoch in range(100): train(...) validate(...) optimizer.step() # 需要在优化器参数更新之后再动态调整学习率 # scheduler的优化是在每一轮后面进行的 scheduler1.step() ... schedulern.step()我们可以看到scheduler是在每一轮训练结束后使用的，需要放在optimizer后面进行使用模型微调我们在使用参数量比较大的网络时，不能将模型从头到尾再训练一遍例如我们在进行特定的图像分类时可以重写分类层，前面学习到的“知识”不变，所以我们要进行模型微调pretrained参数通过True或者False来决定是否使用预训练好的权重，在默认状态下pretrained = False，意味着我们不使用预训练得到的权重，当pretrained = True，意味着我们将使用在一些数据集上预训练得到的权重。训练特定层在我们只想训练特定层时，经常涉及到部分层的冻结，这就涉及到参数的属性 require_grad ，当这个值取False时，该参数不再更新所以我们指定函数进行层的冻结def set_parameter_requires_grad(model, feature_extracting): if feature_extracting: for param in model.parameters(): param.requires_grad = Falsetimm使用timm.list_model进行模型查看 使用timm.create_model进行模型创建timm模型是torch.model的子类所以我们进行模型保存与提取时使用torch的方法即可半精度训练半精度训练能够减少显存的占用，使得同时加载更多的数据进行计算首先我们需要引入from torch.cuda.amp import autocast模型定义中需要使用修饰器@autocast() def forward(self, x): ... return x在训练过程中，只需在将数据输入模型及其之后的部分放入“with autocast():“即可： for x in train_loader: x = x.cuda() with autocast(): output = model(x)半精度训练主要适用于数据本身的size比较大（比如说3D图像、视频等）数据增强我们遇到过拟合问题的时候加入正则项或者减少模型参数 但是最简单的避免过拟合的方法就是增加数据所以数据增强技术可以提高训练数据集的大小与质量 以便于使用他们构建更好的深度学习模型使用imgaug进行数据增强相比于torchvision.transforms，它提供了更多的数据增强方法，因此在各种竞赛中，人们广泛使用imgaug来对数据进行增强操作。imgaug是一个图像增强库，并未提供IO操作，建议使用imageio进行读入，如果是OpenCV进行读入时，需要将BGR图像手动转化成RGB图像 使用PIL.Image进行读取时，因为读取没有shape属性，需要手动将img转换为np.array的形式再进行处理，官方的例程中野兽使用的imageio进行读取单张图片处理from imgaug import augmenters as iaa # 设置随机数种子 ia.seed(4) # 实例化方法 rotate = iaa.Affine(rotate=(-4,45)) img_aug = rotate(image=img) ia.imshow(img_aug)如图就是从augmenters中使用Affine方法进行的操作，将图片随机旋转-4到45度，以便进行图片的增强有时候我们会对一张图片做多种处理我们使用augmenter.Sequential进行数据增强的pipline例如aug_seq = iaa.Sequential([ iaa.Affine(rotate=(-25,25)), iaa.AdditiveGaussianNoise(scale=(10,60)), iaa.Crop(percent=(0,0.2)) ])对批次图片进行处理实际使用中我们需要进行批次图片的处理操作如下images = [img,img,img,img,] images_aug = rotate(images=images) ia.imshow(np.hstack(images_aug))使用images参数，输入图像列表，就能达批次同效果我们甚至可以使用imgaug进行分部分处理使用iaa.sometimes进行比例划分，使用不同的处理方法可视化网络结构复杂的同时，我们需要一个可视化的工具来方便我们确定输入输出、模型参数使用torchinfo可以做到可视化使用方法非常简单，直接使用torchinfo.summary()就行了，必须的参数是model 与 input_size但你使用的是colab或者jupyter notebook时，想要实现该方法，summary()一定是该单元（即notebook中的cell）的返回值，否则我们就需要使用print(summary(...))来可视化。TensorBoard使用TensorBoard就相当于加入一个记录员，记录我们指定的数据，包括每一层的权重，训练loss等，最后使用网页形式进行可视化from tensorboardX import SummaryWriter writer = SummaryWriter('./runs')我们首先制定了writer作为记录员pytorch中自带的TensorBoard通过以下方法引入from torch.utils.tensorboard import SummaryWriter我们使用像summary中同样的思路，给定输入数据，前向传播得到模型结构，使用TensorBoard进行可视化writer.add_graph(model, input_to_model = torch.rand(1, 3, 224, 224)) writer.close()对于处理图像，我们也可以在TensorBoard中进行可视化展示对于单张图片，使用add_image对于多张图片，使用add_images有时需要将多张图片拼接成一张图片后用writer.add_image进行表示import torchvision from torchvision import datasets, transforms from torch.utils.data import DataLoader transform_train = transforms.Compose( [transforms.ToTensor()]) transform_test = transforms.Compose( [transforms.ToTensor()]) train_data = datasets.CIFAR10(".", train=True, download=True, transform=transform_train) test_data = datasets.CIFAR10(".", train=False, download=True, transform=transform_test) train_loader = DataLoader(train_data, batch_size=64, shuffle=True) test_loader = DataLoader(test_data, batch_size=64) images, labels = next(iter(train_loader)) # 仅查看一张图片 writer = SummaryWriter('./pytorch_tb') writer.add_image('images[0]', images[0]) writer.close() # 将多张图片拼接成一张图片，中间用黑色网格分割 # create grid of images writer = SummaryWriter('./pytorch_tb') img_grid = torchvision.utils.make_grid(images) writer.add_image('image_grid', img_grid) writer.close() # 将多张图片直接写入 writer = SummaryWriter('./pytorch_tb') writer.add_images("images",images,global_step = 0) writer.close()torch生态torchvisiontorchvision.datasets其中包含了我们在计算机视觉领域常见的数据集torchvision.transforms我们知道，数据集中的数据格式或者大小不一样，需要进行归一化与大小缩放等操作，都是常用的数据预处理方法，例如from torchvision import transforms data_transform = transforms.Compose([ transforms.ToPILImage(), # 这一步取决于后续的数据读取方式，如果使用内置数据集则不需要 transforms.Resize(image_size), transforms.ToTensor() ])torchvision.models为了提高训练效率，减少不必要的重复劳动，pytorch提供给我们很多的预训练模型供我们使用torchvision.io里面提供了视频、图片和文件的IO操作等功能，包括读取、写入、编解码处理等操作torchvision.opstorchvision.ops 为我们提供了许多计算机视觉的特定操作，包括但不仅限于NMS，RoIAlign（MASK R-CNN中应用的一种方法），RoIPool（Fast R-CNN中用到的一种方法）。在合适的时间使用可以大大降低我们的工作量，避免重复的造轮子，想看更多的函数介绍可以点击这里进行细致查看。torchvision.utils提供了很多可视化的方法，帮助我们将若干张图片拼接在一起，可视化检测与分割的效果pytorchvideo视频处理 用的时候学torchtext文本处理torchaudio音频处理
