• 关于

    迭代循环怎么用

    的搜索结果

回答

这个依赖于数据结构实现的吧。foreach就是跑迭代器嘛,如果删除某个元素对迭代器迭代不会产生影响,那就可以删。 不过如果这是真的,我还是倾向于这算Java的BUG。foreach就应该是只读的!!###### 有错? 一半用迭代器可以删除当前元素,不知道你是怎么删除其他元素的!######循环中删除,调用iterator的remove才是安全的,foreach里面那不到iterator的引用,还是换成循环iterator的方式吧
优选2 2020-06-09 11:21:57 0 浏览量 回答数 0

回答

这个依赖于数据结构实现的吧。foreach就是跑迭代器嘛,如果删除某个元素对迭代器迭代不会产生影响,那就可以删。 不过如果这是真的,我还是倾向于这算Java的BUG。foreach就应该是只读的!! ###### 有错? 一半用迭代器可以删除当前元素,不知道你是怎么删除其他元素的! ######循环中删除,调用iterator的remove才是安全的,foreach里面那不到iterator的引用,还是换成循环iterator的方式吧
爱吃鱼的程序员 2020-05-30 21:01:31 0 浏览量 回答数 0

问题

从arraylist中删除项目元素

我有一个通用的arraylist对象,在这里我想要删除一些元素。问题是当我用for循环迭代列表时,却不能做一个remove()' s的简单序列,因为元素在每次移除后都会发生变化。怎么在通用的arraylist中删除项目元素?...
蛮大人123 2019-12-01 19:54:41 870 浏览量 回答数 2

回答

可以直接作用于for循环的对象统称为可迭代对象(Iterable)。 可以被next()函数调用并不断返回下一个值的对象称为迭代器(Iterator)。 所有的Iterable均可以通过内置函数iter()来转变为Iterator。 对迭代器来讲,有一个__next()就够了。在你使用for 和 in 语句时,程序就会自动调用即将被处理的对象的迭代器对象,然后使用它的next__()方法,直到监测到一个StopIteration异常。 Python L = [1,2,3][x**2 for x in L][1, 4, 9]next(L) Traceback (most recent call last): File "", line 1, in TypeError: 'list' object is not an iterator I=iter(L)next(I) 1 next(I) 2 next(I) 3 next(I) Traceback (most recent call last): File "", line 1, in StopIteration123456789101112131415161718 L = [1,2,3][x**2 for x in L] [1, 4, 9] next(L) Traceback (most recent call last): File "", line 1, in TypeError: 'list' object is not an iterator I=iter(L)next(I) 1 next(I) 2 next(I) 3 next(I) Traceback (most recent call last): File "", line 1, in StopIteration上面例子中,列表L可以被for进行循环但是不能被内置函数next()用来查找下一个值,所以L是Iterable。 L通过iter进行包装后设为I,I可以被next()用来查找下一个值,所以I是Iterator。 题外话: 内置函数iter()仅仅是调用了对象的__iter()方法,所以list对象内部一定存在方法iter__()内置函数next()仅仅是调用了对象的__next()方法,所以list对象内部一定不存在方法next__(),但是Itrator中一定存在这个方法。for循环内部事实上就是先调用iter()把Iterable变成Iterator在进行循环迭代的。Python L = [4,5,6]I = L.__iter__()L.__next__() Traceback (most recent call last): File "", line 1, in AttributeError: 'list' object has no attribute '__next__' I.__next__() 4 from collections import Iterator, Iterableisinstance(L, Iterable) True isinstance(L, Iterator) False isinstance(I, Iterable) True isinstance(I, Iterator) True [x**2 for x in I] [25, 36]12345678910111213141516171819 L = [4,5,6]I = L.__iter__()L.__next__() Traceback (most recent call last): File "", line 1, in AttributeError: 'list' object has no attribute '__next__' I.__next__() 4 from collections import Iterator, Iterableisinstance(L, Iterable) True isinstance(L, Iterator) False isinstance(I, Iterable) True isinstance(I, Iterator) True [x**2 for x in I] [25, 36]4.Iterator继承自Iterable,从下面的测试中可以很方便的看到Iterator包含__iter()和next()方法,而Iteratble仅仅包含iter__()。 Python from collections import Iterator, Iterablehelp(Iterator) Help on class Iterator: class Iterator(Iterable) | Method resolution order: | Iterator | Iterable | builtins.object |**注解:从这里可以看出Iterable继承自object, Iterator继承自Iterable。 | Methods defined here: | | __iter__(self) | | __next__(self) | Return the next item from the iterator. When exhausted, raise StopIteration...... help(Iterable) Help on class Iterable: class Iterable(builtins.object) | Methods defined here: | | __iter__(self)......12345678910111213141516171819202122232425 from collections import Iterator, Iterablehelp(Iterator) Help on class Iterator: class Iterator(Iterable) | Method resolution order: | Iterator | Iterable | builtins.object |**注解:从这里可以看出Iterable继承自object, Iterator继承自Iterable。 | Methods defined here: | | __iter__(self) | | __next__(self) | Return the next item from the iterator. When exhausted, raise StopIteration...... help(Iterable) Help on class Iterable: class Iterable(builtins.object) | Methods defined here: | | __iter__(self)...... iterable需要包含有__iter()方法用来返回iterator,而iterator需要包含有next__()方法用来被循环 如果我们自己定义迭代器,只要在类里面定义一个 iter() 函数,用它来返回一个带 next() 方法的对象就够了。 直接上代码 Python class Iterable: def __iter__(self): return Iterator() class Iterator: def __init__(self): self.start=-1 def __next__(self): self.start +=2 if self.start >10: raise StopIteration return self.start I = Iterable()for i in I: print(i) 12345678910111213141516class Iterable: def __iter__(self): return Iterator() class Iterator: def __init__(self): self.start=-1 def __next__(self): self.start +=2 if self.start >10: raise StopIteration return self.start I = Iterable()for i in I: print(i) 上面的代码实现的是找到10以内的奇数,代码中的类名可以随便取,不是一定需要使用我上面提供的类名的。 如果在Iterator的__next__方法中没有实现StopIteration异常,那么则是表示的全部奇数,那么需要在调用的时候设置退出循环的条件。 Python class Iterable: def __iter__(self): return Iterator() class Iterator: def __init__(self): self.start=-1 def __next__(self): self.start +=2 return self.start I = Iterable()for count, i in zip(range(5),I): #也可以用内置函数enumerate来实现计数工作。 print(i) 1234567891011121314class Iterable: def __iter__(self): return Iterator() class Iterator: def __init__(self): self.start=-1 def __next__(self): self.start +=2 return self.start I = Iterable()for count, i in zip(range(5),I): #也可以用内置函数enumerate来实现计数工作。 print(i) 我们通过range来实现打印多少个元素,这里表示打印5个元素,返回结果和上面一致。 当然,我们可以把这两个类合并在一起,这样实现程序的简练。最终版本如下 Python class Iterable: def __iter__(self): return self def __init__(self): self.start=-1 def __next__(self): self.start +=2 if self.start >10: raise StopIteration return self.start I = Iterable()for i in I: print(i) 1234567891011121314class Iterable: def __iter__(self): return self def __init__(self): self.start=-1 def __next__(self): self.start +=2 if self.start >10: raise StopIteration return self.start I = Iterable()for i in I: print(i) 复制迭代器 迭代器是一次性消耗品,使用完了以后就空了,请看。 Python L=[1,2,3]I=iter(L)for i in I: ... print(i, end='-')...1-2-3- next(I) Traceback (most recent call last): File "", line 1, in StopIteration12345678910 L=[1,2,3]I=iter(L)for i in I: ... print(i, end='-')...1-2-3- next(I) Traceback (most recent call last): File "", line 1, in StopIteration当循环以后就殆尽了,再次使用调用时会引发StopIteration异常。 我们想通过直接赋值的形式把迭代器保存起来,可以下次使用。但是通过下面的范例可以看出来,根本不管用。 Python I=iter(L)J=Inext(I) 1 next(J) 2 next(I) 3 next(J) Traceback (most recent call last): File "", line 1, in StopIteration123456789101112 I=iter(L)J=Inext(I) 1 next(J) 2 next(I) 3 next(J) Traceback (most recent call last): File "", line 1, in StopIteration那怎么样才能达到我们要的效果呢? 我们需要使用copy包中的deepcopy了,请看下面: Python import copyI=iter(L)J=copy.deepcopy(I)next(I) 1 next(I) 2 next(J) 1123456789 import copyI=iter(L)J=copy.deepcopy(I)next(I) 1 next(I) 2 next(J) 1补充:迭代器不能向后移动, 不能回到开始。 所以需要做一些特殊的事情才能实现向后移动等功能。 以上代码均在Python 3.4 中测试通过。 日志: 8月13日完成8月14日添加关于Iterator, Iterable的更多解释在题外话的第4点。
xuning715 2019-12-02 01:10:08 0 浏览量 回答数 0

回答

1.列表生成式列表生成式即List Comprehensions,是Python内置的非常简单却强大的可以用来创建list的生成式。举个例子,要生成list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]可以用list(range(1, 11)):list(range(1, 11))[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]但如果要生成[1x1, 2x2, 3x3, ..., 10x10]怎么做?方法一是循环:L = []for x in range(1, 11):... L.append(x * x)...L[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]但是循环太繁琐,而列表生成式则可以用一行语句代替循环生成上面的list:[x * x for x in range(1, 11)][1, 4, 9, 16, 25, 36, 49, 64, 81, 100]写列表生成式时,把要生成的元素x * x放到前面,后面跟for循环,就可以把list创建出来,十分有用,多写几次,很快就可以熟悉这种语法。for循环后面还可以加上if判断,这样我们就可以筛选出仅偶数的平方:[x * x for x in range(1, 11) if x % 2 == 0][4, 16, 36, 64, 100]还可以使用两层循环,可以生成全排列:[m + n for m in 'ABC' for n in 'XYZ']['AX', 'AY', 'AZ', 'BX', 'BY', 'BZ', 'CX', 'CY', 'CZ']三层和三层以上的循环就很少用到了。运用列表生成式,可以写出非常简洁的代码。例如,列出当前目录下的所有文件和目录名,可以通过一行代码实现:import os # 导入os模块,模块的概念后面讲到[d for d in os.listdir('.')] # os.listdir可以列出文件和目录['.emacs.d', '.ssh', '.Trash', 'Adlm', 'Applications', 'Desktop', 'Documents', 'Downloads', 'Library', 'Movies', 'Music', 'Pictures', 'Public', 'VirtualBox VMs', 'Workspace', 'XCode']for循环其实可以同时使用两个甚至多个变量,比如dict的items()可以同时迭代key和value:d = {'x': 'A', 'y': 'B', 'z': 'C' }for k, v in d.items():... print(k, '=', v)...y = Bx = Az = C因此,列表生成式也可以使用两个变量来生成list:d = {'x': 'A', 'y': 'B', 'z': 'C' }[k + '=' + v for k, v in d.items()]['y=B', 'x=A', 'z=C']最后把一个list中所有的字符串变成小写:L = ['Hello', 'World', 'IBM', 'Apple'][s.lower() for s in L]['hello', 'world', 'ibm', 'apple']2.字典生成式[python] view plain copyd = {key: value for (key, value) in iterable} 其中iterable是一个可迭代的对象,比如list[python] view plain copyorg_dict = {'x': 1, 'y': 2, 'z': 3} new_dict = {v: k for k,v in some_dict.items()}
xuning715 2019-12-02 01:10:38 0 浏览量 回答数 0

问题

【百问百答】Java开发手册灵魂15问之为什么要求谨慎使用ArrayList中的subList方法

1. Arraylist与LinkedList区别 2. Collections.sort和Arrays.sort排序的实现原理 3. 简述Java语言中Collections.sort底层实现 4. 简述Java语言中Arrays....
huc_逆天 2021-01-15 10:47:39 8 浏览量 回答数 0

回答

什么是质数:质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1与该数本身两个因数的数)。——via维基百科简单来说就是,只能除以1和自身的数(需要大于1)就是质数。举个栗子,5这个数,从2开始一直到4,都不能被它整除,只有1和它本身(5)才能被5整除,所以5就是一个典型的质数。那么想计算出一个随机数是不是质数用Python应该怎么写呢?首先第一句话肯定是接受用户输入的数字:n = int(input("please enter the number:"))接着要计算该数是不是质数,那么就要从2开始一直除到该数之前的那个自然数,很明显是一个数字范围:for i in range(2, n):在循环体里面,每次循环当然就是要判断当次除法是否是整除,这里可以使用求模运算,也就是取余,当余数为0时,该数就不是质数:if n % i == 0: print("%d is not a prime number!" % n) break这个break意思就是当该数不是质数时,就跳出整个循环,该数就不是我们要的数字了。那么,所有循环迭代都完成后还没有找出能整除的情况的话,那么可以判断该数就是一个质数,所以:else: print("%d is a prime number!" % n)那么此时,所有代码就写好了,不过为了看起来简单,没有罩一层是否大于1的判断,用户输入的数字默认需要大于1:n = int(input("please enter the number:"))for i in range(2, n): if n % i == 0: print("%d is not a prime number!" % n) breakelse: print("%d is a prime number!" % n)这里要细细品味这段代码,else其实不是和if是一对,而是和for并排的,我们常见的是if…else…或者if…elif…else诸如此类,但其实for也可以和else搭配出现,在这段代码里,当某一次遍历结果余数为0后,break生效,那循环就结束了,那与之成对出现的else代码也就不执行了;当所有遍历结束后没有一次余数为0,那该循环就转到else开始执行,打印输出“该数为质数”。最后我们来随便输2个数字看看功能有没有实现:please enter the number:1111 is a prime number! please enter the number:2121 is not a prime number!
世事皆空 2019-12-02 01:07:38 0 浏览量 回答数 0

问题

【精品问答】python必备面试干货

谁能想到60%开发者想要学习的python,竟然诞生于80年代的圣诞节期间。 在阿姆斯特丹,百无聊赖的Guido决心开发继承ABC语言的脚本解释程序。就这样,python在Guido的手中诞生了。...
问问小秘 2019-12-01 21:53:38 1125 浏览量 回答数 2

问题

【算法】五分钟算法小知识:洗牌算法

我知道大家会各种花式排序,但是如果叫你打乱一个数组,你是否能做到胸有成竹?即便你拍脑袋想出一个算法,怎么证明你的算法就是正确的呢?乱序算法不像排序算法,结果...
游客ih62co2qqq5ww 2020-05-06 13:22:45 11 浏览量 回答数 1

问题

【面试必备】2020最新Java集合容器面试题

【面试必备】2020最新Java集合容器面试题 集合容器概述 什么是集合 集合框架:用于存储数据的容器。 集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。 任何集合框架都包含三大块内容:对外的...
剑曼红尘 2020-03-24 14:00:04 7 浏览量 回答数 1

问题

【python学习全家桶】263道python热门问题,阿里百位技术专家答疑解惑

阿里极客公益活动:或许你挑灯夜战只为一道难题或许你百思不解只求一个答案或许你绞尽脑汁只因一种未知那么他们来了,阿里系技术专家来云栖问答为你解答技术难题了他们用户自己手中的技术来帮助用户成长本次活动特邀百位阿里技术专家对python常见问题进...
管理贝贝 2019-12-01 20:07:21 7217 浏览量 回答数 2

问题

【精品问答】Python字符串面试知识点50问

Python字符串面试知识点总结 1.python中的下标索引怎么用 2.python中的切片操作 3.pythonfind()函数的使用 4.python中index()函数 5.python中replace怎么使用 6.python中s...
珍宝珠 2019-12-01 22:06:38 25 浏览量 回答数 0

回答

1.字符串转义序列转义字符 描述(在行尾时) 续行符\ 反斜杠符号' 单引号" 双引号a 响铃b 退格(Backspace)e 转义000 空n 换行v 纵向制表符t 横向制表符r 回车f 换页oyy 八进制数yy代表的字符,例如:o12代表换行xyy 十进制数yy代表的字符,例如:x0a代表换行other 其它的字符以普通格式输出 2.字符串格式化 3.操作符 一、算术运算符 注意: 双斜杠 // 除法总是向下取整。 从符点数到整数的转换可能会舍入也可能截断,建议使用math.floor()和math.ceil()明确定义的转换。 Python定义pow(0, 0)和0 ** 0等于1。 二、比较运算符 运算符 描述< 小于<= 小于或等于 大于= 大于或等于== 等于 != 不等于is 判断两个标识符是不是引用自一个对象is not 判断两个标识符是不是引用自不同对象注意: 八个比较运算符优先级相同。 Python允许x < y <= z这样的链式比较,它相当于x < y and y <= z。 复数不能进行大小比较,只能比较是否相等。 三、逻辑运算符 运算符 描述 备注x or y if x is false, then y, elsex x andy if x is false, then x, elsey not x if x is false, then True,elseFalse 注意: or是个短路运算符,它只有在第一个运算数为False时才会计算第二个运算数的值。 and也是个短路运算符,它只有在第一个运算数为True时才会计算第二个运算数的值。 not的优先级比其他类型的运算符低,所以not a == b相当于not (a == b),而 a == not b是错误的。 四、位运算符 运算符 描述 备注x | y 按位或运算符 x ^ y 按位异或运算符 x & y 按位与运算符 x << n 左移动运算符 x >> n 右移动运算符 ~x 按位取反运算符 五、赋值运算符 复合赋值运算符与算术运算符是一一对应的: 六、成员运算符 Python提供了成员运算符,测试一个元素是否在一个序列(Sequence)中。 运算符 描述in 如果在指定的序列中找到值返回True,否则返回False。not in 如果在指定的序列中没有找到值返回True,否则返回False。 4.关键字总结 Python中的关键字包括如下: and del from not while as elif global or with assert else if pass yield break except import print class exec in raise continue finally is return def for lambda try你想看看有哪些关键字?OK,打开一个终端,就像这样~ long@zhouyl:~$ pythonPython 2.7.3 (default, Jan 2 2013, 16:53:07) [GCC 4.7.2] on linux2Type "help", "copyright", "credits" or "license" for more information. import keywordkeyword.kwlist ['and', 'as', 'assert', 'break', 'class', 'continue', 'def', 'del', 'elif', 'else', 'except', 'exec', 'finally', 'for', 'from', 'global', 'if', 'import', 'in', 'is', 'lambda', 'not', 'or', 'pass', 'print', 'raise', 'return', 'try', 'while', 'with', 'yield'] ============================== 华丽的 正文分隔符 ======================================== 看到这些关键字你还能记得多少?你不妨自己一个一个对照想想它的用法,下面是我总结的,我根据前面的学习笔记将上述关键字分为以下几类: 1.判断、循环 对于Python的循环及判断主要包括这些关键字: if elif else for while break continue and or is not in 这几个关键字在前面介绍 if 语法、while语法、for语法以及and...or语法中已有介绍,下面再一笔带过: 1.1 if 语法 if语法与C语言、shell脚本之下的非常类似,最大的区别就是冒号以及严格的缩进,当然这两点也是Python区别于其他语言的地方: if condition1: do something elif condition2: do another thing else: also do something 1.2 while 语法 Python的while语法区别于C、shell下的while除了冒号及缩进之外,还有一点就是while可以携带一个可选的else语句: while condition: do something else: do something 注:else语句是可选的,但是使用while语句时一定要注意判断语句可以跳出! 1.3 for 语法 与while类似,Python的for循环也包括一个可选的else语句(跳出for循环时执行,但是如果是从break语句跳出则不执行else语句块中的代码!),而且for 加上 关键字in就组成了最常见的列表解析用法(以后会写个专门的博客)。 下面是for的一般用法: for i in range(1,10,2): do something if condition: break else: do something for的列表解析用法: for items in list: print items 1.4 and...or 语法 Python的and/or操作与其他语言不同的是它的返回值是参与判断的两个值之一,所以我们可以通过这个特性来实现Python下的 a ? b : c ! 有C语言基础的知道 “ a ? b : c ! ” 语法是判断 a,如果正确则执行b,否则执行 c! 而Python下我们可以这么用:“ a and b or c ”(此方法中必须保证b必须是True值),python自左向右执行此句,先判断a and b :如果a是True值,a and b语句仍需要执行b,而此时b是True值!所以a and b的值是b,而此时a and b or c就变成了b or c,因b是True值,所以b or c的结果也是b;如果a是False值,a and b语句的结果就是a,此时 a and b or c就转化为a or c,因为此时a是 False值,所以不管c是True 还是Flase,a or c的结果就是c!!!捋通逻辑的话,a and b or c 是不是就是Python下的a ? b : c ! 用法? 1.5 is ,not is 和 is not 是Python下判断同一性的关键字,通常用来判断 是 True 、False或者None(Python下的NULL)! 比如 if alue is True : ... (不记得本节的童鞋罚复习:python 学习笔记 2 -- 判断语句) 2.函数、模块、类 对于Python的函数及模块主要包括这些关键字: from import as def pass lambda return class 那么你还能记得它们么?下面简单介绍一下: 2.1 模块 Python的编程通常大量使用标准库中的模块,使用方法就是使用import 、from以及as 关键字。 比如: import sys # 导入sys模块 from sys import argv # 从sys模块中导入argv ,这个在前面介绍脚本传参数时使用到 import cPickle as p # 将cPickle模块导入并在此将它简单命名为p,此后直接可以使用p替代cPickle模块原名,这个在介绍文件输入输出时的存储器中使用到 2.2 函数 Python中定义函数时使用到def关键字,如果你当前不想写入真实的函数操作,可以使用pass关键字指代不做任何操作: def JustAFunction: pass 当然,在需要给函数返回值时就用到了return关键字,这里简单提一下Python下的函数返回值可以是多个(接收返回值时用相应数量的变量接收!)! 此外Python下有个神奇的Lambda函数,它允许你定义单行的最小函数,这是从Lisp中借用来的,可以用在任何需要函数的地方。比如: g = lambda x : x*2 # 定义一个Lambda函数用来计算参数的2倍并返回! print g(2) # 使用时使用lambda函数返回的变量作为这个函数的函数名,括号中带入相应参数即可! (不记得本节的童鞋罚复习:python 学习笔记 4 -- 函数篇) 3.异常 对于Python的异常主要包括这些关键字: try except finally raise 异常这一节还是比较简单的,将可能出现的异常放在 try: 后面的语句块中,使用except关键字捕获一定的异常并在接下来的语句块中做相应操作,而finally中接的是无论出现什么异常总在执行最后做finally: 后面的语句块(比如关闭文件等必要的操作!) raise关键字是在一定的情况下引发异常,通常结合自定义的异常类型使用。 (不记得本节的童鞋罚复习:python 学习笔记 6 -- 异常处理) 4.其他 上面的三类过后,还剩下这些关键字: print del global with assert yield exec 首先print 在前面的笔记或者任何地方你都能见到,所以还是比较熟悉的,此处就不多介绍了!del 关键字在前面的笔记中已有所涉及,比如删除列表中的某项,我们使用 “ del mylist[0] ” 可能这些剩下来的关键字你比较陌生,所以下面来介绍一下: 4.1.global 关键字 当你在函数定义内声明变量的时候,它们与函数外具有相同名称的其他变量没有任何关系,即变量名称对于函数来说是 局部 的。这称为变量的 作用域 。所有变量的作用域是它们被定义的块,从它们的名称被定义的那点开始。 eg. ? 1 2 3 4 5 6 7 8 9 10 11 !/usr/bin/python Filename: func_local.py def func(x): print'x is', x x = 2 print'Changed local x to', x x = 50 func(x) print'x is still', x 运行的结果是这样的:? 1 2 3 4 $ python func_local.py x is 50 # 运行func函数时,先打印x的值,此时带的值是作为参数带入的外部定义的50,所以能正常打印 x=50 Changed local x to 2 # 在func函数中将x赋2,并打印 x is still 50 # 运行完func函数,打印x的值,此时x的值仍然是之前赋给的50,而不是func函数中修改过的2,因为在函数中修改的只是函数内的局部变量 那么为什么我们要在这提到局部变量呢?bingo,聪明的你一下就猜到这个global就是用来定义全局变量的。也就是说如果你想要为一个在函数外定义的变量赋值,那么你就得告诉Python这个变量名不是局部的,而是 全局 的。我们使用global语句完成这一功能。没有global语句,是不可能为定义在函数外的变量赋值的。eg.? 1 2 3 4 5 6 7 8 9 10 11 12 !/usr/bin/python Filename: func_global.py def func(): global x print'x is', x x = 2 print'Changed local x to', x x = 50 func() print'Value of x is', x 运行的结果是这样的:? 1 2 3 4 $ python func_global.py x is 50 Changed global x to 2 Value of x is 2 # global语句被用来声明x是全局的——因此,当我们在函数内把值赋给x的时候,这个变化也反映在我们在主块中使用x的值的时候。 你可以使用同一个global语句指定多个全局变量。例如global x, y, z。 4.2.with 关键字 有一些任务,可能事先需要设置,事后做清理工作。对于这种场景,Python的with语句提供了一种非常方便的处理方式。一个很好的例子是文件处理,你需要获取一个文件句柄,从文件中读取数据,然后关闭文件句柄。如果不用with语句,打开一个文件并读文件的代码如下:? 1 2 3 file = open("/tmp/foo.txt") data = file.read() file.close() 当然这样直接打开有两个问题:一是可能忘记关闭文件句柄;二是文件读取数据发生异常,没有进行任何处理。下面是添加上异常处理的版本:? 1 2 3 4 5 file = open("/tmp/foo.txt") try: data = file.read() finally: file.close() 虽然这段代码运行良好,但是太冗余了。这时候就是with一展身手的时候了。除了有更优雅的语法,with还可以很好的处理上下文环境产生的异常。下面是with版本的代码:? 1 2 with open("/tmp/foo.txt") as file: data = file.read() 这看起来充满魔法,但不仅仅是魔法,Python对with的处理还很聪明。基本思想是with所求值的对象必须有一个__enter__()方法,一个__exit__()方法。with语句的执行逻辑如下:紧跟with后面的语句被求值后,返回对象的__enter__()方法被调用,这个方法的返回值将被赋值给as后面的变量。当with后面的代码块全部被执行完之后,将调用前面返回对象的__exit__()方法。 下面例子可以具体说明with如何工作:? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 !/usr/bin/python with_example01.py classSample: def __enter__(self): print"In __enter__()" return"Foo" def __exit__(self, type, value, trace): print"In __exit__()" def get_sample(): returnSample() with get_sample() as sample: print"sample:", sample 运行代码,输出如下? 1 2 3 4 $python with_example01.py In __enter__() # __enter__()方法被执行 sample: Foo # __enter__()方法返回的值 - 这个例子中是"Foo",赋值给变量'sample',执行代码块,打印变量"sample"的值为"Foo" In __exit__() # __exit__()方法被调用 4.3.assert 关键字 assert语句是一种插入调试断点到程序的一种便捷的方式。assert语句用来声明某个条件是真的,当assert语句失败的时候,会引发一AssertionError,所以结合try...except我们就可以处理这样的异常。 mylist # 此时mylist是有三个元素的列表['a', 'b', 'c']assert len(mylist) is not None # 用assert判断列表不为空,正确无返回assert len(mylist) is None # 用assert判断列表为空 Traceback (most recent call last): File "", line 1, in AssertionError # 引发AssertionError异常 4.4.yield 关键字 我们先看一个示例:? 1 2 3 4 5 6 7 8 def fab(max): n, a, b = 0,0,1 whilen < max: yield b # print b a, b = b, a + b n = n + 1 ''' 使用这个函数:? 1 2 3 4 5 6 7 8 forn in fab(5): ... print n ... 1 1 2 3 5 简单地讲,yield 的作用就是把一个函数变成一个 generator(生成器),带有 yield 的函数不再是一个普通函数,Python 解释器会将其视为一个 generator,调用 fab(5) 不会执行 fab 函数,而是返回一个 iterable(可迭代的)对象!在 for 循环执行时,每次循环都会执行 fab 函数内部的代码,执行到 yield b 时,fab 函数就返回一个迭代值,下次迭代时,代码从 yield b 的下一条语句继续执行,而函数的本地变量看起来和上次中断执行前是完全一样的,于是函数继续执行,直到再次遇到 yield。也可以手动调用 fab(5) 的 next() 方法(因为 fab(5) 是一个 generator 对象,该对象具有 next() 方法),这样我们就可以更清楚地看到 fab 的执行流程:? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 f = fab(5) f.next() 1 f.next() 1 f.next() 2 f.next() 3 f.next() 5 f.next() Traceback (most recent call last): File"", line 1, in StopIteration 当函数执行结束时,generator 自动抛出 StopIteration 异常,表示迭代完成。在 for 循环里,无需处理 StopIteration 异常,循环会正常结束。 我们可以得出以下结论:一个带有 yield 的函数就是一个 generator,它和普通函数不同,生成一个 generator 看起来像函数调用,但不会执行任何函数代码,直到对其调用 next()(在 for 循环中会自动调用 next())才开始执行。虽然执行流程仍按函数的流程执行,但每执行到一个 yield 语句就会中断,并返回一个迭代值,下次执行时从 yield 的下一个语句继续执行。看起来就好像一个函数在正常执行的过程中被 yield 中断了数次,每次中断都会通过 yield 返回当前的迭代值。 yield 的好处是显而易见的,把一个函数改写为一个 generator 就获得了迭代能力,比起用类的实例保存状态来计算下一个 next() 的值,不仅代码简洁,而且执行流程异常清晰。 注:如果看完此段你还未明白yield,没问题,因为yield是初学者的一个难点,那么你下一步需要做的就是……看一看下面参考资料中给的关于yield的博文! 4.5.exec 关键字 官方文档对于exec的解释: "This statement supports dynamic execution of Python code."也就是说使用exec可以动态执行Python代码(也可以是文件)。? 1 2 3 4 5 6 7 8 9 10 11 12 13 longer = "print "Hello World ,my name is longer"" # 比如说我们定义了一个字符串 longer 'print "Hello World ,my name is longer"' exec(longer) # 使用exec 动态执行字符串中的代码 Hello World ,my name is longer exec(sayhi) # 使用exec直接打开文件名(指定sayhi,sayhi.py以及"sayhi.py"都会报一定的错,但是我觉得直接带sayhi报错非常典型) Traceback (most recent call last): File"", line 1, in TypeError: exec: arg 1must be a string, file, or code object # python IDE报错,提示exec的第一个参 数必须是一个字符串、文件或者一个代码对象 f = file("sayhi.py") # 使用file打开sayhi.py并创建f实例 exec(f) # 使用exec直接运行文件描述符f,运行正常!! Hi,thisis [''] script 上述给的例子比较简单,注意例子中exec语句的用法和eval_r(), execfile()是不一样的. exec是一个关键字(要不然我怎么会在这里介绍呢~~~), 而eval_r()和execfile()则是内建函数。更多关于exec的使用请详看引用资料或者Google之 在需要在字符中使用特殊字符时,python用反斜杠()转义字符。 原始字符串 有时我们并不想让转义字符生效,我们只想显示字符串原来的意思,这就要用r和R来定义原始字符串。如: print r’tr’ 实际输出为“tr”。 转义字符 描述 (在行尾时) 续行符 反斜杠符号 ’ 单引号 ” 双引号 a 响铃 b 退格(Backspace) e 转义 000 空 n 换行 v 纵向制表符 t 横向制表符 r 回车 f 换页 oyy 八进制数yy代表的字符,例如:o12代表换行 xyy 十进制数yy代表的字符,例如:x0a代表换行 other 其它的字符以普通格式输出
xuning715 2019-12-02 01:10:21 0 浏览量 回答数 0

问题

状态压缩技巧:动态规划的降维打击 7月14日 【今日算法】

我们号之前写过十几篇动态规划文章,可以说动态规划技巧对于算法效率的提升非常可观,一般来说都能把指数级和阶乘级时间复杂度的算法优化成 O(N^2),堪称算法界的二向箔,把各路魑魅魍魉统统...
游客ih62co2qqq5ww 2020-07-14 23:53:52 6 浏览量 回答数 1

回答

在使用内置模块的时候需要导入,例如import abc,则导入abc模块,当然模块也可以自己写,相当于一个类,后面放到类里说,这个因为环境闲置,有些无法执行,只能理解了 os系统操作 import os os.system('ls') #调用系统命令,并返回执行结果,os.system('dir').... os.popen('ls') #和system相似,system会直接把结果打印到屏幕上,popen可以把结果返回给一个变量,然后可以用read()或for循环来遍历 os.chdir('/home/myuser/py') #windows可以直接把路径打成'c:mypy'这种,os可以将路径改成通用路径 dir_path = os.getcwd() #获取到当前目录,结果是当前目录路径'/home/myuser/py' os.listdir(dir_path) #获取指定目录下的所有文件和文件夹,结果是一个list os.path.isdir(dir_name) #判断指定名称是否是文件夹,假如dir_name是个文件夹,则返回True,否则False os.path.join(dir1,dir2,file1) #合并多个路径,可以是dir1,dir2...,file1 os.mkdir('py') #创建目录,和linux一样,没什么可说的 os.rmdir('py') #删除目录,必须是个空目录,和linux一样 os.environ.get(env) #获取环境变量,例os.environ.get('oracle_home') re正则操作 import re a = "my py it's fucking greate!" 几个常用的正则内容,|或,.通配符(同excel的),?匹配0个或1个,匹配0个或多个,+匹配1个或多个,\符号,*比如要匹配需要用转义就是只是个而不是0个或多个,^匹配行开始,$匹配行结尾 (?<=XXX)前视,(?=XXX)后视,这个可以百度,我说不清,一般不会用,爬虫时候用的多 [A-Z]大写的全部字母,[a-z]小写的全部字母,[0-9]全部数字 正则默认是贪婪模式, .*?这样写是非贪婪模式,(XXX)匹配一个字符串 re_value = re.compile('^.*? ') #编译正则表达式,这段正则的意思是匹配从开始到第一个空格的内容,正则最好先编译下再用 re_search = re.search(re_value,a) #在字符串里找正则匹配的,这个不能直接显示需要group print re_search.group() #结果是my re_find = re.findall(re_value,a) #在字符串里找全部可以匹配的结果,返回一个迭代 for i in re_find: print i #因为只有一行,因此只找到一个,结果是my,可以自己搞多行试试 re.sub(re_value,'',a) #用''替换re_value,就是把正则匹配的结果替换成空,当然也可以替换成别的,结果是"py it's fucking greate!" sys,这个功能很乱,我也不知道应该怎么归类 import sys sys.argv #取得外部传入参数,返回一个list,平常执行命令python a.py,参数在后面输入,例 a.py a = sys.argv #执行命令python a.py 111 222,执行后a变量的结果是[a.py,111,222] 各种随机生成 import random random.randint(1,10) #随机生成一个1到10的随机数,结果可能是1/2/3/4/5/6/7/8/9/10其中任意一个 a = ['a','b','c'] #搞个a存个list random.choice(a) #从a里面随机抽个元素出来,结果可能是'a'/'b'/'c' random.uniform(1,10) #随机生成一个1到10的随机小数,结果可能是。。。。。这个我就不写了,你懂的
元芳啊 2019-12-02 01:04:40 0 浏览量 回答数 0

问题

【精品问答】python技术1000问(1)

为了方便python开发者快速找到相关技术问题和答案,开发者社区策划了python技术1000问内容,包含最基础的如何学python、实践中遇到的技术问题、python面试等维度内容。 我们会以每天至少50条的...
问问小秘 2019-12-01 21:57:48 456417 浏览量 回答数 22

问题

从一道面试题谈谈一线大厂码农应该具备的基本能力 7月16日 【今日算法】

##关于一线码农的面试,我想说 求职面试在绝大部分人来说都是必不可少的,自己作为求职者也参与了不少面试(无论成功或者失败),作为技术面试官参与面试也有四五年的经验&#x...
游客ih62co2qqq5ww 2020-07-22 13:45:47 118 浏览量 回答数 1

问题

优化求最值 5月29日 【今日算法】

今天主要来聊两个问题:给一个数组,如何同时求出最大值和最小值,如何同时求出最大值和第二大值? 这两个问题看起来都特别简单,一个 for 循环,几个大小判断...
游客ih62co2qqq5ww 2020-05-29 14:02:23 6 浏览量 回答数 1

问题

【算法】五分钟算法小知识:动态规划详解

动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法,只不过在计算机问题上应用比较多,比如说让你求最长递增子序列呀,最小编辑距离呀等等。 既然是要求最值,核心问题是...
游客ih62co2qqq5ww 2020-05-07 14:48:09 25 浏览量 回答数 1

问题

不搞清这8大算法思想,刷再多题效果也不好的 7月23日 【今日算法】

算法和数据结构一直以来都是程序员的基本内功,可以说没有数据结构的基础建设和算法加持,也就没有这将近八十年的信息革命时代。数据结构可以看作是算法实现的容器,通过一系列特殊结构的数据集合,...
游客ih62co2qqq5ww 2020-07-29 11:10:09 3 浏览量 回答数 1

回答

看了下 servo 中 dom 节点的处理方式,构造了个例子 use std::cell::{Cell, RefCell}; struct Element { flag: Cell<i32>, id: Cell<i32>, children: RefCell<Vec<RefCell<Element>>>, } impl Element { fn new() -> Element { Element { flag: Cell::new(0), id: Cell::new(1), children: RefCell::new(Vec::new()), } } fn add_child(&self, child: Element) { self.flag.set(self.flag.get() + 1); self.children.borrow_mut().push(RefCell::new(child)); } fn before_remove(&self) { self.flag.set(0); } fn after_remove(&self) { self.id.set(0); } fn remove_children(&self) { self.before_remove(); for e in self.children.borrow().iter() { e.borrow().remove_children(); } self.after_remove(); } } fn main() { let e1 = Element::new(); let e2 = Element::new(); let e3 = Element::new(); let e4 = Element::new(); let e5 = Element::new(); let e6 = Element::new(); let e7 = Element::new(); e6.add_child(e7); e5.add_child(e6); e4.add_child(e5); e3.add_child(e4); e2.add_child(e3); e1.add_child(e2); e1.remove_children(); println!("..."); } Element 中所有的字段用 Cell/RefCell 包装后,所有的成员方法都使用 &self 不可变借用来调用 remove_children 应该是能还原你原始的问题了。所有要嵌套/递归修改自己的地方都只用 borrow() 不可变借用就行。 而其他的基础类型字段,如 i32, vec 由于不会嵌套修改,可以 borrow_mut() 修改完马上还回来,保证一句话修改完就行。 children 我给简写了,实际上由于要再被其他人引用,应该在外面再包一层 Rc 的。 大致搜了下有类似需求的一些项目,处理方式都是类似这样的。 ######回复 @DogFeet :c++里,这些地方相对较少,而变更对象时,改其它对象是很多的,在有交互的代码里可以说是大量,成本不一样######回复 @templar : 不需要把每个修改都封装到单独的函数里面。至于说所有路径都测试到,C++也一样有这个问题,如果你在 Objects 的迭代中某个 object.update 中修改了 Objects 的布局,一样可能会导致迭代器出问题,这些只是你在 C++ 中习惯了,知道 update 中有些事情其实也是不能做的。######回复 @DogFeet : borrow_mut在运行中检查,实际中很难所有路径都测试到,所以rust还是太累了,暂时还是不用了,不过这个问题也算是有解决方法了,谢谢了######回复 @DogFeet : 那得很注意,把每个修改都封到单独的函数里,行是行,就是太费劲了~~~######回复 @templar : 转换成你那个例子就是 update 用 &self 调用,只需要 borrow 借用,update 中又一次借用自己也是用 borrow,由于 life 字段被 Cell 包起来了,所以可以通过 &self 修改。而多次 borrow 并不会有什么问题。这样就解决你原来的问题了。###### 已经用上rust了!  赞一个, ######用Recell+Mutex试下。###### 如果是多个线程要修改你的objects,则用Arc 如果只有一个线程多个地方要修改objects,则用Rc ######回复 @DogFeet : 搞不定~~求个示例代码。。。这个问题就是持有一个μt T的情况下,调用其成员函数,在该成员函数里,又需要修改自已或别的对象,就是也要获得μt T,在游戏服务器里,放技能这类逻辑,都会修改多个对象的属性###### @templar .而且用Rc了一般就不会再传引用了,你什么时候见过到处 &shared_ptr的。。。。。全局变量的问题,Rust是不推荐的,所以你要写传统语言中常见的单例模式会发现很难。###### @templar Rc没有你说的这种要求,都说了就是非线程安全版的shared_ptr######回复 @DogFeet : 看文档,rc是用于不可变量的,要获得μt还是得传入μt RC<T>,一层层往上推,又得全是μt,而且还要求rc是unique的,可能你说的可行吧,但现在暂时没什么兴趣了,写一个全局变量都这么费劲,哪天有精神了再弄吧,多谢回答######回复 @templar : Rc 就是用来解决你多个地方要共享修改一个元素的,等同于 C++ 非线程安全版 shared_ptr###### 引用来自“DogFeet”的评论 如果是多个线程要修改你的objects,则用Arc 如果只有一个线程多个地方要修改objects,则用Rc  #[derive(Debug)] pub struct OBJ {     x : i32, } fn main() {     let mut x1 = Rc::new(OBJ { x: 100 } );     let mut x2 = x1.clone();     x1.x = 101;     x2.x = 102;     println!("{:?}",x1);     println!("{:?}",x2); } src\main.rs(105,5): error : cannot assign to immutable field src\main.rs(106,5): error : cannot assign to immutable field std::rc::Rc A reference-counted pointer type over an immutable value. 要获得&mut T,还是需要 fn get_mut(rc: &mut Rc<T>) -> Option<&mut T>[−] Unstable Returns a mutable reference to the contained value if the Rc<T> is unique. Returns None if the Rc<T> is not unique. ###### 我想可能rust不适合其它语言那种N层嵌套调用,可能得写成比较扁平的类,Github上的开源,也大都如此,比如技能这个,可能就得把技能拉出来,跟OBJ同层,用RefCell只临时borrow_mut,不过这样又得导致很多其它的不便,也是挺恶心的 ###### fn main() { let x1 = Rc::new(RefCell::new(OBJ { x: 100 } )); let x2 = x1.clone(); x1.borrow_mut().x = 101; x2.borrow_mut().x = 103; println!("{:?}",x1); println!("{:?}",x2); } 所有使用你那个HashMap的地方拿到的都是一个类似上面的 x1, x2 的对象,不用保存引用,可变引用的哦,也不会传染到上层哦。 我比较好奇的是你的 get_global_objects () 打算怎么实现,要实现这种类似单例类会很麻烦的。 ######https://github.com/Kimundi/lazy-static.rs 这个宏可以简化全局变量######Global是有办法的,参照os.Stdout,比较烦一点,不过可以用宏实现######两次borrow_mut会panic的,在N层嵌套里,要想保持单一个borrow几乎不可能的,一个技能出发一个效果,影响N个对象,N个对象上的反应器又会触发其它效果,完全不可控,这个我在最上面说过不行######我说的两次borrow_mut会panic的,是指先持一个mut,调用其内部函数,在函数里,可能需要borrow自已,或其它对象,一层层函数调下去,需要borrow的对象是动态的,不可知的 你没仔细看我的问题 impl for OBJ { fn update(&mut self) { // 这里borrow另一个,可能是自已,或别人 // 假如那个对象已经被borrow了,就panic了 } } fn main() {     let x1 = Rc::new(RefCell::new(OBJ { x: 100 } ));     let x2 = x1.clone();       x1.borrow_mut().update()       println!("{:?}",x1);     println!("{:?}",x2); } ######不过RefCell可以解决HashMap的引用了,不必都用iter_mut了###### 引用来自“templar”的评论 我想可能rust不适合其它语言那种N层嵌套调用,可能得写成比较扁平的类,Github上的开源,也大都如此,比如技能这个,可能就得把技能拉出来,跟OBJ同层,用RefCell只临时borrow_mut,不过这样又得导致很多其它的不便,也是挺恶心的 如果你能做到扁平的,那就可以直接用 &, &mut 来borrow了,用完直接还掉,就没上面的问题了呀。 但事实上很难做到的,我也是做游戏的。比如常见的触发器需求,有时候触发器关联了2个对象,这个触发器需要引用这2个对象吧,C++可能就直接用到智能指针了(有的解决方案是用ID做句柄,不过也有麻烦的地方,要手动解除ID的关联,除非能保证ID不回环)。 所有的对象都被 Objects borrow 了,触发器再 borrow 肯定要出事,这种需求很难通过做平来避免的。######打包成事件扔到顶层循环处理,会勉强可以,不过很不自然,会导致别的问题###### 引用来自“templar”的评论我说的两次borrow_mut会panic的,是指先持一个mut,调用其内部函数,在函数里,可能需要borrow自已,或其它对象,一层层函数调下去,需要borrow的对象是动态的,不可知的 你没仔细看我的问题 impl for OBJ { fn update(&mut self) { // 这里borrow另一个,可能是自已,或别人 // 假如那个对象已经被borrow了,就panic了 } } fn main() {     let x1 = Rc::new(RefCell::new(OBJ { x: 100 } ));     let x2 = x1.clone();       x1.borrow_mut().update()       println!("{:?}",x1);     println!("{:?}",x2); } 你说的这个我还没考虑到。 如果是这样,那确实很麻烦,按照多人共享用 Rc 的策略,如果 Objects 中的 entry 也需要多人共享,那把 entry 也用 Rc 包起来?不过这样,entry.update(&mut self) 就得改写成 entry_update(e: Rc<...>) 了,这样也确实很丑。 或者是模仿 Rc, Arc 这种用 unsafe 包装内部可变性的方式,把 entry 的 update 用 unsafe 包起来,外面拿 immutable borrow 的 entry 也能通过调用其成员函数来做到修改内部状态。就像 Rc 的 clone。不过这种感觉也不是解决方法。 我再问问其他看看 ######unsafe也试过了,在unsafe里不能把获得的μt T作为参数调用其它安全函数
kun坤 2020-06-06 14:56:09 0 浏览量 回答数 0

问题

最大限度利用 JavaScript 和 Ajax 性能:报错

简介 在 web 早期,优化 web 页面的性能通常意味着避免了使用不必要的 HTML 标记,将 JavaScript 代码量控制到最小,并尽量减小所有图片文件大小,否则上网冲浪者会...
kun坤 2020-06-05 22:56:50 0 浏览量 回答数 1

回答

Python数据结构篇数据结构篇主要是阅读[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [该网址链接可能会比较慢]时写下的阅读记录,当然,也结合了部分[算法导论](Introduction to Algorithms)中的内容,此外还有不少wikipedia上的内容,所以内容比较多,可能有点杂乱。这部分主要是介绍了如何使用Python实现常用的一些数据结构,例如堆栈、队列、二叉树等等,也有Python内置的数据结构性能的分析,同时还包括了搜索和排序(在算法设计篇中会有更加详细的介绍)的简单总结。每篇文章都有实现代码,内容比较多,简单算法一般是大致介绍下思想及算法流程,复杂的算法会给出各种图示和代码实现详细介绍。**这一部分是下面算法设计篇的前篇,如果数据结构还不错的可以直接看算法设计篇,遇到问题可以回来看数据结构篇中的某个具体内容充电一下,我个人认为直接读算法设计篇比较好,因为大家时间也都比较宝贵,如果你会来读这些文章说明你肯定有一定基础了,后面的算法设计篇中更多的是思想,这里更多的是代码而已,嘿嘿。**(1)[搜索](Python Data Structures) 简述顺序查找和二分查找,详述Hash查找(hash函数的设计以及如何避免冲突)(2)[排序](Python Data Structures) 简述各种排序算法的思想以及它的图示和实现(3)[数据结构](Python Data Structures) 简述Python内置数据结构的性能分析和实现常用的数据结构:栈、队列和二叉堆(4)[树总结](Python Data Structures) 简述二叉树,详述二叉搜索树和AVL树的思想和实现2.Python算法设计篇算法设计篇主要是阅读[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)[**点击链接可进入Springer免费下载原书电子版**]之后写下的读书总结,原书大部分内容结合了经典书籍[算法导论](Introduction to Algorithms),内容更加细致深入,主要是介绍了各种常用的算法设计思想,以及如何使用Python高效巧妙地实现这些算法,这里有别于前面的数据结构篇,部分算法例如排序就不会详细介绍它的实现细节,而是侧重于它内在的算法思想。这部分使用了一些与数据结构有关的第三方模块,因为这篇的重点是算法的思想以及实现,所以并没有去重新实现每个数据结构,但是在介绍算法的同时会分析Python内置数据结构以及第三方数据结构模块的优缺点,也就意味着该篇比前面都要难不少,但是我想我的介绍应该还算简单明了,因为我用的都是比较朴实的语言,并没有像算法导论一样列出一堆性质和定理,主要是对着某个问题一步步思考然后算法就出来了,嘿嘿,除此之外,里面还有很多关于python开发的内容,精彩真的不容错过。这里每篇文章都有实现代码,但是代码我一般都不会分析,更多地是分析算法思想,所以内容都比较多,即便如此也没有包括原书对应章节的所有内容,因为内容实在太丰富了,所以我只是选择经典的算法实例来介绍算法核心思想,除此之外,还有不少内容是原书没有的,部分是来自算法导论,部分是来自我自己的感悟,嘻嘻。该篇对于大神们来说是小菜,请一笑而过,对于菜鸟们来说可能有点难啃,所以最适合的是和我水平差不多的,对各个算法都有所了解但是理解还不算深刻的半桶水的程序猿,嘿嘿。本篇的顺序按照原书[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)的章节来安排的(章节标题部分相同部分不同哟),为了节省时间以及保持原著的原滋原味,部分内容(一般是比较难以翻译和理解的内容)直接摘自原著英文内容。 **1.你也许觉得很多内容你都知道嘛,没有看的必要,其实如果是我的话我也会这么想,但是如果只是归纳一个算法有哪些步骤,那这个总结也就没有意义了,我觉得这个总结的亮点在于想办法说清楚一个算法是怎么想出来的,有哪些需要注意的,如何进行优化的等等,采用问答式的方式让读者和我一起来想出某个问题的解,每篇文章之后都还有一两道小题练手哟****2.你也许还会说算法导论不是既权威又全面么,基本上每个算法都还有详细的证明呢,读算法导论岂不更好些,当然,你如果想读算法导论的话我不拦着你,读完了感觉自己整个人都不好了别怪小弟没有提醒你哟,嘻嘻嘻,左一个性质右一个定理实在不适合算法科普的啦,没有多少人能够坚持读完的。但是码农与蛇的故事内容不多哟,呵呵呵****3.如果你细读本系列的话我保证你会有不少收获的,需要看算法导论哪个部分的地方我会给出提示的,嘿嘿。温馨提示,前面三节内容都是介绍基础知识,所以精彩内容从第4节开始哟,么么哒 O(∩_∩)O~**(1)[Python Algorithms - C1 Introduction](Python Algorithms) 本节主要是对原书中的内容做些简单介绍,说明算法的重要性以及各章节的内容概要。(2)[Python Algorithms - C2 The basics](Python Algorithms) **本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。**(3)[Python Algorithms - C3 Counting 101](Python Algorithms) 原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法(4)[Python Algorithms - C4 Induction and Recursion and Reduction](Python Algorithms) **本节主要介绍算法设计的三个核心知识:Induction(推导)、Recursion(递归)和Reduction(规约),这是原书的重点和难点部分**(5)[Python Algorithms - C5 Traversal](Python Algorithms) **本节主要介绍图的遍历算法BFS和DFS,以及对拓扑排序的另一种解法和寻找图的(强)连通分量的算法**(6)[Python Algorithms - C6 Divide and Combine and Conquer](Python Algorithms) **本节主要介绍分治法策略,提到了树形问题的平衡性以及基于分治策略的排序算法**(7)[Python Algorithms - C7 Greedy](Python Algorithms) **本节主要通过几个例子来介绍贪心策略,主要包括背包问题、哈夫曼编码和最小生成树等等**(8)[Python Algorithms - C8 Dynamic Programming](Python Algorithms) **本节主要结合一些经典的动规问题介绍动态规划的备忘录法和迭代法这两种实现方式,并对这两种方式进行对比**(9)[Python Algorithms - C9 Graphs](Python Algorithms) /question/19889750/answer/27901020有哪些用 Python 语言讲算法和数据结构的书
琴瑟 2019-12-02 01:22:41 0 浏览量 回答数 0

问题

Pytorch不会通过迭代张量结构进行反向传播

我目前正在尝试在Pytorch中迭代地构建一个张量。 遗憾的是,在循环中backprop不能与就地操作一起工作。例如,我已经尝试了使用stack的等价程序。有人知道怎么用一个有效的支撑来建立张量吗? 这是一个产生...
kun坤 2019-12-30 10:02:55 0 浏览量 回答数 1

回答

1.1。Numba的约5分钟指南 Numba是Python的即时编译器,它最适用于使用NumPy数组和函数以及循环的代码。使用Numba的最常用方法是通过其装饰器集合,可以应用于您的函数来指示Numba编译它们。当调用Numba修饰函数时,它被编译为机器代码“及时”执行,并且您的全部或部分代码随后可以以本机机器代码速度运行! 开箱即用的Numba使用以下方法: 操作系统:Windows(32位和64位),OSX和Linux(32位和64位) 架构:x86,x86_64,ppc64le。在armv7l,armv8l(aarch64)上进行实验。 GPU:Nvidia CUDA。AMD ROC的实验。 CPython的 NumPy 1.10 - 最新 1.1.1。我怎么得到它? Numba可作为畅达包为 蟒蛇Python发布: $ conda install numba Numba还有pip可供选择: $ pip install numba Numba也可以 从源代码编译,虽然我们不建议首次使用Numba用户。 Numba通常用作核心包,因此其依赖性保持在绝对最小值,但是,可以按如下方式安装额外的包以提供其他功能: scipy- 支持编译numpy.linalg功能。 colorama - 支持回溯/错误消息中的颜色突出显示。 pyyaml - 通过YAML配置文件启用Numba配置。 icc_rt - 允许使用Intel SVML(高性能短矢量数学库,仅限x86_64)。安装说明在 性能提示中。 1.1.2。Numba会为我的代码工作吗? 这取决于你的代码是什么样的,如果你的代码是以数字为导向的(做了很多数学运算),经常使用NumPy和/或有很多循环,那么Numba通常是一个不错的选择。在这些例子中,我们将应用最基本的Numba的JIT装饰器,@jit试图加速一些函数来演示哪些有效,哪些无效。 Numba在代码看起来像这样: from numba import jit import numpy as np x = np.arange(100).reshape(10, 10) @jit(nopython=True) # Set "nopython" mode for best performance def go_fast(a): # Function is compiled to machine code when called the first time trace = 0 for i in range(a.shape[0]): # Numba likes loops trace += np.tanh(a[i, i]) # Numba likes NumPy functions return a + trace # Numba likes NumPy broadcasting print(go_fast(x)) 对于看起来像这样的代码,如果有的话,它将无法正常工作: from numba import jit import pandas as pd x = {'a': [1, 2, 3], 'b': [20, 30, 40]} @jit def use_pandas(a): # Function will not benefit from Numba jit df = pd.DataFrame.from_dict(a) # Numba doesn't know about pd.DataFrame df += 1 # Numba doesn't understand what this is return df.cov() # or this! print(use_pandas(x)) 请注意,Numba不理解Pandas,因此Numba只是通过解释器运行此代码,但增加了Numba内部开销的成本! 1.1.3。什么是nopython模式? Numba @jit装饰器从根本上以两种编译模式运行, nopython模式和object模式。在go_fast上面的例子中, nopython=True在@jit装饰器中设置,这是指示Numba在nopython模式下操作。nopython编译模式的行为本质上是编译装饰函数,以便它完全运行而不需要Python解释器的参与。这是使用Numba jit装饰器的推荐和最佳实践方式,因为它可以带来最佳性能。 如果编译nopython模式失败,Numba可以编译使用 ,如果没有设置,这是装饰器的 后退模式(如上例所示)。在这种模式下,Numba将识别它可以编译的循环并将它们编译成在机器代码中运行的函数,并且它将运行解释器中的其余代码。为获得最佳性能,请避免使用此模式objectmode@jitnopython=Trueuse_pandas 1.1.4。如何衡量Numba的表现? 首先,回想一下,Numba必须为执行函数的机器代码版本之前给出的参数类型编译函数,这需要时间。但是,一旦编译完成,Numba会为所呈现的特定类型的参数缓存函数的机器代码版本。如果再次使用相同的类型调用它,它可以重用缓存的版本而不必再次编译。 测量性能时,一个非常常见的错误是不考虑上述行为,并使用一个简单的计时器来计算一次,该计时器包括在执行时编译函数所花费的时间。 例如: from numba import jit import numpy as np import time x = np.arange(100).reshape(10, 10) @jit(nopython=True) def go_fast(a): # Function is compiled and runs in machine code trace = 0 for i in range(a.shape[0]): trace += np.tanh(a[i, i]) return a + trace DO NOT REPORT THIS... COMPILATION TIME IS INCLUDED IN THE EXECUTION TIME! start = time.time() go_fast(x) end = time.time() print("Elapsed (with compilation) = %s" % (end - start)) NOW THE FUNCTION IS COMPILED, RE-TIME IT EXECUTING FROM CACHE start = time.time() go_fast(x) end = time.time() print("Elapsed (after compilation) = %s" % (end - start)) 这,例如打印: Elapsed (with compilation) = 0.33030009269714355 Elapsed (after compilation) = 6.67572021484375e-06 衡量Numba JIT对您的代码的影响的一个好方法是使用timeit模块函数来执行时间,这些函数测量多次执行迭代,因此可以在第一次执行时适应编译时间。 作为旁注,如果编译时间成为问题,Numba JIT支持 编译函数的磁盘缓存,并且还具有Ahead-Of-Time编译模式。 1.1.5。它有多快? 假设Numba可以在nopython模式下运行,或者至少编译一些循环,它将针对您的特定CPU进行编译。加速因应用而异,但可以是一到两个数量级。Numba有一个 性能指南,涵盖了获得额外性能的常用选项。 1.1.6。Numba如何运作? Numba读取装饰函数的Python字节码,并将其与有关函数输入参数类型的信息相结合。它分析并优化您的代码,最后使用LLVM编译器库生成函数的机器代码版本,根据您的CPU功能量身定制。每次调用函数时都会使用此编译版本。 1.1.7。其他感兴趣的东西: Numba有相当多的装饰,我们看到@jit和@njit,但也有: @vectorize- 生成NumPy ufunc(ufunc支持所有方法)。文件在这里。 @guvectorize- 产生NumPy广义ufuncs。 文件在这里。 @stencil - 将函数声明为类似模板操作的内核。 文件在这里。 @jitclass - 对于jit感知类。文件在这里。 @cfunc - 声明一个函数用作本机回调(从C / C ++等调用)。文件在这里。 @overload- 注册您自己的函数实现,以便在nopython模式下使用,例如@overload(scipy.special.j0)。 文件在这里。 一些装饰者提供额外选项: parallel = True- 启用功能的 自动并行化。 fastmath = True- 为该功能启用快速数学行为。 ctypes / cffi / cython互操作性: cffi- 模式支持调用CFFI函数nopython。 ctypes- 模式支持调用ctypes包装函数nopython。。 Cython导出的函数是可调用的。 1.1.7.1。GPU目标: Numba可以针对Nvidia CUDA和(实验性)AMD ROC GPU。您可以使用纯Python编写内核,让Numba处理计算和数据移动(或明确地执行此操作)。单击关于CUDA或ROC的 Numba文档 。 示例:接下来我们写一段简单的代码,来计算一下执行时间: 示例1:不使用numba的: import time def num(): arr = [] for i in range(10000000): arr.append(i) stime = time.time() num() etime = time.time() - stime print(arr) print('用时:{}秒'.format(etime)) 示例输出时间: 用时:1.4500024318695068秒 示例2:使用numba @jit import time from numba import jit @jit def num(): arr = [] for i in range(10000000): arr.append(i) stime = time.time() num() etime = time.time() - stime print(arr) print('用时:{}秒'.format(etime)) 示例输出: 用时:0.5530002117156982秒 结论: 上述两个示例代码,一个使用了numba,另一个没有使用numba;可以看出使用numba @jit装饰后,时间明显快了很多倍。 这只是一个简单示例;对于复杂计算提高速度更明显。
天枢2020 2020-03-13 18:38:04 0 浏览量 回答数 0

回答

1.Python数据结构篇 数据结构篇主要是阅读[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [该网址链接可能会比较慢]时写下的阅读记录,当然,也结合了部分[算法导论](Introduction to Algorithms)中的内容,此外还有不少wikipedia上的内容,所以内容比较多,可能有点杂乱。这部分主要是介绍了如何使用Python实现常用的一些数据结构,例如堆栈、队列、二叉树等等,也有Python内置的数据结构性能的分析,同时还包括了搜索和排序(在算法设计篇中会有更加详细的介绍)的简单总结。每篇文章都有实现代码,内容比较多,简单算法一般是大致介绍下思想及算法流程,复杂的算法会给出各种图示和代码实现详细介绍。 **这一部分是下面算法设计篇的前篇,如果数据结构还不错的可以直接看算法设计篇,遇到问题可以回来看数据结构篇中的某个具体内容充电一下,我个人认为直接读算法设计篇比较好,因为大家时间也都比较宝贵,如果你会来读这些文章说明你肯定有一定基础了,后面的算法设计篇中更多的是思想,这里更多的是代码而已,嘿嘿。** (1)[搜索](Python Data Structures) 简述顺序查找和二分查找,详述Hash查找(hash函数的设计以及如何避免冲突) (2)[排序](Python Data Structures) 简述各种排序算法的思想以及它的图示和实现 (3)[数据结构](Python Data Structures) 简述Python内置数据结构的性能分析和实现常用的数据结构:栈、队列和二叉堆 (4)[树总结](Python Data Structures) 简述二叉树,详述二叉搜索树和AVL树的思想和实现 2.Python算法设计篇 算法设计篇主要是阅读[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)[**点击链接可进入Springer免费下载原书电子版**]之后写下的读书总结,原书大部分内容结合了经典书籍[算法导论](Introduction to Algorithms),内容更加细致深入,主要是介绍了各种常用的算法设计思想,以及如何使用Python高效巧妙地实现这些算法,这里有别于前面的数据结构篇,部分算法例如排序就不会详细介绍它的实现细节,而是侧重于它内在的算法思想。这部分使用了一些与数据结构有关的第三方模块,因为这篇的重点是算法的思想以及实现,所以并没有去重新实现每个数据结构,但是在介绍算法的同时会分析Python内置数据结构以及第三方数据结构模块的优缺点,也就意味着该篇比前面都要难不少,但是我想我的介绍应该还算简单明了,因为我用的都是比较朴实的语言,并没有像算法导论一样列出一堆性质和定理,主要是对着某个问题一步步思考然后算法就出来了,嘿嘿,除此之外,里面还有很多关于python开发的内容,精彩真的不容错过。 这里每篇文章都有实现代码,但是代码我一般都不会分析,更多地是分析算法思想,所以内容都比较多,即便如此也没有包括原书对应章节的所有内容,因为内容实在太丰富了,所以我只是选择经典的算法实例来介绍算法核心思想,除此之外,还有不少内容是原书没有的,部分是来自算法导论,部分是来自我自己的感悟,嘻嘻。该篇对于大神们来说是小菜,请一笑而过,对于菜鸟们来说可能有点难啃,所以最适合的是和我水平差不多的,对各个算法都有所了解但是理解还不算深刻的半桶水的程序猿,嘿嘿。 本篇的顺序按照原书[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)的章节来安排的(章节标题部分相同部分不同哟),为了节省时间以及保持原著的原滋原味,部分内容(一般是比较难以翻译和理解的内容)直接摘自原著英文内容。 **1.你也许觉得很多内容你都知道嘛,没有看的必要,其实如果是我的话我也会这么想,但是如果只是归纳一个算法有哪些步骤,那这个总结也就没有意义了,我觉得这个总结的亮点在于想办法说清楚一个算法是怎么想出来的,有哪些需要注意的,如何进行优化的等等,采用问答式的方式让读者和我一起来想出某个问题的解,每篇文章之后都还有一两道小题练手哟** **2.你也许还会说算法导论不是既权威又全面么,基本上每个算法都还有详细的证明呢,读算法导论岂不更好些,当然,你如果想读算法导论的话我不拦着你,读完了感觉自己整个人都不好了别怪小弟没有提醒你哟,嘻嘻嘻,左一个性质右一个定理实在不适合算法科普的啦,没有多少人能够坚持读完的。但是码农与蛇的故事内容不多哟,呵呵呵** **3.如果你细读本系列的话我保证你会有不少收获的,需要看算法导论哪个部分的地方我会给出提示的,嘿嘿。温馨提示,前面三节内容都是介绍基础知识,所以精彩内容从第4节开始哟,么么哒 O(∩_∩)O~** (1)[Python Algorithms - C1 Introduction](Python Algorithms) 本节主要是对原书中的内容做些简单介绍,说明算法的重要性以及各章节的内容概要。 (2)[Python Algorithms - C2 The basics](Python Algorithms) **本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。** (3)[Python Algorithms - C3 Counting 101](Python Algorithms) 原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法 (4)[Python Algorithms - C4 Induction and Recursion and Reduction](Python Algorithms) **本节主要介绍算法设计的三个核心知识:Induction(推导)、Recursion(递归)和Reduction(规约),这是原书的重点和难点部分** (5)[Python Algorithms - C5 Traversal](Python Algorithms) **本节主要介绍图的遍历算法BFS和DFS,以及对拓扑排序的另一种解法和寻找图的(强)连通分量的算法** (6)[Python Algorithms - C6 Divide and Combine and Conquer](Python Algorithms) **本节主要介绍分治法策略,提到了树形问题的平衡性以及基于分治策略的排序算法** (7)[Python Algorithms - C7 Greedy](Python Algorithms) **本节主要通过几个例子来介绍贪心策略,主要包括背包问题、哈夫曼编码和最小生成树等等** (8)[Python Algorithms - C8 Dynamic Programming](Python Algorithms) **本节主要结合一些经典的动规问题介绍动态规划的备忘录法和迭代法这两种实现方式,并对这两种方式进行对比** (9)[Python Algorithms - C9 Graphs](Python Algorithms)
寒凝雪 2019-12-02 01:22:23 0 浏览量 回答数 0

回答

Python数据结构篇 数据结构篇主要是阅读[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [该网址链接可能会比较慢]时写下的阅读记录,当然,也结合了部分[算法导论](Introduction to Algorithms) 中的内容,此外还有不少wikipedia上的内容,所以内容比较多,可能有点杂乱。这部分主要是介绍了如何使用Python实现常用的一些数据结构,例 如堆栈、队列、二叉树等等,也有Python内置的数据结构性能的分析,同时还包括了搜索和排序(在算法设计篇中会有更加详细的介绍)的简单总结。每篇文 章都有实现代码,内容比较多,简单算法一般是大致介绍下思想及算法流程,复杂的算法会给出各种图示和代码实现详细介绍。 **这一部分是下 面算法设计篇的前篇,如果数据结构还不错的可以直接看算法设计篇,遇到问题可以回来看数据结构篇中的某个具体内容充电一下,我个人认为直接读算法设计篇比 较好,因为大家时间也都比较宝贵,如果你会来读这些文章说明你肯定有一定基础了,后面的算法设计篇中更多的是思想,这里更多的是代码而已,嘿嘿。** (1)[搜索](Python Data Structures) 简述顺序查找和二分查找,详述Hash查找(hash函数的设计以及如何避免冲突) (2)[排序](Python Data Structures) 简述各种排序算法的思想以及它的图示和实现 (3)[数据结构](Python Data Structures) 简述Python内置数据结构的性能分析和实现常用的数据结构:栈、队列和二叉堆 (4)[树总结](Python Data Structures) 简述二叉树,详述二叉搜索树和AVL树的思想和实现 2.Python算法设计篇 算法设计篇主要是阅读[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)[**点击链接可进入Springer免费下载原书电子版**]之后写下的读书总结,原书大部分内容结合了经典书籍[算法导论](Introduction to Algorithms), 内容更加细致深入,主要是介绍了各种常用的算法设计思想,以及如何使用Python高效巧妙地实现这些算法,这里有别于前面的数据结构篇,部分算法例如排 序就不会详细介绍它的实现细节,而是侧重于它内在的算法思想。这部分使用了一些与数据结构有关的第三方模块,因为这篇的重点是算法的思想以及实现,所以并 没有去重新实现每个数据结构,但是在介绍算法的同时会分析Python内置数据结构以及第三方数据结构模块的优缺点,也就意味着该篇比前面都要难不少,但 是我想我的介绍应该还算简单明了,因为我用的都是比较朴实的语言,并没有像算法导论一样列出一堆性质和定理,主要是对着某个问题一步步思考然后算法就出来 了,嘿嘿,除此之外,里面还有很多关于python开发的内容,精彩真的不容错过。 这里每篇文章都有实现代码,但是代码我一般都不会分 析,更多地是分析算法思想,所以内容都比较多,即便如此也没有包括原书对应章节的所有内容,因为内容实在太丰富了,所以我只是选择经典的算法实例来介绍算 法核心思想,除此之外,还有不少内容是原书没有的,部分是来自算法导论,部分是来自我自己的感悟,嘻嘻。该篇对于大神们来说是小菜,请一笑而过,对于菜鸟 们来说可能有点难啃,所以最适合的是和我水平差不多的,对各个算法都有所了解但是理解还不算深刻的半桶水的程序猿,嘿嘿。 本篇的顺序按照原书[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)的章节来安排的(章节标题部分相同部分不同哟),为了节省时间以及保持原著的原滋原味,部分内容(一般是比较难以翻译和理解的内容)直接摘自原著英文内容。 **1. 你也许觉得很多内容你都知道嘛,没有看的必要,其实如果是我的话我也会这么想,但是如果只是归纳一个算法有哪些步骤,那这个总结也就没有意义了,我觉得这 个总结的亮点在于想办法说清楚一个算法是怎么想出来的,有哪些需要注意的,如何进行优化的等等,采用问答式的方式让读者和我一起来想出某个问题的解,每篇 文章之后都还有一两道小题练手哟** **2.你也许还会说算法导论不是既权威又全面么,基本上每个算法都还有详细的证明呢,读算法导论岂 不更好些,当然,你如果想读算法导论的话我不拦着你,读完了感觉自己整个人都不好了别怪小弟没有提醒你哟,嘻嘻嘻,左一个性质右一个定理实在不适合算法科 普的啦,没有多少人能够坚持读完的。但是码农与蛇的故事内容不多哟,呵呵呵** **3.如果你细读本系列的话我保证你会有不少收获的,需要看算法导论哪个部分的地方我会给出提示的,嘿嘿。温馨提示,前面三节内容都是介绍基础知识,所以精彩内容从第4节开始哟,么么哒 O(∩_∩)O~** (1)[Python Algorithms - C1 Introduction](Python Algorithms) 本节主要是对原书中的内容做些简单介绍,说明算法的重要性以及各章节的内容概要。 (2)[Python Algorithms - C2 The basics](Python Algorithms) **本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。** (3)[Python Algorithms - C3 Counting 101](Python Algorithms) 原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法 (4)[Python Algorithms - C4 Induction and Recursion and Reduction](Python Algorithms) **本节主要介绍算法设计的三个核心知识:Induction(推导)、Recursion(递归)和Reduction(规约),这是原书的重点和难点部分** (5)[Python Algorithms - C5 Traversal](Python Algorithms) **本节主要介绍图的遍历算法BFS和DFS,以及对拓扑排序的另一种解法和寻找图的(强)连通分量的算法** (6)[Python Algorithms - C6 Divide and Combine and Conquer](Python Algorithms) **本节主要介绍分治法策略,提到了树形问题的平衡性以及基于分治策略的排序算法** (7)[Python Algorithms - C7 Greedy](Python Algorithms) **本节主要通过几个例子来介绍贪心策略,主要包括背包问题、哈夫曼编码和最小生成树等等** (8)[Python Algorithms - C8 Dynamic Programming](Python Algorithms) **本节主要结合一些经典的动规问题介绍动态规划的备忘录法和迭代法这两种实现方式,并对这两种方式进行对比** (9)[Python Algorithms - C9 Graphs](Python Algorithms) https://www.zhihu.com/question/19889750/answer/27901020
青衫无名 2019-12-02 01:23:20 0 浏览量 回答数 0

回答

1.Python数据结构篇 数据结构篇主要是阅读[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [该网址链接可能会比较慢]时写下的阅读记录,当然,也结合了部分[算法导论](Introduction to Algorithms)中的内容,此外还有不少wikipedia上的内容,所以内容比较多,可能有点杂乱。这部分主要是介绍了如何使用Python实现常用的一些数据结构,例如堆栈、队列、二叉树等等,也有Python内置的数据结构性能的分析,同时还包括了搜索和排序(在算法设计篇中会有更加详细的介绍)的简单总结。每篇文章都有实现代码,内容比较多,简单算法一般是大致介绍下思想及算法流程,复杂的算法会给出各种图示和代码实现详细介绍。 **这一部分是下面算法设计篇的前篇,如果数据结构还不错的可以直接看算法设计篇,遇到问题可以回来看数据结构篇中的某个具体内容充电一下,我个人认为直接读算法设计篇比较好,因为大家时间也都比较宝贵,如果你会来读这些文章说明你肯定有一定基础了,后面的算法设计篇中更多的是思想,这里更多的是代码而已,嘿嘿。** (1)[搜索](Python Data Structures) 简述顺序查找和二分查找,详述Hash查找(hash函数的设计以及如何避免冲突) (2)[排序](Python Data Structures) 简述各种排序算法的思想以及它的图示和实现 (3)[数据结构](Python Data Structures) 简述Python内置数据结构的性能分析和实现常用的数据结构:栈、队列和二叉堆 (4)[树总结](Python Data Structures) 简述二叉树,详述二叉搜索树和AVL树的思想和实现 2.Python算法设计篇 算法设计篇主要是阅读[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)[**点击链接可进入Springer免费下载原书电子版**]之后写下的读书总结,原书大部分内容结合了经典书籍[算法导论](Introduction to Algorithms),内容更加细致深入,主要是介绍了各种常用的算法设计思想,以及如何使用Python高效巧妙地实现这些算法,这里有别于前面的数据结构篇,部分算法例如排序就不会详细介绍它的实现细节,而是侧重于它内在的算法思想。这部分使用了一些与数据结构有关的第三方模块,因为这篇的重点是算法的思想以及实现,所以并没有去重新实现每个数据结构,但是在介绍算法的同时会分析Python内置数据结构以及第三方数据结构模块的优缺点,也就意味着该篇比前面都要难不少,但是我想我的介绍应该还算简单明了,因为我用的都是比较朴实的语言,并没有像算法导论一样列出一堆性质和定理,主要是对着某个问题一步步思考然后算法就出来了,嘿嘿,除此之外,里面还有很多关于python开发的内容,精彩真的不容错过。 这里每篇文章都有实现代码,但是代码我一般都不会分析,更多地是分析算法思想,所以内容都比较多,即便如此也没有包括原书对应章节的所有内容,因为内容实在太丰富了,所以我只是选择经典的算法实例来介绍算法核心思想,除此之外,还有不少内容是原书没有的,部分是来自算法导论,部分是来自我自己的感悟,嘻嘻。该篇对于大神们来说是小菜,请一笑而过,对于菜鸟们来说可能有点难啃,所以最适合的是和我水平差不多的,对各个算法都有所了解但是理解还不算深刻的半桶水的程序猿,嘿嘿。 本篇的顺序按照原书[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)的章节来安排的(章节标题部分相同部分不同哟),为了节省时间以及保持原著的原滋原味,部分内容(一般是比较难以翻译和理解的内容)直接摘自原著英文内容。 **1.你也许觉得很多内容你都知道嘛,没有看的必要,其实如果是我的话我也会这么想,但是如果只是归纳一个算法有哪些步骤,那这个总结也就没有意义了,我觉得这个总结的亮点在于想办法说清楚一个算法是怎么想出来的,有哪些需要注意的,如何进行优化的等等,采用问答式的方式让读者和我一起来想出某个问题的解,每篇文章之后都还有一两道小题练手哟** **2.你也许还会说算法导论不是既权威又全面么,基本上每个算法都还有详细的证明呢,读算法导论岂不更好些,当然,你如果想读算法导论的话我不拦着你,读完了感觉自己整个人都不好了别怪小弟没有提醒你哟,嘻嘻嘻,左一个性质右一个定理实在不适合算法科普的啦,没有多少人能够坚持读完的。但是码农与蛇的故事内容不多哟,呵呵呵** **3.如果你细读本系列的话我保证你会有不少收获的,需要看算法导论哪个部分的地方我会给出提示的,嘿嘿。温馨提示,前面三节内容都是介绍基础知识,所以精彩内容从第4节开始哟,么么哒 O(∩_∩)O~** (1)[Python Algorithms - C1 Introduction](Python Algorithms) 本节主要是对原书中的内容做些简单介绍,说明算法的重要性以及各章节的内容概要。 (2)[Python Algorithms - C2 The basics](Python Algorithms) **本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。** (3)[Python Algorithms - C3 Counting 101](Python Algorithms) 原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法 (4)[Python Algorithms - C4 Induction and Recursion and Reduction](Python Algorithms) **本节主要介绍算法设计的三个核心知识:Induction(推导)、Recursion(递归)和Reduction(规约),这是原书的重点和难点部分** (5)[Python Algorithms - C5 Traversal](Python Algorithms) **本节主要介绍图的遍历算法BFS和DFS,以及对拓扑排序的另一种解法和寻找图的(强)连通分量的算法** (6)[Python Algorithms - C6 Divide and Combine and Conquer](Python Algorithms) **本节主要介绍分治法策略,提到了树形问题的平衡性以及基于分治策略的排序算法** (7)[Python Algorithms - C7 Greedy](Python Algorithms) **本节主要通过几个例子来介绍贪心策略,主要包括背包问题、哈夫曼编码和最小生成树等等** (8)[Python Algorithms - C8 Dynamic Programming](Python Algorithms) **本节主要结合一些经典的动规问题介绍动态规划的备忘录法和迭代法这两种实现方式,并对这两种方式进行对比** (9)[Python Algorithms - C9 Graphs](Python Algorithms) **本节主要介绍图算法中的各种最短路径算法,从不同的角度揭示它们的内核以及它们的异同**
一键天涯 2019-12-02 01:23:49 0 浏览量 回答数 0

回答

遍历一个 List 有哪些不同的方式?每种方法的实现原理是什么?Java 中 List 遍历的最佳实践是什么? 遍历方式有以下几种: for 循环遍历,基于计数器。在集合外部维护一个计数器,然后依次读取每一个位置的元素,当读取到最后一个元素后停止。 迭代器遍历,Iterator。Iterator 是面向对象的一个设计模式,目的是屏蔽不同数据集合的特点,统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。 foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现,使用时不需要显式声明 Iterator 或计数器。优点是代码简洁,不易出错;缺点是只能做简单的遍历,不能在遍历过程中操作数据集合,例如删除、替换。 最佳实践:Java Collections 框架中提供了一个 RandomAccess 接口,用来标记 List 实现是否支持 Random Access。 如果一个数据集合实现了该接口,就意味着它支持 Random Access,按位置读取元素的平均时间复杂度为 O(1),如ArrayList。如果没有实现该接口,表示不支持 Random Access,如LinkedList。 推荐的做法就是,支持 Random Access 的列表可用 for 循环遍历,否则建议用 Iterator 或 foreach 遍历。 说一下 ArrayList 的优缺点 ArrayList的优点如下: ArrayList 底层以数组实现,是一种随机访问模式。ArrayList 实现了 RandomAccess 接口,因此查找的时候非常快。ArrayList 在顺序添加一个元素的时候非常方便。 ArrayList 的缺点如下: 删除元素的时候,需要做一次元素复制操作。如果要复制的元素很多,那么就会比较耗费性能。插入元素的时候,也需要做一次元素复制操作,缺点同上。 ArrayList 比较适合顺序添加、随机访问的场景。 如何实现数组和 List 之间的转换? 数组转 List:使用 Arrays. asList(array) 进行转换。List 转数组:使用 List 自带的 toArray() 方法。 代码示例: ArrayList 和 LinkedList 的区别是什么? 数据结构实现:ArrayList 是动态数组的数据结构实现,而 LinkedList 是双向链表的数据结构实现。随机访问效率:ArrayList 比 LinkedList 在随机访问的时候效率要高,因为 LinkedList 是线性的数据存储方式,所以需要移动指针从前往后依次查找。增加和删除效率:在非首尾的增加和删除操作,LinkedList 要比 ArrayList 效率要高,因为 ArrayList 增删操作要影响数组内的其他数据的下标。内存空间占用:LinkedList 比 ArrayList 更占内存,因为 LinkedList 的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。线程安全:ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全; 综合来说,在需要频繁读取集合中的元素时,更推荐使用 ArrayList,而在插入和删除操作较多时,更推荐使用 LinkedList。 补充:数据结构基础之双向链表 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。 ArrayList 和 Vector 的区别是什么? 这两个类都实现了 List 接口(List 接口继承了 Collection 接口),他们都是有序集合 线程安全:Vector 使用了 Synchronized 来实现线程同步,是线程安全的,而 ArrayList 是非线程安全的。性能:ArrayList 在性能方面要优于 Vector。扩容:ArrayList 和 Vector 都会根据实际的需要动态的调整容量,只不过在 Vector 扩容每次会增加 1 倍,而 ArrayList 只会增加 50%。 Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。 Arraylist不是同步的,所以在不需要保证线程安全时时建议使用Arraylist。 插入数据时,ArrayList、LinkedList、Vector谁速度较快?阐述 ArrayList、Vector、LinkedList 的存储性能和特性? ArrayList、LinkedList、Vector 底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢。 Vector 中的方法由于加了 synchronized 修饰,因此 Vector 是线程安全容器,但性能上较ArrayList差。 LinkedList 使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但插入数据时只需要记录当前项的前后项即可,所以 LinkedList 插入速度较快。 多线程场景下如何使用 ArrayList? ArrayList 不是线程安全的,如果遇到多线程场景,可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样: 为什么 ArrayList 的 elementData 加上 transient 修饰? ArrayList 中的数组定义如下: private transient Object[] elementData; 再看一下 ArrayList 的定义: public class ArrayList extends AbstractList implements List<E>, RandomAccess, Cloneable, java.io.Serializable 可以看到 ArrayList 实现了 Serializable 接口,这意味着 ArrayList 支持序列化。transient 的作用是说不希望 elementData 数组被序列化,重写了 writeObject 实现: 每次序列化时,先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素,然后遍历 elementData,只序列化已存入的元素,这样既加快了序列化的速度,又减小了序列化之后的文件大小。 List 和 Set 的区别 List , Set 都是继承自Collection 接口 List 特点:一个有序(元素存入集合的顺序和取出的顺序一致)容器,元素可以重复,可以插入多个null元素,元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。 Set 特点:一个无序(存入和取出顺序有可能不一致)容器,不可以存储重复元素,只允许存入一个null元素,必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。 另外 List 支持for循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为他无序,无法用下标来取得想要的值。 Set和List对比 Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。 List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变 Set接口 说一下 HashSet 的实现原理? HashSet 是基于 HashMap 实现的,HashSet的值存放于HashMap的key上,HashMap的value统一为PRESENT,因此 HashSet 的实现比较简单,相关 HashSet 的操作,基本上都是直接调用底层 HashMap 的相关方法来完成,HashSet 不允许重复的值。 HashSet如何检查重复?HashSet是如何保证数据不可重复的? 向HashSet 中add ()元素时,判断元素是否存在的依据,不仅要比较hash值,同时还要结合equles 方法比较。 HashSet 中的add ()方法会使用HashMap 的put()方法。 HashMap 的 key 是唯一的,由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key,并且在HashMap中如果K/V相同时,会用新的V覆盖掉旧的V,然后返回旧的V。所以不会重复( HashMap 比较key是否相等是先比较hashcode 再比较equals )。 以下是HashSet 部分源码: hashCode()与equals()的相关规定: 如果两个对象相等,则hashcode一定也是相同的 两个对象相等,对两个equals方法返回true 两个对象有相同的hashcode值,它们也不一定是相等的 综上,equals方法被覆盖过,则hashCode方法也必须被覆盖 hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode(),则该class的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。 ** ==与equals的区别** ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同 ==是指对内存地址进行比较 equals()是对字符串的内容进行比较3.==指引用是否相同 equals()指的是值是否相同 HashSet与HashMap的区别 Queue BlockingQueue是什么? Java.util.concurrent.BlockingQueue是一个队列,在进行检索或移除一个元素的时候,它会等待队列变为非空;当在添加一个元素时,它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一部分,主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间,或消费者有可用的对象,因为它都在BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现,比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。 在 Queue 中 poll()和 remove()有什么区别? 相同点:都是返回第一个元素,并在队列中删除返回的对象。 不同点:如果没有元素 poll()会返回 null,而 remove()会直接抛出 NoSuchElementException 异常。 代码示例: Queue queue = new LinkedList (); queue. offer("string"); // add System. out. println(queue. poll()); System. out. println(queue. remove()); System. out. println(queue. size()); Map接口 说一下 HashMap 的实现原理? HashMap概述: HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 HashMap的数据结构: 在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。 HashMap 基于 Hash 算法实现的 当我们往Hashmap中put元素时,利用key的hashCode重新hash计算出当前对象的元素在数组中的下标存储时,如果出现hash值相同的key,此时有两种情况。(1)如果key相同,则覆盖原始值;(2)如果key不同(出现冲突),则将当前的key-value放入链表中获取时,直接找到hash值对应的下标,在进一步判断key是否相同,从而找到对应值。理解了以上过程就不难明白HashMap是如何解决hash冲突的问题,核心就是使用了数组的存储方式,然后将冲突的key的对象放入链表中,一旦发现冲突就在链表中做进一步的对比。 需要注意Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn) HashMap在JDK1.7和JDK1.8中有哪些不同?HashMap的底层实现 在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做拉链法的方式可以解决哈希冲突。 JDK1.8之前 JDK1.8之前采用的是拉链法。拉链法:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。 JDK1.8之后 相比于之前的版本,jdk1.8在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。 JDK1.7 VS JDK1.8 比较 JDK1.8主要解决或优化了一下问题: resize 扩容优化引入了红黑树,目的是避免单条链表过长而影响查询效率,红黑树算法请参考解决了多线程死循环问题,但仍是非线程安全的,多线程时可能会造成数据丢失问题。 HashMap的put方法的具体流程? 当我们put的时候,首先计算 key的hash值,这里调用了 hash方法,hash方法实际是让key.hashCode()与key.hashCode()>>>16进行异或操作,高16bit补0,一个数和0异或不变,所以 hash 函数大概的作用就是:高16bit不变,低16bit和高16bit做了一个异或,目的是减少碰撞。按照函数注释,因为bucket数组大小是2的幂,计算下标index = (table.length - 1) & hash,如果不做 hash 处理,相当于散列生效的只有几个低 bit 位,为了减少散列的碰撞,设计者综合考虑了速度、作用、质量之后,使用高16bit和低16bit异或来简单处理减少碰撞,而且JDK8中用了复杂度 O(logn)的树结构来提升碰撞下的性能。 putVal方法执行流程图 ①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容; ②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③; ③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals; ④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤; ⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可; ⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。 HashMap的扩容操作是怎么实现的? ①.在jdk1.8中,resize方法是在hashmap中的键值对大于阀值时或者初始化时,就调用resize方法进行扩容; ②.每次扩展的时候,都是扩展2倍; ③.扩展后Node对象的位置要么在原位置,要么移动到原偏移量两倍的位置。 在putVal()中,我们看到在这个函数里面使用到了2次resize()方法,resize()方法表示的在进行第一次初始化时会对其进行扩容,或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发,这也是JDK1.8版本的一个优化的地方,在1.7中,扩容之后需要重新去计算其Hash值,根据Hash值对其进行分发,但在1.8版本中,则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0,重新进行hash分配后,该元素的位置要么停留在原始位置,要么移动到原始位置+增加的数组大小这个位置上 HashMap是怎么解决哈希冲突的? 答:在解决这个问题之前,我们首先需要知道什么是哈希冲突,而在了解哈希冲突之前我们还要知道什么是哈希才行; 什么是哈希? Hash,一般翻译为“散列”,也有直接音译为“哈希”的,这就是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值(哈希值);这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 所有散列函数都有如下一个基本特性**:根据同一散列函数计算出的散列值如果不同,那么输入值肯定也不同。但是,根据同一散列函数计算出的散列值如果相同,输入值不一定相同**。 什么是哈希冲突? 当两个不同的输入值,根据同一散列函数计算出相同的散列值的现象,我们就把它叫做碰撞(哈希碰撞)。 HashMap的数据结构 在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做链地址法的方式可以解决哈希冲突: 这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下,但相比于hashCode返回的int类型,我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4(即2的四次方16)要远小于int类型的范围,所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率,并且最坏情况下还会将HashMap变成一个单链表,所以我们还需要对hashCode作一定的优化 hash()函数 上面提到的问题,主要是因为如果使用hashCode取余,那么相当于参与运算的只有hashCode的低位,高位是没有起到任何作用的,所以我们的思路就是让hashCode取值出的高位也参与运算,进一步降低hash碰撞的概率,使得数据分布更平均,我们把这样的操作称为扰动,在JDK 1.8中的hash()函数如下: static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算(高低位异或) } 这比在JDK 1.7中,更为简洁,相比在1.7中的4次位运算,5次异或运算(9次扰动),在1.8中,只进行了1次位运算和1次异或运算(2次扰动); JDK1.8新增红黑树 通过上面的链地址法(使用散列表)和扰动函数我们成功让我们的数据分布更平均,哈希碰撞减少,但是当我们的HashMap中存在大量数据时,加入我们某个bucket下对应的链表有n个元素,那么遍历时间复杂度就为O(n),为了针对这个问题,JDK1.8在HashMap中新增了红黑树的数据结构,进一步使得遍历复杂度降低至O(logn); 总结 简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的: 使用链地址法(使用散列表)来链接拥有相同hash值的数据;使用2次扰动函数(hash函数)来降低哈希冲突的概率,使得数据分布更平均;引入红黑树进一步降低遍历的时间复杂度,使得遍历更快; **能否使用任何类作为 Map 的 key? **可以使用任何类作为 Map 的 key,然而在使用之前,需要考虑以下几点: 如果类重写了 equals() 方法,也应该重写 hashCode() 方法。 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。 如果一个类没有使用 equals(),不应该在 hashCode() 中使用它。 用户自定义 Key 类最佳实践是使之为不可变的,这样 hashCode() 值可以被缓存起来,拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变,这样就会解决与可变相关的问题了。 为什么HashMap中String、Integer这样的包装类适合作为K? 答:String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性,能够有效的减少Hash碰撞的几率 都是final类型,即不可变性,保证key的不可更改性,不会存在获取hash值不同的情况 内部已重写了equals()、hashCode()等方法,遵守了HashMap内部的规范(不清楚可以去上面看看putValue的过程),不容易出现Hash值计算错误的情况; 如果使用Object作为HashMap的Key,应该怎么办呢? 答:重写hashCode()和equals()方法 重写hashCode()是因为需要计算存储数据的存储位置,需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能,这样虽然能更快但可能会导致更多的Hash碰撞; 重写equals()方法,需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x,x.equals(null)必须返回false的这几个特性,目的是为了保证key在哈希表中的唯一性; HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标 答:hashCode()方法返回的是int整数类型,其范围为-(2 ^ 31)~(2 ^ 31 - 1),约有40亿个映射空间,而HashMap的容量范围是在16(初始化默认值)~2 ^ 30,HashMap通常情况下是取不到最大值的,并且设备上也难以提供这么多的存储空间,从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内,进而无法匹配存储位置; 那怎么解决呢? HashMap自己实现了自己的hash()方法,通过两次扰动使得它自己的哈希值高低位自行进行异或运算,降低哈希碰撞概率也使得数据分布更平均; 在保证数组长度为2的幂次方的时候,使用hash()运算之后的值与运算(&)(数组长度 - 1)来获取数组下标的方式进行存储,这样一来是比取余操作更加有效率,二来也是因为只有当数组长度为2的幂次方时,h&(length-1)才等价于h%length,三来解决了“哈希值与数组大小范围不匹配”的问题; HashMap 的长度为什么是2的幂次方 为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀,每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。 这个算法应该如何设计呢? 我们首先可能会想到采用%取余的操作来实现。但是,重点来了:“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方;)。” 并且 采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是2的幂次方。 那为什么是两次扰动呢? 答:这样就是加大哈希值低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性&均匀性,最终减少Hash冲突,两次就够了,已经达到了高位低位同时参与运算的目的; HashMap 与 HashTable 有什么区别? 线程安全: HashMap 是非线程安全的,HashTable 是线程安全的;HashTable 内部的方法基本都经过 synchronized 修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap 吧!); 效率: 因为线程安全的问题,HashMap 要比 HashTable 效率高一点。另外,HashTable 基本被淘汰,不要在代码中使用它; 对Null key 和Null value的支持: HashMap 中,null 可以作为键,这样的键只有一个,可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null,直接抛NullPointerException。 **初始容量大小和每次扩充容量大小的不同 **: ①创建时如果不指定容量初始值,Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。②创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。 推荐使用:在 Hashtable 的类注释可以看到,Hashtable 是保留类不建议使用,推荐在单线程环境下使用 HashMap 替代,如果需要多线程使用则用 ConcurrentHashMap 替代。 如何决定使用 HashMap 还是 TreeMap? 对于在Map中插入、删除和定位元素这类操作,HashMap是最好的选择。然而,假如你需要对一个有序的key集合进行遍历,TreeMap是更好的选择。基于你的collection的大小,也许向HashMap中添加元素会更快,将map换为TreeMap进行有序key的遍历。 HashMap 和 ConcurrentHashMap 的区别 ConcurrentHashMap对整个桶数组进行了分割分段(Segment),然后在每一个分段上都用lock锁进行保护,相对于HashTable的synchronized锁的粒度更精细了一些,并发性能更好,而HashMap没有锁机制,不是线程安全的。(JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。) HashMap的键值对允许有null,但是ConCurrentHashMap都不允许。 ConcurrentHashMap 和 Hashtable 的区别? ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。 底层数据结构: JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟HashMap1.8的结构一样,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的; 实现线程安全的方式(重要): ① 在JDK1.7的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。(默认分配16个Segment,比Hashtable效率提高16倍。) 到了 JDK1.8 的时候已经摒弃了Segment的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6以后 对 synchronized锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在JDK1.8中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;② Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。 两者的对比图: HashTable: JDK1.7的ConcurrentHashMap: JDK1.8的ConcurrentHashMap(TreeBin: 红黑二叉树节点 Node: 链表节点): 答:ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步,HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。 ConcurrentHashMap 底层具体实现知道吗?实现原理是什么? JDK1.7 首先将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问。 在JDK1.7中,ConcurrentHashMap采用Segment + HashEntry的方式进行实现,结构如下: 一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似,是一种数组和链表结构,一个 Segment 包含一个 HashEntry 数组,每个 HashEntry 是一个链表结构的元素,每个 Segment 守护着一个HashEntry数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment的锁。 该类包含两个静态内部类 HashEntry 和 Segment ;前者用来封装映射表的键值对,后者用来充当锁的角色;Segment 是一种可重入的锁 ReentrantLock,每个 Segment 守护一个HashEntry 数组里得元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 锁。 JDK1.8 在JDK1.8中,放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现,synchronized只锁定当前链表或红黑二叉树的首节点,这样只要hash不冲突,就不会产生并发,效率又提升N倍。 结构如下: 如果该节点是TreeBin类型的节点,说明是红黑树结构,则通过putTreeVal方法往红黑树中插入节点;如果binCount不为0,说明put操作对数据产生了影响,如果当前链表的个数达到8个,则通过treeifyBin方法转化为红黑树,如果oldVal不为空,说明是一次更新操作,没有对元素个数产生影响,则直接返回旧值;如果插入的是一个新节点,则执行addCount()方法尝试更新元素个数baseCount; 辅助工具类 Array 和 ArrayList 有何区别? Array 可以存储基本数据类型和对象,ArrayList 只能存储对象。Array 是指定固定大小的,而 ArrayList 大小是自动扩展的。Array 内置方法没有 ArrayList 多,比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。 对于基本类型数据,集合使用自动装箱来减少编码工作量。但是,当处理固定大小的基本数据类型的时候,这种方式相对比较慢。 如何实现 Array 和 List 之间的转换? Array 转 List: Arrays. asList(array) ;List 转 Array:List 的 toArray() 方法。 comparable 和 comparator的区别? comparable接口实际上是出自java.lang包,它有一个 compareTo(Object obj)方法用来排序comparator接口实际上是出自 java.util 包,它有一个compare(Object obj1, Object obj2)方法用来排序 一般我们需要对一个集合使用自定义排序时,我们就要重写compareTo方法或compare方法,当我们需要对某一个集合实现两种排序方式,比如一个song对象中的歌名和歌手名分别采用一种排序方法的话,我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌星名排序,第二种代表我们只能使用两个参数版的Collections.sort(). 方法如何比较元素? TreeSet 要求存放的对象所属的类必须实现 Comparable 接口,该接口提供了比较元素的 compareTo()方法,当插入元素时会回调该方法比较元素的大小。TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进 行排 序。 Collections 工具类的 sort 方法有两种重载的形式, 第一种要求传入的待排序容器中存放的对象比较实现 Comparable 接口以实现元素的比较; 第二种不强制性的要求容器中的元素必须可比较,但是要求传入第二个参数,参数是Comparator 接口的子类型(需要重写 compare 方法实现元素的比较),相当于一个临时定义的排序规则,其实就是通过接口注入比较元素大小的算法,也是对回调模式的应用(Java 中对函数式编程的支持)。
剑曼红尘 2020-03-24 14:41:57 0 浏览量 回答数 0

问题

《暗时间》读书笔记与读后感:报错

写博以来对自己要求博文每月至少一篇,可现在博客的更新一停就是两月,感情上很对不起自己的坚持T.T ... 可不管怎样,高压的时间终于算告一段落鸟,打算在这个舒适的周末,用...
kun坤 2020-06-09 15:28:47 3 浏览量 回答数 1

云产品推荐

上海奇点人才服务相关的云产品 小程序定制 上海微企信息技术相关的云产品 国内短信套餐包 ECS云服务器安全配置相关的云产品 开发者问答 阿里云建站 自然场景识别相关的云产品 万网 小程序开发制作 视频内容分析 视频集锦 代理记账服务 阿里云AIoT