OE.Heart's Blog

Leftist Heaps Target: Speed up merging in O(N)O(N)O(N) Heap: Structure Property + Order Property Leftist Heap Order Property – the same Structure Property – binary tree, but unbalanced [Definition] The null path length, Npl(X), of any node X is the length of the shortest path from X to a node without two children. Npl(NULL)=–1Npl(NULL) = –1Npl(NULL)=–1 Npl(X)=min⁡{Npl(C)+1 for all C as children of X}Npl(X) = \min\{ Npl(C) + 1 \text{ for all C as children of X} \}Npl(X)=min{Npl(C) ...

Solution1: Scan each page Solution2: Term-Document Incidence Matrix Solution3: Compact Version - Inverted File Index 倒排文件索引 [Definition] Index is a mechanism for locating a given term in a text. [Definition] Inverted file contains a list of pointers (e.g. the number of a page) to all occurrences of that term in the text Note: Inverted because it lists for a term, all documents that contain the term. AND 操作从最小频率的 term 开始求交，速度快 Index Generator 1234567891011while ( read a document D ) ...

Red-Black Trees Target: Balanced binary search tree [Definition] A red-black tree is a binary search tree that satisfies the following red-black properties: Every node is either red or black The root is black Every leaf (NIL) is black If a node is red, then both its children are black For each node, all simple paths from the node to descendant leaves contain the same number of black nodes [Definition] The black-height of any node xxx, denoted by bh(x)\text{bh}(x)bh(x), is the number of b ...

AVL Trees Target: Speed up searching (with insertion and deletion) Tool: Binary search trees Problem: Although Tp=O(height)T_p = O( \text{height} )Tp​=O(height), but the height can be as bad as O(N)O( N )O(N) [Definition] An empty binary tree is height balanced. If TTT is a nonempty binary tree with TLT_LTL​ and TRT_RTR​ as its left and right subtrees, then TTT is height balanced if and only if TLT_LTL​ and TRT_RTR​ are height balanced, and ∣hL−hR∣≤1| h_L - h_R | \leq 1∣hL​−hR​∣≤1 where hLh ...

实验目的 创建用户态进程，并设置 sstatus 来完成内核态转换至用户态 正确设置用户进程的用户态栈和内核态栈， 并在异常处理时正确切换 补充异常处理逻辑，完成指定的系统调用（ SYS_WRITE, SYS_GETPID ）功能 实验内容及要求 巩固页式内存管理以及虚拟内存的相关知识 在低地址空间映射用户态程序，并尝试编写简单的系统调用处理函数 实现用户态进程，完成 write、getpid 系统调用 阅读背景知识介绍，跟随实验步骤完成实验，以截图的方式记录命令行的输入与输出，注意进行适当的代码注释 如有需要，对每一步的命令以及结果进行必要的解释 实验环境 本次实验全部在 Ubuntu 20.04.3 LTS x86_64 操作系统上进行，具体环境信息如下图所示： 在本次实验中继续使用 Lab0 中搭建好的 Docker 容器，Docker 版本为 20.10.8 实验步骤 准备工程 此次实验基于 Lab3 所实现的代码进行，从仓库同步代码：user/，Makefile，增加 syscall.c，syscall.h 文件，并放置在正确放置。 完成后项目文件组织结构 ...

实验目的 学习虚拟内存的相关知识，实现物理地址到虚拟地址的切换 了解 RISC-V 架构中 SV39 分页模式，实现虚拟地址到物理地址的映射，并对不同的段进行相应的权限设置 实验内容及要求 开启虚拟地址以及通过设置页表来实现地址映射和权限控制 实现 SV39 分配方案下的三级页表映射 了解页表映射的权限机制，设置不同的页表映射权限 阅读背景知识介绍，跟随实验步骤完成实验，以截图的方式记录命令行的输入与输出，注意进行适当的代码注释 如有需要，对每一步的命令以及结果进行必要的解释 实验环境 本次实验全部在 Ubuntu 20.04.3 LTS x86_64 操作系统上进行，具体环境信息如下图所示： 在本次实验中继续使用 Lab0 中搭建好的 Docker 容器，Docker 版本为 20.10.8 实验步骤 准备工程 此次实验基于 Lab3 所实现的代码进行，从仓库同步代码：def.h，vmlinux.lds.S，Makefile，并放置在正确放置。 其中 vmlinux.lds.S 用作模版生成 vmlinux.lds 文件。链接脚本中的 ramv 代表 LMA(Vi ...

实验目的 了解线程概念，并学习线程相关结构体，并实现线程的初始化功能 了解如何使用时钟中断来实现线程的调度 了解线程切换原理，并实现线程的切换 掌握简单的线程调度算法，并完成两种简单调度算法的实现 实验内容及要求 理解进程调度与进程切换过程 利用时钟中断模拟进程调度实验，实现优先级算法和短作业优先算法 阅读背景知识介绍，跟随实验步骤完成实验，以截图的方式记录命令行的输入与输出，注意进行适当的代码注释 如有需要，对每一步的命令以及结果进行必要的解释 实验环境 本次实验全部在 Ubuntu 20.04.3 LTS x86_64 操作系统上进行，具体环境信息如下图所示： 在本次实验中继续使用 Lab0 中搭建好的 Docker 容器，Docker 版本为 20.10.8 实验步骤 准备工程 此次实验基于 Lab2 所实现的代码进行，从仓库同步代码: rand.h/rand.c，string.h/string.c，mm.h/mm.c，并放置在正确放置。其中 mm.h/mm.c 提供了简单的物理内存管理接口，rand.h/rand.c提供了rand()函数接口用以提供伪随机数 ...

实验目的 学习 RISC-V 的异常处理相关寄存器与指令，完成对异常处理的初始化 理解 CPU 上下文切换机制，并正确实现上下文切换功能 编写异常处理函数，完成对特定异常的处理 调用 OpenSBI 提供的接口，完成对时钟中断事件的设置 实验内容及要求 理解 RISC-V 异常委托与异常处理机制 利用 OpenSBI 平台的 SBI 调用触发时钟中断，并通过代码设计实现定时触发时钟中断的效果 阅读背景知识介绍，跟随实验步骤完成实验，以截图的方式记录命令行的输入与输出，注意进行适当的代码注释 如有需要，对每一步的命令以及结果进行必要的解释 实验环境 本次实验全部在 Ubuntu 20.04.3 LTS x86_64 操作系统上进行，具体环境信息如下图所示： 在本次实验中继续使用 Lab0 中搭建好的 Docker 容器，Docker 版本为 20.10.8 实验步骤 准备工程 本次实验基于 Lab1 中实现的代码进行，根据实验指导同步修改原有代码后，项目文件组织结构如下： 开启异常处理 我们将 M 模式的事务交由 OpenSBI 进行处理，从而只需要关注 S 模式 ...

实验目的 学习 RISC-V 汇编， OpenSBI，以及 Makefile 相关知识 编写 head.S 实现跳转到内核运行的第一个 C 函数 调用 OpenSBI 接口完成字符的输出以及编写 Makefile 来完成对整个工程的管理 实验内容及要求 阅读 RISC-V 中文手册，学习 RISC-V 相关知识 学习 Makefile 编写规则，补充 Makefile 文件使得项目成功运行 了解 OpenSBI 的运行原理，编写代码通过 sbi 调用实现字符串的打印 独立完成实验，任何抄袭行为都将使本次实验判为0分 阅读背景知识介绍，跟随实验步骤完成实验，以截图的方式记录命令行的输入与输出，注意进行适当的代码注释 如有需要，对每一步的命令以及结果进行必要的解释 实验环境 本次实验全部在 Ubuntu 20.04.3 LTS x86_64 操作系统上进行，具体环境信息如下图所示： 在本次实验中继续使用 Lab0 中搭建好的 Docker 容器，Docker 版本为 20.10.8 实验步骤 准备工程 创建容器并建立映射关系 首先建立本地工作目录并进入，目录路径为 / ...

Author: Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever Link: https://openai.com/blog/language-unsupervised/ Introduction 从未标记的文本中利用字级以上的信息困难的两个原因 目前还不清楚哪种类型的优化目标在学习对迁移有用的文本表示形式时最有效 对于将这些习得的表征转化到目标任务的最有效方法，目前还没有达成共识 本文探索语言理解任务的半监督方法，结合无监督的预训练和监督的微调，目标是学习一种普适性的表征，这种表征只需要少量的修改就可以迁移到广泛的任务。 采用两阶段的训练方式： 在未标记数据上使用语言建模目标来学习神经网络模型的初始参数 使用相应的监督目标将这些参数调整到目标任务 Related Work Semi-supervised learning for NLP Unsupervised pre-training Auxiliary training objectives Framework Unsuper ...