空间与时间的变换只不过是时间与空间、空间与时间两种方式。
当时axdkj完成了空间交换时间,曾有时间用大量土地换取自己的喘息。
因为在实际开发中时间=运行时,空间=运行内存,所以空间和时间的转换实际上是运行时和内存之间的占有率。 在时间运行中如何处理好两者的关系,才能提高系统的运行速度。 改变时间是指执行复杂程序时占用很大的内存,需要将程序划分为不同的模块,减少执行使用时间,减少内存消耗。
在程序开发的过程中,我们对数据的处理有一些检查。
检查有简单校验和复杂校验两种。
简单检查是否有用户、密码是否正确等。 这样的检查,可以说几乎不花时间。 所以也不需要在这里优化。
对于复杂的检查,可以通过联合查询,多次查询,达到数据的准确性。 当然,这个检查的执行会很慢。
对于程序开发来说,时间复杂度和空间复杂度是可以相互转化的通俗地说就是对于执行的慢的程序,可以通过消耗内存(即构造新的数据结构)来进行优化。而消耗内存的程序,也可以多消耗时间来降低内存的消耗。
前者使用得最多。 很少有人为了节约内存而浪费时间。
感兴趣的同学,请仔细看完这个例子。看如何是如何消耗内存来提高性能的。如果有不正确的地方,还请指出来。
首先以场景为例。 分别看看正常思路的处理方法和优化的处理方法。
例如,给学生上课。 学生和课程是多对多的关系。
在一般逻辑中,应该有维持两者关系的关系表。
现在,将约束添加到校验中。 例如,清洁雪碧上学期学的课,上课时不应该上这样的课。
所以,需要约束表(也就是历史成绩单)。
也就是说,学生的选择列表需要学生的成绩单作为约束。
处理方式比较方案1 :常规处理方式:某学生再次选课时。 有必要调查学生的选择列表,确认是否已经存在。
也就是说,存在以下检查:
//调查学生代码和课程代码是否分别存在a和b的数据
//list收藏着学生的选择记录的所有数据
liststudentrecordentityliststudentrecord=service.find all (;
//调查数据,看是否已经存在
studentrecordentityensr=liststudentrecord.find (s=s .学生代码==a s .课程代码==b );
if (ensr==空值) {
//学生没有选这门课程
//.
}else{
//学生已经选了这门课程
//.
() ) ) ) )。
上面这些代码的写法非常简洁。 而且很容易理解。
首先,假设有5000名学生,100门课。 在学生选修课的数据集中,数据量为5000*100。 数据量将为10万级别的数量级。
查询10万条数据中,学生=A课程=B的1条记录。 执行效率降低。 find方法的查询是where查询,因此它遍历并搜索数据集。
所以,用上面的代码。 随着数据量的增加,程序的执行效率会大幅降低。
(ps )数据量的增加在这个例子中不太合适。 例子可能不太合适。 总之,恐怕就是这个意思。 ) )
场景2 :使用内存优化效率:
这种做法需要消耗内存。 或者,向前进行检查的工作(数据的初始化在导入系统的过程中进行)。 也就是说,页面加载时数据只调用被提供的public方法进行检查。
//学生在数组索引中编码
Private Dictionarystring,int _DicStudentCodeToArrayIndex;
//从课程代码到数据索引
Private Dictionarystring,int _DicCourseCodeToArrayIndex;
p>//所有学生List<StudentEntity> ListStudent=service.findAllStudent();
//所有课程
List<CourseEntity> ListCourse=service.findAllCourse();
//所有 学生选课记录
List<StudentCourseEntity> ListStudentRecord=service.finAll();
Private int[,] _ConnStudentRecord=new int[ListStudent.count,ListCourse.count];
//构造 学生、课程的 数组 用于快速查找字典索引
Private void GenerateDic(){
For(int i=0;i<ListStudent.Count;i++)
_DicStudentCodeToArrayIndex.Add(ListStudent[i].code,i)
}
For(int i=0;i<ListCourse.Count;i++){
_DicCourseCodeToArrayIndex.Add(ListCourse[i].code,i)
}
}
//构造学生选课 匹配的 二维数组。 1表示 学生已选该课程
Private void GenerateArray(){
Foreach(StudentRecordEntity sre in ListStudentRecord){
Int x=_DicStudentCodeToArrayIndex[sre.学生Code];
Int y=DicCourseCodeToArrayIndex[sre.课程Code];
ConnStudentRecord[x,y]=1;
}
}
//对外公开的方法:根据学生Code 和课程Code 查询 选课记录是否存在
/// <returns>返回1 表示存在。返回0表示不存在</returns>
Public void VerifyRecordByStudentCodeAndCourseCode(String pStudentCode,String pCourseCode){
Int x=_DicStudentCodeToArrayIndex[pStudentCode];
Int y=_DicCourseCodeToArrayIndex[pCourseCode];
Return ConnStudentRecord[x,y];
}
性能分析
分析一下第二种方案的表象。
1、方法很多。
2、使用的变量很多。
首先要说一下。该优化的目的,是提高 学生在选课的时候,所出现的卡顿现象(校验数据量大)。
分别对以上两种方案进行分析:
假设学生为N,课程为M
第一种方案:
时间复杂度很容易计算 第一种方案最小为O(NM)
第二种方案:
1、代码多。但是给用户提供的只有一个VerifyRecordByStudentCodeAndCourseCode方法。
2、变量多,因为该方案就是要使用内存提高效率的。
这个方法执行流程:1、在Dictionary中使用Code找Index 2、使用Index查询数组。
第一步中,Dictionary中查询是使用的Hash查找算法。时间复杂度为O(lgN) 时间比较快。第二步,时间复杂度为O(1),因为数组 是连续的 使用索引 会直接查找对应的地址。
所以,使用第二种方案进行校验,第二种方案时间复杂度为O(lgN+lgM)