算法设计与分析课程设计

quantumxiaol/NEU_Algorithm_coursedesign

¹⁾(东北大学 计算机学院, 沈阳市 10000)

摘  要 随着计算机技术与互联网技术的飞速发展，越来越丰富的信息呈现在用户面前，但同时伴随的问题是用户越来越难以获得其最需要的信息。本次课程设计旨在设计与实现一个小型搜索引擎系统，主要分为四部分：首先需要利用爬虫爬取网页信息；其次进行分词，再应用字典树查重与统计词频并编号，生成临时索引；之后对单词编号进行希尔排序、归并排序与多路平衡归并排序并整合，生成倒排索引；最后根据倒排索引查询结果，并用堆排序对网页编号出现次序排序，最后用二分查找查询结果并输出。

关键词 搜集、分词、字典树、临时索引、希尔排序、归并排序、多路平衡归并排序、倒排索引、堆排序、二分查找

 

Implementation of a simple search engine

Liu XiaoLong¹⁾  Wang YiZheng²⁾  Ji Ye³⁾  Teng Peng⁴⁾

¹⁾(Northeastern University, ShenYang 10000, China)

 

Abstract With the rapid development of computer technology and Internet technology, more and more abundant information is presented to users, but at the same time, it is more and more difficult for users to obtain the information they need most. This course is designed to design and implement a small search engine system, which is mainly divided into four parts: first, we need to use crawlers to crawl web page information; Secondly, word segmentation is carried out, and then dictionary tree duplicate checking and word frequency statistics are applied and numbered to generate temporary index; After that, the word numbers are sorted and integrated to generate an inverted index; Finally, according to the inverted index query results, and use heap sorting to sort the sequence of web page numbers, and finally use binary search query results and output.

Key words Collect; Word Segmentation; Dictionary Tree; Temporary index; Shell Sort; Merging sort; Multi-channel Balanced Merge Sort; Inverted index; Heap Sort; Binary Search

 

1 课题概述

1.1 课题任务

课题任务即不调用算法库的条件下，实现一个小型搜索引擎，分块完成搜集、分析、索引、查询四部分。其中：

搜集指利用爬虫爬取网页信息；

分析是对网页内容抽取、分词，构建临时索引；

索引是在临时索引的基础上，进行排序与整合，构建倒排索引；

查询是响应用户的请求，根据倒排索引获取相关网页，计算网页排名，返回查询结果给用户。

1.2  课题原理

首先在互联网中发现、搜集网页信息；同时对信息进行提取和组织建立索引库；再由检索器根据用户输入的查询关键字，在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并将查询结果返回给用户。

1.3  相关知识

主要算法：

1. 字典树
2. 希尔排序
3. 归并排序
4. 多路平衡归并排序
5. 堆排序
6. 二分查找

2  算法设计

2.1  类函数列表

类型	内容
结构 体	struct TrieNode{ vector<TrieNode *> child;     bool isEnd;     int wordid;   TrieNode() {this->child=vector<TrieNode *> (67,nullptr); this->isEnd=false;        wordid=-114514;}};
类（ public为部 分函 数）	class WordDictionary { public: WordDictionary() {} ~WordDictionary(){} void release(TrieNode* r){} void addWord(string word,int id) {} void printWordDictionary(){} void readWordDictionary(){} void inputWordDictionary(){} intsearchwordid(stringword){} bool search(string word) {} bool dfsid(const string & word,int index,TrieNode * node,int &id) {} bool dfs(const string & word,int index,TrieNode *  node) {} private:     TrieNode *trie;}
结构体	struct trie {     int n;     bool isRecord;     trie* son[67];     trie (): n(0) {         isRecord=false;         for (int i = 0; i < 67; ++i) {             son[i] = nullptr;         }}};
类	class WordsFrequency { private:     trie* root; public:     WordsFrequency(vector<string>& book) {}}
函数	void debugWordDictionary(){} bool isletter(char str) bool isdigit(char str) int mainTPfunction(){} int readsitestory_TP(long long int id,vector<string> &input){} inttempindex(longlongintid,vector<string>htmlword, vector<string>&wordlist,WordDictionary &WD,vector<pair<int,int>>&index1){} int tempindexwithfrequency(longlongintid, vector<string>htmlword,WordDictionary &WD,vector<pair<int,pair<int,int>>>&index1){} int analyseHtml(int num=HTMLNUM){} int generate_temp_index(vector<pair<int,int>> input){} voidPrintVector(vector<string>v,string information){}；int runsearch(); int keyword_search(std::vector<std::string> &inputlist); int isContinue();int preProcess(); int debugtest();int test(int num); int inputwordlist(std::vector<std::pair< std::string,int>> &input); int readwordlist(std::vector<std::pair< std::string,int>> &input); int inputtempindex(std::vector< std::pair<int,int>> &input); int readtempindex(std::vector< std::pair<int,int>> &input); int inputindex(std::vector<std::pair<int, std::vector<int>>> &input); int readindex(std::vector<std::pair<int, std::vector<int>>> &input); intinputtempindexfrequency(std::vector< std::pair<int, std::pair<int,int>>> &input); int readtempindexfrequency(std::vector< std::pair<int,std::pair<int,int>>> &input); void Readcsv();bool isHttp(std::string str); void inputsitestory(long long int htmlnum,std::string str); void readstory();void debugtest_read(); int readsitestory(long long int id, std::vector<std::string> &input); intreadsitestory_state(longlongint id,std::vector<std::string> &input); void debugtext_readhtml(int num); int analyseHtml(); void debugtext_analyseHtml();

2.1  文件格式定义

网页数据从new.csv文件中读取出来放入代码根目录的SearchEngine\1\html doc_id的txt文件中（doc_id为网页编号）

读取html doc_id中的网页文件，分词查重之后存入单词编号文件wordlist.txt,生成临时索引tempindex.txt,生成带词频的临时索引文件tempindexfrequency.txt

读取tempindex.txt中的文件，通过归并排序、希尔排序生成倒排索引文件index.txt

2.2  输入输出

输入：csv文件

输出：网页查询结果

Figure 1 程序整体流程

3  方案实现

3.1  关键算法

英文分词、利用字典树查重、希尔排序、归并排序、外部排序、堆排序

3.1  个人程序设计

• 网页的提取，单词的编号，生成临时索引，生成倒排索引：刘小龙[1]

伪代码：

TEMINDEX=READTEMPINDEXFILE();
FOR(AUTO IT=TEMINDEX.BEGIN();IT!=TEMINDEX.END();){
    IF(IT==TEMINDEX.BEGIN()){IT++;CONTINUE;}
    INT WORDID=(*(IT-1)).FIRST;
    IF((*IT).FIRST==(*(IT-1)).FIRST){
        SMALL.PUSH_BACK( (*(IT-1)).SECOND );
        TEMINDEX.DELETE(IT-1);
        IT++;
        CONTINUE;
    }
    ELSE{
        SMALL.PUSH_BACK((*(IT-1)).SECOND);
        INDEXTEST.PUSH_BACK(MAKE_PAIR(WORDID,SMALL));
        SMALL.CLEAR();
        VECTOR<INT>().SWAP(SMALL);
        IT++;
    }
}

流程设计：

算法复杂度分析：

字典树

时间复杂度：初始化为 O(1)，其余操作为 O(|S|)，其中 |S| 是每次插入或查询的字符串的长度。

空间复杂度：O(|T|·Σ)，其中 |T| 为所有插入字符串的长度之和，Σ 为字符集的大小，Σ=67。

个人感悟：这一部分使用向量容器，对排好序的向量容器前后两个比较，对单词编号相同的记录出现的网页编号（和单词在该网页出现的频率），插入到一个记录网页编号的向量容器，然后删除一行记录，继续比较；出现不同则一个单词记录完成，将一行记录写入文件，重新比较。
这一部分我遇到了性能瓶颈，写入文件的时间要75min（带频率信息的文件是95min），现在想来，是STLvector的删除所致，应该直接读写文件。我的测试样例vector的大小有815321行，牵一发而动全身，拖慢了节奏。

• 英文分词：滕鹏[2]

伪代码：

WHILE (TEST>>STR)

IF STR[I]==标点符号/空格

DELETE STR[I]

ELSE

COUTINUE

流程设计：

Figure 2 英文分词流程

算法复杂度分析：

时间复杂度：O(n)，n是文件中的行数

空间复杂度：取决于文件大小

个人感悟：在这次课程设计当中，我了解到了我的不足，如算法的不完善、不细心和耐心不是很好等等。不细心的我在调试程序时，老是因为某个书写错误导致错误；对这些错误，我不得不花大量的时间去更正，并且还要重复检查是否出现雷同的错误而导致程序不能运行。但是通过这次课程设计，我的这些缺点有些改善。我在写新的程序时，首先要考虑的深入一点、仔细一点，这样要修改程序的时间就会少很多。并且也不会因为自己不细心而导致的浪费时间的情况出现。在进行程序设计时，要注意想好思路。即要有恰当模块名、变量名、常量名、子程序名等。将每个功能的模块，即函数名要清晰的表述出来，使用户能够一目了然此程序的功能。当然适当的给写注释，也是方便用户的理解。还有在编写程序时要注意对程序的适当分配，便于用户看懂程序，也便于自己检查城市。但是完成任何一个较大的程序，都需要掌握一定的编程基础，需要不断的探索和求知过程，这样对自己编程能力的提高有较大的帮助。

• 希尔排序、归并排序：季晔[3]

伪代码：

VOID MERGE_SORT(VECTOR<PAIR<INT,INT>>&Q, INT L, INT R){
IF (L >= R) RETURN;
INT MID = (L + R) >> 1;
MERGE_SORT(Q, L, MID);
MERGE_SORT(Q, MID + 1, R);
INT K = 0, I = L, J = MID + 1;
VECTOR<PAIR<INT,INT>> TMP(Q.SIZE());
WHILE (I <= MID && J <= R){
IF (Q[I].FIRST <= Q[J].FIRST) {
TMP[K++] = Q[I++];
}
ELSE TMP[K++] = Q[J++];
}
WHILE (I <= MID) TMP[K++] = Q[I++];
WHILE (J <= R) TMP[K++] = Q[J++];
FOR (INT I = L, J = 0; I <= R; I++, J++) Q[I] = TMP[J];}

多路平衡归并排序伪代码
INT ADJUST(LOSERTREE &LS,INT S,EXTERNAL &B){//调整败者树
INT T=(S+5)/2;
WHILE(T>0){
IF(CMPEXNODEG(B[S],B[LS[T]])){//S指向新的胜者，而LS[T]指向败者
INT TEM=S;
S=LS[T];
LS[T]=TEM;}
T/=2;//向上继续比较}
LS[0]=S;}
VOID CREATE_LOSERTREE(LOSERTREE &LS,EXTERNAL &B){
FOR(INT I=0;I!=5;++I){//设置LS败者的初值都为5， K位置的关键字已经设置为了-1，
LS[I]=5;}
FOR(INT I=0;I!=5;++I){//一次从存储点第一个关键词开始进行调整
ADJUST(LS,I,B);}}
VOID K_MERGE(LOSERTREE &LS,EXTERNAL &B,VECTOR<VECTOR<PAIR<INT,INT>>> R){
FOR(INT I=0;I!=K;++I){//先将个归并段的第一个关键字，放入存储数组
B[I].KEY=R[I][0];
}
B[K].KEY=-1;//设置一个最小值，作为建立败者树时用，
CREATE_LOSERTREE(LS,B);
INT NEXT0=1,NEXT1=1,NEXT2=1,NEXT3=1,NEXT4=1,NEXT5=1,NEXT6=1,NEXT7=1;
WHILE(B[LS[0]].KEY!=1000){//当1000出来的时候，说明归并已经完成
INT Q=LS[0];
COUT<<B[Q].KEY<<”  “;//输出一个被选出来的关键字
ADJUST(LS,Q,B);//再进行调整，
}
}

流程设计：

Figure 3外部排序

算法复杂度分析：

希尔排序：

时间复杂度：最好情况是序列是正序排列，每一趟只需比较(n-1)次，即O(n)，而因为直接插入排序对有序的序列效率很高，因此最坏情况要优于直接插入排序的O(n^2)，渐进时间复杂度为O(nlog2n)

空间复杂度：希尔排序每一趟都只需要常量级空间，空间复杂度为O(1)

归并排序：

时间复杂度：归并排序分为数组划分和有序数组归并两个步骤，其中有序数组归并的时间复杂度为O（n），因为代码中有两个长度为n的循环。所以得到公式T（n）=2T（n/2）+O（n）得到归并排序的时间复杂度T（n）=O（nlogn）

空间复杂度：归并过程中临时的数组和递归压栈的数据占用空间为n+logn，因此空间复杂度为O(n)

多路平衡归并排序：

时间复杂度：由于是外部排序，涉及文件读写，所以很大一部分是文件读写时间，其余部分 内部排序时间复杂度是O(nlogn)，内部归并排序时间复杂度是O(logn)

个人感悟：

本次课程设计

1.让我认识到了算法的选择对一个程序影响之大。我负责索引部分的排序算法，内部排序中，希尔排序与归并排序各有其时空方面的利弊，但针对本次任务，需要排序的数据量过大，显然避免内存不足，外部排序是更好的选择。

2.巩固了我课内的知识，也锻炼了我的思维与代码编写能力。归并排序用到了递归分治的思想，希尔排序本质则是分段进行多次插入排序。而外部排序是我第一次尝试学习并实现，尽管最终未能整合进总程序，但利用外存储器与利用败者树这一特殊结构实现还是让我感叹算法之精妙。

3.培养了我的团队协作能力。我在整个课程设计中，尤其是文件读写和多路平衡归并排序的实现中遇到了许多困难，但得益于团队的帮助，我最终克服了这些困难。一起编写程序、一起准备汇报、一起写报告，这些都让我认识到团队的力量与合作精神。

4.让我认识到了自己存在的不足。显然我编写代码的能力存在不足，不仅写起代码很是生疏，而且许多我负责的部分也没能独立完成，这让我认识到自身存在的不足，我会在未来磨练自己的能力。

• 网页查询：王怡正[4]

伪代码：

堆排序：//建堆,
N= LENGTH(A)
FOR I= N/2 DOWNTO 1 DOLL从非叶子节点开始，自底往上，使A变成最大堆
MAX HEAPIFY(A, I,N)
END
/调整为最大堆,T(N)= O(LGN)
MAX_HEAPIFY(A,IDX,MAX) //IDX:数组开始的下标, MAX:最大的数组下标LEFT = 2*IDX
RIGHT = 2*IDX
IF(LEFT<MAX AND A[LEFT]-A[IDX]) THENLARGEST = LEFT
ELSE
LARGEST = IDX
IF(RIGHT < MAX AND A[RIGHT]>A[LARGEST]) THENLARGEST = RITHT
IF(LARGEST != IDX) THEN
EXCHANGE A[LARGEST] WITH A[IDX]
MAX_HEAPIFY(A,LARGEST,MAX)//交换位置后，还需要调整它的子树END
HEAPSORT(A)
BUILDHEAP(A)
FOR I = LENGTH(A) DOWNTO 2 DO
EXCHANGE A[1] WITH A[n]//把最大堆根节点与最后一个互换
MAX_HEAPIFY(A,1, I-1)//把交互后的排除在堆之外，重新从1到I-1,调整堆
END

流程设计：

Figure 4二分查找实现流程

Figure 5堆排序流程

算法复杂度分析：

堆排序

时间O(nlogn),

空间复杂度O(1)

二分查找

时间复杂度O(logn),

空间复杂度O(1)

个人感悟：在做这次算法的课程设计的过程中，我充分意识到不同算法对一个程序的处理数据的能力会造成多大的影响，这种影响在数据不大的情况下可能不会太过于明显，而一旦数据变得比较大那么这种影响就会很大程度上的显现出来，比如这次在设计查询的过程中，因为需要排序和查询两部分，我认真比较了不同算法之间的复杂度区别，最终选择了我认为时间复杂度和空间复杂度都适合的堆排序和二分查找，在编写的过程中，我仔细学习了两个算法的思路和本质，最后用递归程序将两个算法实现.在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。

如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。因此，学习算法无疑会增强自己的竞争力，提高自己的修为，为自己增彩。

3.2  程序优化

查单词编码：遍历查找->字典树查找

顺序查找：最好情况（查找第一个就是）时间复杂度为O(1)，最坏情况（查找最后一个是）时间复杂度为O(n)，平均情况即为(n+1)/2。而字典树有额外空间换时间，一般而言认为建树的额外空间是常数级，时间复杂度为O(1)。

 

参 考 文 献

 

[1]   Li Dan-Yang, Zhao Ya-Hui, Luo Meng-Jiang, Cui Rong-yi. Query text proofreading method of professional courses based on trie tree language model, Journal of Yanbian University(Natural Science) 2020, 1004-4353（2020）03-0260-05(in Chinese)
（李丹阳，赵亚慧，罗梦江，崔荣一.基于字典树语言模型的专业课查询文本校对方法，延边大学学报（自然科学版），2020，1004-4353（2020）03-0260-05）
[2] Chen Zhi-Feng. Design of Automatic Word Segmentation System for Network Retrieval Based on Data Mining, Journal of Hubei University of Science and Technology, 2022, 2095-4654 (2022) 03-0117-05(in Chinese)
（陈志锋. 基于数据挖掘的网络检索自动分词系统设计,湖北科技学院学报，2022，2095-4654（2022）03-0117-05）

[3] （解学武. 数据结构与算法， data.biancheng.net）

[4] Wang Xiao-Di. Research on Query Recommendation Algorithm Based on Search Engine, Software Guide, 1672-7800(2020)010-0076-04(in Chinese)
（王晓迪，基于搜索引擎的查询推荐算法研究，软件导刊，2020,1672-7800（2020）010-0076-04）

Github:quantumxiaol/NEU_NLP_AccelerateviaMoE:

Design and Implement of Model Inference Acceleration via Mixture-of-Experts

Sen Yang, Xiaolong Liu, Ye Ji, Aobo Guo

Abstract

By mixing experts, the one layer with wider dimensions in the original model is divided into several expert networks with smaller dimensions, which can effectively reduce the number of parameters and achieve the purpose of improving efficiency.

1 Introduction

Reasoning acceleration is an important means to improve model performance and efficiency, which can save time, save energy, reduce costs and enhance user experience.

There are many methods to accelerate model reasoning, such as model compression, model quantification, model pruning, model distillation and so on, but these methods usually sacrifice certain model accuracy or generalization ability.

The model reasoning acceleration method based on mixed experts is a novel method, which can increase the capacity of the model by several orders of magnitude while ensuring the operation speed, thus improving the expression ability and prediction ability of the model.

Transformer-based models revolutionize the field of natural language processing, and demonstrate excellent performance in various tasks such as machine translation, emotion analysis and information retrieval. [1] However, the traditional Transformer model often calculates all neurons at the same time, which leads to high computational cost. However, according to our observation of FFN in Transformer, we found a sparse activation phenomenon, that is, only a small number of neurons were activated for a single input. By mixing experts, the one layer with wider dimensions in the original model is divided into several expert networks with smaller dimensions, which can effectively reduce the number of parameters and achieve the purpose of improving efficiency.

The purpose of this project is to divide the feedforward network (FFN) layer into several experts, each of whom pays attention to a group of neurons that are often activated. We expect this “division of labor” to improve the computational efficiency and performance of our model.

We decided to explore a Transformer model trained on a German-to-English translation dataset, in which Encoder and Decoder have three levels. In the multi-head attention mechanism, the number of heads is set to 4. The dimensions of word embedding and position embedding of the model are both 256. The dimension of the full connection layer is four times that of the word embedding dimension.

Our division expert at the Decoder level. Our research results show that when only half of the experts are used in the decoder layer, the speed is increased by about 20% compared with the original model, and the accuracy loss is about 10%.

 

2 Approaches

The model reasoning acceleration method based on mixed experts was first proposed by Shazeer et al. in 2017. They called this method Sparsely-Gated Mixture-of-Experts Layer and applied it to language modeling tasks. [2]

They split a large-scale language model into several small-scale language models, and use a gating network to dynamically select which small-scale language models to activate. They solve the batch reduction problem by data parallelism and single-step splitting, and solve the equalization problem by adding noise and penalty term of loss function. They trained a language model with 13.7 billion parameters on the 1B word corpus and achieved 23.7% perplexity on the test set

After that, Lepikhin et al. further expanded this method in 2020. They called this method Switch Transformers and applied it to machine translation tasks. [3]

They split a large-scale Transformer model into several small-scale Transformer models, and use a gating network to dynamically select which small-scale Transformer models to activate. They use adaptive gating network and expert pooling techniques to improve the efficiency and flexibility of the model. They trained a machine translation model with 170 billion parameters on WMT ’14 English-German translation task, and achieved a BLEU score of 28.92 on the test set.

Zhang et al. observed that neurons in FFN are only sparsely activated for most inputs, which is similar to the functional partition of human brain. [4] They put forward a hypothesis that there are also functional partitions in FFN, that is, different neurons are responsible for processing different types of inputs. To test this hypothesis, they proposed a method to transform the ordinary Transformer model into MoE version, called MoEfication. Specifically, MoEfication includes two stages: first, divide the parameters of FFN into multiple functional partitions as experts, and then build an expert router to decide which experts to use for each input.

They experimented on different models and downstream tasks, and found that MoEfication can use only 10% to 30% FFN parameters while maintaining more than 95% original performance. In addition, MoEfication brings two advantages. It significantly reduces the FLOPS of reasoning, that is, it can achieve 2 times acceleration by using 25% FFN parameters, and provides a fine-grained perspective to study the internal mechanism of FFN, which enhances the interpretability of the model.

The Transformer model we chose has implemented some basic functions. The model is applied to German-to-English machine translation task, the main goal of which is to translate the input German sentences into English. We use Beam Search strategy, which is a heuristic search strategy. It selects k options with the highest probability at each step (k is the beam width), and then selects k results with the highest probability from these k options in the next step, and so on. This method can solve the problem that greedy search can only get local optimal solution to a certain extent, thus improving the accuracy of translation. For each German sentence, we use Beam Search to find the k most likely English translation results. Then, the BLEU score of each translation result is calculated, and the average BLEU score is output to evaluate the translation quality of the model.

 

Algorithm1  BeamSearch

Input: model, source_sentence, k: integer Output: final_result

1: Convert source_sentence into numerical representation 2: Initialize candidates with the start character id, scores with 0 3: Initialize final_results as empty list 4: While length of final_results < k do: 1: For each candidate in candidates do: 1: If candidate is complete (ends with end token or reaches max length), move it to final_results 2: Else, get next possible tokens from the model, add to the new candidates 2: Select top k candidates from new candidates by their scores 5: Return final results

 

Here is my analysis of the complexity of the Simplified_BeamSearch algorithm. Suppose V is the size of the vocabulary, n is the length of the source sentence, and k is the number of candidates.

Step	Description	Time complexity	Space complexity
1	Convert source_sentence into numerical representation	O(n)	O(n)
2	Initialize candidates with the start character id, scores with 0	O(1)	O(k)
3	Initialize final_results as empty list	O(1)	O(k)
4	While length of final_results < k do	–	–
4.1	For each candidate in candidates do	–	–
4.1.1	If candidate is complete (ends with end token or reaches max length)	O(1)	O(1)
4.1.2	get next possible tokens from the model, add to the new candidates	O(V)	O(V)
4.2	Select top k candidates from new candidates by their scores	O(k log k)	O(1)
5	Return final_results	O(1)	O(1)

Time complexity：The main loop step of the algorithm will run about k times, so the overall time complexity is about O(k * V + k^2 log k).

Space complexity：Because each iteration will generate a new candidate list, the space complexity is O (k + V), where V is the maximum number of candidates that the model can generate at one time. In addition, the final result list also takes up the space of O (k).

 

Firstly, we studied the sparsity of FFN layer and found that most neurons were not activated. We then refer to the MoEfication approach and conditionally use a portion of the FFN parameter to preserve raw performance. Our main work is to construct expert networks, which combine neurons that are usually activated at the same time. We use two methods to construct expert networks: co-activation graph method and cluster splitting method. The former is based on graph partition, while the latter is based on the principle that similar neurons are activated at the same time. Then, we construct a gating network to select experts, and the output of the gating function determines the final output of the MoE model. Finally, we compare the performance of the original model and the hybrid expert acceleration model, and use the mechanism of inter-thread communication to solve the thread insecurity problem of Tkinter.

 

3 Experiments

We use the data set of German-English translation to explore. Transformer model is used for sequence-to-sequence (seq2seq) learning, and the original German and English text data are segmented by Byte Pair Encoding (BPE) algorithm.

Transformer’s encoder and decoder are both set to 3 layers. The number of heads in the multi-head attention mechanism is set to 4. The dimension of word embedding and position embedding is set to 256. The hidden layer dimension in the Feed Forward network is set to 4 times d_model, that is, 1024.

We have done the following work in turn.

 

3.1 Sparsity Verification

At first, we modify forward method in FFN layer, record neurons with negative values, calculate the ratio, and find that about 90% of neurons in Encoder are not activated, and about 80 ~ 90% of neurons in Decoder are not activated.。

We compare the MoEfication papers, and MoEfication can conditionally use 10% ~ 30% FFN parameters while maintaining more than 95% of the original performance, that is, their expert system selects these working neurons (accounting for 10 ~ 30% of the original), and then achieves similar performance.

 

3.2 Constructing expert network

We want to divide a layer of FFN in a Transformer into several experts. The core idea is to combine neurons that are usually activated at the same time. In this way, we can choose a small number of experts to cover all activated neurons as much as possible.

The first is the co-activation graph method. We construct a co-activation graph for each FFN, in which the nodes are neurons and the edge weight is set to the number of times the two neurons are co-activated. Then, we divide the graph into several subgraphs with strong internal connections (Karypis and Kumar, 1998), and regard each subgraph as an expert. [5]

Karypis and Kumar’s approach consists of three phases:

Coarsening stage: Reduce the size of the graph to a manageable level by repeatedly collapsing nodes and edges in the graph.

Partition stage: Some heuristic algorithm (such as spectral partition or Kernighan-Lin algorithm) is used on the coarsest graph to obtain an initial partition.

Thinning phase: Improve partitioning by reverse expanding the graph and using local optimization techniques (such as Kernighan-Lin algorithm or its variants) at each level.

They also propose a new coarsening heuristic algorithm, called double edge heuristic algorithm, which selects the node pairs to be folded according to the weights of edges in the graph. They proved that this heuristic algorithm can guarantee a partition equivalent to the final partition on the coarsest graph.

We use Metis’s open source tools to call their methods. Metis is a popular graph segmentation software package, which implements a graph segmentation algorithm based on multi-level partition scheme. Metis can handle large-scale graphs well, and provides a variety of optimization options to adapt to different graphs and application scenarios.

We also use the minimum spanning tree to divide the subgraph. A graph is divided into several sub-graphs or clusters, and the internal connections of these sub-graphs are as strong as possible, while the connections between sub-graphs are as weak as possible. The minimum spanning tree ensures that all nodes are connected together and the total edge weight is minimal. Remove n-1 edges with the greatest weight from this tree, and the graph is divided into n parts.

Fig. 2 Co-activation diagram (heat diagram)

 

We compared two graph partitioning methods for large, dense graphs. We found that Karypis and Kumar’s approach (implemented in METIS), which simplifies the graph before refining it, handles such graphs better than our minimum spanning tree method, which may not balance partition quality and execution efficiency as effectively. In the case of such dense graphs, it may not be able to fully consider the global characteristics of the graph, and the balance between partition quality and execution efficiency may not be as good as the multi-level partitioning method.

 

Fig. 3 Co-activation graph (undirected graph)

 

 

 

Secondly, clustering and splitting method. Based on the mathematical intuition that the results of similar vector operations are similar, we assume that similar neurons will be activated at the same time. Considering the parameter information, the columns of W matrix in FFN are treated as vector sets with doddle dimensions. Then, balanced k-means is applied to this set, and experts are constructed by k clusters. However, our research results show that the division effect is not good, and the internal connection among experts is not strong.

 

 

Fig. 4 Co-activation graph (divided subgraph)

 

3.3 Establish gating network

The output of gate function determines whether the final output of MoE model is the integration of experts or the output of only a few experts, that is, whether MoE model is a dense integration model or a sparse model. The core idea is to use a limited number of experts to provide as many activated neurons as possible. In order to achieve this goal, we first find the best choice on the training data through greedy algorithm (equivalent to constructing the data set first), and then use them to train a shallow network as an expert router, and select x experts based on the hidden layer input. I enter some test samples and record their word vectors and expert tag numbers activated at this layer as tags to construct the data set.

Fig. 5 Gate network architecture

 

 

 

Algorithm2 Transformer with Expert System Acceleration

1. Initialize Transformer model with pre-defined parameters 2. Prepare input data for Encoder and Decoder 3. Initialize Expert System (ExpertModel and ExpertList) 4. Run forward pass of the Transformer model 5. Return the final result

 

 

3.4 Visualization

In the visual interface, for the same test case, I call the original model and mixed experts to speed up the model test, count the time and score, and calculate the speedup ratio. Because the thread of Tkinter is unsafe, it means that Tkinter GUI cannot be updated from a different thread. My solution is to use mechanisms for inter-thread communication, such as queue.Queue, which is thread-safe, so it is safe to put data in one thread and then fetch it in another. Queue the data that needs to be updated in the GUI in the worker thread, and then periodically check the queue in another thread of Tkinter and update it accordingly. This approach avoids updating the GUI directly from different threads, thus avoiding thread safety issues.

Fig. 6  UI

 

 

 

4 Analysis

We test several sets of input data of different sizes to observe their reasoning time and scores.

It can be seen that the hybrid expert acceleration model takes less time for these samples when four of the eight experts are used, although the accuracy will decrease.

First we explore the influence of the number of selected experts on the model.

Table 1 shows the effect of different numbers of experts. Firstly, the hybrid expert model (MoE) is superior to the original model in processing time regardless of the amount of data, especially when the number of experts is 2 or 4, the processing time is the shortest. However, when the number of experts increased to 8, the processing time of the model began to increase, even exceeding the original model. This may be because the complexity of the model increases with the increase of the number of experts, which leads to the increase of processing time.

Secondly, from the perspective of accuracy, the accuracy of the original model is mostly higher than that of the MoE model, but when the number of experts is 4, the accuracy of the MoE model is almost the same as that of the original model. When the number of experts increases to 8, the accuracy of MoE model is consistent with the original model again. This shows that the MoE model can achieve similar accuracy to the original model with proper number of experts.

Table 1:  Number of experts and model performance.

Data	10	15	20	25	30	40	50
Origin-Time	4.00	4.16	4.82	5.50	6.73	7.50	10.71
Origin-Acc	0.21	0.20	0.25	0.24	0.25	0.24	0.27
1MoE-Time	2.67	3.29	4.08	4.72	5.91	6.94	10.85
1MoE-Acc	0.15	0.15	0.15	0.15	0.16	0.14	0.16
2MoE-Time	2.28	2.71	3.15	4.41	5.48	6.61	9.63
2MoE-Acc	0.15	0.16	0.17	0.18	0.18	0.18	0.21
4MoE-Time	2.19	2.82	3.35	4.09	5.15	6.17	9.21
4MoE-Acc	0.20	0.19	0.22	0.22	0.22	0.21	0.25
8MoE-Time	2.68	3.18	4.30	5.23	6.40	7.52	11.48
8MoE-Acc	0.21	0.20	0.25	0.24	0.25	0.24	0.27

 

Fig. 7  Number of experts and model performance

 

 

 

Table 2:  Mixed expert acceleration effect.

 

Sample	1	2	3	4	5	6	7	8	9	10
Origin-Time	4.00	4.16	4.82	5.50	6.73	7.50	10.71	16.74	21.63	30.62
Origin-Accuracy	0.21	0.20	0.25	0.24	0.25	0.24	0.27	0.28	0.27	0.30
MoE-Time	2.19	2.82	3.35	4.09	5.15	6.17	9.21	14.71	19.51	29.78
MoE-Accuracy	0.20	0.19	0.22	0.22	0.21	0.25	0.26	0.25	0.27	0.28

To sum up, an appropriate number of experts (for example, 4) can significantly reduce the processing time of the hybrid expert model while maintaining accuracy. However, too many experts may lead to an increase in processing time, even exceeding the original model. Therefore, choosing the appropriate number of experts is the key to improve the performance of the hybrid expert model.

We then explore the performance of the hybrid expert model with four experts on more samples.

Compared with the original model, the mixed expert model with four experts (MoE) has significant advantages in processing time, and the processing time of MoE model is shorter than that of the original model in both small samples and large samples. For example, for 10 samples, the processing time of MoE model is 2.19, while that of original model is 4.00. For 100 samples, the processing time of MoE model is 29.78, while that of original model is 30.62. This shows that MoE model has a good performance in processing efficiency.

In terms of accuracy, MoE model and the original model performance is similar, and when the number of samples increases, the accuracy of MoE model has improved. For example, for 6 samples, the accuracy of MoE model is 0.25, while that of original model is 0.24; For 10 samples, the accuracy of MoE model is 0.28, and that of original model is 0.30. This shows that MoE model still has room for improvement on the basis of keeping the original accuracy.

To sum up, the hybrid expert model with four experts can greatly reduce the processing time and improve the efficiency of the model while keeping the accuracy similar. In the case of a large number of samples, the accuracy of hybrid expert model tends to improve, showing good scalability and robustness.

5 Conclusion

We use Mixture of expert model to reduce the computational complexity of the model. When only half of the experts are used in the decoder layer, the speed is increased by about 20% compared with the original model, and the accuracy loss is about 10%.

 

References

[1] Vaswani, Ashish, et al. “Attention is all you need.” Advances in neural information processing systems. 2017.

[2]Shazeer, Noam, et al. “Outrageously large neural networks: The sparsely-gated mixture-of-experts layer.” arXiv preprint arXiv:1701.06538 (2017).

[3]Lepikhin, D., Lee, H., Xu, Y., Chen, D., Firat, O., Huang, Y., … & Chen, M. X. (2020). Gshard: Scaling giant models with conditional computation and automatic sharding. arXiv preprint arXiv:2006.16668.

[4] Zhang, Zhengyan, et al. “MoEfication: Transformer Feed-forward Layers are Mixtures of Experts.” arXiv preprint arXiv:2110.01786 (2021).

[5] Karypis, George, and Vipin Kumar. “A fast and high-quality multilevel scheme for partitioning irregular graphs.” SIAM Journal on scientific Computing 20.1 (1998): 359-392.

 

帮助

本程序在菜单的选择上具有一定的强健性，可以识别菜单操作的异常。

登录界面：：

Back（返回）：返回上一级界面

Quit（退出）：终止并退出所有程序

Information（信息）：了解程序开发的一些信息

Help（帮助）：获取程序的使用帮助

Log（登录）：输入用户名密码登录系统，自动判断用户身份（普通用户/管理员用户）

 

管理员界面：：

Security and Setting（安全和设置）：设置管理员的用户名密码，修改普通用户的用户名密码，设置程序语言（汉语/英语）

Data Management（数据操作）：管理学生信息，管理课程信息、管理成绩

普通用户界面：

Security（安全）：修改普通用户的用户名密码

Data Examine（数据查看）：查看学生信息（排序、统计、查询），查看课程信息，查看成绩信息

本程序由刘小龙、王怡正、滕鹏编写，编写过程中参考了一些开源项目的数据结构，使用studentInfo.txt文件储存学生信息（姓名、学号、住址、性别、课程、成绩、绩点、学分），使用bin文件储存账号、密码。

开发中使用bulider模式初始化对象。

建造者模式，将一个复杂对象的构建与它的表示分离， 使得同样的构建过程可以创建不同的表示。用户只需要指定需要建造的类型就可以得到他们，而具体建造的过程和细节就不需要知道了。之所以使用这个，是因为我最初的Student类构造函数参数极多，我想找个偷懒的方法，就在Java中发现Builder模式，于是用来替代多参数构造函数。

设计模式（Design Pattern）是前辈们对代码开发经验的总结，是解决特定问题的一系列套路。它不是语法规定，而是一套用来提高代码可复用性、可维护性、可读性、稳健性以及安全性的解决方案。

1995 年，GoF（Gang of Four，四人组/四人帮）合作出版了《设计模式：可复用面向对象软件的基础》一书，共收录了 23 种设计模式，从此树立了软件设计模式领域的里程碑，人称「GoF设计模式」。（详见http://c.biancheng.net/view/1354.html）

 

 

开发中使用了STL中的“vector”、“map”、“list”等类型。

C++ STL（标准模板库）是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构，如向量、链表、队列、栈。
C++ 标准模板库的核心包括以下三个组件：
容器（Containers） 容器是用来管理某一类对象的集合。C++ 提供了各种不同类型的容器，比如 deque、list、vector、map 等。
算法（Algorithms） 算法作用于容器。它们提供了执行各种操作的方式，包括对容器内容执行初始化、排序、搜索和转换等操作。
迭代器（iterators） 迭代器用于遍历对象集合的元素。这些集合可能是容器，也可能是容器的子集。
这三个组件都带有丰富的预定义函数，帮助我们通过简单的方式处理复杂的任务。

vector（容器）

vector::vector
vector::~vector
member functions:
vector::assign
vector::at
vector::back
vector::begin
vector::capacity
vector::cbegin
vector::cend
vector::clear
vector::crbegin
vector::crend
vector::data
vector::emplace
vector::emplace_back
vector::empty
vector::end
vector::erase
vector::front
vector::get_allocator
vector::insert
vector::max_size
vector::operator=
vector::operator[]
vector::pop_back
vector::push_back
vector::rbegin
vector::rend
vector::reserve
vector::resize
vector::shrink_to_fit
vector::size
vector::swap
non-member overloads:
relational operators (vector)
swap (vector)

1.构造函数
vector():创建一个空vector
vector(int nSize):创建一个vector,元素个数为nSize
vector(int nSize,const t& t):创建一个vector，元素个数为nSize,且值均为t
vector(const vector&):复制构造函数
vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中
2.增加函数
void push_back(const T& x):向量尾部增加一个元素X
iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x
iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x
iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据
3.删除函数
iterator erase(iterator it):删除向量中迭代器指向元素
iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
void pop_back():删除向量中最后一个元素
void clear():清空向量中所有元素
4.遍历函数
reference at(int pos):返回pos位置元素的引用
reference front():返回首元素的引用
reference back():返回尾元素的引用
iterator begin():返回向量头指针，指向第一个元素
iterator end():返回向量尾指针，指向向量最后一个元素的下一个位置
reverse_iterator rbegin():反向迭代器，指向最后一个元素
reverse_iterator rend():反向迭代器，指向第一个元素之前的位置
5.判断函数
bool empty() const:判断向量是否为空，若为空，则向量中无元素
6.大小函数
int size() const:返回向量中元素的个数
int capacity() const:返回当前向量所能容纳的最大元素值
int max_size() const:返回最大可允许的vector元素数量值
7.其他函数
void swap(vector&):交换两个同类型向量的数据
void assign(int n,const T& x):设置向量中前n个元素的值为x
void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量元素
总结
1.push_back 在数组的最后添加一个数据
2.pop_back 去掉数组的最后一个数据
3.at 得到编号位置的数据
4.begin 得到数组头的指针
5.end 得到数组的最后一个单元+1的指针
6．front 得到数组头的引用
7.back 得到数组的最后一个单元的引用
8.max_size 得到vector最大可以是多大
9.capacity 当前vector分配的大小
10.size 当前使用数据的大小
11.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
12.reserve 改变当前vecotr所分配空间的大小
13.erase 删除指针指向的数据项
14.clear 清空当前的vector
15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty 判断vector是否为空
18.swap 与另一个vector交换数据

 

map（关联容器）

map 容器是关联容器的一种。在关联容器中，对象的位置取决于和它关联的键的值。键可以是基本类型，也可以是类类型。字符串经常被用来作为键，如果想要保存姓名和地址的记录，就可以这么使用。名称通常可能是一个或多个字符串。关联容器中的对象位置的确定取决于容器中的键的类型，而且对于特定容器类型的内部组织方式，不同的 STL 有不同的实现。

map<K，T> 类模板定义在 map 文件头中，它定义了一个保存 T 类型对象的 map，每个 T 类型的对象都有一个关联的 K 类型的键。容器内对象的位置是通过比较键决定的。可以用适当的键值从 map 容器中检索对象。

map::map
map::~map
member functions:
map::at
map::begin
map::cbegin
map::cend
map::clear
map::count
map::crbegin
map::crend
map::emplace
map::emplace_hint
map::empty
map::end
map::equal_range
map::erase
map::find
map::get_allocator
map::insert
map::key_comp
map::lower_bound
map::max_size
map::operator=
map::operator[]
map::rbegin
map::rend
map::size
map::swap
map::upper_bound
map::value_comp
non-member overloads:
relational operators (map)
swap (map)

 

list（链表）

list::list
list::~list
member functions:
list::assign
list::back
list::begin
list::cbegin
list::cend
list::clear
list::crbegin
list::crend
list::emplace
list::emplace_back
list::emplace_front
list::empty
list::end
list::erase
list::front
list::get_allocator
list::insert
list::max_size
list::merge
list::operator=
list::pop_back
list::pop_front
list::push_back
list::push_front
list::rbegin
list::remove
list::remove_if
list::rend
list::resize
list::reverse
list::size
list::sort
list::splice
list::swap
list::unique
non-member overloads:
relational operators (list)
swap (list)

1.list中的构造函数：

list() 声明一个空列表；

list(n) 声明一个有n个元素的列表，每个元素都是由其默认构造函数T()构造出来的

list(n,val) 声明一个由n个元素的列表，每个元素都是由其复制构造函数T(val)得来的

list(n,val) 声明一个和上面一样的列表

list(first,last) 声明一个列表，其元素的初始值来源于由区间所指定的序列中的元素

2. begin()和end()：通过调用list容器的成员函数begin()得到一个指向容器起始位置的iterator，可以调用list容器的 end() 函数来得到list末端下一位置，相当于：int a[n]中的第n+1个位置a[n]，实际上是不存在的，不能访问，经常作为循环结束判断结束条件使用。

3. push_back() 和push_front()：使用list的成员函数push_back和push_front插入一个元素到list中。其中push_back()从list的末端插入，而 push_front()实现的从list的头部插入。

4. empty()：利用empty() 判断list是否为空。

5. resize()： 如果调用resize(n)将list的长度改为只容纳n个元素，超出的元素将被删除，如果需要扩展那么调用默认构造函数T()将元素加到list末端。如果调用resize(n,val)，则扩展元素要调用构造函数T(val)函数进行元素构造，其余部分相同。

6. clear()： 清空list中的所有元素。

7. front()和back()： 通过front()可以获得list容器中的头部元素，通过back()可以获得list容器的最后一个元素。但是有一点要注意，就是list中元素是空的时候，这时候调用front()和back()会发生什么呢？实际上会发生不能正常读取数据的情况，但是这并不报错，那我们编程序时就要注意了，个人觉得在使用之前最好先调用empty()函数判断list是否为空。

8. pop_back和pop_front()：通过删除最后一个元素，通过pop_front()删除第一个元素；序列必须不为空，如果当list为空的时候调用pop_back()和pop_front()会使程序崩掉。

9. assign()：具体和vector中的操作类似，也是有两种情况，第一种是：l1.assign(n,val)将 l1中元素变为n个T(val）。第二种情况是：l1.assign(l2.begin(),l2.end())将l2中的从l2.begin()到l2.end()之间的数值赋值给l1。

10. swap()：交换两个链表(两个重载)，一个是l1.swap(l2); 另外一个是swap(l1,l2)，都可能完成连个链表的交换。

11. reverse()：通过reverse()完成list的逆置。

12. merge()：合并两个链表并使之默认升序(也可改)，l1.merge(l2，greater<int>()); 调用结束后l2变为空，l1中元素包含原来l1 和 l2中的元素，并且排好序，升序。其实默认是升序，greater<int>()可以省略，另外greater<int>()是可以变的，也可以不按升序排列。

迭代器：

要访问顺序容器和关联容器中的元素，需要通过“迭代器（iterator）”进行。迭代器是一个变量，相当于容器和操纵容器的算法之间的中介。迭代器可以指向容器中的某个元素，通过迭代器就可以读写它指向的元素。从这一点上看，迭代器和指针类似。

迭代器按照定义方式分成以下四种。

1) 正向迭代器，定义方法如下：
容器类名::iterator 迭代器名;

2) 常量正向迭代器，定义方法如下：
容器类名::const_iterator 迭代器名;

3) 反向迭代器，定义方法如下：
容器类名::reverse_iterator 迭代器名;

4) 常量反向迭代器，定义方法如下：
容器类名::const_reverse_iterator 迭代器名;
迭代器用法示例

通过迭代器可以读取它指向的元素，*迭代器名就表示迭代器指向的元素。通过非常量迭代器还能修改其指向的元素。

迭代器都可以进行++操作。反向迭代器和正向迭代器的区别在于：
对正向迭代器进行++操作时，迭代器会指向容器中的后一个元素；
而对反向迭代器进行++操作时，迭代器会指向容器中的前一个元素。

 

sort(first_pointer,first_pointer+n,cmp)

该函数可以给数组，或者链表list、向量排序。

实现原理：sort并不是简单的快速排序，它对普通的快速排序进行了优化，此外，它还结合了插入排序和推排序。系统会根据你的数据形式和数据量自动选择合适的排序方法，这并不是说它每次排序只选择一种方法，它是在一次完整排序中不同的情况选用不同方法，比如给一个数据量较大的数组排序，开始采用快速排序，分段递归，分段之后每一段的数据量达到一个较小值后它就不继续往下递归，而是选择插入排序，如果递归的太深，他会选择推排序。

此函数有3个参数：

参数1：第一个参数是数组的首地址，一般写上数组名就可以，因为数组名是一个指针常量。

参数2：第二个参数相对较好理解，即首地址加上数组的长度n（代表尾地址的下一地址）。

参数3：默认可以不填，如果不填sort会默认按数组升序排序。也就是1,2,3,4排序。也可以自定义一个排序函数，改排序方式为降序什么的，也就是4,3,2,1这样。

使用此函数需先包含：

#include <algorithm>
并且导出命名空间：

using namespace std;
简单例子：对数组A的0~n-1元素进行升序排序，只要写sort(A,A+n)即可；对于向量V也一样，sort(v.begin(),v.end())即可。

自己编写排序规则函数

例如：
bool compare(int a,int b)
{
return a<b; //升序排列，如果改为return a>b，则为降序

}
sort扩展

sort不只是能像上面那样简单的使用，我们可以对sort进行扩展，关键就在于第三个参数<cmp比较函数>，我们想降序排列，或者说我不是一个简简单单的数组，而是结构体、类怎么办，下面给出一些方法和例子。

方法一：定义比较函数（最常用）
//情况一：数组排列
int A[100];
bool cmp1(int a,int b)//int为数组数据类型
{
return a>b;//降序排列
//return a<b;//默认的升序排列
}
sort(A,A+100,cmp1);

//情况二：结构体排序
Student Stu[100];
bool cmp2(Student a,Student b)
{
return a.id>b.id;//按照学号降序排列
//return a.id<b.id;//按照学号升序排列
}
sort(Stu,Stu+100,cmp2);
注：比较方法也可以放在结构体中或类中定义。

方法二：使用标准库函数

另外，其实我们还可以再懒一点，在标准库中已经有现成的。它在哪呢？答案是functional，我们include进来试试看。functional提供了一堆基于模板的比较函数对象，它们是：equal_to<Type>、not_equal_to<Type>、greater<Type>、greater_equal<Type>、less<Type>、less_equal<Type>。这些东西的用法看名字就知道了。在这里，我么sort要用到的也只是greater和less就足够了，用法如下：

● 升序：sort(begin,end,less<data-type>())

● 降序：sort(begin,end,greater<data-type>())

缺点：也只是实现简单的排序，结构体不适用。

在开发过程中预留了迭代升级的空间。

打算用我最喜欢的音乐记录一下我的成长。回忆逐渐变得奢侈起来，使我不愿回想起过去。我能做的就是以流水账的形式记录一下自己不同阶段喜欢的音乐，当再次听到熟悉的曲调时，也许会进入那段回忆，但也许并不会。

初中时，我常常听着这首《蒙娜丽莎的微笑》。按理说这是一首相当悲伤的歌，但我却十分喜欢。可能是希望自己早点成熟一点，给自己强行贴上“忧郁”的标签，强迫自己压抑自己的情感。

初三时，我开始喜欢听新的歌曲，开始喜欢含有“爱情”元素的歌曲，像是《孤单北半球》《后来》《勇气》，但奇怪的这些好像都算不上是“圆满”的那种情感。

高一时，喜欢这种，非常激昂的《We have returned》。

高二时，有几首音乐对我特别重要。好在学校允许把电子词典带进去，我可以在早晚饭和上下学路上放音乐，毕竟没有什么能陪伴我。

《梦中的婚礼》

《Kiss the rain》，初中的放学铃声，也很优美。

《Secret Garden》，和当时的我特别像。

《something just like this》

让别人帮我买的《Imagine》。I am not the only one.

星期天下午放假，我在走前还能放一放其他歌曲。

《寒蝉鸣泣之时》

高二结束后的暑假，在去学校补习的时候，我常在路上听《克罗地亚狂想曲》，并时常幻想自己的大学。

《Halley’s comet》”Any life on worlds of that far-off future should be safe but they would be treated to an amazing billion-year-long light show, a dance of a half a trillion stars to music first heard on one little world by a man who had but one true friend “（几千亿颗恒星的舞蹈，以及一位伟人和他的挚友所共同谱写的精彩乐章）

高三时，每天5:40前能到学校。

《canon》。两条轨迹开始交织，但却最终分离。

《童年记忆》

《C418》Minecraft，2013年开始的故事，至今还在继续。

《Secret Base》

《恋爱循环》

《Doraemon》我一直在强迫自己“成熟”，可是却从来没有长大。

《Gettysburgg》第一篇能背过的英语演讲，不仅因为文采斐然，更是因为我想成为像林肯（《林肯传》中塑造的那样）一样高尚的人。

高考之后黯然离场，“没发挥好”、“临时改变做题方式”其实都是逃避真相的借口，只能说确实是没有学到位。高三一年，仿佛我每次抬头看时，天都是灰蒙蒙的，眼前的路仿佛也非常狭窄。我必须承认，长期的营养不良对我的记忆和思维造成了一定的负面影响，那时我是一个素食主义者，不吃蛋奶以外的所有肉制品。我当时看《瓦尔登湖》，梭罗在反驳“不吃肉不能长身体时”说“牛用青草构筑出了庞大的骨架”，我认为十分有道理，加之对肉味比较反感，于是开始吃素。我还记得我特别喜欢去阳台外面，看月亮升起，看太阳落下，看着斑驳的天空中闪出细微的星光；最喜欢的还是有云的时候，我最喜欢看云的变化，无论是从美学的角度还是气象学的角度。

https://www.bilibili.com/video/BV1yf4y167Yi?share_source=copy_web

（我复读时用延时摄影拍的，大概有30多天，但只放上了2020.5.26和2020.6.25两天的。）

在去图书馆逃避现实的路上，我常常听着《樱花樱花想见你》，那段时间还看了《谢谢你用一生陪伴我》，使得我想选择孤独，也想选择陪伴。活在矛盾之中，活在迷茫之中，不知道自己到底该选择什么样的路。

录取结果出来的第二天，我就进入了复读的学校，准备重新开始。

或许当时还有着约定，也或许是心中还有希望，我还是挺喜欢补习生活的，毕竟成绩比较好，老师也较为照顾，生活过的不错，一直坐在后排靠窗的座位——能够经常看着窗外的树和远处的云。还有两次，看到了雨后的五色祥云，云彩混在彩虹之中，美丽，却转瞬即逝——或者是转瞬即逝，但却异常美丽。

《The truth that you leave》或许算得上一语成谶，再次听的时候，他讲的已经是我的故事了。

在上学的路上，我常常放着坂井泉水的《不要认输》，为此一直穿着戴帽子和口袋的衬衣。因为终点就在眼前了，还有人等着我，毕竟，喜欢一个科学家就应该和他考同一所学校——虽然我没有这个水平。

三、四月封闭管理的时候，我听着这两首歌走到教学楼，直到五四之后。

《only my railgun》

《起风了》

在补习的一年，也能逐渐认识到自己才能的平庸。我理科好，当我理综考275的时候，有的人考了299，仅有生物扣了一分；当我数学又错了几道选填和郁闷的统计压轴题，有的人直接满分。无论我怎么努力，他们总是很轻松的高我三十四分。偶尔题目对我非常有利时，却还有十来分的差距——这还是平时考试，我并没有什么心态上的波动。当那年高考时，题目设置对我不利、加之突发的心态波动，当我最终考623排全省4100时，他们是689排全省前100，加上有些人有自主招生的降分，去了清华北大不错的专业，而有的“遗憾的”去了浙江大学。

不管过去如何，也不管命运如何捉弄我，我想我是时候真正的从跌倒处站起来了。躲在真相后面，沉浸在自我幻想建构出的世界舔舐伤口，或许可以宽慰自己，但是，这对于现实无济于事。

序号 代码 含意
1.0×00000000 作业完成。
2.0×00000001 不正确的函数。
3.0×00000002 系统找不到指定的档案。
4.0×00000003 系统找不到指定的路径。
5.0×00000004 系统无法开启档案。
6.0×00000005 拒绝存取。
7.0×00000006 无效的代码。
8.0×00000007 储存体控制区块已毁。
9.0×00000008 储存体空间不足，无法处理这个指令。
10.0×00000009 储存体控制区块地址无效。
11.0x0000000A 环境不正确。
12.0x0000000B 尝试加载一个格式错误的程序。
13.0x0000000C 存取码错误。
14.0x0000000D 资料错误。
15.0x0000000E 储存体空间不够，无法完成这项作业。
16.0x0000000F 系统找不到指定的磁盘驱动器。
17.0×00000010 无法移除目录。
18.0×00000010 无法移除目录。
19.0×00000011 系统无法将档案移到 其它的磁盘驱动器。
20.0×00000012 没有任何档案。
21.0×00000013 储存媒体为写保护状态。
22.0×00000014 系统找不到指定的装置。
23.0×00000015 装置尚未就绪。
24.0×00000016 装置无法识别指令。
25.0×00000017 资料错误 (cyclic redundancy check)
26.0×00000018 程序发出一个长度错误的指令。
27.0×00000019 磁盘驱动器在磁盘找不到 持定的扇区或磁道。
28.0x0000001A 指定的磁盘或磁盘无法存取。
29.0x0000001B 磁盘驱动器找不到要求的扇区。
30.0x0000001C 打印机没有纸。
31.0x0000001D 系统无法将资料写入指定的磁盘驱动器。
32.0x0000001E 系统无法读取指定的装置。
33.0x0000001F 连接到系统的某个装置没有作用。
34.0×00000020 文件被另一进程使用中不能访问The process cannot access the file because it is being used by another process.
35.0×00000021 档案的一部份被锁定， 现在无法存取。
36.0×00000022 磁盘驱动器的磁盘不正确。
37.0×00000024 开启的分享档案数量太多。
38.0×00000026 到达档案结尾。
39.0×00000027 磁盘已满。
40.0×00000032 不支持这种网络要求。
41.0×00000033 远程计算机无法使用。
42.0×00000034 网络名称重复。
43.0×00000035 网络路径找不到。
44.0×00000036 网络忙碌中。
45.0×00000037 特殊的网络资源或设备不可再使用The specified network resource or device is no longer available.
46.0×00000038 网络BIOS命令已达到限制The network BIOS command limit has been reached.
47.0×00000039 网络配接卡发生问题。
48.0x0000003A 指定的服务器无法执行要求的作业。
49.0x0000003B 网络发生意外错误。
50.0x0000003C 远程配接卡不兼容。
51.0x0000003D 打印机队列已满。
52.0x0000003E 服务器的空间无法储存等候打印的档案。
53.0x0000003F 等候打印的档案已经删除。
54.0×00000040 指定的网络名称无法使用。
55.0×00000041 拒绝存取网络。
56.0×00000041 拒绝存取网络。
57.0×00000042 网络资源类型错误。
58.0×00000043 网络名称找不到。
59.0×00000044 超过区域计算机网络配接卡的名称限制。
60.0×00000045 超过网络 BIOS 作业阶段的限制。
61.0×00000046 远程服务器已经暂停或者正在起始中。
62.0×00000047 由于联机数目已达上限，此时无法再联机到这台远程计算机。
63.0×00000048 指定的打印机或磁盘装置已经暂停作用。
64.0×00000050 档案已经存在。
65.0×00000052 无法建立目录或档案。
66.0×00000053 INT 2484 0x00000054 处理这项要求的储存体无法使用。
67.0×00000055 近端装置名称已经在使用中。
68.0×00000056 指定的网络密码错误。
69.0×00000057 参数错误。
70.0×00000058 网络发生资料写入错误。
71.0×00000059 此时系统无法执行其它行程。
72.0×00000064 无法建立其它的系统 semaphore。
73.0×00000065 属于其它行程专用的 semaphore.
74.0×00000066 semaphore 已经设定，而且无法关闭。
75.0×00000067 无法指定 semaphore 。
76.0×00000068 在岔断时间无法要求专用的 semaphore 。
77.0×00000068 在岔断时间无法要求专用的 semaphore 。
78.0×00000069 此 semaphore 先前的拥有权已经结束。
79.0x0000006A 请将磁盘插入。
80.0x0000006B 因为代用的磁盘尚未插入，所以程序已经停止。
81.0x0000006C 磁盘正在使用中或被锁定。
82.0x0000006D Pipe 已经中止。
83.0x0000006E 系统无法开启指定的 装置或档案。
84.0x0000006F 档名太长。
85.0×00000070 磁盘空间不足。
86.0×00000071 没有可用的内部档案标识符。
87.0×00000072 目标内部档案标识符不正确。
88.0×00000075 由应用程序所执行的 IOCTL 呼叫 不正确。
89.0×00000076 写入验证参数值不正确。
90.0×00000077 系统不支持所要求的指令。
91.0×00000078 此项功能仅在 Win32 模式有效。
92.0×00000079 semaphore 超过逾时期间。
93.0x0000007A 传到系统呼叫的资料区域 太小。
94.0x0000007B 文件名、目录名称或储存体卷标语法错误。
95.0x0000007C 系统呼叫层次不正确。
96.0x0000007D 磁盘没有设定卷标。
97.0x0000007E 找不到指定的模块。
98.0x0000007F 找不到指定的程序。
99.0×00000080 没有子行程可供等待。
100.0×00000080 没有子行程可供等待。
101.0×00000081 这个应用程序无法在 Win32 模式下执行。
102.0×00000082 Attempt to use a file handle to an open disk partition for an operation other than raw disk I/O.
103.0×00000083 尝试将档案指针移至档案开头之前。
104.0×00000084 无法在指定的装置或档案，设定档案指针。
105.0×00000085 JOIN 或 SUBST 指令 无法用于 内含事先结合过的磁盘驱动器。
106.0×00000086 尝试在已经结合的磁盘驱动器，使用 JOIN 或 SUBST 指令。
107.0×00000087 尝试在已经替换的磁盘驱动器，使 用 JOIN 或 SUBST 指令。
108.0×00000088 系统尝试删除 未连结过的磁盘驱动器的连结关系。
109.0x0000008A 系统尝试将磁盘驱动器结合到已经结合过之磁盘驱动器的目录。
110.0x0000008B 系统尝试将磁盘驱动器替换成已经替换过之磁盘驱动器的目录。
111.0x0000008C 系统尝试将磁盘驱动器替换成已经替换过之磁盘驱动器的目录。
112.0×000000 系统尝试将磁盘驱动器 SUBST 成已结合的磁盘驱动器 目录。
113.0x0000008E 系统此刻无法执行 JOIN 或 SUBST。
114.0x0000008F 系统无法将磁盘驱动器结合或替换同一磁盘驱动器下目录。
115.0×00000090 这个目录不是根目录的子目录。
116.0×00000091 目录仍有资料。
117.0×00000092 指定的路径已经被替换过。
118.0×00000093 资源不足，无法处理这项 指令。
119.0×00000094 指定的路径这时候无法使用。
120.0×00000094 指定的路径这时候无法使用。
121.0×00000095 尝试要结合或替换的磁盘驱动器目录，是已经替换过的的目标。
122.0×00000096 CONFIG.SYS 文件未指定系统追踪信息，或是追踪功能被取消。
123.0×00000097 指定的 semaphore事件 DosMux0000SemWait 数目不正确。
124.0×00000098 DosMux0000SemWait 没有执行；设定太多的 semaphore。
125.0×00000099 DosMux0000SemWait 清单不正确。
126.0x0000009A 您所输入的储存媒体标 元长度限制。
127.0x0000009B 无法建立其它的执行绪。
128.0x0000009C 接收行程拒绝接受信号。
129.0x0000009D 区段已经被舍弃，无法被锁定。
130.0x0000009E 区段已经解除锁定。
131.0x0000009F 执行绪识别码的地址不正确。
132.0x000000A0 传到 DosEx0000ecPgm 的自变量字符串不正确。
133.0x000000A1 指定的路径不正确。
134.0x000000A2 信号等候处理。
135.0x000000A4 系统无法建立执行绪。
136.0x000000A7 无法锁定档案的部份范围。
137.0x000000AA 所要求的资源正在使用中。
138.0x000000AD 取消范围的锁定要求不明显。
139.0x000000AE 档案系统不支持自动变更锁定类型。
140.0x000000B4 系统发现不正确的区段号码。
141.0x000000B6 操作系统无法执行。
142.0x000000B6 操作系统无法执行。
143.0x000000B7 档案已存在，无法建立同一档案。
144.0x000000BA 传送的旗号错误。
145.0x000000BB 指定的系统旗号找不到。
146.0x000000BC 操作系统无法执行。
147.0x000000BD 操作系统无法执行。
148.0x000000BE 操作系统无法执行。
149.0x000000BF 无法在 Win32 模式下执行 。
150.0x000000C0 操作系统无法执行。
151.0x000000C1 %1 不是正确的 Win32 应用程序。
152.0x000000C2 操作系统无法执行。
153.0x000000C3 操作系统无法执行。
154.0x000000C4 操作系统无法执行 这个应用程序。
155.0x000000C5 操作系统目前无法执行 这个应用程序。
156.0x000000C6 操作系统无法执行。
157.0x000000C7 操作系统无法执行 这个应用程序。
158.0x000000C8 程序代码的区段不可以大于或等于 64KB。
159.0x000000C9 操作系统无法执行。
160.0x000000CA 操作系统无法执行。
161.0x000000CB 系统找不到输入的环境选项。
162.0x000000CD 在指令子目录下，没有任何行程有信号副处理程序。
163.0x000000CE 文件名称或扩展名太长。
164.0x000000CF ring 2 堆栈使用中。
165.0x000000CF ring 2 堆栈使用中。
166.0x000000D0 输入的通用档名字元 * 或 ? 不正确， 或指定太多的通用档名字元。
167.0x000000D1 所传送的信号不正确。
168.0x000000D2 无法设定信号处理程序。
169.0x000000D4 区段被锁定，而且无法重新配置。
170.0x000000D6 附加到此程序或动态连结模块的动态连结模块太多。
171.0x000000D7 Can’t nest calls to LoadModule.
172.0x000000E6 The pipe state is invalid.
173.0x000000E7 所有的 pipe instances 都在忙碌中。
174.0x000000E8 The pipe is being closed.
175.0x000000E9 No process is on the other end of the pipe.
176.0x000000EA 有更多可用的资料。
177.0x000000F0 作业阶段被取消。
178.0x000000FE 指定的延伸属性名称无效。
179.0x000000FF 延伸的属性不一致。
180.0×00000103 没有可用的资料。
181.0x0000010A 无法使用 Copy API。
182.0x0000010B 目录名称错误。
183.0×00000113 延伸属性不适用于缓冲区。
184.0×00000114 在外挂的档案系统上的延伸属性档案已经毁损。
185.0×00000115 延伸属性表格文件满。
186.0×00000116 指定的延伸属性代码无效。
187.0×00000116 指定的延伸属性代码无效。
188.0x0000011A 外挂的这个档案系统不支持延伸属性。
189.0×00000120 意图释放不属于叫用者的 mutex0000。
190.0x0000012A semaphore 传送次数过多。
191.0x0000012B 只完成 Read/WriteProcessMemory 的部份要求。
192.0x0000013D 系统找不到位于讯息文件中编号为 0x000的讯息。
193.0x000001E7 尝试存取无效的地址。
194.0×00000216 运算结果超过 32 位。
195.0×00000217 信道的另一端有一个行程在接送资料。
196.0×00000218 等候行程来开启信道的另一端。
197.0x000003E2 存取延伸的属性被拒。
198.0x000003E3 由于执行绪结束或应用程序要求，而异常终止 I/O 作业。
199.0x000003E4 重叠的 I/O 事件不是设定成通知状态。
200.0x000003E5 正在处理重叠的 I/O 作业。
201.0x000003E6 对内存位置的无效存取。
202.0x000003E7 执行 inpage 作业发生错误。
203.0x000003E9 递归太深，堆栈满溢。
204.0x000003EA 窗口无法用来传送讯息。
205.0x000003EB 无法完成这项功能。
206.0x000003EC 旗号无效。
207.0x000003ED 储存媒体未含任何可辨识的档案系统。 请确定以加载所需的系统驱动程序，而且该储存媒体并未毁损。
208.0x000003EE 储存该档案的外部媒体发出警告，表示该已开启档案已经无效。
209.0x000003EF 所要求的作业无法在全屏幕模式下执行。
210.0x000003F0 An attempt was made to reference a token that does not ex0000ist.
211.0x000003F1 组态系统登录数据库毁损。
212.0x000003F2 组态系统登录机码无效。
213.0x000003F3 无法开启组态系统登录机码。
214.0x000003F4 无法读取组态系统登录机码。
215.0x000003F5 无法写入组态系统登录机码。
216.0x000003F6 系统登录数据库中的一个档案必须使用记录或其它备份还原。 已经还原成功。
217.0x000003F7 系统登录毁损。其中某个档案毁损、或者该档案的 系统映对内存内容毁损、会是档案无法复原。
218.0x000003F8 系统登录起始的 I/O 作业发生无法复原的错误。 系统登录无法读入、写出或更新，其中的一个档案 内含系统登录在内存中的内容。
219.0x000003F9 系统尝试将档案加载系统登录或将档案还原到系统登录中，但是，指定档案的格式不是系统登录文件的格式。
220.0x000003FA 尝试在标示为删除的系统登录机码，执行不合法的操作。
221.0x000003FA 尝试在标示为删除的系统登录机码，执行不合法的操作。
222.0x000003FB 系统无法配置系统登录记录所需的空间。
223.0x000003FC 无法在已经有子机码或数值的系统登录机码建立符号连结。
224.0x000003FD 无法在临时机码下建立永久的子机码。
225.0x000003FE 变更要求的通知完成，但信息 并未透过呼叫者的缓冲区传回。呼叫者现在需要自行列举档案，找出变更的地方。
226.0x0000041B 停止控制已经传送给其它服务 所依峙的一个服务。
227.0x0000041C 要求的控制对此服务无效
228.0x000003F8 系统登录起始的 I/O 作业发生无法复原的错误。 系统登录无法读入、写出或更新，其中的一个档案 内含系统登录在内存中的内容。
229.0x000003F9 系统尝试将档案加载系统登录或将档案还原到系统登录中，但是，指定档案的格式不是系统登录文件的格式。
230.0x000003FA 尝试在标示为删除的系统登录机码，执行不合法的操作。
231.0x000003FA 尝试在标示为删除的系统登录机码，执行不合法的操作。
232.0x000003FB 系统无法配置系统登录记录所需的空间。
233.0x000003FC 无法在已经有子机码或数值的系统登录机码建立符号连结。
234.0x000003FD 无法在临时机码下建立永久的子机码。
235.0x000003FE 变更要求的通知完成，但信息 并未透过呼叫者的缓冲区传回。呼叫者现在需要自行列举档案，找出变更的地方。
236.0x0000041B 停止控制已经传送给其它服务 所依峙的一个服务。
237.0x0000041C 要求的控制对此服务无效
238.0x0000041C 要求的控制对此服务无效
239.0x0000041D The service did not respond to the start or control request in a timely fashion. 0x0000041E 无法建立服务的执行绪。
240.0x0000041F 服务数据库被锁定。
241.0×00000420 这种服务已经在执行。
242.0×00000421 帐户名称错误或者不存在。
243.0×00000422 指定的服务暂停作用，无法激活。
244.0×00000423 指定循环服务从属关系。
245.0×00000424 指定的服务不是安装进来的服务。
246.0×00000425 该服务项目此时无法接收控制讯息。
247.0×00000426 服务尚未激活。
248.0×00000427 无法联机到服务控制程序。
249.0×00000428 处理控制要求时，发生意外状况。
250.0×00000429 指定的数据库不存在。
251.0x0000042A 服务传回专属于服务的错误码。
252.0x0000042B The process terminated unex0000pectedly.
253.0x0000042C 从属服务或群组无法激活。
254.0x0000042D 因为登入失败，所以没有激活服务。
255.0x0000042E 在激活之后，服务在激活状态时当机。
256.0x0000042F 指定服务数据库锁定无效。
257.0×00000430 指定的服务已经标示为删除。
258.0×00000431 指定的服务已经存在。
259.0×00000432 系统目前正以上一次执行成功的组态执行。
260.0×00000433 从属服务不存在，或已经标示为删除。
261.0×00000434 目前的激活已经接受上一次执行成功的 控制设定。
262.0×00000435 上一次激活之后，就没有再激活服务。
263.0×00000436 指定的名称已经用于服务名称或服务显示 名称。
264.0x0000044C 已经到了磁带的最后。
265.0x0000044D 到了档案标示。
266.0x0000044E 遇到磁带的开头或分割区。
267.0x0000044C 已经到了磁带的最后。
268.0x0000044D 到了档案标示。
269.0x0000044E 遇到磁带的开头或分割区。
270.0x0000044F 到了档案组的结尾。
271.0×00000450 磁带没有任何资料。
272.0×00000451 磁带无法制作分割区。
273.0×00000452 存取多重容体的新磁带时，发现目前 区块大小错误。
274.0×00000453 加载磁带时，找不到磁带分割区信息。
275.0×00000454 无法锁住储存媒体退带功能。
276.0×00000454 无法锁住储存媒体退带功能。
277.0×00000455 无法解除加载储存媒体。
278.0×00000456 磁盘驱动器中的储存媒体已经变更。
279.0×00000457 已经重设 I/O 总线。
280.0×00000458 磁盘驱动器没有任何储存媒体。
281.0×00000459 目标 multi-byte code page，没有对应 Unicode 字符。
282.0x0000045A 动态链接库 (DLL) 起始例程失败。
283.0x0000045B 系统正在关机。
284.0x0000045C 无法中止系统关机，因为没有关机的动作在进行中。
285.0x0000045D 因为 I/O 装置发生错误，所以无法执行要求。
286.0x0000045E 序列装置起始失败，会取消加载序列驱动程序。
287.0x0000045F 无法开启装置。这个装置与其它装置共享岔断要求 (IRQ)。至少已经有一个使用同一IRQ 的其它装置已经开启。
288.0×00000460 A serial I/O operation was completed by another write to the serial port(The IOCTL_SERIAL_x0000OFF_COUNTER reached zero.)
289.0×00000461 因为已经过了逾时时间，所以序列 I/O 作业完成。
290.(IOCTL_SERIAL_x0000OFF_COUNTER 不是零。)
291.0×00000462 在磁盘找不到任何的 ID 地址标示。
292.0×00000463 磁盘扇区 ID 字段与磁盘控制卡追踪地址 不符。
293.0×00000464 软式磁盘驱动器控制卡回报了一个软式磁盘驱动器驱动程序无法识别的错误。
294.0×00000465 软式磁盘驱动器控制卡传回与缓存器中不一致的结果。
295.0×00000466 存取硬盘失败，重试后也无法作业。
296.0×00000467 存取硬盘失败，重试后也无法作业。
297.0×00000468 存取硬盘时，必须重设磁盘控制卡，但是 连重设的动作也失败。
298.0×00000469 到了磁带的最后。
299.0x0000046A 可用服务器储存空间不足，无法处理这项指令。
300.0x0000046B 发现潜在的死锁条件。
301.0x0000046C 指定的基本地址或档案位移没有适当 对齐。
302.0×00000474 尝试变更系统电源状态，但其它的应用程序或驱动程序拒绝。
303.0×00000475 系统 BIOS 无法变更系统电源状态。
304.0x0000047E 指定的程序需要新的 Windows 版本。
305.0x0000047F 指定的程序不是 Windows 或 MS-DOS 程序。
306.0×00000480 指定的程序已经激活，无法再激活一次。
307.0×00000481 指定的程序是为旧版的 Windows 所写的。
308.0×00000482 执行此应用程序所需的链接库档案之一毁损。
309.0×00000483 没有应用程序与此项作业的指定档案建立关联。
310.0×00000484 传送指令到应用程序发生错误。
311.0×00000485 找不到执行此应用程序所需的链接库档案。
312.0x000004B0 指定的装置名称无效。
313.0x000004B1 装置现在虽然未联机，但是它是一个记忆联机。
314.0x000004B2 尝试记忆已经记住的装置。
315.0x000004B3 提供的网络路径找不到任何网络提供程序。
316.0x000004B3 提供的网络路径找不到任何网络提供程序。
317.0x000004B4 指定的网络提供程序名称错误。
318.0x000004B5 无法开启网络联机设定文件。
319.0x000004B6 网络联机设定文件坏掉。
320.0x000004B7 无法列举非容器。
321.0x000004B8 发生延伸的错误。
322.0x000004B9 指定的群组名称错误。
323.0x000004BA 指定的计算机名称错误。
324.0x000004BB 指定的事件名称错误。
325.0x000004BC 指定的网络名称错误。
326.0x000004BD 指定的服务名称错误。
327.0x000004BE 指定的网络名称错误。
328.0x000004BF 指定的资源共享名称错误。
329.0x000004C0 指定的密码错误。
330.0x000004C1 指定的讯息名称错误。
331.0x000004C2 指定的讯息目的地错误。
332.0x000004C3 所提供的条件与现有的条件组发生冲突。
333.0x000004C4 尝试与网络服务器联机，但是 与该服务器的联机已经太多。
334.0x000004C5 其它网络计算机已经在使用这个工作群组或网域名称。

Last Diary

目覚めた部屋は
醒来了的房间

色もなくて
毫无色彩

心の声さえ
连心的声音

砕けて溶けていく
也破碎、融化了

めくればこぼれる
想藏起来的话会溢出的

記憶ごと
如果能连记忆一起

捨てられたらと
丢弃的话

一秒ごとに
每一秒

祈り続けてた
都在祈祷着

だけどほら
但是你看

君がくれた
用你给我的

この光を
这份光芒

空白のページ
将空白的书页

開いて
打开

綴り出せば
装订的话

途切れていた
戛然而止的

止まっていた
停止的

日々が
日常

輝くよな想い出に
将闪耀的回忆

埋められていくの
都不断掩埋

忘れないよ
不会忘记的

覚えてるよ
我会记得的

この瞬間を
这个瞬间

終わりに
结束时

残す言葉は
留下的话语

「また会おうね」
「下次再见」

ふたりの約束
两人的约定

過ごした部屋で
在一起生活过的房间

肩寄せ合い
肩靠着肩

読み返していた
反复读着

ふたりのストーリー
两人的故事

明けていく夜に
在黎明前

想い出を重ね合わせて
将回忆重合

心の余白
把心中的空白

そっと埋めていく
悄悄地埋藏

伝えたい気持ち
将想向你诉说的心情

空へ
向天空

解き放てば
倾诉的话

夢のよな時間
梦幻的时间

朝陽で霞んでくよ
在朝阳中模糊吧

君の横で笑っていた日々は
睡在你身旁欢笑的日子

モノクロだった世界を
将毫无色彩的世界

あざやかに染めた
染上鲜艳的颜色

忘れないよ
不会忘记的

覚えてるよ
我会记得的

あの瞬間を
这个瞬间

未来へ
向未来

託す言葉は
许下的话语

「また会おうね」
「再见」

ふたりの約束
两人的约定

この時間戻せなくても
即使不能回到这个时间

目を閉じれば
闭上眼睛

よみがえるよ
就能到达哦

綴った記憶
编缀的记忆

なにもかも
一切都

途切れていた
戛然而止的

止まっていた
停止了

日々を
日常

輝くよな想い出で
将闪耀的回忆

彩っていこう
染上色彩吧

忘れないよ
不会忘记的

覚えてるよ
我会记得的

この瞬間を
这个瞬间

終わりのページ開けば
将结束的书页打开

君とふたり
与你一起

あの日誓った
那天许下了

「また会おうね」
「再见」

そんな約束
这样的诺言

首先准备在电脑上安装CentOS7。

使用u盘制作启动盘。推荐使用100%开源且免费的ventoy（https://www.ventoy.net/cn/download.html），可以同时启动多个镜像。

接下来配置Linux系统。这里以清华大学软件镜像站的CentOS7系统为例。https://mirrors.tuna.tsinghua.edu.cn/centos/7.9.2009/isos/x86_64/CentOS-7-x86_64-Everything-2009.iso（完全安装包，约9G）。在得当的下载工具（如Free Download Manager）下，约15分钟下完镜像文件。

两个文件也可以在链接：https://pan.baidu.com/s/1UpScYIOrUMBSm3RW3ljrwQ 提取码：unix 中查找。

进入笔记本BIOS设置，设置以USBdivice启动。

进入Ventoy界面，选择CentOS7安装。安装源（I）默认为本地介质，无需更改。在软件选择（S）中选择配置。由于是完全安装包，可以配置图形界面。接下来配置网络选项。点击开始安装（B），进入用户设置界面，配置root密码和创建用户（可选）。随后等待安装glibc的进度条读完。

安装结束后重启进入GRUB界面，进入CentOS7系统。

Linux进入后默认为图形界面（非最小化安装），按Alt+Ctrl+（Fn）+F2进入命令行界面。按Alt+Ctrl+（Fn）+F3/F4/F5/F6进入其他命令行界面。按Alt+Ctrl+（Fn）+F1回到图形界面。

随后登录之前设置的账户。

在操作前检测编译器情况。安装正常的情况下，输入命令gcc -v，会返回编译器的信息，表明已经存在有gcc编译器。输入命令make -v，返回make版本的信息。

接下来可以在命令行模式编写C语言程序，（当然图形界面也可以编写，还更简单）。

 

在此之前了解Linux的几个相关命令。

一、创建文件夹

1、创建本目录下文件夹

mkdir dir

2、创建其他目录下文件夹

mkdir dir/file

3、创建多级目录文件夹

mkdir -p tmp/dir

4、创建file.txt文件

mkdir dir/file.txt

二、修改文件夹名

1、文件夹重命名

mv dir dir1

2、文件重命名

mv dir/file.txt dir/files.txt

三、查看文件夹/文件

cd dir

cd dir/dir1

回到主目录 cd  ~

4、查看目录下内容 ll （或者ls）

返回上一级 cd  ..

cd dir/dir1/dir2

四、删除文件夹/文件

删除本目录下文件夹及文件

rm -rf dir1  （强制删除，不提示）

强制删除文件，不提示

rm -f file

递归删除其文件和文件夹

rm -r dir

 

首先新建文件夹。输入命令mkdir ctest及cd ctest/进入文件夹，输入ls查看文件夹。

接下来了解vi的一些操作。

1、vi的基本概念
基本上vi可以分为三种状态，分别是命令模式（command mode）、插入模式（Insert mode）和底行模式（last line mode），各模式的功能区分如下：

1) 命令行模式command mode）

控制屏幕光标的移动，字符、字或行的删除，移动复制某区段及进入Insert mode下，或者到 last line mode。

2) 插入模式（Insert mode）

只有在Insert mode下，才可以做文字输入，按「ESC」键可回到命令行模式。

3) 底行模式（last line mode）

将文件保存或退出vi，也可以设置编辑环境，如寻找字符串、列出行号……等。

2、vi的基本操作
a) 进入vi

在系统提示符号输入vi及文件名称后，就进入vi全屏幕编辑画面：

$ vi myfile

进入vi之后处于「命令行模式（command mode）」，要切换到「插入模式（Insert mode）」才能够输入文字、编辑文件。

在「命令行模式（command mode）」下按一下字母「i」就可以进入「插入模式（Insert mode）」，这时候你就可以开始输入文字了。

b) Insert 的切换

处于「插入模式（Insert mode）」，只能一直输入文字，如果输错了字，想用光标键往回移动，将该字删除，就b要先按一下「ESC」键转到「命令行模式（command modce）」再删除文字。

c) 退出vi及保存文件

在「命令行模式（command mode）」下，按一下「：」冒号键进入「Last line mode」，例如：

: w filename （输入 「w filename」将文章以指定的文件名filename保存）

: wq (输入「wq」，存盘并退出vi)

: q! (输入q!， 不存盘强制退出vi)

3、命令行模式（command mode）功能键
1）插入模式

按「i」切换进入插入模式「insert mode」，按“i”进入插入模式后是从光标当前位置开始输入文件；

按「a」进入插入模式后，是从目前光标所在位置的下一个位置开始输入文字；

按「o」进入插入模式后，是插入新的一行，从行首开始输入文字。

2）从插入模式切换为命令行模式

按「ESC」键。

3）移动光标

vi可以直接用键盘上的光标来上下左右移动，但正规的vi是用小写英文字母「h」、「j」、「k」、「l」，分别控制光标左、下、上、右移一格。

 

其次新建文件。输入命令vi testhello.c创建并打开文件。进入插入模式，输入代码

#include <stdio.h>

int main()

{printf(“hello world!”);

return 0;}

按esc退出插入模式，按“:”“wq”存盘保存。

 

输入ls查看当前文件夹下的文档，发现有testhello.c。

输入命令gcc -E testhello.c -o testhello.i预编译。

输入ls查看当前文件夹下的文档，发现有testhello.c和testhello.i两个。

输入命令gcc -S testhello.i -o testhello.s编译。

输入ls查看当前文件夹下的文档，发现有testhello.c、testhello.i和testhello.s三个。

输入命令gcc -c testhello.s -o testhello.o汇编。

此时可以通过objdump -d testhello.o反汇编来查看该文件。

输入命令gcc testhello.o -o testhello链接。

输入命令./testhello执行程序，输出hello world！。

 

 

That’s here.That’s home.That’s us.On it, everyone you love,everyone you know,everyone you ever heard of,every human being who ever was,lived out their lives.The aggregate of our joy and suffering,thousands of confident religions, ideologies,and economic doctrines,every hunter and forager,every hero and coward,every creator and destroyer of civilization,every king and peasant,every young couple in love,every mother and father,hopeful child,inventor and explorer,every teacher of morals,every corrupt politician,every superstar,every supreme leader,every saint and sinner in the history of our species,lived there…on a mote of dust,suspended… in a sunbeam.

The Earth is a very small stage in a vast, cosmic arena.Think of the rivers of blood,spilled by all those generals and emperors,so that in glory and triumph.they could become the momentary master of a fraction… of a dot.Think of the endless cruelties visited by the inhabitants of one corner of this pixel on the scarcely distinguishable inhabitants of some other corner.How frequent their misunderstandings,how eager they are to kill one another,how fervent their hatreds.Our posturings,our imagined self-importance,the delusion that we have some privileged position in the universe,are challenged by this point of pale light.Our planet…is a lonely speck in the great,enveloping cosmic dark.

In our obscurity,in all this vastness,there is no hint that help will come from elsewhere,to save us from ourselves.The Earth is the only world known so far to harbor life.There is nowhere else,at least in the near future,to which our species could migrate.Visit, yes.Settle, not yet.Like it or not,for the moment, the Earth is where we make our stand.It has been said that astronomy is a humbling and character-building experience.There is perhaps no better demonstration of the folly of human conceits than this distant image.To me, it underscores our responsibility to deal more kindly with one another and to preserve and cherish the pale blue dot,the only home we’ve ever known.

How did we,tiny creatures living on that speck of dust,ever manage to figure out how to send spacecraft out among the stars of the Milky Way?Only a few centuries ago,a mere second of cosmic time,we knew nothing of where or when we were.Oblivious to the rest of the cosmos,we inhabited a kind of prison–a tiny universe bounded by a nutshell.How did we escape from the prison?It was the work of generations of searchers who took five simple rules to heart.

Question authority.No idea is true just because someone says so,including me.Think for yourself.Question yourself.Don’t believe anything just because you want to.Believing something doesn’t make it so.Test ideas by the evidence gained from observation and experiment.If a favorite idea fails a well-designed test,it’s wrong!Get over it.Follow the evidence,wherever it leads.If you have no evidence,reserve judgment.And perhaps the most important rule of all…Remember, you could be wrong.Even the best scientists have been wrong about some things.Newton, Einstein,and every other great scientist in history,they all made mistakes.Of course they did–they were human.Science is a way to keep from fooling ourselves and each other.Have scientists known sin?Of coursWe have misused science,just as we have every other tool at our disposal,and that’s why we can’t afford to leave it in the hands of a powerful few.The more science belongs to all of us,the less likely it is to be misused.These values undermine the appeals of fanaticism and ignorance,and, after all,the universe is mostly dark.dotted by islands of light.

Learning the age of the Earth or the distance to the stars,or how life evolves–what difference does that make?Well, part of it depends on how big a universe you’re willing to live in.Some of us like it small.That’s fine.Understandable.But I like it big.And when I take all of this into my heart and my mind,I’m uplifted by it.And when I have that feeling,I want to know that it’s real,that it’s not just something happening inside my own head,because it matters what’s true,and our imagination is nothing compared with Nature’s awesome reality.

I want to know what’s in those dark places,and what happened before the Big Bang.I want to know what lies beyond the cosmic horizon,and how life began.Are there other places in the cosmos where matter and energy have become alive and aware?I want to know my ancestors–all of them.I want to be a good, strong linkin the chain of generations.I want to protect my children and the children of ages to come.

We, who embody the local eyes and ears and thoughts and feelings of the cosmos,we’ve begun to learn the story of our origins-star stuff contemplating the evolution of matter,tracing that long path by which it arrived at consciousness.We and the other living things on this planet carry a legacy of cosmic evolution spanning billions of years.if we take that knowledge to heart,if we come to know and love nature as it really is,then we will surely be remembered by our descendants as good, strong links in the chain of life.And our children will continue this sacred searching,seeing for us as we have seen for those who came before,discovering wonders yet undreamt of…in the cosmos.