XIAOSUO 记录个人学习的足迹

摘要：泛型缓存字典是通过静态构造函数只被执行一次的调用机制，在首次执行时存好值，后面不再计算直接调用，以达到缓存下效果。 静态构造函数：静态构造函数用于初始化任何静态数据，或执行仅需执行一次的特定操作。 将在创建第一个实例或引用任何静态成员之前自动调用静态构造函数。 说人话就是：只有该类第一次被调用时执行一次静态构造函数，该类后面再继续被调用时都不会再去执行静态构造函数。（跟踪调试发现确实这样，编译器能识别） public class GenericCacheTest { public static void Show() { for (int i = 0; i 5; i++) { Console.WriteLine(GenericCacheint.GetCache()); Thread.Sleep(10); Console.WriteLine(GenericCachelong.GetCache()); Thread.Sleep(10); Console.WriteLine(GenericCacheDateTime.GetCache()); Thread.Sleep(10); Console.WriteLine(GenericCachestring.GetCache()); Thread.Sleep(10); Console.WriteLine(GenericCacheGenericCacheTest.GetCache()); Thread.Sleep(10); } } } /// summary /// 字典缓存： /// 原理：静态属性常驻内存，是key-value的hash存储，每次调用时需要去内存器查找要进行哈希运算 /// /summary public class DictionaryCache { private static DictionaryType, string _TypeTimeDictionary = null; static DictionaryCache()//静态构造函数 { Console.WriteLine(This is DictionaryCache 静态构造函数); _TypeTimeDictionary = new Dictio…… 阅读全文

摘要：内容导读 概述 当你声明一个变量背后发生了什么？ 堆和栈 值类型和引用类型 哪些是值类型，哪些是引用类型？ 装箱和拆箱 装箱和拆箱的性能问题 一、概述 　　本文会阐述六个重要的概念：堆、栈、值类型、引用类型、装箱和拆箱。本文首先会通过阐述当你定义一个变量之后系统内部发生的改变开始讲解，然后将关注点转移到存储双雄：堆和栈。之后，我们会探讨一下值类型和引用类型，并对有关于这两种类型的重要基础内容做一个讲解。 　　本文会通过一个简单的代码来展示在装箱和拆箱过程中所带来的性能上的影响，请各位仔细阅读。 二、当你声明一个变量背后发生了什么？ 　　当你在一个.NET应用程序中定义一个变量时，在RAM中会为其分配一些内存块。这块内存有三样东西：变量的名称、变量的数据类型以及变量的值。 　　上面简单阐述了内存中发生的事情，但是你的变量究竟会被分配到哪种类型的内存取决于数据类型。在.NET中有两种可分配的内存：栈和堆。在接下来的几个部分中，我们会试着详细地来理解这两种类型的存储。 三、存储双雄：堆和栈 　　为了理解栈和堆，让我们通过以下的代码来了解背后到底发生了什么。 public void Method1() { // Line 1 int i=4; // Line 2 int y=2; //Line 3 class1 cls1 = new class1(); } 代码只有三行，现在我们可以一行一行地来了解到底内部是怎么来执行的。 **Line 1：**当这一行被执行后，编译器会在栈上分配一小块内存。栈会在负责跟踪你的应用程序中是否有运行内存需要 **Line 2：**现在将会执行第二步。正如栈的名字一样，它会将此处的一小块内存分配叠加在刚刚第一步的内存分配的顶部。你可以认为栈就是一个一个叠加起来的房间或盒子。在栈中，数据的分配和解除都会通过LIFO (Last In First Out)即先进后出的逻辑规则进行。换句话说，也就是最先进入栈中的数据项有可能最后才会出栈。 **Line 3：**在第三行中，我们创建了一个对象。当这一行被执行后，.NET会在栈中创建一个指针，而实际的对象将会存储到一个叫做“堆”的内存区域中。“堆”不会监测运行内存，它只是能够被随时访问到的一堆对象而已。不同于栈，堆用于动态内存的分配。 …… 阅读全文

摘要：虽然散列表在关键字和存储位置之间建立了对应关系，理想情况是无须关键字的比较就可找到待查关键字。但是由于冲突的存在，散列表的查找过程仍是一个和关键字比较的过程，不过散列表的平均查找长度比顺序查找、二分查找等完全依赖于关键字比较的查找要小得多。 注意： 　 ①由同一个散列函数、不同的解决冲突方法构造的散列表，其平均查找长度是不相同的。 　②散列表的平均查找长度不是结点个数n的函数，而是装填因子α的函数。因此在设计散列表时可选择α以控制散列表的平均查找长度。 　③ α的取值 　α越小，产生冲突的机会就小，但α过小，空间的浪费就过多。只要α选择合适，散列表上的平均查找长度就是一个常数，即散列表上查找的平均时间为O(1)。 　④ 散列法与其他查找方法的区别 除散列法外，其他查找方法有共同特征为：均是建立在比较关键字的基础上。其中顺序查找是对无序集合的查找，每次关键字的比较结果为"="或"!="两种可能，其平均时间为O(n)；其余的查找均是对有序集合的查找，每次关键字的比较有"="、"<"和">"三种可能，且每次比较后均能缩小下次的查找范围，故查找速度更快，其平均时间为O(lgn)。而散列法是根据关键字直接求出地址的查找方法，其查找的期望时间为O(1)。 阅读全文

摘要：在用线性查找和二分查找的过程中需要依据关键字进行若干次的比较判断，确定数据集合中是否存在关键字等于某个给定关键字的记录以及该记录在数据表中的位置，查找效率与比较的次数密切相关。在查找时需要不断进行比较的原因是建立数据表时，只考虑了各记录的关键字之间的相对大小，记录在表中的位置和其关键字无直接关系。而之前介绍的哈希表就记录了存储位置和其关键字之间的某种直接关系，那么使用哈希表进行查找时，就无须比较或只做很少的比较久能直接由关键字找到相应的记录。实际上哈希表也就是为解决查找问题提出的。具体哈希表的内容请参考之前的“散列表”相关文章。 阅读全文

摘要：　分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。 一、 二分查找表存储结构 　二分查找表由分块有序的线性表和索引表组成。 （1）分块有序的线性表 　表R[1..n]均分为b块，前b-1块中结点个数为 ，第b块的结点数小于等于s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是分块有序的。 （... 阅读全文

摘要：一、二分查找(Binary Search) 　 二分查找又称折半查找，它是一种效率较高的查找方法。 　二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。 二、二分查找的基本思想 　二分查找的基本思想是：（设R[low..high]是当前的查找区间） （1）首先确定该区间的中点位置： （2）然后将待查的K值与R[mid].key... 阅读全文

摘要：　　在表的组织方式中，线性表是最简单的一种。顺序查找是一种最简单的查找方法。 一、顺序查找的基本思想 　　基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。 　　顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作存储结构时，扫... 阅读全文

摘要：一、概述 　　对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若u，v ∈E(G)，则u在线性序列中出现在v之前。 　通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。 注意： 　①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的... 阅读全文

摘要：一、概述　　 对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作： 　　 这里: 　　TE表示T的边集 　　w(u，v)表示边(u，v)的权。 　　权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。 二、最小生成树的应用 　　最小生成树有许多重要的应用。 【例】网络G表示n各城市之间的通信线路网线路... 阅读全文

摘要：问题描述 对每一对顶点vi ≠ vj，求出vi与vj之间的最短路径和最短路径长度 Floyd算法 Floyd(Floyd-Warshall)算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，该算法名称以创始人之一罗伯特·弗洛伊德命名。 Floyd-Warshall算法是动态规划的一个例子，即该算法中的前面的运算都会给予后面结果一些影响，下一步得出的结果可能会... 阅读全文