DouKaku?beta

Comment detail

BFコンパイラー (Nested Flatten)

This comment is reply for 3963 dpp: 自己ツッコミ。 このままだと"～[]～...(BFコンパイラー). Go to thread root.

これまたifの羅列をHashに置き換え。ただし、pythonの場合、[]は少し特別扱いが必要。こちらはindent不要とは行かないので。 あと、関数名やインターフェースも好みにあわせて変えました。

Dan the Novice Snake Tamer 

 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
#!/usr/bin/env python
import sys
from getopt import getopt

def bf2py(bfcode):
    depth = 0
    opcode = {
        '>':'ptr += 1',
        '<':'ptr -= 1',
        '+':'tape[ptr] = tape.get(ptr, 0) + 1',
        '-':'tape[ptr] = tape.get(ptr, 0) - 1',
        ',':'tape[ptr] = sys.stdin.read(1)',
        '.':'sys.stdout.write(chr(tape.get(ptr, 0)))',
        '[':'while tape.get(ptr, 0):',
        ']':'pass'
    }
    pycode = []
    stack = []
    
    pycode.append('import sys')
    pycode.append('tape, ptr = {}, 0')
    
    for c in bfcode:
        if opcode.has_key(c):
            pycode.append( '\t' * depth + opcode[c])
            if c == '[':
                stack.append(depth)
                depth += 1
            elif c == ']':
                depth = stack.pop()
     
    return '\n'.join(pycode)

if __name__ == '__main__':
    defout = 'a.py'
    optlist, args = getopt(sys.argv[1:], 'o:', [])
    if args:
        pysrc = bf2py(''.join(file(args[0]).readlines()));
        file(defout or ops['-o'], 'w').write(pysrc)

せっかくなので++++がbf.inc(4)に置き換わるような設計にしてみました。

この程度の規模なら正規表現でも十分いけるんじゃないかと思いつつ勉強がてらにlexとyaccを使いました。

PLY (Python Lex-Yacc)

あとインデントうんぬんを考慮しないといけないのはそもそも直接while文を使うからなので式で表現しました。

,+[-.,+]を入力するとbf.get()or bf.inc(1)or bf.loop(lambda: bf.inc(-1)or bf.put()or bf.get()or bf.inc (1))と出力されます。

下のFizzBuzzコードを食わせると2638バイトの出力で、処理時間はあっという間でした。 http://d.hatena.ne.jp/n_shuyo/20070516/fizzbuzz

  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
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
from ply import lex, yacc
import sys

# lex
tokens = "PLUS MINUS LEFT RIGHT WHILE WEND PUT GET COMMENT".split()

t_WHILE = "\["
t_WEND = "]"
t_PUT = "\."
t_GET = ","

def t_PLUS(t):
    "\++"
    t.value = len(t.value)
    return t

def t_MINUS(t):
    "-+"
    t.value = len(t.value)
    return t

def t_LEFT(t):
    "<+"
    t.value = len(t.value)
    return t

def t_RIGHT(t):
    ">+"
    t.value = len(t.value)
    return t

def t_COMMENT(t):
    '[^[\]><+-,.]' # return nothing

def t_error(t): pass
    
# yacc
"""*** grammar definition
sequence : sequence command
         | command

command : PLUS
        | MINUS
        | LEFT
        | RIGHT
        | PUT
        | GET
        | loop

loop : WHILE sequence WEND
"""

def p_sequence(p):
    "sequence : sequence command"
    p[0] = p[1] + "or " + p[2]

def p_sequence_command(p):
    "sequence : command"
    p[0] = p[1]

def p_command_PLUS(p):
    "command : PLUS"
    p[0] = "bf.inc(%s)" % p[1]

def p_command_MINUS(p):
    "command : MINUS"
    p[0] = "bf.inc(%s)" % -p[1]

def p_command_LEFT(p):
    "command : LEFT"
    p[0] = "bf.mov(%s)" % -p[1]

def p_command_RIGHT(p):
    "command : RIGHT"
    p[0] = "bf.mov(%s)" % p[1]

def p_command_PUT(p):
    "command : PUT"
    p[0] = "bf.put()"

def p_command_GET(p):
    "command : GET"
    p[0] = "bf.get()"

def p_command_loop(p):
    "command : loop"
    p[0] = p[1]
    
def p_loop(p):
    "loop : WHILE sequence WEND"
    p[0] = "bf.loop(lambda: %s)" % p[2]

def p_error(p): pass

# input and parse
data = sys.stdin.read()
lex.lex()
yacc.yacc()
result = yacc.parse(data)

# output
print """
from collections import defaultdict
import sys
class BF(object):
    mem = defaultdict(int)
    cur = 0
    def inc(self, n):
        self.mem[self.cur] += n
        self.mem[self.cur] %= 256
    def mov(self, n):
        self.cur += n
    def put(self):
        c = chr(self.mem[self.cur])
        sys.stdout.write(c)
    def get(self):
        c = sys.stdin.read(1)
        self.mem[self.cur] = ord(c)
    def loop(self, seq):
        while self.mem[self.cur]:
            seq()

bf = BF()
"""

print result

素数探索のコード：

http://labs.cybozu.co.jp/blog/kazuho/archives/2006/06/bf_prime.php

さすがに結構時間がかかるなー。Core2Duo @2.4GHzで1分くらい。

real    1m2.317s
user    0m0.015s
sys     0m0.031s

8行修正して[-]を単体で「リセット命令」にしたらreal　0m54.380sになった。

うーん、これ以上高速化するとなるとコピーの処理を置き換えるとかになりそうだけど、それは正規表現では無理な気がするなぁ。パースしながら出力文字列を作るのをやめて、sequenceを文字列に変換する際にmovとincだけで構成されているかどうかをチェックして…となるのかな。面倒だな。

Pythonだとこれだけ時間がかかるんですね。
参考になります。

Scalaでもやってみたところ、#3960のコードで
出力したものを、コンパイルせずインタプリタで
実行しても1秒以内に結果が出ました。
Scalaは実はできる子です（笑

うーん、それはちょっと違いますね。 #3960のコードはコードを一つの関数の中にローカルに展開しているのに対して、上のコードは一つ一つの命令がメソッド呼び出しですから。PythonとScalaの性能の違いと言うより、生成されたコードの質の違い思います。

# 要するに僕のコードが生成したのは質が悪いと！orz

毎回bf.fooとメソッド名の解決をしているのをやめるとreal：0m32.481sになり、きちんとインデントするようにしたら(毎回関数呼び出しをするのをやめたら)real：0m15.548sになりました。

それでもScalaには全然追いつかないのか…orz

コードを張り忘れたので。
 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
51
52
53
54
55
56
57
58
59
60
61
def p_sequence(p):
    "sequence : sequence command"
    p[0] = p[1] + p[2]

def p_sequence_command(p):
    "sequence : command"
    p[0] = p[1]

def p_command_PLUS(p):
    "command : PLUS"
    p[0] = "\nmem[cur] = (mem[cur] + %s) %% 256" % p[1]

def p_command_MINUS(p):
    "command : MINUS"
    p[0] = "\nmem[cur] = (mem[cur] - %s) %% 256" % p[1]

def p_command_LEFT(p):
    "command : LEFT"
    p[0] = "\ncur -= %s" % p[1]

def p_command_RIGHT(p):
    "command : RIGHT"
    p[0] = "\ncur += %s" % p[1]

def p_command_PUT(p):
    "command : PUT"
    p[0] = "\nsys.stdout.write(chr(mem[cur]))"

def p_command_GET(p):
    "command : GET"
    p[0] = "\nmem[cur] = ord(sys.stdin.read(1))"

def p_command_RESET(p):
    "command : RESET"
    p[0] = "\nmem[cur] = 0"

def p_command_loop(p):
    "command : loop"
    p[0] = p[1]
    
def p_loop(p):
    "loop : WHILE sequence WEND"
    p[0] = "\nwhile mem[cur]:%s" % p[2].replace("\n", "\n    ")

def p_error(p): pass

# input and parse
data = sys.stdin.read()
lex.lex()
yacc.yacc()
result = yacc.parse(data)

# output
print """
from collections import defaultdict
import sys
mem = defaultdict(int)
cur = 0
"""

print result

あ、確かにそうですね。見落としてました。

せっかくなので#3952の素朴なタイプでも手元で時間とって見ましたが、

dppさんの#3952：55秒程度
にしおさんの#3988：2分10秒程度

でした。

あと、メモリとしてdictを使っているけど、
[0]*0xffffみたいにリストで長さ決めうちにすると
だいぶマシですね。55 -> 31秒程度まで短縮できました。

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]