• 2x2的计算 (0+1*5+2*4+3*4+4)/16=1.8125
lt  发表于 2020-02-09 08:45:27
推荐
• 编了一个画图程序
n=2
g=2**(n*2)
for i in range(0,2**(n*2)):
print("area",i)
ch='□■'
s=bin(i+g)[3:]
x=0
for j in s:
x+=1
print(ch[int(j)],end='')
if x==n:print('');x=0
输出
area 0
□□
□□
area 1
□□
□■
area 2
□□
■□
area 3
□□
■■
lt  发表于 2020-02-09 10:24:14
推荐
• 还原4x4 5.76487732*65536=377807
lt  发表于 2020-02-10 04:28:13
推荐
• 一些测试
e(1,1) =(0+1)/2=1/2
e(2,1) =(0+1+1+2)/4=1
e(3,1) =(0+1*4+2*2+3)/8=11/8
e(4,1) =(0+1*7+2*5+3*2+4)/16=27/16
e(5,1)=(0+1*12+2*11+3*5+4*2+5)=62/32
e(6,1)=(0+1*20+2*23+3*12+4*5+5*2+6*1)/64=138/64
e(2,2)=(0+1*6+2*4+3*4+4)/16=30/16
e(3,2)=(0+1*16+2*16+3*14+4*10+5*6+6)/64=166/64
lt  发表于 2020-02-10 19:53:45
推荐
• pypy2快很多,4x4
(5.7648773193359375, 0.6999998092651367)
lt  发表于 2020-02-13 12:59:45
推荐
• 累计时间
>>>> print(setcolor(4,5),time.time()-tm)
(6.829985618591309, 128.9599997997284)
>>>> print(setcolor(4,6),time.time()-tm)
(7.778921723365784, 199.9229998588562)
>>>> print(setcolor(5,5),time.time()-tm)
(8.146968275308609, 348.0130000114441)

lt  发表于 2020-02-13 13:05:17
• 精确值
>>> 6.829985618591309*2**20
7161759.0
>>> 7.778921723365784*2**24
130508650.0
>>> 8.146968275308609*2**25
273366893.0

lt  发表于 2020-02-13 13:08:47
• 把类和对象换成全局函数/列表
(5.7648773193359375, 0.19499993324279785)

lt  发表于 2020-02-13 13:33:53
• 其实area和uf的内容重复，只有根[]值的正负不同，然后uf和color也不必每次新建
调整后
>>>> tm=time.time();print(setcolor(5,5),time.time()-tm)
(8.146968275308609, 120.75600004196167)

lt  发表于 2020-02-14 19:43:27
• 改写成c程序
递归
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31
8.14696828
Kernel Time = 0.031 = 0%
User Time = 18.096 = 88%
Process Time = 18.127 = 88%
Global Time = 20.515 = 100%

非递归
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31
8.14696828
Kernel Time = 0.000 = 0%
User Time = 19.156 = 89%
Process Time = 19.156 = 89%
Global Time = 21.320 = 100%

lt  发表于 2020-02-14 19:44:17
• 利用itpub上newkid的pl/sql代码改写的c程序
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31
8.14696828
Kernel Time = 0.000 = 0%
User Time = 7.488 = 88%
Process Time = 7.488 = 88%
Global Time = 8.443 = 100%

lt  发表于 2020-02-16 10:34:07
• 他的思路是用如下二进制位结构，这样下层可以重用上层的计算结果
1 2 5 10 17
4 3 6 11 18
9 8 7 12 19
16 15 14 13 20
25 24 23 22 21

lt  发表于 2020-02-16 10:38:31
• 我的思路是2块合并,比如2个4x4或8x2可以拼成1个8x4，这样可以利用小块已有的最大值和根，只需要计算两块的边界，大约能省一半时间
7 x 4
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31
2316532263 268435456
8.62975517

Kernel Time = 0.031 = 0%
User Time = 119.949 = 99%
Process Time = 119.980 = 99%
Global Time = 120.583 = 100%

Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31
5.76487732
4.56225586
2316532263 268435456
8.62975517

Kernel Time = 0.156 = 0%
User Time = 62.213 = 97%
Process Time = 62.369 = 97%
Global Time = 64.077 = 100%

8 x 4
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31
40363313539 4294967296
9.39781627

Kernel Time = 3.369 = 0%
User Time = 2205.276 = 99%
Process Time = 2208.646 = 99%
Global Time = 2224.916 = 100%

Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31
5.76487732
5.76487732
40363313539 4294967296
9.39781627

Kernel Time = 0.920 = 0%
User Time = 1096.952 = 99%
Process Time = 1097.872 = 99%
Global Time = 1106.203 = 100%

lt  发表于 2020-02-18 20:02:26
• newkid新的二分法比我的快2倍
6x 5
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31
9.33239948

Kernel Time = 0.031 = 0%
User Time = 107.796 = 97%
Process Time = 107.827 = 97%
Global Time = 110.347 = 100%

我的
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31
6.06586838
4.18261719
10020587641 1073741824
9.33239948

Kernel Time = 0.421 = 0%
User Time = 309.583 = 99%
Process Time = 310.005 = 99%
Global Time = 312.206 = 100%

lt  发表于 2020-02-20 16:29:10
• 用递归构造的01字符串,而不是0~2^(w*h)-1的二进制，可以利用前一步的结果，快了1半
def fill2(color,lv,p,uf):
global w,h,totalarea
n=w*h
if lv==n: totalarea+=n;return
j=p-1
if (j-1)%w>0 and j-1>0 and color[j]==color[j-1]: union(uf, j,j-1)
if j-w>0 and color[j]==color[j-w]: union(uf, j,j-w) #颜色相同的相邻格加入同一个集合
maxarea=uf[0]
for j in range(1,p):
if color[j]=='1' and -uf[j]>maxarea: maxarea=-uf[j] ;uf[0]=-uf[j]
totalarea+=maxarea
for i in range(p,n+1):
tmpu=[x for x in uf] #save current uf
color[i]='1'
fill2(color,lv+1,i+1,uf)
color[i]='0' #restore color[i]
for x in range(n+1):uf[x]=tmpu[x] #restore saved uf

#fill1(s1,0,1,uf)

w,h=5,5
totalarea=0.0
s1=['0']*(w*h+1)
uf1=[-1]*(w*h+1)
uf1[0]=0
tm=time.time();fill2(s1,0,1,uf1);print(totalarea/(2**(w*h)),time.time()-tm)

(8.146968275308609, 44.39699983596802)

tm=time.time();print(setcolor(5,5),time.time()-tm)
(8.146968275308609, 110.45700001716614)

lt  发表于 2020-02-23 16:29:07
• 改写为c程序
8.14696828

Kernel Time = 0.031 = 0%
User Time = 7.628 = 92%
Process Time = 7.659 = 92% Virtual Memory = 1 MB
Global Time = 8.236 = 100% Physical Memory = 2 MB

lt  发表于 2020-02-23 18:19:13
• 思路处理对称,不是保存已有的值,而是见到一个没处理过的,就把它的对称全列一遍,打上标记,然后看不重复的有几个(根据标记),得到这个形状的权重
下次见到处理过的就直接跳过
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31
273366893 33554432
8.14696828
Kernel Time = 0.109 = 1%
User Time = 6.364 = 86%
Process Time = 6.474 = 88%
Global Time = 7.348 = 100%
打标记+递归填1