2020-04
30

字典和递归

By xrspook @ 8:48:32 归类于: 烂日记

还记得在看微软的python入门视频的时候。我第一次接触字典这种东西。我觉得那是相当深奥的一件事,因为我搞不懂,那跟列表有什么区别,有什么牛逼的功能。之所以这样,大概是因为微软的视频里字典的录入他们用的是手动输入,显然我觉得一个一个对应太麻烦了。而且用起来的时候我也没发现有什么特别高的效率。入门终归是入门,你看不到字典的牛逼之处,当然就会对学习这东西没什么兴趣。当我在做Think Python 2习题,而且做得死去活来之后。当我用尽九牛二虎之力才终于用列表的方法以二分法搜索的方式找出某个词,而当我后来学习了字典,轻而易举就能找到某个词,效率差了一大截以后,我才明白到字典的超级牛逼之处。显然对我来说,现在我还不怎么熟悉字典这个东西。因为我只是用到了最基本的功能,还有非常多的东西我还不知道,一些它真正的用法我还没有使用到。比如现在的字典我只是停留在第一层级的程度上,通常的键和键值只是某个字符串。如果键值被换成一堆的列表呢?如果一堆列表里面还有一堆的元组呢?想想都觉得这相当恐怖,如果到达那个境界,我该用什么方法去访问那些东西呢?现在对我来说,那是个未解之谜,因为我还没遇到那种题目。

因为工作的原因,我已经放下python一两天了。这种东西一天不练就会手生,下次再重新开始的时候,大概我已经不记得某些语句该怎么写了,于是又得花一些时间去复习之前学过的东西。

还记得在接触python之前,我已经有听说有字典这种牛逼东西。在C语言里好像有,Excel VBA里好像也有,但是我都从来没有用过。因为我觉得那对我来说是非常遥远的存在。在python的学习过程中,我觉得字典就像吃饭睡觉一样,是基本的核心功能。字符串列表字典和元组就像数学里面的加减乘除。当然我这里列举了关系,并不是一一对应的,而是说明他们都是基本的功能,全部都得熟练运用。

还记得貌似是在学递归的那一章。在总结的时候,我记得那里好像说要我们学会不要在一个点上过分纠结,要有全局思维。其实递归并不需要把一个数值竟放进去,然后不断地按照程序进行不断的套用,应该从大局方面想,完成了这个操作,我应该得到什么答案,得到这个答案以后,我就可以把程序继续下去了。这说得简单,但实际上,有时我真想不到,递归最终我能得到什么答案,所以每次我都只能自己很傻地一遍一遍尝试。有些时候我图快,一下子放进去不是最基础的数字,结果就把我自己搞死了。后来才发现,原来一开始进去的东西就应该用最简单的,那才能最快地得出应该有的答案。直到现在,我还是非常难适应这种思维方式。在我没学习递归之前,我已经见识过了斐波那契数列。当时我是用循环的方法实现,但实际上更直观简单的方法是递归。还记得高中的数学里面也经常要我们把某些东西最终以某些方式表达出来,而当时他们给出的题目真是一些递归的东西。所以可能很早以前我就接触过递归了,但是当时没有学编程,也没有计算机,非常苦逼。

如果在学习的时候,能一边的学习编程一边学数学,大概当年就不会那么痛苦了。

2020-04
24

用两天琢磨一道题

By xrspook @ 20:32:30 归类于: 扮IT

前面还在沾沾自喜我写出来的脚本运行效率战胜了参考答案,但这道题目我是看着参考答案都不知道他们在说什么。如果只是一个词,我的确可以列举出它一次减少一个字母可以出现的所有可能,但怎么知道上一层可能和这一层的哪个配套???我花了2天时间去研究、消化答案。一边搞清楚答案为什么这样,另一边考虑有没有其它容易吃透的表达方式。这道题之所以让我非常纠结,根本的原因是我想不透到底我可以用什么手段实现。没有可以实现的逻辑,就不会有可行的编程。

Exercise 4: Here’s another Car Talk Puzzler (http://www.cartalk.com/content/puzzlers): What is the longest English word, that remains a valid English word, as you remove its letters one at a time? Now, letters can be removed from either end, or the middle, but you can’t rearrange any of the letters. Every time you drop a letter, you wind up with another English word. If you do that, you’re eventually going to wind up with one letter and that too is going to be an English word—one that’s found in the dictionary. I want to know what’s the longest word and how many letters does it have? I’m going to give you a little modest example: Sprite. Ok? You start off with sprite, you take a letter off, one from the interior of the word, take the r away, and we’re left with the word spite, then we take the e off the end, we’re left with spit, we take the s off, we’re left with pit, it, and I. Write a program to find all words that can be reduced in this way, and then find the longest one. This exercise is a little more challenging than most, so here are some suggestions: You might want to write a function that takes a word and computes a list of all the words that can be formed by removing one letter. These are the “children” of the word. Recursively, a word is reducible if any of its children are reducible. As a base case, you can consider the empty string reducible. The wordlist I provided, words.txt, doesn’t contain single letter words. So you might want to add “I”, “a”, and the empty string. To improve the performance of your program, you might want to memoize the words that are known to be reducible. Solution: http://thinkpython2.com/code/reducible.py.

最终,我觉得自己总算消化了,顺便画了个思维导图帮助大家理解到底分解到什么程度叫做完成,什么状态叫做分解失败。[”]和[]是两种不同的东西!!!!!!

is_reducible()是最关键的函数,memos用在这里,memos初始设置了known[”] = [”]也很关键,这是个守卫模式,没有守卫is_reducible()根本没法玩。这个脚本里的5个函数,除了一开始的创建字典函数,其余函数都可以单独测试,把一个固定单词放进去脚手架测试,可以帮助理解。cut_letter(),is_reducible()和all_reducible()这三个函数最终返回的都是列表,它们的样式都是类似的。希望我理解过程中的注释能帮助到有需要的人。PS一句:参考答案的打印效果让人很晕,我修改版的打印效果很美丽:)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
from time import time
def set_dict(fin):
    d = {}
    for line in fin:
        word = line.strip()
        d[word] = 0
    for word in ['a', 'i', '']:
        d[word] = 0
    return d
def cut_letter(word, d): # 生成子单词,返回列表
    l = []
    for i in range(len(word)):
        new_word = word[:i] + word[i+1:]
        if new_word in d:
            l.append(new_word)
    return l # ['']长度为1,[]长度为0,无子词不能分解时返回[],'a'返回['']
def is_reducible(word, d): # 判断能否生成无限子单词,返回列表
    if word in known: # 守卫模式下,''空字符串被列入初始字典,不列入永远会被递归到[],无果
        return known[word]
    # if word == '': # 不用memos的时候,需要加入这句守卫
    #     return ['']
    l = []
    for new_word in cut_letter(word, d):
        if len(is_reducible(new_word, d)) > 0:
            l.append(new_word)
    known[word] = l
    return l
def all_reducible(d): # 收集所有无限子单词的单词,返回列表
    l = []
    for word in d:
        if len(is_reducible(word, d)) > 0: # 有列表,即有无限子单词
            l.append((len(word), word)) # 列表含有N个元组,元组里有2个元素,1为单词的字母数量,2为单词本尊
    new_l = sorted(l, reverse = True) # 每次减少一个字母,单词的字母越多当然就能降解出越多层了
    return new_l
def word_list(word): # 打印单词及子单词
    if len(word) == 0: # 最后一个进入is_reducible()的是[''],对应l[0]为无,打印结束
        return
    print(word)
    l = is_reducible(word, d) # 因为是被鉴定过词汇表里的词,所以必定有无限子单词
    word_list(l[0]) # 子单词有多个时只选第1个
known = {} # memos实际上只在is_reducible()起作用,除了提高效率,还能用作守卫
known[''] = [''] # 因为is_reducible()返回的是列表,所以即便是空字符串,键值也必须是列表!
fin = open('words.txt')
start = time()
d = set_dict(fin) # 普通的字典,键为单词,键值为0
words = all_reducible(d) # 列表,元组,2元素
for i in range(5):
    word_list(words[i][1]) # 列表里第某个元组的第2个元素
end = time()
print(end - start)
# complecting
# completing
# competing
# compting
# comping
# coping
# oping
# ping
# pig
# pi
# i
# twitchiest
# witchiest
# withiest
# withies
# withes
# wites
# wits
# its
# is
# i
# stranglers
# strangers
# stranger
# strange
# strang
# stang
# tang
# tag
# ta
# a
# staunchest
# stanchest
# stanches
# stances
# stanes
# sanes
# anes
# ane
# ae
# a
# restarting
# restating
# estating
# stating
# sating
# sting
# ting
# tin
# in
# i
# 0.6459996700286865
# 无memos 1.5830001831054688, 有memos 0.6459996700286865
2020-04
24

拉卷纸的熊猫

By xrspook @ 9:19:00 归类于: 烂日记

循环和递归,对路人甲来说那是差不多的玩意,反正就是在那里转圈圈。但是,虽然已经认识递归好些时间了,但我依然非常害怕这个存在。之所以害怕递归,是因为我很难想象到底递归什么时候才是个头,而我又非常明白,达不到递归的头,就不能把东西返回出来,得到我想要的答案。这个玩意就像一个无底洞。于是每次当我遇到递归,我都会在那里瑟瑟发抖,大概要克服这个,我需要非常大量的递归练习,让理解这个东西变成我的条件反射。

我不知道,在实际编程过程之中,到底会不会真的经常用到递归这种恐怖的东西。在Think Python 2这本书里面,很早就已经在说递归。还记得递归这种东西他们是结合小海龟一起折腾人的。现在回想起来,这或许是个正确的选择。因为小海龟是一个画图的东西,会让你用更直观地去理解递归到底在做什么。我还记得他们要我们理解的那个树杈和雪花。树杈那个图还算是一个比较正经的东西,雪花那个图案,简直是让我头皮发毛。每次说起递归,我就会想起小时候家里那个卷纸筒。黄色的卷纸筒上面,有一个卡通熊猫在拉卷纸的图案,而它拉的那个卷纸筒上面也贴着一个熊猫在拉卷纸。每次看到纸筒上的那个图案,我就会盯着看,然后脑子就会不断想象,熊猫卷纸筒,熊猫卷纸筒……想着想着甚至会觉得好恐怖,到底什么时候才是个头!这跟俄罗斯的套娃不一样。我总觉得,俄罗斯套娃无论套子多精细,总会有个头,但是,拉卷纸的熊猫,对我来说简直是个噩梦。我觉得,拉卷纸的熊猫是递归,而套娃是循环。

昨天我花了大半天的时间查单位的某些账本。查出了一箩筐的问题,我不知道为什么之前他们检查居然没发现。绝大多数都是弱智的问题,不弱智的问题则代表了他们做事的时候根本没用脑子去思考。那些莫名其妙的错误几乎到达了一种人人都有永不落空的境地。这也实在是太强大了吧!归根到底,是因为根本没有人去统一他们。每个人都看着那个规则,每个人都有自己的理解,又或者他们没看规则,只是按照上一个人的方法去做,但是他们对上一个人的做法的理解又各不相同。情况就像一个人不断地传话给下一个人,当人数传到一定程度的时候,原本的故事就会变得乱七八糟。我还记得第一次发现这个现象是在翡翠台的综艺节目超级掌门人上。这是我第一次认真地去揪他们的错误。不只是核对核心数据,也看了格式上到底合不合要求。有时我真的不明白他们,这样干活,他们觉得自己对得住自己的工资吗?他们晚上为什么居然能睡得着觉?换个说法,为什么他们这般吊儿郎当却没有东西惩罚他们?即便不是金钱上的惩罚,但起码也要让他们心里不好过,比如批评一下。但或许批评根本无效,就像你妈妈骂你一样,左耳进右耳出,就只是一阵耳边风。既然不能用惩罚,能不能用奖励的机制呢?在这个单位,爬上去的那些人你也说不上到底牛逼在哪里。没有惩罚,也没有奖励,于是也就可以理解,为什么他们会这样。

不是人人都能自律,对不自律的人必须用铁手腕。

2020-04
18

死磕二分法搜索

By xrspook @ 15:00:07 归类于: 扮IT

我是看着题目的中文版做题的

练习10:要检查一个单词是不是在上面这个词汇列表里,你可以使用 in 运算符,但可能会很慢,因为这个 in 运算符要从头到尾来搜索整个词汇表。我们知道这些单词是按照字母表顺序组织的,所以我们可以加速一下,用一种对折搜索(也叫做二元搜索),这个过程就和你在现实中用字典来查单词差不多。你在中间部分开始,看看这个要搜索的词汇是不是在中间位置的前面。如果在前面,就又对前半部分取中间,继续这样来找。当然了,不在前半部分,就去后半部分找了,思路是这样的。不论怎样,每次都会把搜索范围缩减到一半。如果词表包含了113809个单词,最多就是17步就能找到单词,或者能确定单词不在词汇表中。那么问题来了,写一个函数,名为 in_bisect,接收一个整理过的按照字母顺序排列的列表,以及一个目标值,在列表中查找这个值,找到了就返回索引位置,找不到就返回空。

做到死去活来词语在词汇表里有索引正确,没有时却会疯掉的时候我不得不去看答案,看到答案后傻眼了,答案对单词的判断只有True和False,再去找原题,我那个去,题目改了!不要求索引了好吗!

Exercise 10: To check whether a word is in the word list, you could use the in operator, but it would be slow because it searches through the words in order. Because the words are in alphabetical order, we can speed things up with a bisection search (also known as binary search), which is similar to what you do when you look a word up in the dictionary (the book, not the data structure). You start in the middle and check to see whether the word you are looking for comes before the word in the middle of the list. If so, you search the first half of the list the same way. Otherwise you search the second half. Either way, you cut the remaining search space in half. If the word list has 113,809 words, it will take about 17 steps to find the word or conclude that it’s not there. Write a function called in_bisect that takes a sorted list and a target value and returns True if the word is in the list and False if it’s not. Or you could read the documentation of the bisect module and use that! Solution: http://thinkpython2.com/code/inlist.py.

又纠结一番后我终于写出了一句“first > last”返回例外情况,终于,世界被拯救了!记录索引和不记录索引很不一样啊,按照参考答案的解法,i即便返回也永远是1,索引无能。纠结是有好处的,让我明白到二分法搜索有多么的高效,简直甩while循环几十条街,但如果真索引的话,估计我会很懒地直接用list.index(),虽然用之前必须用in历遍列表,判断是否存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import time
def in_bisect(library, first, last, myword): # 二分法搜索,10万数据查询最多只需不到20步
    if first > last: # 这是一句拯救了我的条件
        return None
    else:
        mid = (first + last)//2
        if myword == library[mid]:
            return mid
        elif library[mid] > myword:
            return in_bisect(library, first, mid-1, myword)
        else:
            return in_bisect(library, mid+1, last, myword)
myword = 'zoo' # input('myword is: ')
i = 0
library = []
fin = open('words.txt')
for line in fin:
    word = line.strip()
    library.append(word)
library.sort()
start = time.time()
 
# j = 0
# while i < len(library) - 1: # 我的脑洞第一反应用的循环
#     if myword == library[i]:
#         j = i
#         break
#     i += 1
# if j == 0:
#     print('myword is not in library')
# else:
#     print('index =', j)
 
# if myword in library: # 伟大列表自带的查询索引号,但先得确定单词在那里
#     i = library.index(myword, 0, len(library)-1)
# if i == 0:
#     print('myword is not in library')
# else:
#     print('index =', i)
 
if in_bisect(library, 0, len(library), myword) == None: 
    print('myword is not in library')
else:
    print('index =', in_bisect(library, 0, len(library), myword))
end = time.time()
print(end-start)
# myword is not in library while 0.07   index 0.003  bisect 0.001
# apple 4450               while 0.003  index 0.001  bisect 0.001
# zoo 113707               while 0.07   index 0.005  bisect 0.001
# while,index和bisect没有对比就没有伤害
2020-04
10

强大到让我瑟瑟发抖的递归

By xrspook @ 8:41:56 归类于: 烂日记

大学学习C语言的时候,基本上我不会写单独的函数,所有要解决的事都在主函数里搞定了。当时我学过判断和循环,但是,我却从来没学过递归。在解决一些简单事情的时候,循环跟递归,没什么差别。从理解程度来说,我觉得循环更简洁一些,但是,当某个东西像套娃那样一层叠一层,每层里面依然用同样的规则继续套叠,不知道要叠多少层的时候。递归就会展现它无穷的魔力。循环难以实现这个,又或者循环并非实现不了,但是递归在完全不需要体现循环的框架下,简洁的语言就已经在做着循环的事情。

昨天,我第一次在Python里见到这个恐怖的递归。外国人的书,我觉得都有一个特点。正文的时候举的例子都很简单,但是一到习题,就会把你彻底搞死。习题里面会偷偷带入一些超纲的东西。大概写书的人理所当然默认你应该知晓。这种事情我已经在学习Java的时候领略过。当时那本书之所以没法看下去,就是因为我没办法想象出作者的脑洞到底是什么。他们的习题几乎可以说大多是一些填空题,但要实现一个功能,其实未必一定就得用某种方法。你给我一个条件,给我一些目标值,我能做出来也就OK了,为啥必须走你的路呢,这非常难。之前我不觉得自己跟外国人的脑洞到底差多远,但是当我对比过自己和他们写的程序以后,我发现真的差挺远的。虽然我们都能实现某个功能,就效率而言,感觉上没差多少,因为我只是在做一些非常初级的东西。应试教育的时候,有标准答案,当然好判定成绩,但实际上,编程这种东西真心应该天马行空。给我一个效率的限制,比如说完成某件事,必须在多长时间之内解决,代码长度不能多于多少,至于我用什么办法,这是我的事。

说回递归函数这件事,在处理几个简单数字的时候,可能你感觉不到它的强大,但是,当我见识过用那个东西画出来的层级图形以后,我简直就只有站在旁边瑟瑟发抖的份儿。真的不知道是哪个神经质想出来这么强大的东西。但实际上,深究下去,那也不是很强大,那不过是不断地重复一些已经设计好的事情而已。如果要人去做那些重复,一开始还好,但是随着事情的深入,会慢慢乱套,但是计算机不会,他们会一根筋地执行我们的指令。最终出来的结果是令人惊叹的优雅,还是乱七八糟一坨屎:就得看设定规律的人的功力了。

递归现在对我来说是一个非常恐怖的东西。因为我不了解它,所以我害怕它,就像当年认识循环一样。但是,用好递归以后,我的武器库里就会增加一个杀伤性非常大的家伙。说到递归,让我联想起新冠病毒。这个东西的递归到底什么时候才是个头?我觉得这肯定不是一个死循环,自然界非常擅长递归,处处都是数学和逻辑你知道吗?!但是,到底要递归多少次,全人类才最终能看到隧道尽头的曙光呢?到底这个新冠病毒函数的递归里埋伏了多少个随机数呢?学习递归让我明白到,层级少好对付,层级一旦扩增,那就是次数级的增长,而且,说不准到达一定层级的以后就会触发某些大招炸弹,想想都心寒。

编程是一个让我重新理解自然规律的过程。

© 2004 - 2024 我的天 | Theme by xrspook | Power by WordPress