2020-04
21

PK我自己

By xrspook @ 19:04:38 归类于: 扮IT

用了几分钟时间，写了个用字典法查找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 # 字典法搜索
标签：, , , , , , , ,
还没有评论
2020-04
21

字典真牛

By xrspook @ 12:03:27 归类于: 扮IT

字典用好了以后666得不知道该如何形容。创造字典，搜索词典，快得就像眨眼间。列表需要考虑的长度问题，字典里一个in就高效快捷了。

这是一道扯淡的习题，因为条件没固定，参考答案可以怎么参考呢？

Exercise 5: Two words are “rotate pairs” if you can rotate one of them and get the other (see rotate_word in Exercise 5). Write a program that reads a wordlist and finds all the rotate pairs. Solution: http://thinkpython2.com/code/rotate_pairs.py.

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

def rotate_word(something, n): # a-z: 97-122, A-Z: 65-90
    newletter1 = ''
    for letter in something:
        if ord(letter) < ord('A') or ord('Z') < ord(letter) < ord('a') or ord('z') < ord(letter):
            newletter2 = newletter1 + letter
        else:
            if ord(letter) + n > ord('z'):
                newletter2 = newletter1 + chr(ord(letter) + n - 26)
            elif ord('a') > ord(letter) + n > ord('Z'):
                newletter2 = newletter1 + chr(ord(letter) + n - 26)
            else:
                newletter2 = newletter1 + chr(ord(letter) + n)
        newletter1 = newletter2
    return newletter2
def set_dict(fin):
    d = {}
    for line in fin:
        word = line.strip().lower()
        d[word] = 0
    return d
fin = open('words.txt')
count = 0
d = set_dict(fin)
for word in d:    
    for i in range(1, 14): # 8.13.5的习题没有说要移多少位，参考答案直接定义为1-14位，你猜我在想什么
        if rotate_word(word, i) in d:
            print(word, i, rotate_word(word, i))
            count += 1
print(count)
# ......
# zax 1 aby
# zax 4 deb
# zebu 7 glib
# zebu 10 jole
# zee 1 aff
# zee 9 inn
# zips 12 lube
# zoa 6 fug
# zoa 12 lam
# 1137
标签：, , , , , , , ,
还没有评论
2020-04
21

循序渐进

By xrspook @ 9:25:39 归类于: 烂日记

我觉得必定把我搞死的筛选词汇表里的二锁三锁单词，居然不怎么费劲就做出来了。

第一次，我在里面用了一个很傻的循环，其实根本就没有必要。可以不用自己的循环就千万不要在词汇表搜索时多用，但我的第一次尝试并不是毫无意义的，，因为已经能得出结果了，而且结果是对的，虽然非常慢，慢到我无法忍受程序继续运行下去。然后，我把要搜索的东西全部都丢到二分法搜索里面，循环只剩下一个必须做的，因为要把词汇表过一遍。第一次做二词互锁的时候，我在一个循环里套了两个if，然后我又把那两个if做成平行的，其实也就是把两个本来嵌套起来的条件用一个and连接起来，很多时候我们都需要这么干。因为除了要二锁，还要考虑三锁，显然人肉去做这些判断，写一大堆一模一样的东西实在太无聊，所以我又自定义了一个新函数，把需要判断的东西全部都丢掉里面，最终返回True或者False。其实，之前我已经考虑过要直接这么干，但因为前天在做搜索回文词的时候我已经得出了回文词的索引，所以直接用就好。我个人觉得，效果是差不多的。

在搜索互锁单词的时候，输出时我用的是字符串的变体。因为二分法搜索被我丢到了一个多条件复合的判断函数里面，所以返回的东西，只有True与False。如果全部都是True的话，就意味着那些单词辩题应该全部都OK没问题。也正是因为输出的东西已经没有索引返回，所以结果我直接使用单词的变体表示。这样的效果很惊人。之前我套用了两个if，然后我写了一个判断函数把条件都含进去了，这样的改进让脚本的运行时间缩短了一半。如果一开始我没有见过两秒多的那个效果，我肯定不会为一秒多的那个惊叹。这是我一步一步琢磨出来了的。

首先是实现得出结果，然后是对语句进行重构，接下要让这个程序适用于二、三词互锁，所以我做的东西是泛化。一开始我把所有判断都写在主程序里，后来我又把它分出一个函数，也就是封装。无意之中，我在执行着Think Python第四章里说到的开发方法：写小程序、封装、泛化、重构。无论是大程序还是小程序，其实都会经历这些。我会从一些我最熟悉的东西开始实现功能。但是我最熟悉的东西不意味着效率一定会高。循环再循环以后，得出一个词都要好几秒时间，实在让人难以接受，尤其当这个词到下个时中间要相隔几秒甚至是十几秒才有反应的时候。这就逼迫着我一定要改进，不同的语句能实现同样的功能，但是它们之间的效率是非常不一样。

大家都在用着二分法的思路去搜索，但是我的脚本就比参考答案快接近30倍。单词一蹦出来，我就知道我一定会比参考答案快。因为我的程序里，单词是噼里啪啦完全没有停顿就全部出来的，而参考答案的词语出来的时候虽然不会一直有，但总有一些顿卡现象，那相对于我的程序来说，就像是慢镜头。

我从来没有想过自己能做得比参考答案还要好，或许他们要做到的并不是有多快。相比于不是二分法的搜索，二分法已经很快了。他们想做到的，大概是用最简练的语言，用模块化的方法实现功能，效率倒不是他们最看重的，因为做搜索词汇表这种事在列表里完成肯定比不上直接上字典。但是，如果不曾在列表里面死去活来，又怎么会体验到字典的神奇。

无论我的二分法搜索写得多么高效，肯定还是不如字典的。我体验过用词典进行斐波那契常数计算。当要计算第40个的时候，一般的递归和字典递归简直就是天渊之别。

如果不曾经历，不曾被整得很惨，我大概就不能说自己真学会了那个东西。

标签：, , , , , , , , , ,
还没有评论
2020-04
20

更爽

By xrspook @ 12:00:26 归类于: 扮IT

战胜参考答案从昨晚开始貌似就成了我最大的快乐。互锁词的生成要比昨天的回文词复杂一些，因为这意味着搜索的次数更多了。虽然都是用二分法搜索的思路，但我就是要比参考答案快接近30倍肿么破。至于为什么会这样，我没有研究，或许我应该仔细研究一下。

10万条的单词表里：二词互锁1254条，我用时1.4秒，参考答案用时39.1秒；三词互锁991条，我用时1.5秒，参考答案用时43.4秒。一箩筐的成就感啊啊啊啊啊啊啊～～～

Exercise 12: Two words “interlock” if taking alternating letters from each forms a new word. For example, “shoe” and “cold” interlock to form “schooled”. Solution: http://thinkpython2.com/code/interlock.py. Credit: This exercise is inspired by an example at http://puzzlers.org. Write a program that finds all pairs of words that interlock. Hint: don’t enumerate all pairs! Can you find any words that are three-way interlocked; that is, every third letter forms a word, starting from the first, second or third?

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

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)
def interlock(library, i, num):
    m = 0
    n = num
    while m < num:
        if in_bisect(library, 0, len(library)-1, library[i][m::n]) == -1:
            return False
        else:
            m += 1
            n -+ 1
    return True
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): # 二词互锁
#     if interlock(library, i, 2):
#         print(library[i], library[i][::2], library[i][1::2])
#         count += 1
for i in range(len(library)-1): # 三词互锁
    if interlock(library, i, 3):
        print(library[i], library[i][::3], library[i][1::3], library[i][2::3])
        count += 1
print(count)
end = time.time()
print(end - start)
# 1254, 1.3558001518249512 # 二词互锁 xrspook解法
# 1254, 39.10080027580261  # 二词互锁 参考答案
# 991, 1.4504001140594482  # 三词互锁 xrspook解法
# 991, 43.366000175476074  # 三次互锁 参考答案
标签：, , , , , , , , ,
还没有评论
© 2004 - 2024 我的天 | Theme by xrspook | Power by WordPress
Go to top