Kevin_K edited 6 年，1 月前
# 为什么用Python:人生苦短.
# 准确的说使用Python可以获得更好的输入输出效果.
# 使用re模块.
import re
# 其他必要模块.
import os
import random
# 这个是xlsxwriter第三方模块.可以pip安装.没有的话可以直接删除.用到的地方我会用一串####...隔开.
#################
try:
import xlsxwriter
except:
print('No xlsxwriter!')
#################
# 以下打开文件,支持自动搜索以双城记文本文档本来的名字命名的txt文件,没有的话会提示自己输入文件名.
try:
fileObject = open('A Tale of Two Cities - Charles Dickens.txt')
except:
# 本来是'没有找到,请输入文件名',但我电脑乱码了,机翻成英语了,下同.
print('Did not find, please enter the file name (*.txt):', end=' ')
while 1:
try:
fileObject = open(input() + '.txt')
break
except:
print('Did not find, please enter the file name (*.txt):', end=' ')
# 读文件.
try:
c = fileObject.read()
finally:
fileObject.close()
# 用正则处理文本,为什么正则了这些字符呢?这些字符是用程序预处理找出了文本中非字母字符.(其实下面''中都是预处理程序直接生成的)
# 显然这样处理文本是会出问题的,但真正的找到双城记中不同的单词实际上是一件困难的事情.
# 同一个单词可以有不同的形式,区别这些单词是困难的,用'-'连接的算几个单词?
# 基于以上几种(其实还有更多的)问题,征求老师意见后,我们决定不纠结于部分单词产生的误差中.
# l列表记录双城记中取出的所有单词.
l = re.split(
'\:|\;|2|\-|1|7|\+|\'|\¡|\.|\(|\=|6|\n|\`|\]|5|\¦|9|\[|\)|\"|\,|\ |\?|\*|\¨|\!', c)
# 使大小写不敏感.
l = [x.lower() for x in l]
# 以下是散列的规模数组:
M = [97, 997]
# 定义散列函数:
def hashF(s, x): # s为单词,x为模的大小.
# 以下是一个分支选项,可以使用python自带的散列函数,但效果和我自己写的好像差不多?
# 不过最大最小频率确实比我写的好多了!
# 选用只需将下面的'#'删除.
return hash(s) % x
h = 0
for i in range(len(s)):
# 重要:为什么是1000?因为多次实验中1000的效果莫名的好!
h = h * 1000 + ord(s[i])
return h % x
# 准备模拟表:
# 重要:我认为随机模拟100000次,单词的选取是个大问题.
# 如果随机生成"单词",哪如果长度为5,就有26**5=11881376,双城记的单词数在这个数量下就已经太过渺小.
# 相当于选的单词都是找不到的了,所以为了让结果更加有意义,我随机选取双城记中出现过的单词.
# 不过不同的单词由于出现次数不同所以选中的概率也不同,这个随机有点微妙啊.
# 本来如果能有张模拟单词表就很nice了...
words = []
for i in range(100000):
words += [l[random.randint(0, len(l) - 1)]]
# 开始处理.
for _ in range(len(M)):
mold = M[_] # 方便调用.
res = [[] for i in range(mold)] # res即哈希表.
cnt = 0 # 计数器
# 散列开始.
for i in range(len(l)):
row = hashF(l[i], mold) # 确定散列到哪里.
isPresence = 0 # 默认不存在在行中.
for j in range(len(res[row])):
if res[row][j] == l[i]:
isPresence = 1 # 找到了就改为存在.
break
if not isPresence:
res[row] += [l[i]] # 不存在则加入行中.
cnt += 1
rowSize = [len(x) for x in res] # 记录行宽的列表.
# 散列结束,模拟查找次数开始:
fcnt = 0 # 总比较次数.
for i in range(len(words)):
row = hashF(words[i], mold)
for j in range(rowSize[row]):
fcnt += 1
if res[row][j] == words[i]:
break
fcnt //= len(words)
# 接下来我们来进行数据的输出.
# 我将用txt和Excel分别输出数据,txt的数据会更详尽,但Excel表格方面会做的更棒.
data = 'Average number of comparisons found: %d\nTotal number of words: %d\nAverage number of words per line: %d\nMaximum number of words per line: %d\nMinimum number of words per line: %d\n' % (
fcnt, cnt, cnt // mold, max(rowSize), min(rowSize))
# 创造一个简易柱状图.
for i in range(len(rowSize)):
for j in range(max(rowSize[i], cnt // mold)):
data += ':' if j == cnt // mold - \
1 else '|' if j < rowSize[i] else ' '
data += '\n'
# 最后补一手数据对应关系:
for i in range(len(rowSize)):
data += '%d:%d\n' % (i, rowSize[i])
fileObject = open('mold%d.txt' % mold, 'w')
fileObject.write(data) # 写入数据.
fileObject.close()
# txt写完了,然后让我们写一个Excel.
#################################################################
try:
workbook = xlsxwriter.Workbook("mold%d.xlsx" % mold)
worksheet = workbook.add_worksheet()
headings = ['KeyValue', 'Frequency']
data = [[i for i in range(mold)], [rowSize[i] for i in range(mold)]]
worksheet.write_row('A1', headings)
worksheet.write_column('A2', data[0])
worksheet.write_column('B2', data[1])
chartCol = workbook.add_chart({'type': 'column'})
chartCol.add_series({
'name': '=Sheet1!$B$1',
'categories': '=Sheet1!$A$2:$A$%d' % mold,
'values': '=Sheet1!$B$2:$B$%d' % mold,
'line': {'color': 'blue'},
})
chartCol.set_title({'name': '散列值出现频率'})
chartCol.set_x_axis({'name': '散列值'})
chartCol.set_y_axis({'name': '频率'})
worksheet.insert_chart('C1', chartCol, {'x_offset': 0, 'y_offset': 0})
workbook.close()
except:
print('Something went wrong, it may be that you have not installed xlsxwriter, or you need to close the output file.')
#################################################################