问题求解报告03(部分)

Kevin_K edited 2 年,4 月前

# 为什么用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.')
    #################################################################

Comments

你当前正在回复 博客/题目
存在问题!