文字列の繰り返し（追従記事）

Python

id:hogelog による記事： 文字列の繰り返し - hogeなlog を見たので、Windows上のPython Shell上で試してみた。

def naive(s, i):
	st = ""
	for x in xrange(i):
		st = st + s
	return st

def beki(s, i):
	if i < 1:
		return None
	if i == 1:
		return s
	elif i&1 == 1:
		return beki(s, i-1) + s
	else:
		res = beki(s, i/2)
		return res + res

って感じで。アルゴのリズムは冪乗 - Wikipediaの後者を参考に。

>>> def keisoku(i):
	s = time()
	naive("a",i)
	print "naive : %f" % (time() - s)
	s = time()
	beki("a",i)
	print "beki  : %f" % (time() - s)


>>> keisoku(100)
naive : 0.000000
beki  : 0.000000
>>> keisoku(5000)
naive : 0.000000
beki  : 0.000000
>>> keisoku(50000)
naive : 0.000000
beki  : 0.000000
>>> keisoku(500000)
naive : 0.094000
beki  : 0.000000
>>> keisoku(5000000)
naive : 3.843000
beki  : 0.016000
>>> keisoku(50000000)
naive : 360.109000
beki  : 0.109000

論理からすると当たり前だけど、冪乗にした方が文字列コピーの回数が少なくなるので断然早いですね！
元記事は「処理系とかのソースコードには叡智が詰まってんぜー」というノリですが、ちょいと試してみたかったので、まあ。


研究とは全く関係ないけどね！！


最後の360秒はわりと待ってんのつらかった。もう眠いよ。