首页
Search
1
Linux 下 Bash 脚本 bad interpreter 报错的解决方法
46 阅读
2
Arch Linux 下解决 KDE Plasma Discover 的 Unable to load applications 错误
38 阅读
3
如何在 IOS Shadowrocket 上配置服务
34 阅读
4
Arch Linux 下解决 KDE Plasma Discover 的 Unable to load applications 错误
34 阅读
5
如何在 Clash for Windows 上配置服务
30 阅读
clash
服务器
javascript
全部
游戏资讯
登录
Search
加速器之家
累计撰写
635
篇文章
累计收到
0
条评论
首页
栏目
clash
服务器
javascript
全部
游戏资讯
页面
搜索到
635
篇与
的结果
2024-09-10
NFA与DFA的转换与优化
上一节《编译原理》课讲到了NFA(不确定的有穷自动机)向DFA(确定的有穷自动机)转换。考试要考,所以要手写变换过程,很繁琐,也很有趣。所以周末用python给实现了,并利用动态规划进行优化。转换方法这里主要涉及到对状态集合I的两个操作: 求ε-闭包。表示为ε-closure(I),是指I中的任何状态S经过任意条ε弧能到达的状态的集合。 求I的α弧转换。表示为move(I,α),是指I中某一状态经过一条α弧到达的状态的集合。 比如说这里有一个NFA N:因为NFA是一个五元组,N=(K,E,f,S,Z),即为(状态集合,弧集合,转换集合,开始状态集合,终结状态集合),所以由图可知:NFA N = ({0,1,2,3,4,5,6,7,8,9,10},{a,b},f,{0},{10}),其中 f(0,ε) = {1} f(1,ε) = {2,4} f(2,a) = {3} f(3,ε) = {6} f(4,b) = {5} f(5,ε) = {6} f(6,ε) = {1,7} f{7,a} = {8} f(8,b) = {9} f(9,b) = {10} 那么ε-closure(0)={0,1,2,4,7}move({0,1,2,4,7},a) = {3,8}ε-closure({3,8})={1,2,3,4,6,7,8}可以借助表格来观察整个求解过程,每次求解后如果产生新集合,就会记录下来继续算,直到没有新集合为止。 T A=ε-closure(move(T,a)) B=ε-closure(move(T,b)) ε-closure(s)={0,1,2,4,7}=T0 {1,2,3,4,6,7,8}=T1 {1,2,4,5,6,7}=T2 T1 T1 {1,2,4,5,6,7,9}=T3 T2 T1 T2 T3 T1 {1,2,4,5,6,7,10}=T4 T4 T1 T2 此时T列下的集合{T0,T1,T2,T3,T4}就是DFA的状态,其中含有NFA初始状态的集合为DFA的初始状态({T0}),含有NFA终结状态的集合为DFA的终结状态({T4})。所以由NFA转换后的DFA为:实现首先是数据存储格式,使用json存储NFA的五元组:{ "k" : ["0","1","2","3","4","5","6","7","8","9","10"], "e" : ["a","b"], "f" : { "0" : { "#" : ["1", "7"] }, "1" : { "#" : ["2", "4"] }, "2" : { "a" : ["3"] }, "3" : { "#" : ["6"] }, "4" : { "b" : ["5"] }, "5" : { "#" : ["6"] }, "6" : { "#" : ["1", "7"] }, "7" : { "a" : ["8"] }, "8" : { "b" : ["9"] }, "9" : { "b" : ["10"] } }, "s" : ["0"], "z" : ["10"] }读入时做了一些简单的判断,其实还可以做得更加周全,比如初始集s和终结集z是否被状态集k包含,等等。read()了之后就会把五元组包装返回。def read(input): try: nfa = json.load(open(input,"r")) for i in nfa["f"]: if not i in nfa["k"]: raise Exception("Set f contains iterms that not belongs to set k.") for j in nfa["f"][i]: if not j in nfa["e"] and not j == '#': raise Exception("Set f contains iterms that not belongs to set e.") return (set(nfa["k"]), set(nfa["e"]), nfa["f"], set(nfa["s"]), set(nfa["z"])) except IOError: print "File no found!" sys.exit(1) except (KeyError, TypeError): print "Input data error!" sys.exit(1) except Exception, e: print(e.args[0]) sys.exit(1)使用creat_memo()接下来为计算创建缓存,因为计算闭包有大量的重复计算。memo是一个字典,以e集合(弧集合)的元素为键,每一个键对应的值也是一个字典,在计算闭包的过程中缓存该状态的闭包。(见closure())def creat_memo(e_set): memo = {} for i in e_set: memo[i] = {} memo['#'] = {} return memo从文章开始时提到的转换方法很容易可以看到,两个操作有很大的相似性,所以我把它们封装成一个函数closure()了,调用时使用各自的接口。对应上面提到的弧转换操作,move()中的参数s和arc表示求move(s,arc),而ph_closure()的arc默认为ε,这里用"#"表示。def move(f, memo, s, arc): return closure(f, memo[arc], s, arc) def ep_closure(f, memo, s): return closure(f, memo["#"], s, '#')closure()是本程序的核心部分,当它接受了一个集合c_set时,会对c_set中的元素一一进行求闭包或者弧转换,再合并集合。在进行计算之前先查看缓存memo,看看之前有没有计算过,有就直接合并,没有就先计算出结果,在memo记录之后再进行合并。对于求闭包,因为是ε,所以每次要先包含本身,而弧转换则不需要。注意memo[s] = set([s]),必须是set([s])不能是set(s),因为s为字符串,set(s)会把s中的每个字符都拆开。接下来判断f转换中是否存在有关f(s,arc)的定义,存在的话: 闭包情况:深度优先递归的计算集合f(s,arc)的闭包,将它们合并回来。比如上面的NFA例子,一开始求ε-closure(0)的时候,发现f(0,ε)={1,7},所以继续计算ε-closure(1)和ε-closure(7)。.....一直计算到尽头。每次递归计算过程中也会在memo上记录,所以整个计算过程会越来越快。 弧转换情况:由于弧只需要判断状态s的下个一个arc弧连接的状态,所以不需要递归,直接得出结果。 def closure(f, memo, c_set, arc): res = set() for s in c_set: if not s in memo: memo[s] = set() if arc == '#': #Attention here. Has to be a list memo[s] = set([s]) if s in f: if arc in f[s]: if arc == '#': memo[s] |= closure(f, memo, set(f[s][arc]), arc) else: memo[s] = set(f[s][arc]) res |= memo[s] return rescreat_dfa返回一个空的dfa结构,calc_dfa代表了上面提到的表格的运算过程,并把表格的内容保存到dfa结构中。先对初始状态集k求闭包,接下来为每个弧求弧转换闭包ε-closure(move(s, arc))。出现新集合就交给queue队列,并在dfa["k"]中做记录。我这里是利用集合在dfa["k"]中的index作为dfa状态的命名。def creat_dfa(e_set): dfa = {} dfa["k"] = [] dfa["e"] = list(e_set) dfa["f"] = {} dfa["s"] = [] dfa["z"] = [] return dfa def calc_dfa(k_set, e_set, f, s_set, z_set): dfa = creat_dfa(e_set) dfa_set = [] memo = creat_memo(e_set) ep = ep_closure(f, memo, s_set) #Attention here. Has to be a list queue = deque([ep]) dfa_set.append([ep]) dfa["k"].append("0") dfa["s"].append("0") if not len(ep&z_set) == 0: dfa["z"].append("0") i = 0 while queue: T = queue.popleft() j = "" index = str(i) i = i + 1 dfa["f"][index] = {} for s in e_set: t = ep_closure(f, memo, move(f, memo, T, s)) try: j = str(dfa_set.index(t)) except ValueError: queue.append(t) j = str(len(dfa_set)) dfa_set.append(t) dfa["k"].append(j) dfa["f"][index][s] = j if not len(t&s_set) == 0: dfa["s"].append(j) if not len(t&z_set) == 0: dfa["z"].append(j) return dfa生成json的write_dfa和程序的其余代码:def write_dfa(dfa, f): f = open(f, "w") f.write(json.dumps(dfa)) f.close() def main(): (k_set, e_set, f, s_set, z_set) = read("NFA.json") dfa = calc_dfa(k_set, e_set, f, s_set, z_set) write_dfa(dfa, "DFA.json") if __name__ == '__main__'附上最后生成的json代码,就是上面的图DFA M{ "k": ["0", "1", "2", "3", "4"], "z": ["4"], "e": ["a", "b"], "s": ["0"], "f": { "1": { "a": "1", "b": "3" }, "0": { "a": "1", "b": "2" }, "3": { "a": "1", "b": "4" }, "2": { "a": "1", "b": "2" }, "4": { "a": "1", "b": "2" } } }
2024年09月10日
3 阅读
0 评论
0 点赞
2024-09-10
Jekyll-bootstrap Not Updating Problem Fixed
I had a jekyll blog on the github and changed it to Jekyll-bootstrap yesterday.I tested it locally, everything was ok. Pushed successfully. But my github pages didn't change.After debugging, I realised that the problem occured right after the theme hooligan was installed.To fix this problem, you only need to: Remove the _theme_packages file: git rm _theme_packages Create a .gitignore file in the root of your Page repository. Put _theme_packages/* into the file. Better install the theme again. This solution worked for me.我昨天把jekyll换成了jekyll-bootstrap,在本地测试成功,push也成功了。但是github pages一直没有改变。重复安装了很多次,终于发现当我安装完hooligan主题后,github pages就没反映了。最后发现是主题下载包_theme_packages跟github有冲突。所以,先remove掉git rm _theme_packages在根目录添加.gitignore文件,写入_theme_packages/*最好把主题重新安装一次如果上面的办法没用的话,我建议删掉仓库重新来一遍,我就是这样成功的,注意发布之后有可能要等一会才有效哦。
2024年09月10日
2 阅读
0 评论
0 点赞
2024-09-10
lcc内存对齐代码
今天看lcc源码内存对齐时看到一个roundup(x,n)宏#define roundup(x,n) (((x)+((n)-1))&(~((n)-1)))从字面意思看这个宏应该是用来向上取整的。但是(x+n-1)&(~(n-1))的确让人一时傻眼了。这里要从头说起,首先roundup(x,n)的作用就是向上取整,即求出最小的a * n,使得a*n >= x,即x = a * n - b (0
2024年09月10日
3 阅读
0 评论
0 点赞
2024-09-10
为mp3更新高清封面
我是个受不了安静的人,干活的时候没有音乐不行。我也是欧美音乐fans,多年来积累了不少或热门或冷门的音乐。无奈这些音乐大多没有封面,或者供应商为了节约流量用了压缩的小图,于是在移动设备上显示得惨不忍睹。忍了一段时间后终于忍不住了,亲自改一下。遍历mp3开始的时候当然是要先找到mp3文件了。使用os.walk递归的查找mp3,把文件名和路径存下来:import os def mp3_find(source_path): mp3_list = [] for root, dirs, files in os.walk(source_path): map(lambda x: mp3_list.append((root, x[:-4])), filter(lambda x: x[-4:] == '.mp3', files)) return mp3_list测试一下,放一些mp3文件在test文件夹:if __name__ == '__main__': mp3_list = mp3_find(r'test') print mp3_list读取id3信息接下来要读取mp3的id3信息,我用了eyed3,它不支持python3所以我用的是python2.7import eyed3,sys def mp3_load(mp3_path, mp3_name): try: id3 = eyed3.load(os.path.join(mp3_path, mp3_name+'.mp3')) return id3 except IOError: print ' '.join([mp3_name,'read error.']) sys.exit(1)测试一下mp3_process:def mp3_process(mp3_list): for path, name in mp3_list: id3 = mp3_load(path, name) print ' '.join(map(str, [id3.tag.title,id3.tag.artist,id3.tag.album])) if __name__ == '__main__': mp3_process(mp3_find(r'test'))搜索得到名字之后就要从网络抓取图片,这里使用了豆瓣音乐Api v2,参看音乐的返回格式,默认返回到是小图spic来的,手动改成大图lpic。这里使用了比较肮脏的手段去除ident的标点符号。import json,re def search(ident): ident = ident.translate(string.maketrans(string.punctuation, ' ')) url = r'http://api.douban.com/v2/music/search?q=' + ident mp3_json = json.load(urllib2.urlopen(url), encoding="utf-8") try: if mp3_json['count'] > 0: return re.sub(r'/spic/', r'/lpic/', mp3_json['musics'][0]['image']) except (KeyError, ValueError): pass return False有的mp3可能没有id3标签,所以如果search返回False的话还要按文件名搜一遍。修改mp3_process测试一下def mp3_process(mp3_list): for path, name in mp3_list: id3 = mp3_load(path, name) img = search(' '.join(map(str, [id3.tag.title,id3.tag.artist,id3.tag.album]))) if not img: img = search(name) if not img: continue写入封面因为我的音乐都是英语的,所以编码用latin1保持最大的可用性,utf-8和utf-16有的移动设备会显示不出封面,注意中文不能使用latin1。def mp3_burn(id3, img): id3.tag.images.set( type=3, img_url=None, img_data=urllib2.urlopen(img).read(), mime_type='image/jpeg', description=u"Front cover") id3.tag.save(version = (2, 3, 0), encoding = 'latin1')再次修改mp3_process测试一下,这次是最终版了def mp3_process(mp3_list): faild_list = [] for path, name in mp3_list: print '-- %s:' %name id3 = mp3_load(path, name) img = search(' '.join(map(str,filter(lambda x: x, [id3.tag.title,id3.tag.artist,id3.tag.album])))) if not img: img = search(name) if img: mp3_burn(id3, img) else: faild_list.append(name) return faild_list效果随机找来一坨mp3,如图,可以看到是没有封面的。跑一遍程序,再查看,(ubuntu下不知道怎么刷新缩略图缓存,我是把文件夹复制一份)后话豆瓣的api是有频率限制的,最好申请一个APIKey,或者使用代理,也可以在循环中加入sleep凑合用,一般情况都会没问题。完整源码在这里。
2024年09月10日
6 阅读
0 评论
0 点赞
2024-09-10
脆弱的力量
今天看到了个TED Talk “Brené Brown: The power of vulnerability”,讲者讲诉了自身的经历后得出结论要接受脆弱: Let ourselves be seen, deeply seen, vulnerably seen. Love with our whole hearts, even though there is no guarantee. Practice gratitude learn into joy. Believe that we are enough. 讲者还有一个重要的论点——我们在“麻痹脆弱”(numb vulnerability)。教父说过“Never hate your enemies. It affects your judgment.”我认为是讨厌做一件事才会麻痹(拖延),喜欢做的事从来不会拖延。像上不喜欢课经常会走神,而编程有时候爽起来会编通宵。而我的一个师兄有句口头禅“讨厌做一件事是因为做不好,做好了就会喜欢了”。是不是有点悖论的味道。但是很多时候就像冬天洗冷水澡一样,“忍一下就不痛了”。正所谓凡事开头难,但只有拿起球杆打几盘才知道合不合手。讲者还有个很有趣的定义Blame - A way to discharge pain and discomfort.以后想要责怪别人的时候想想这句话,把口收住。学学Vito Corleone的胸襟。最后奉上一张图,时刻警惕,不要成为工厂刻出来的模子瞎扯完了,洗洗睡。
2024年09月10日
3 阅读
0 评论
0 点赞
1
...
19
20
21
...
127