Forwarded from dnaugsuz
这个真是生草， 3↑↑2=3**3 ； 3↑↑↑2=3↑↑(3↑↑2) …… 天文数字
Forwarded from dnaugsuz
ackermann 函数和那个大^操作符对计算机科学在什么地方有意义？🤔 能评价算法的优劣吗
真的有太阳爆炸前算不出来的东西的意义吗
看见它实现了 < ，所以说这种数值的意义是比大小吗，取位数或取余也不行吗
可是真的有数学界外的算法 会有这种复杂度吗
为什么靠 REPL call 一个 func 就能得到复杂度呢，因为有 dt 和 call count 吗
可是复杂度是算法意义的，怎么忽略常数呢
真的有太阳爆炸前算不出来的东西的意义吗
看见它实现了 < ，所以说这种数值的意义是比大小吗，取位数或取余也不行吗
可是真的有数学界外的算法 会有这种复杂度吗
为什么靠 REPL call 一个 func 就能得到复杂度呢，因为有 dt 和 call count 吗
可是复杂度是算法意义的，怎么忽略常数呢
Forwarded from dnaugsuz
感觉数学这么定义一大堆记法和展开式是药丸的
明明就是
非得弄成第一维度第二维度的东西写死了，草
明明就是
nums.fold(0) { a,b -> pow(a,b) } 的问题非得弄成第一维度第二维度的东西写死了，草
Forwarded from dnaugsuz
这些东西看起来这么厉害，是不是已经用到实际算法优化中去了
感觉 C++ 是这方面的先遣兵
还有，现在很多人别说手推算法复杂度了，选算法跑个分都懒得跑，因为根本没有好方法可以自动评测、自动选特定程序版本，自动化程度太低
要是构建系统给点力就不会这样
应该教导程序员多写几个 等价版的不同实现方式
提供方便的测试套件确定一致性和 对比性能
感觉好简单却没有啊草
噢才记起来 ACM 算法好像不是针对计算机而言的吧
感觉 C++ 是这方面的先遣兵
还有，现在很多人别说手推算法复杂度了，选算法跑个分都懒得跑，因为根本没有好方法可以自动评测、自动选特定程序版本，自动化程度太低
要是构建系统给点力就不会这样
应该教导程序员多写几个 等价版的不同实现方式
提供方便的测试套件确定一致性和 对比性能
感觉好简单却没有啊草
噢才记起来 ACM 算法好像不是针对计算机而言的吧
Forwarded from dnaugsuz
嘛，如果是要索引我给个逐个 bsearch 算法 #Python #code
def bsearch(x, xs): #xs: (<)sorted
def atSub(iL, iR):
i=(iL+iR)//2; v = xs[i]
return i if v==x else (-1) if (iR-iL)==1 else atSub(i,iR) if v<x else atSub(iL,i) if v>x else (-1)
return atSub(0, len(xs))
ary = ["1 7 12 32", "5 9 18 38", "9 13 19 41", "17 20 32 50"]
ary = [[int(sn) for sn in s.split(" ")] for s in ary] def search(v, a) -> [int,int]:
for i, xs in enumerate(a):
j = bsearch(v, xs)
if j != -1: return [i,j] assert search(50,ary) == [3,3]二维 bsearch (相当于 flatten&bsearch 省内存)的我抽提下代码(头疼)，
itself = lambda x,xs: x
def bsearch(x, xs, key=itself): #xs: (<)sorted
def atSub(iL, iR):
i=(iL+iR)//2; v = key(xs[i])
if isinstance(v, list): ii=v[0]; v=v[1]
resI = i if v==x else None if (iR-iL)==1 else atSub(i,iR) if v<x else atSub(iL,i) if v>x else (-1)
return [resI]+(ii) if isList else resI
return atSub(0, len(xs)) bsearch(50, ary, lambda x,xs: [bsearch(x,xs), sum(xs)/len(xs)]) == [3,3]Forwarded from dnaugsuz
啊第一眼看成超级牛， mn 我一时眼花了，写完再看才发现是 (<)序单调增 啊…… 斜二分不能，的确是只能先 list(flatten(xss)) 🤔
如果点用 [i,j] 表示的话的确可行，是
不过写起来应该有点不方便
如果点用 [i,j] 表示的话的确可行，是
sibling = (n) => [n-1,n,n+1]; iter.product(sibling((iML+iMR)/2), sibling((iNL+iNR)/2)) 3*3个不过写起来应该有点不方便
Forwarded from dnaugsuz
不过人家问的是存在性而不是索引号，这样的话直接位并集也是方便的算法 🌝
当然大O并没有缩小就是了，T常量变小而已
当然大O并没有缩小就是了，T常量变小而已
Forwarded from dnaugsuz
再考虑下九宫格 bsearch ，刚才是比较 v<xs[(iR-iL)//2] ，二维纵向不单调不能拆分两层，也只能逐个判断坐标了 🤔为了简化就做成四宫格 UDLR ，没用 numpy
真是头疼呢，但只有写出来才有意义
def shape(a,fname="__iter__"):
return [len(a)]+(shape(a[0]) if len(a)!=0 and hasattr(a[0],fname) else [])
def zeromap(f, xs):
for i,x in enumerate(xs):
for y in f(x): o = xs.copy(); o[i] = y; yield o
def quadBsearch(v, a, div2=lambda n: n//2):
(n,m) = shape(a)
sibling = lambda n: (n+d for d in [-1,+1])
def atSub(i0, i1, j0, j1):
i=div2(i1-i0); j=div2(j1-j0)
[l,r,u,d] = (a[i][j] for i,j in zeromap(sibling, [i,j]))
cv = a[i][j]
if cv==v: return [i,j]
# 然后对 LR 和 UD 能有什么操作呢，操作 i0/1 没有 ij 斜向单调序的保证 也无法排除任何项吧... [0][m-1] 就大于 [n-1][m-1] 的可能性也是有的吧
return atSub(0,n, 0,m)Forwarded from dnaugsuz
这个人就是 wtm 好 f**k 啊， linear search 个 for()return true; return false; 他也能写这么长，这么乱 仿佛写乱了速度就快一样我去
Forwarded from dnaugsuz
你们真的确定 a[i][j] 有 a[i][0]<a[i+1][0] 和 a[i][j]<a[i][j+1] 两个 prop 就能二维 bsearch 优化了，有没有什么细致点的思路啊
如果再保证 a[i][m-1]<a[i+1][0] 就可以直接用 flatten 了，基本没啥意义；可是如果不保证那最好估计是逐个 row 算 bounds 先选一遍吧…… bsearch 做不到，有 overlap ，太难了
四宫格都不知道怎么调，别说九宫格了…… 当卷积核还不错
如果再保证 a[i][m-1]<a[i+1][0] 就可以直接用 flatten 了，基本没啥意义；可是如果不保证那最好估计是逐个 row 算 bounds 先选一遍吧…… bsearch 做不到，有 overlap ，太难了
四宫格都不知道怎么调，别说九宫格了…… 当卷积核还不错
duangsues.is_a? SaltedFish
https://blog.csdn.net/sunshine2285/article/details/104866910/
噢，原来有 a[i][j]<a[i+1][j] & a[i][j]<a[i][j+1] ，ij 方向都有单调序，这就好办了，纵横向逐个算 ij 区间嘛，不对，纵向得连起来……
还是有点难
drop = (n,a) => [row[n:] for row in a[n:]] 的话边角都大些def quadBsearch(v, a, div2=lambda n: n//2):
(n,m) = shape(a)
def atSub(i0, i1, j0, j1):
i=div2(i1-i0); j=div2(j1-j0)
[l,r,u,d] = (a[i][j] for i,j in zeromap(sibling, [i,j]))
cv = a[i][j]
if cv==v: return [i,j]
return atSub(0,n, 0,m) 还是有点难
Forwarded from dnaugsuz
噢大概就是这个模板
def rectBsearch(v, a, div2=lambda n: n//2):
h,w = shape(a)
def inRect(ra):
i,j,n,m = ra; vc = a[i][j]
rects = lambda: [*bigger()] if vc<v else [*smaller()] if vc>v else []
return 1 if vc==v else sum(map(inRect, rects()))==0
return inRect([div2(h), div2(w), h, w])Forwarded from dnaugsuz
草，也是啊，为什么边角 LD i=max,j=0 就那么特殊
“选左下角，往右走增大，往上走减小，可选
“选左下角，往右走增大，往上走减小，可选
Forwarded from dnaugsuz
都知道有 prop ，但这种走迷宫一样的方法竟然没想到…… 反而首先想 sorted 可以 bsearch