最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

天天短讯!读编程与类型系统笔记10_泛型算法和迭代器

来源:博客园


(相关资料图)

1.常用算法

1.1.map()

1.1.1.接受一个T值序列和一个函数(value: T) => U,将该函数应用到序列中的全部元素,然后返回一个U值序列

1.1.2.别名

1.1.2.1.fmap()

1.1.2.2.select()

1.2.filter()

1.2.1.接受一个T值序列和一个谓词(value: T) => boolean,并返回一个T值序列,其中包含谓词返回true的所有数据项

1.2.2.别名

1.2.2.1.where()

1.3.reduce()

1.3.1.接受一个T值序列、一个T类型的初始值,以及将两个T值合并为一个值的操作(x: T, y: T) => T

1.3.2.当使用该操作把序列中的全部元素合并起来后,它返回一个T值

1.3.3.别名

1.3.3.1.fold()

1.3.3.2.collect()

1.3.3.3.accumulate()

1.3.3.4.aggregate()

1.4.any()

1.4.1.接受一个T值序列和一个谓词(value: T) => boolean

1.4.2.如果序列中的任何一个元素满足谓词,它就返回true。

1.5.all()

1.5.1.接受一个T值序列和一个谓词(value: T) => boolean

1.5.2.如果序列的全部元素满足谓词,它将返回true

1.6.none()

1.6.1.接受一个T值序列和一个谓词(value: T) => boolean

1.6.2.如果序列中没有元素满足谓词,它将返回true

1.7.take()

1.7.1.接受一个T值序列和一个数字n

1.7.2.它返回的结果序列由原序列的前n个元素构成

1.7.3.别名

1.7.3.1.limit()

1.8.drop()

1.8.1.接受一个T值序列和一个数字n

1.8.2.它返回的结果序列包含原序列中除前n个元素之外的所有元素

1.8.2.1.前n个元素将被丢弃

1.8.3.别名

1.8.3.1.skip()

1.9.zip()

1.9.1.接受一个T值序列和一个U值序列

1.9.2.它返回的结果序列由T和U值对组成,实际上是把两个序列组合了起来

1.10.其他算法

1.10.1.order()

1.10.2.reverse()

1.10.3.split()

1.10.4.concat()

1.11.库算法

1.11.1.在Java中,它们包含在java.util.stream包

1.11.2.在C#中,它们包含在System.Linq命名空间中

1.11.3.在C++中,它们包含在标准库头文件中

1.11.3.1.C++现在越来越倾向于使用范围

1.11.3.2.通过更新算法,使其接受范围作为实参,并返回范围

1.11.4.JavaScript的underscore.js包和lodash包

1.11.5.把大部分循环替换为调用库算法

1.12.经验准则

1.12.1.自己在编写循环时,应该检查是否有库算法或者管道能够完成相同的工作

1.12.1.1.库算法被高效实现并且经过实践证明,而且因为能够明确表达所做的操作,所以我们的代码也更加容易理解

1.12.2.并不是所有数据结构都支持特化的迭代器

1.12.3.如果确实遇到了使用可用算法无法解决的问题,则应该考虑为解决方案创建一个泛型的、可重用的实现,而不是特定的、一次性的实现

1.13.实现流畅管道

1.13.1.一个流畅的API来把算法链接成管道

1.13.2.流畅的API是基于方法链的API,可以使代码更加容易阅读

1.13.3.方便地从左到右阅读,而且我们能够用一种非常自然的语法,链接任意多个算法来构成管道

1.13.4.缺点

1.13.4.1.包含了所有的算法,所以很难扩展

1.13.4.1.1.C#提供了扩展方法,可以用来向类或接口添加方法,而不必修改其代码

1.13.4.2.如果它是库的一部分,那么调用代码在不修改类的情况下,很难添加一个新的算法

2.约束类型参数

2.1.约束告诉编译器某个类型实参必须具有的能力

2.2.一旦要求泛型类型上必须有特定成员,就使用约束将允许类型的集合限制为具有必要成员的那些类型

2.3.哈希集合

2.3.1.类型T需要提供一个哈希函数,该函数接受T类型的一个值,返回一个数字,即其哈希值

2.3.2.Java的顶层类型Object有一个hashCode()方法

2.3.3.C#的顶层类型Object有一个GetHashCode()方法

3.大O表示法

3.1.当函数的实参趋近于特定值n时,执行该函数需要的时间和空间的上界

3.2.时间上界

3.2.1.时间复杂度

3.2.2.常量时间,或O(1)

3.2.2.1.函数的执行时间不依赖于它需要处理的数据项个数

3.2.2.2.例如:函数first()取出一个序列中的第一个元素

3.2.3.对数时间,或O(logn)

3.2.3.1.函数的输入在每一步减半,所以即使对于很大的n值,它的效率也很高

3.2.3.2.例如,在排序后的序列中进行二分搜索

3.2.4.线性时间,或O(n)

3.2.4.1.函数的运行时间与其输入成比例。遍历一个序列需要的时间是O(n)

3.2.5.二次方时间,或O(n2)

3.2.5.1.其效率比线性时间低得多,因为运行时间的增长比输入规模的增长快得多

3.2.5.2.序列上的两个嵌套循环的运行时间为O(n2)

3.2.6.线性代数时间,或O(nlogn)

3.2.6.1.不如线性时间高效,但是比二次方时间高效

3.2.6.2.最高效的比较排序算法是O(nlogn)

3.2.6.3.不能只使用一个循环排序一个序列,但能够做到比使用两个嵌套循环更快

3.3.空间上界

3.3.1.空间复杂度

3.3.2.常量空间,或O(1)

3.3.2.1.在输入的规模增长时,函数不需要更多空间

3.3.2.2.max()函数需要额外的内存来存储正在计算中的最大值和迭代器,但无论序列有多大,函数需要的内存量是固定的

3.3.3.线性空间,或O(n)

3.3.3.1.函数需要的内存量与其输入的规模成比例

3.3.3.2.二叉树遍历就是这样一个函数,它将所有结点的值复制到一个数组中,以提供树的迭代器

4.常用迭代器

4.1.输入迭代器

4.1.1.能够遍历序列一次并提供其值的迭代器

4.1.1.1.允许读取值

4.1.2.不能第二次重放值,因为值可能已经不再可用

4.2.输出迭代器

4.2.1.能够遍历一个序列并向其写入值的迭代器,它并不需要能够读出值

4.2.1.1.允许设置值

4.3.前向迭代器

4.3.1.可以向前推进、可以读取当前位置的值以及更新该值的迭代器

4.3.2.可以被克隆,推进该迭代器不会影响该迭代器的克隆

4.3.3.能够遍历一个序列任意多次,并修改序列

4.4.双向迭代器

4.4.1.具有前向迭代器的所有能力,但除此之外,还可以递减

4.4.2.既可以前向,又可以后向遍历序列

4.4.3.泛型reverse()

4.5.随机访问迭代器

4.5.1.能够以常量时间向前或向后跳过任意多个元素

4.5.2.能够实现最高效的算法,提供这种迭代器的数据结构相对较少

4.5.2.1.双向链表不能支持随机访问迭代器

5.自适应算法

5.1.为功能较少的迭代器提供了更加通用的、效率相对较低的实现

5.1.1.一个低效,但是对迭代器要求较低的版本

5.2.为功能较多的迭代器提供了更加高效的、没那么通用的实现

5.2.1.一个高效,但是对迭代器要求更高的版本

关键词: 更加容易 运行时间