#java #news #algorithm https://www.ithome.com.tw/news/163820

当我听说这个月Gosling退休时，其实我挺开心的，因为java API在我看来普及了不少无语意的知识，为八股文爱好者提供了极大方便，可以说是糟粕
这样给程序员带来麻烦的老灯，退休当然是好事，让他们的OOP繁衍下去是浪费人类的逻辑

但另一方面，这并不是JDK本身或 Doug Lea 等工程师的问题。与C++相比，java并不难。除了简化发布流程，还自带电池，提供了许多xml这类最终被滥用的工具
尽管在数据结构/IO上灵活性低，以及导致了十亿美元bug（nullish），java API并没有做错什么.

错就错在跨领域研究编程范式的人太少，以至于过去20年里没有新模型，Rust go 这些还是在拿interface 模仿OOP，没有一种把 json struct enum union override,FP 混合起来的通用编程方法

#algorithm 动态规划 dynamic programming
eg. lcs公共子串, knapack背包最佳配重, edit-distance编辑距离
http://www.bilibili.com/video/BV1FJ4m1M7RJ

🌚这是连“二参记忆化递归”这个常识都没说出来啊。
其实DP的经典案例是fib f x=x if x<2 else f(x-1)+f(x-2)
转化为一维的 f=[0,0]; f.i=f.(i-1)+f.(i-2)
这样，动归比递归的主要难度，是确立基线，以及用抽象的2D数组.ij取代fib()思考「状态转移方程」

二者的相似，好比「积分傅里叶变换」与离散DFT
动归比 @memo def fib 只优化了常量时间
fib只需要朝0的方向计算两个子问题，可以 iter 优化

实现上，如 lcs
f(,)=0
f(a,ab)=1
f(b,ab)=1
来，可视化一个corner case!
\ a b
a 1 0
b 0 2
可见，参数网格

r.(0 0)= A0==B0
r.(i j)= (Ai==Bj? 1:0)+
try max( r.(i-1) r.(j-1))
i==0: r.(0 j-1) #第0行没法再减
j==0: r.(i-1 0)

晦涩就对了，因为它等效这个：
lcs([A],[B])=A==B
lcs([A,a],[B,b])=
max(lcs(a,b) lcs(b,a))+(A==B? 1:0)
lcs([A,a],[B])= lcs(a)+(A==B? 1:0)
+2分支

f(a,ab)=1 直接匹配AaBb +1
f(b,ab)=1 则匹配ABb，居然也与表格等效

更易懂了吗？见仁见智，尤其是 (a,b)(b,a)是干啥？ 当然，因为lcs本身就有交换律啊..
不过我要指出，这个语法是有问题的(尽管 #haskell 在红黑树/快排上比cpp可易读不止一半)，如果专门对DP设计，一定有 np.einsum 那样更优雅的表述

DP教学总是涉及表格[i,j] 而可视化并不方便，不过解「编辑距离」，你总得先学diff(abc, aBc)=[1: -1+B] 怎么计算吧

* https://t.me/dsuses/5335 基于memo的lcs，人不如AI
* https://t.me/dsuse/18877?single fib流

只能先留个坑🌝触摸屏累死了

#rust #go #algorithm UmbraString 是对带长度指针(py.bytes, rs.slice) 的(免链接inline)，而 SwissTable 是对Hash预分组查表的免链接！

我们知道，Java 存在(装箱boxing) 一说，也就是int,char等字面值的堆分配 (这是泛型擦除 vs template<>化新建的编译期细节)，因此JDK8用class Stream.OfInt{}缓解了reified泛型的缺失

那么，(拆箱unwrap) 其实就是在值的内存上内联，像C++栈分配。 除了禁止null，拆箱在运行时有省内存GC、免链接、CPU快取等好处

这么好的算法升级，实现难吗？
map采用预分组查表,哈希值冲突(哈希值一样)的键值对会被放在一个桶中，查找桶=hash(key) mod size，然后再遍历桶中Eq的元素，这里有通过额外的bit做更快的检查。 #dalao https://gufeijun.com/post/map/1/

一旦map的负载因子(键值对个数与桶个数比值)过大，查找需要线性遍历多个桶，性能会退化为O(n)，所以这种实现需要更频繁地对桶进行扩容，保持负载因子在低水平。
拉链法是大多数编程语言的选择，每个桶后面跟上一个链表，所有的同义词通过链表中节点形式串联

SwissTable 使用一种称为Closed Hashing的方案。每一个哈希值都会有一个自己的槽位(slot),槽的选择是由哈希值决定，从hash(key) mod size的槽开始查找，一直往后查找到空的槽(null)
SwissTable也是和内建的map一样采用短哈希(8b hash),以便支持快速检查，但是它的元数据却是独立存储的，和哈希值存储分开。

把hash值分为高7位和低57位：
高7位用在control byte中解决hash冲突 (这7位只是以很低的代价，减少了90%键与键的比较。)

低57位是slot的指针，每个slot对应一个1一个byte的控制字节。

Control byte的高1位用于表示状态 0xFF=undef, 0x80=null值 ，低7位用于存储hashcode的高7位
128bit对齐的连续8字节的control byte称为一个group

使用这种方式，可以通过SIMD 指令并行比较 16 个短哈希，比 std::unord_set 快两倍 （map只是K:V元组按K搜的set）
Flat hashtable不仅仅只是CPU CACHE友好，这样的结构配合原子操作，相信很容易做出一个并发版本的hash table

#algorithm #防自学 🤓 让我来示范一下怎么概括算法思路
要介绍的是在stdlib里，用于组织集合类、JSON的3个重要结构: b"ytesPtr", {K:V}, sorted([0 2 1])=[0 1 2]
它们对各种app和其他算法性能效能的重要性，好比json(cbor.me)之于REST、zip之于jvm和pip。 因为是涉及SDK实现的内容，也主观评价下语法设计

下面用胖指针(x64上void*是8b, 胖指16b)、链表、快速排序简单的实现3者 #code

#define Col(...) typedef struct{__VA_ARGS__;} T;

#define T Str
Col(size_t n; char* buf) //C的类型本应默认为指针, *胖指针，像kt那样对Int等类型免链接化。简洁的UNIX里，Type* 快成为public那样的形式主义啦

#define T_Link(E,T) struct T{E x; T* xs;}
T_Link(int,Nums)  //template<T> 允许类型推理，即一致化调用和返回处的<T>。可怜gcc/clang无论对宏还是模板的报错皆如内容农场，不具有可读性

https://colobu.com/2023/06/29/replace-std-map-faster/chunk-index-memory.jpg
用例和 #haskell #code https://gist.github.com/duangsuse/26b80c39e1d8f7549b9cf244d8de1ce4
题外话，闭包值和 x.interface_cast(T) 的双指针&dyn 随结构传入T的函数表

qsort :: (Ord a) => [a] -> [a]
qsort [] = []  
qsort (x:xs) = 
    let smallerSorted = qsort [a | a <- xs, a <= x]
        largerSorted = qsort [a | a <- xs, a > x]
    in smallerSorted ++ [x] ++ largerSorted

UmbraString 和上文Str{n,buf}胖指针一样是16b，但它的.n和jvm一样只寻址[4b:int]的长度，其后最少随4b的免链接char 用于比大小
对于n>12的buf，剩下8b换成指针，指针的高2位用于标记GC信息： 持久pin、临时ref、用后即焚val

很明显！这是一种灵活利用了x86内存布局的b"length"实现，和x32压缩指针一样，节省了sort解指针的时间

SwissTable 是对Hash预分组查表的免链接。我们知道， dict/HashMap/lua.Table 这样的{K:V, K1:V} 单映射常被用于查找和缓存，在C++里更是会区分 unordered_map, rb_map(以排序radix,SortedSet,而非hash作为预分组线索)
它的最简实现是lisp里的链表 T_Link(struct {int A,B;}, int_LnKV) ：没留任何线索来减枝！

即便8b hashCode，也是一定会冲突的，哪怕是int.hash也会因 buck[hash%nBuck] 有限而退化为线性查找，负载因子(kv/nBuck 过大)，这时就要扩容。Go的扩容基于一种空间换时间的优化(图1, 为了减少求余数的冲突，除数都会采用2的指数)
扩容后的冲突集，可以用链表(UnionFind)或数组(slot), 从那往右找
Swiss 更聪明，它对每slot对应1b的元数据，最高位0x80=无效项 ，0xFF=null结尾 ，低7位用于存储hashcode的高7位，这么摘要是为了SIMD128bit 1次对比8个KV
不仅仅只是CPU CACHE友好，这样的结构配合原子操作，相信很容易做出一个并发版本的hash table

快速求余(x,n)= uint32((uint64(x) * uint64(n)) >> 32)
#dalao https://init.blog/fast-newton-sqrt/

float InvSqrt(float x) {
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i >> 1);
    x = *(float*)&i;
    x = x*(1.5f - xhalf*x*x);
    return x;
}

最近的一种基于partition(区间而非idx)的快排也很有趣： less than pivotL | between pivotL and pivotR | greater than pivotR

https://liyucang-git.github.io/2021/02/12/前端包管理器对比-npm-yarn-和-pnpm/#:~:text=2、大量重复的包被安装，文件体积超级大。比如跟%20foo%20同级目录下有一个baz，两者都依赖于同一个版本的lodash，那么%20lodash%20会分别在两者的%20node_modules%20中被安装，也就是重复安装；

#js #meme #algorithm PNPM.io 的前世， 幽默脚本小子： 依赖图(dependency graph #tool) 都没学过，只知道递归下载(wget -r)树 😅

一个 ln -s 文件树+硬链接=图DAG; =NodeGraph滤镜=let赋值复用=.. 的道理都没学过， 居然敢做软件架构 ……

Python 当初是没有 malloc 或 GC 的，全靠Rc，和当今一堆编译期运行时的过度工程相比。简直是一股清流。

#linux #algorithm 嵌入式 链表

在内核中，我们不能用定长数组（pid这些东西是经常增删、完全遍历的），首尾相接 双向链表 + inline优化 是Linus的选择
IntList* 只能保存int， 但嵌入式链表能包含多个子类，都可以遍历查表，再以 container_of 解指针。 Lua 以这种做法实现 int tag; union{}

这和C的 struct T{ char tail []} 很像，被用于保存 len+ptr\0 字符串
https://www.zhihu.com/question/30262900/answer/34688512238
#冷知识 py.list tuple js.array cpp.vector gl.vec3(ndarray) .. 「茴的四种写法」是哪来的？

英语上只有 list 和 matrix ，LISP 把(只读)链表称为 list，C因长度固定用了 array
C++ 因长度动态且非链表，用了 std::vec .. list 则意味着 linked
tuple 则是 namedtuple 结构体的前身

#algorithm Tex 使用的 text-wrap: pretty 算法，和默认的wrap差在会主动缩减行长，来为尾行凑字数，偶尔看起来更整齐
https://blog.ppresume.com/posts/zh-cn/on-typesetting-engines#:~:text=并未实现%20Knuth%20Plass
https://output.jsbin.com/hopejeb

[...new Intl.Segmenter('zh', {granularity: 'word'}).segment( "hello world 你好世界")]
//Intl.Hyphenation 是 granularity: 'wordroot'

https://github.com/mnater/Hyphenopoly?tab=readme-ov-file#automatic-hyphenation
https://opentype.js.org/ <<SVG 字形的滤镜

哈哈，Web怎么可能没实现呢？ MathJax.org 都比Tex好用的多了。Tex不仅慢还难调 https://github.com/robertknight/tex-linebreak

和这个 #tool https://latex.js.org/playground.html 一比差好远，简直不比 PostScript 美观

#js #面试 https://liyucang-git.github.io/2018/05/27/浅谈浏览器运行机制及单线程js的执行/

#py #dalao #algorithm https://blog.laisky.com/p/algorithm/

#c #algorithm #bin 位运算 优化跳空格
glibc strlen.c 默认实现 «Bit Twiddling Hacks>
btw. “减法时间比位运算长”的问题，时间的最小粒度是CPU周期。只需要看这个指令需要几个周期就行了，ALU都是1cycle，比从内存读取快了几个数量级

bool has_zero_byte(uint32_t v)
{
    const uint32_t himagic = 0x80808080;
    const uint32_t lomagic = 0x01010101;

    return ((v - lomagic) & ~v & himagic) != 0;
}

向量实现手写AVX，然而再怎么玩都不如string类型直接存好长度快。

纯sdf, 顺手移植了一个给 numpy+tty

花了1小时吧：
cv2.open(mode=HSL亮L).降采样为(stty size) mix(256色到" .*#"色) .追加\n列 .光标到(0,0)print

我用了比yes命令内存效能低的join''，但也不打紧

#performance fwrite() 就像CtrlV，要打'y'*500你是粘贴五百次还是多复制、缓冲？
把rows('<U1').buf分隔复制到 int8(w*h+1h)，按帧yield给/dev/pts/0管道更省
若一开始就 open(w+1'\n',h) 就是SIMD汇编一样快了，当然，0copy 不如 diff update ，之前逐px试过确实。

有时看 #bilibili 编程圈，感觉是「时无英雄竖子成名」，比如那个开「知识」星球赚百w的鱼皮
像🐴一龙那样因追求，最终有钱的少，更多技术人有比钱更高的需求。
在老中这很搞笑很虚伪吧？ #statement

不过我是很清楚，B站上真大佬有 #algorithm #OI 的一大堆， @从0开始数 就是，
其实是学生们只喜欢看抽象的「编程娱乐直播」 JavaWeb PHP 什么的曾经很赚钱的 🥰 甚至不一定要有代码，可敬抄嘛，
那个微信首屏卡成 🐴，音视频通话按钮都混乱，拿AI做避讳和偷窥这样的脏事， 还一堆人 pixel perfect 地致敬张小龙，其实就是这种大厂功利心态，
何同学呢？ 作为主=5G的第二个受益者 ，其实不配说热爱 奋斗 赛博丁真