2020-04
21
PK我自己
用了几分钟时间，写了个用字典法查找10万单词的词汇表回文词的脚本。字典法肯定要比列表二分法快，但到底快多少呢？实测大概10倍。相比之下，字典法语言实在简练太多。二分法的函数还得考虑递归和起点终点神马，字典法一个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 -1 # 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) # j = 0 # count = 0 # library = [] # fin = open('words.txt') # for line in fin: # word = line.strip() # library.append(word) # library.sort() # start = time.time() # for i in range(len(library)-1): # 二分法搜索 # j = in_bisect(library, 0, len(library)-1, library[i][::-1]) # if j > -1 and library[i] < library[j]: # print(library[i], library[j]) # count += 1 # print(count) # end = time.time() # print(end - start) # 397, 1.2810001373291016 # 二分法搜索 import time def set_dict(fin): # 字典法搜索 d = {} for line in fin: word = line.strip() d[word] = 0 return d count = 0 fin = open('words.txt') start = time.time() mydict = set_dict(fin) for word in mydict: if word[::-1] in mydict and word < word[::-1]: print(word, word[::-1]) count += 1 print(count) end = time.time() print(end - start) # 397, 0.14300012588500977 # 字典法搜索 |
还没有评论