全英文

#Haha #CS https://t.me/lycheewood/8402

今天开始真的 写了

想先写篇关于之前那个排序问题的论文...

其实我想了很久（一天）了，我还是无法弄清楚（虽然考虑了一两种情况）drakeet 到底是在哪里想出问题的...

虽然待会还有别的东西要写.... 不少，但是马上放假了就很不缺时间了吧

#linux #sysadmin https://lexuge.github.io/posts/building-a-practical-system-based-on-arch-linux/

5 没有被手动排序过，5 排在 1 前面，4 被手动排序过，4 也在 1 前面，但 5 和 4 却无法得出谁在谁前

我... 其实我一直在想的是（没错，我记错了，但是这句话我一直在想一直在想... 我真的不知道到底是哪里，在设计什么算法什么数据结构才可能导致他理解出了这类偏差）

a 没有被手动排序过，a 排在 c 的前面，b 被手动排序过，b 也在 c 的前面，但是 a 和 b 却无法确定谁在前面

之前一直以为是抽象的，实际上居然是用数值... 那我应该又找到新的突破点了...

之前我一直怀疑是不是他修改那类算法的时候出了问题，现在想想也可能是调试的时候发现了这个『漏洞』

是不是也有可能是把“不可排序”的文章映射到数值的时候导致的问题？
如果后端存储是支持查询排序的 ORM，是不是可以说就是上面这种情况？

我猜的第一种情况是对于任意两项

import java.util.function.*;

class OrderLT<T> implements Comparator<T> {
private enum Ord { LT, EQ, GT; }
private final Predicate<T> lessThanP;
public OrderLT(Predicate<Pair<? super T, ? super T>> ltP) {lessThanP = ltP;}

@Override int compare(T a, T b) {
if (lessThanP.test(Pair.of(a, b))) return LT.toInt();
return (a.equals(b)? EQ : GT).toInt();
}

@Override boolean equals(Object cmpQ) {return cmpQ instanceof OrderLT && cmpQ.lessThan}
}

上面这个是 Ord 的实现，但是我不该强行用 Predicate... 有点过分了...
我想想可能是什么问题...

我之前想到的第一个是为每个文章建立一个『是否被手动排序过？』布耳值，对于表中每（要比较的）两项，如果任何一项被标记为手动排序过则直接返回预期的顺序（默认按照 lessThan 排序，输出升序列 Ascending sequence，这种情况直接返回 -1 （LT）表示顺序已经满足）不过，虽然理论上会导致这种问题（这是肯定的，原因我待会的文章会说）但是实践上（假设是冒泡排序的交换，快速排序就不能肯定了）只会导致手动排序部分以及边上的两个被“锁死”不可能移动位置而已，没有 5,4 『找不到』谁在前的问题（显然 5 旁边锁死了排序算法就不会工作，因为两项的顺序满足了目标序列，如果本来就是正确的则自动部分排序结果正确，否则自动排序部分是非有序列的，但对此算法是正常情况）。

当然排序算法按操作分选择、插入、交换三类，序的理论却是唯一的，就一个 lessThan ⊏ 和一个反对称性、传递性最重要（如果不是 lessThan 显然就是 equals 或者 greaterThan 了，不过实际上实现这一个 predicate，判定[1]）

5 没有被手动排序过，5 排在 1 前面，4 被手动排序过，4 也在 1 前面，但 5 和 4 却无法得出谁在谁前

Given
list <= {5,4,1} (>)
Where
5 自动排序
5 在 1 前面
4 在 1 前面
In
5 和 4 无法得出谁在谁前

其中有一个容易误会的点是对于集合 {5,4,1} (>) 序是指算法输出

forall i in lastIndex(list). list[i] > list[i+1]

（当然这里我不指定 i in... 或者随便指定 i in indices(list) 也没错... 数学嘛，请滑稽处理，跑）

而不是『某简单排序算法看到 5 > 4 为真，则交换成 4,5, 它是“确保”条件成立并且应用偏序传递性而不是“否认”比较操作符』

... 首先根据 5 和 4 无法得出谁在谁前... 认为是在设计排序算法的过程中出的问题吧
因为 drakeet 是一个非函数式也不太学算法的（真正意义上的纯）工程师，假设他使用了把“文章”直接映射到某标量的方式，我觉得比较有可能（而不是比如设置一个 lessThan 关系集合，然后 comparator 判断某项是否在集合内并且打破偏序）

.... 这种算法到底是哪样的呢？假设它是类似冒泡排序的交换排序

bubbleSort (>) [5,4,1]

它要比较两次：

5>4

= true
4>1 = true

可显然这不是问题，那就假设我之前的猜测是对的，输入是一个二元组

bubbleSort cmp [(4, True), (1, True), (5, False)]
where cmp (x, p) (r, q) = if p and q then (fst x) > (fst r) else True)

我假设他所说这个『无法得出』是无法得出“正确”的结果的意思，那这个程序的输出是（product 箭头拆掉元组部分） [4, 1, 5]
5 和 4 的确是无法得出谁在谁前，因为 snd (5, False) 是 False，不允许交换的

那只好再审题...

5 没有被手动排序过
我考虑一个列表 [5]
5 排在 1 前面
[5, 1] 证明这个列表是 (>) 降序(Descending)的
可是，开始我直觉上（思路上还是有的）没有考虑到这是一种“部分序列”
4 被手动排序过


4 也在 1 前面

用户选择把 4 放在了一个地方，这个地方符合约束： (> 1)
其实情景是『在自动排序序列中插入一项』？
现在列表看起来有一个不定位置的 4，它必须满足 (4 > 1)

5 和 4 却无法得出谁在谁前
首先：听起来这不像是在写代码，因为 5 和 4 的确可以“比较”吧
除非 4 是用户给出“在 1 前面”的那一个，用户没有告诉我们它是否 (>5) 这样就有两种可能的结果：

[5,4,1] when (4<5)

[4,5,1] when (4>5)

这怎么得出呢？显然这类算法没有简单到一定程度

但以上讨论显然好像是忽略了某些本来存在的信息... 总之，想猜出是“为什么错”的还真是非常困难，因为解决方案和理论错误的都可能是由很奇妙的因素导致的... 可能性有无数种，无数种错误都可能在某个侧面被描述为
5 没有被手动排序过，5 排在 1 前面，4 被手动排序过，4 也在 1 前面，但 5 和 4 却无法得出谁在谁前
... 看起来是我还不熟悉实际工程？

现在把 5 4 1 泛化成 a b c，升序排列，然后考虑一下实际上如果我们实现某种算法的话会不会出茬子

b, c 是自动排序的项目 且 b < c

[b, c]

现在用户加入了一项 a 且要求 a < c

『要求』怎么抽象？其实可以做一个 lessThanC 集合，如果右项目是 c，则直接判断左项目是否在 lessThanC 布耳映射内否则返回 True（满足序列）
但是就出现了一个问题：
用户只是说 a < c，我们却不知道 a 和 b 什么关系... 看起来好像是必须要实现全函数 ord 的，这问题当然不可解

但依此得出『无法按要求排序列表』，这其实是一个误区... 因为给定的偏序关系本来就已经满足，a 和 b 是什么关系你随便指定，a>b, a<b 都可以。只要 a < c


Given (b < c, a < c)

我们能不能解 a < b？当然不可以，因为显然不能无中生有，如果 a < c、b < a 是能得出 b < c 的（偏序操作符 < 有传递性可推出 b < a < c），但是上面那货只是指定了一个 a 的取值区间，没有具体到拿 b 去限制它,a b 都只是各自 <c 而已

{a b} < c 

...我决定停下，我还有很多有意义的事情可以做，我真的不知道 drakeet 是在写代码的时候（我觉得不太可能，因为这个理论想弄个算法出来想靠模板化代码.... 另外开始就写代码反而不可能想到这个问题，而且以 drakeet 之前的见识这种问题可能要先想，不过我是受教了...）想到的还是在开始想理论的时候弄错的，但不管怎么样、不管为什么错，知道它是错的就好了...

那我等一会就写文吧，不要追想是为啥错的，也怪浪费时间的。（虽然我觉得是想理论模拟比较算法的时候就出了问题，他的思路还的确蛮跳跃的，我都没有把偏序关系抽象成这个样子只是觉得可以『部分排序』和『固定位置』两种，或许是他开始打算使用 Collections API 的 sort 函数吧，那要实现一个 java.util.Comparator<T>）

—
[1] 之所以不称谓词（predicate）是因为我的确很困惑为啥要这么翻译
我开始把它和量词（qunatifier）弄混了，还好很快就明白自己搞错了
这个翻译成谓词（the part of a sentence or clause containing a verb and stating something about the subject）感觉有点不准确（但是谓语『我爱你』的这个爱的确是谓词），这里我不会用，不过别的地方以后我还是照用不误
#zhihu https://www.zhihu.com/question/28698429

到底是为什么错的啊.... 😭

我真的不太相信 drakeet 真的想到了上面说的那种方法（就是依然用 sort API，但是允许用户利用视图移动指定 a 项目比某一项大或者小，显然这种算法没有那么简单也绝对抄不来，和大学里可能教的冒泡排序是有很大区别的）
即使现在看起来这种情况最有可能导致这种误区...

真的，这就是个无解的问题，到底为什么，只能问他本人，然而他本人就是最开始还没有和我、Telegram 决裂的时候也不愿意多说一个字的相关信息，大概他得把答案带到坟墓里去了...

5 没有被手动排序过，5 排在 1 前面，4 被手动排序过，4 也在 1 前面，但 5 和 4 却无法得出谁在谁前

我的天啊... 还有什么别的可能没有，几乎我想到每一种可能性都有可能被解释成这个样子，但是只有实现一个 interface java.util.Comparator<T> 的情况最可能

我从『被手动排序过』一字猜出了一种限制排序运行（比较时必须两边都『可自动排序』才真正比较）的可能性
从『无法得出』猜出了动态定义偏序关系的可能性

之前我还从排序算法而不是比较算法的角度想过『用户固定位置』的可能性

可是这个题目真正的直觉是啥子，我一根毛都想不到... 这就好像通过一点点蛛丝马迹推断结论之前的成立条件一样... 可能总结出这个结论的算法有一千种，可是最可能的那种到底是什么？
是的，前面 4 句都很正常，可是他是怎么想到最后一句的...

目前就这么说吧：

+ drakeet 不是在实现算法的时候想到这个问题的，而是在想法子实现的时候首先考虑到了这种情况，然后立刻放弃了实现
+ 思路是这样的：
1. 可客观排序列表中有两种项
一种是主观排序项目，按照 Ascending (<) 和 Descending (>) 序来排列
一种是客观排序项目，按照『此项小于某项』来排列
2. 首先验证此模型是否有效

设数据集合 {5, 4, 1} (>) 其中用户指定 4 > 1 也即 1 < 4（用户把 4 移到了 1 之前的位置，定义了这里 4 在 1 前面的关系）
然后 5 本来 (> 1)

首先比较 5, 4 where 4 > 1 可是无法得出 5, 4 谁在谁前（>），因为一个是被用户排序的一个不是，而且因为不知道 4>1 限制有没有导致 5 > 4 ≯ 1 所以这是可能导致结果错误的 （这是个误区，因为排序算法会自动完成偏序关系的传递，不需要比较算法考虑，后者上面的题目没有考虑到，但是这也是正常的，因为本来这么做就屏蔽了部分原生的序列方法）

...

总之.... 这个题目都可能是有问题的，比如是否本应是

5 没有被手动排序过，5 排在 1 后面，4 被手动排序过，所以 4 排在 1 前面，但 5 和 4 却无法得出谁在谁前

这才是真正相悖的结论...
因为 5,4,1 关于 (>) 本身就是一个有序数列... 管他是否有手动排序什么的，看起来更像是『最开始』（还没有考虑要顺序不对可能要交换的情况）的模拟就出错了，因为他觉得无法比较用户限制的对象 (4 where...) 和普通使用原生序的对象 5？这样不那么烧脑一些，也很有可能。

但这等于就是说他完全没有想到啥是偏序关系... 只是 naive 地觉得用户直接安排过后的东西用 < 运算符就不可直接比较了，要不然就会打破用户定义的关系，怎么说也是一种可能，但是否有点太低估人家的意思了。少说人家还写过冒泡排序呢（跑

Current settled on this. 关于某排序问题，我最终总结『为什么会有这个误解』的结论就是：

（原问题来自 drakeet 的 Android 应用 PureWriter 文章列表实现『同时自动/手动排序』功能）

drakeet 想了这个问题，然后举了一个类似 a > b > c 的（可主观自动排序列表，降序排列, ord=(>)）例子
其中 b 是被用户安排的项目，且用户希望 b > c



5 没有被手动排序过，5 排在 1 前面 (5 > 1)
4 被*手动排序*过，4 也在 1 前面 (4 > 1)

他的想法是因为
比较 a （自由项目 "5"，线性相关处理后使用 > 操作符直接比较）
和 b （用户限制项目 "4"）不可行（返回什么都可能会打破用户定义的顺序）
（也就是说无法得出 a 和 b 是不是 (a > b) 关系或者 (b > a) 关系，因为 b 是“手动排序的”即便 b 是 5; a 是 4 也不能被比较）

这本身是一个误解，因为用户指定的是 (b > 1) 也就是 (b > c) 仅此而已，和 a 是不是 greaterThan b 无关（对于他的问题答案就是，只要 b>c 就可以，a<b;b<a 你随便选一个喜欢的用户都满意），何况实现『可自动排序同时允许手动排序』的列表也不一定非得采用这种方法，即使只是先分开排序合并再存储下顺序，不需要动态地再次用比较函数排序也可以做到。

我最终从猜到的四种可能里选出这个的原因是，他给出的这个例子本身就符合顺序，看起来就像是才开始想到这个分析方法（此时输入示例都还是有序列表）就断言 a 和 b 因为一个手动一个自动就无法比较；况且如果他开始想使用 Java 的 Collections API 排序静态方法也不是不可能，这些理论基础也是实现时必须首先想到的。

结论当然可能不准确，不过我在这里也得说几句。

+ 首先我可懒得踢什么 drakeet 的馆的（根本不是一个世界的人）也无意诽谤他，对我来说显然比刻意抹黑他而言有更多重要的事，你们现在看到的是技术上对他提出过这个问题的分析，而且之前我还有几次分析或成功或失败。
+ 爱因斯坦说过，如果你不能把道理给六岁小孩讲明白，那你自己其实不理解这个道理。我希望以后如果你要提出的问题和 drakeet 的这个一样

5 没有被手动排序过，5 排在 1 前面，4 被手动排序过，4 也在 1 前面，但 5 和 4 却无法得出谁在谁前

令人感到莫名其妙，别忘了加点注释、做点总结、多给点信息，别人提出质疑或者帮助的时候也不要一副『我啥都知道了，你肯定是错的』的样子

+ 曾经我觉得任何社交问题，只要不涉及原则性问题，都要尽可能保证双方友好。
也就是说，我不仅默认给所有人基本的尊严和尊重、还包容一切你的自满、骄傲、自以为是、玻璃心、独裁，不愿听取人何关于自己有任何可能负面的话，即使我完全可以说出来，即使我本来没有错。
而且很多人都觉得这么做是理所当然的。

也就是说，不管后来 drakeet 表现有多么奇怪，多么不包容，甚至他有好自满的毛病、因为我提了一个『他错误』的可能他就把我踢了，我都忍了（当然也是有限度的，比如他最后一次毫无理由和预警就踢了我之后我在 60 人的频道上公平客观地评价了一些他的开源项目，虽然现在没人能证明我的评价的确是客观的），我以为就只是表面上开开心心的就好，因为不经常接触，你骄傲一点属于性格不同，我改变不了他的性格，与我无关

人不可有傲气，但不可无傲骨。

可我就没有遇见过和持我不一样态度的人吗？千里冰封 @ice1000 他是真·大佬，真的是很喜欢交朋友而且待人非常宽容的人，表示愿意认识并且确认我的确是沾得上边的同好之后就把我拉进了友群，不过当时我太 naive，即便冰封好友群里的大佬都表示希望我有长进，我还是说了很多很弱智的话（比如一知半解甚至完全不懂的时候我重复过王某 HM 类型系统 SB 的言论，当然那时候我连 HM 的 type variable 都没见过），这时候冰封没有一味地纵容我，把我踢了，但没有直接当傻逼一样屏蔽我（比如我还是可以在 GitHub 上找他，他也依然回复我的问题、Merge 我的 PR）

可是当时我当然是看不出他对我有多么宽容的，甚至包括后来那些话有多愚蠢我也是现在才感受到，班门弄府，而且还是纸做的斧头（工程系的一些人会觉得王垠是天才，他真的是无人能比永远不犯错且任何言论从任何角度看都是正确正确正确的天才呢，还是他扯淡的呢，这话是他的博客标题）还是借来的，真的是无法想像。 若是一个载人航天科学家回复一个农民里的工程师，为什么不用柴油机驱动火箭上天的话，那科学家输了。

后来我把他当时批判我的话发到 Telegram 上，还被人喷他说是不尊重人。
尊重？听起来好像人类社会里，一个啥都不干的懒汉都能得到尊重？那换到计算机科学的群（主要是编译原理\PLT）里，连自己的编译器都没弄出来有什么脸获得『尊重』？当然是先做好自己该做的才能得到自己该有的尊重，尊重不是胡乱发给妄图天上掉馅饼的懒汉的。

也正是因为他们排斥，我才明确地注意到了其实我还真的是太辣鸡了，辣鸡到没有资本和他们一个群讨论也学不到什么，那我就彻底离开冰封，独自想办法学习努力算了。
这个做法才是正确的，差距太大了，想合群就只能潜水，还不如认真在旁边看看感兴趣的东西，也不一定非得加入进去讨论，这也是我一直在做的事情（实际上我也看过很多篇冰封的文章的，我现在 19 年大概只有他 2017 年技术上部分方面的水平... 这就是差距）

曾经我对 drakeet 不仅有对前辈 + 在职（还去过 Alibaba，现在在 M$）工程师的尊重，甚至还包容了他异想天开的逻辑

可是现在我改变主意了，我这么“包容”他，反而是对他不利的，不管我能不能改变别人的性格、我自己采取什么样的策略对待这种性格，世界可未必是这个样子的...

drakeet 就算不打算当“一个高尚的人、一个纯粹的人、一个热爱工作的人、一个摆脱了重复堆砌的人”，但他作为在业的工程师照样要面对无数人，如果我是这个接受一切的特例，是不是反而让他知道了，原来即使保持自己的差性格，原来“冒充先知”其实会被有的人接受？

我还是要和常遇到的人取一个平均... 不能一切都接受了，必要的时候该怼就得怼，实际上这才是真正为他个人着想，也是在为我自己的公平着想。

+ 实践是检验真理的唯一标准

有句话 @drakeet 曾经说过：

[Forwarded from Drakeets]

我觉得 telegram 应该出一个「禁止他人转发私聊消息」功能，总有人私自未经允许将私聊消息转发到各种公开群里，引起不适和曲解。这种人真是非常不礼貌、自私。如果你发现这样的人，还是避免交往比较好。

噢不是这个，这条我支持，不过因为他现在已经气到离开 Telegram 了.... 所以，找不到

大概就是说 Telegram 应该推出禁止转发广播的功能，理由和上面那一条差不多，害怕评论，害怕所谓的『曲解』。

还是这之前的事情。

哎说起来 drakeet 最近（2 月）发了一篇 MultiType Recycler ViewHolder dispatch 4.0 库的演示片，要不要去看看（这里就只是技术上，别问我是不是有啥恩怨什么的）

到底是哲学指导实验还是实验指导哲学？（来自《三体 I：地球往事》）

当然是正确的 @drakeet （原文：马克思主义哲学）理论指导实验！

可是这等于说是正确的理论就是从天上掉下来的，反对实践出真知，恰恰是违背马克思主义以实践作为认识自然根本原则的！

为什么说是理论来自实践？为什么认为唯心主义现在不如唯物主义？为什么很多人觉得上帝不存在？

因为科学是基于实践建立起来的，不像神佛鬼怪，科学只是反映了现实，那个所有人都觉得最基本，最不可能改变的客观真理和规律。

真理是不害怕质疑的，质疑只会让完美的真理在谗妄者的诽谤和学者的证明中愈发显出其正确性，真理像是一种生物，它的天敌就是所有想要打倒它、扭曲它、证伪它的人，自然选择是真理诞生和生存中必须要有的经历，因为存在，因为扛住了时间的冲刷打击，所以是真理。

一个人敢于宣称自己说的永远是正确的，最终只会成为暴君，所有人对他任何作品的评论都会被当成是学术欺压，他保留对自己任何作品的解释权、只允许任何人对它们的赞美而任何显得自己没面子的评价都是不可能与之共生的，他运用各种方法屏蔽一切任何对他略有微词的、不利的东西，他保护自己的理论，没有人能说他是错的、他做的是不对的、他弄错了某些东西，可是也惯坏了自己的理论，惯坏了自己的技术，进入这种状态的人终此一生将没有任何实质上的长进，因为他已经屏蔽了进化的源泉。

人们应该追求真理，因为真理让我们变得更好。你觉得真理应该是什么样子，真理应该以什么标准被选择出来？
应该是『某个人说的话全都是真理，我记住它们』还是『一个命题太浅，给我证明它、让我理解它！』？

相信这里的每个人都有自己的答案，当然没有也没办法了，因为对一部分人来说第一个选项在 Telegram 上已经是灰色的了，对另一部分，恐怕也够呛 🌝

中国还是在中国，这种例子很少吗，暴君真的少吗？

#Statement

顺便说一下为啥要进行 n 次，每次都要排序列表从 0 到 n - i -1 的项目，虽然我现在还没有证明为什么 bubble sort 输出的列表就一定是有序的的能力（归纳证明）

排序算法，就是给一个输入序列、一个测试函数『序(order)』，输出序列满足以下条件

forall i. list[i] `order` list[i+1]

比如 list=[3,2,1]; ord=(<) 简单的选择排序每次挑一个『最大』的元素出来（它满足 forall x in list. x <= it），复杂度是 O(n) 当然 n 是输入长度，线性复杂度，这也是必须的（显然得遍历一遍才能找出最大的），没得优化

max [] = undefined
max xs = let (maxidx, max) = (0, xs[0])
  in xs.with_index.forEach(cmpChg)

max

  where cmpChg = { |it, idx| if it > max then (maxidx, max) <- (idx, it) else Unit 

}


然后每次找到这个最大的，忽略掉它（比如直接 delete），再把它 push 到期待的有序列表里，就成了升序(ascending) 序列（栈是 LIFO 的，collect 到列表后最后 push 进去的最小值成了第一项）

naiveSort xs = let result = []
in xs.length.times do
(maxidx, max) <- max xs
xs.delete(maxidx)
result.push(max)

当然我不知道有没有真正 Haskell 并且还好看的写法，或许依然要枚举索引... 也可以用链表和递归大概，但这里不讲它

对于 bubble sort，首先有一个过程，它遍历一遍所有 list[i] list[i+1]，假若 list[i] `ord` list[i+1] 不成立则交换（因为偏序关系有反对称性，所以这是正确的，可以向最终对输出全称量词(forall) 成立的方向演进）
（这里就隐式限定了 i < list.length-1-1 因为 list[?] 的 ? 必须 inbounds [0..list.length] 那这里 ? 的最大值是 i+1，最小值是 i）
给定 i+1 inbounds 0..list.length 推出（直接用加法的逆运算推导） i inbounds 0..list.length-1 转化为 Java 的布耳表达式就是 (0 <=i && i< list.length-1).

为什么 bubble sort 这种交换排序就需要再循环 n 次呢？而且为什么每一次排序的序列都可以是 [0..tailidx-i] 最后索引递减呢？

对于任何排序算法，都要做到一个最基本的东西：完成对偏序关系的传递
a R b ⇒ b R c ⇒ a R c
对于 R = (<) 的情况就是

a < b ⇒ b < c ⇒ a < c

这样的序列看起来像：

a < b < c

很简单吧
其中快速排序是基于 D&C （一种基于递归的）优雅算法，它对问题解决方式的表达很好地反映了这个道理

(Scala)

def qsort[T](xs: List[T])(implicit ord: Ordering[T]) = {...}

快速排序是一种基于交换的排序算法（这类算法一般都比较高效能，对于原表几乎不需要有任何概念上的数据复制），对问题的解决妙就妙在它把二元关系给“分治”到了二叉树上。
它的递归每层返回一个有序列表、基线是列表已经有序（长度 2 以下）

  if (xs.length <=2) { return xs }

找一个基线，作为交换的基点。

  val pivot: T = xs{xs.length /2}

[1,2,3,4] 基于快速排序它会被分成 [1,2] 和 [3,4] 两个子问题（理论上，其实实际使用了优化），
val lts = xs.filter(x => ord.lt(x, pivot))
val gts = xs.filter(x => ord.gt(x, pivot))

最后，返回一个有序的列表，这里用到了递归定义，因为我们不知道子列表是否已经有序，所以要递归下去拿到有序的列表

  return qsort(lts) ++ List(pivot) ++ qsort(gts)

想复制实现代码看这里

每个子问题只有一个子结果：一个有序的列表，实际上这样，它的每一个子问题就只有 O(log2 n) 的时间复杂度，它的传递方式就是『找出每个子树里最大的，然后把它和同层的其他子树做二元比较交换，再次找到最大的比较交换...』这样就在 O(n log2 n) （n 是平均情况下要解决子问题的个数，log2 n 是解决每层子问题二元比较的次数，因为它利用递归切分子问题和偏序的传递性，只需要很少的比较次数 log2 n 就可以得出正确的结果）

Question: 如果输入列表长度是单数(odd)岂不是无法切分为两个『子问题』？
Answer: 对于这种情况，设置一个递归分支 qsort [x] = [x] 就好了，这是应对单数输入的情况
此外 qsort [] = [] 也是一种递归中可能发生的情况

==
那现在问题来了，冒泡排序又是怎么完成这个偏序关系传递的呢？
因为冒泡排序比较不适合 Haskell 和 Scala 的风格，就用 Jawa 写好啦！

冒泡排序的思路就是，遍历交换遍历交换... 直到列表有序

有一个基本子，它针对 list[0..ri] 线性（join 每两项，实际上最后真正比较的次数超乎你想象，它做到的『传递』几乎每轮只能增加一个项目... 而不是 i^2 个）排序一遍，这样我们实际上只能保证两边不存在偏序传播问题的项目是完全有序的，因为前面的其他项目的偏序关系全部都没有被传递而只是相邻两项之间有关系而已，(<), [3, 2, 1]，最后弄成 [2, 1, 3] 完全有可能，因为它交换 [3,1] 的时候看的是 2 < 3 但是不知道后面还有 2≮1, 和 qsort 基于栈存储的比较次数和每层输出一定有序的断言一比高下立判，优雅性也远远不及后者

private static <T extends Comparable<? super T>> void propagateOnce(List<T> xs, final int ri) {
  for (int i =ri -1; i >=0; i--) {
    T lhs = xs.get(i), rhs = xs.get(i+1);
    boolean ordered = lhs < rhs;
    if (!ordered) { // swap!
      xs.set(i, rhs); xs.set(i+1, lhs); }
  }
}

那既然无法保证 [3,2,1] (<) 之类在 propagateOnce 内 < 的传递性可以被尊重，怎么办？
有一个办法，就是循环 n 次，每次处理 [0..i] 的个子列表，因为虽然像是铁块上的石蜡一样偏序关系无法传递无法透过，边角上的 [2,1] 显然还是能保证顺序的（数学归纳法的基线）
这样处理 (n/2)*n 次过后，实际上就把最刁钻的关系传递到位了（比如 [5, 0, 0, 0, 0, -1] (<) 这个极端情况，会被切分成 5 个子序列从长到短依次串起来副作用排序，-1 会被不断当成边角被“冒泡”到第一个位置，这也是算法名字的来由）

public static <T extends Comparable<? super T>> List<T> bubbleSort(final List<T> xs) {
  List<T> output = xs.clone();

  for (int rlim =(xs.length-1); rlim >0; rlim--)
    { propagateOnce(output, rlim); }
  return output;
}

当然从左边递增切分子序列也是可以的，这里只是因为从右边更符合直觉

—
刚才看荔枝频道上那个基于遗传算法（物竞天择适者生存）的程序综合（program synthesis）机器人会自己生成排序算法，NB 啊。
是不是 Prolog, Coq 这类描述式编程语言也会这么做呢？ #Algorithm #Scala #Java #Haskell

#Haha #China #Huawei

估计消息传开后就
华为：？？？
媒体：？？？
鸿蒙：？？？
最惨的是最后这个

现在看起来我果然是比之前通透一些了... 🤔
但是工程还是“好像”做不得，比如 JavaEE 那些东西我还是没有背住，而且现在也没有动真正的代码，那我就做一段时间理论吧

可是也就是两个月的时间而已... 19 年 4~7 月

仿佛已经是很久之前的事情了，但是我却不知道我是否真的会默写我之前写过的所有代码

对了，看到 drakeet 的这个广播，我突然想起来我本周有一个应该纠错和反省的东西得提到，不能忘了（虽然马上要放暑假）

有朋友说他会反复看我写的东西，令我很感动，因为我也是这样，我也会无数遍不停看自己写的东西或分享，所以当有人细心一点会发现我的内容即使有错别字或不妥的内容，但最终都会相对改正和变得相对得当，这点上我也很佩服王垠，他的博客文章，我从来没有发现错别字，即使我是一个很敏锐且阅读文章特别慢的人 ... 只是说人的东西永远都会成为黑历史，经典是非常难得的，因为一个好的人应该是不断飞速成长的，如果黑历史没有精力去一一重新审视扶正，就会变得不负责任，或自己也不能接受，所以删除是好事。

很不幸，因为本频道全 TM 是没有用的计算机科学理论性较强的内容，而且一方面我又是比较正常洋文水平也不太差的学生，所以错别字本身就少的可怜，然后内容我又经常

无数遍不停看自己写的东西或分享，所以当有人细心一点会发现我的内容即使有错别字或不妥的内容，但最终都会相对改正和变得相对得当。

所以从来没有过错别字
这一点本频道一直以来的态度都可以证实，显然 judge 别人是不好的，但是我想这么干 🥺
这点上我也很佩服王垠，他的博客文章，我从来没有发现错别字，也从来没有看透过其内容，即使我是一个很迟钝且阅读文章特别不走心的人...

人的东西永远都会成为黑历史，经典是非常难得的，所以要努力努力再努力把自己整个人都变成黑历史，从不迟钝和后退~ I won't give up, no I won't give in
Til I reach the end and then I'll start again
No I won't leave, I wanna try everything
I wanna try even though I could fail
— Try Everything

（敲黑板）因为一个好的人应该是不断飞速成长的

如果黑历史没有精力去一一重新审视扶正，就会变得不负责任但又那么有意义，或自己也不能接受
但即使这样我们还是希望能回首过去，发现自己曾经的误区、鼓励别人走一遍自己走过、不可或缺的理解之路，所以保留是好事。

#OOP #fix 这个要订正的东西关于面向对象编程多态的底层实现。

这里提到的面向对象编程多态是指子类型多态 (subtyping polymorphism)

这里出问题的广播是我给 Ra 程序设计语言写的一点小示例

data Person { name :: Str }

data Student is Person
{ grade :: Nat * class :: Class }

data Teacher is Person
{ classes :: Vec of Class }

abstract fun Person.briefDesc(): Str = "a person called $self.name"

这里 Person.briefDesc 其实是一个虚(virtual)函数

我所谓的优化看这里

昨天我阅读《Lua 的设计与实现》这本书的时候，看了一下关于 GC 和面向对象实现（其实就是子类型重写 override 多态）的部分

"""
Ra 的多态也是使用类似 C++ 虚表的方法实现的，不过 Ra 支持的多态不多，也不支持多继承，但可以 mixin traits

当你定义拥有 abstract 操作符 (self fun) 的类型时，Ra 编译器自动为这个类型（必须 data，也即 Product type，因为 Sum type 可以直接进行判断没有必要使用多态）

data Person { name :: Str * _briefDesc :: <Self> -> Str }

"""

data Person { name :: Str * _briefDesc :: <Self> -> Str }

这是错误的，因为它没有明显地使用虚表优化
虽然它的确可行（我出错是因为多方原因共同作用，但是归根究底可以认为是学习还不够深入、想的太少、对所有权和优化不敏感），其实，虚表应该是被一个类所拥有的，而不是它的实例
也就是说，不存在可能的 _briefDesc 闭包成员，只可以有一个全局（和类本身一个作用域）的地方存储它们的虚表，其中包含实际实现闭包的引用

vtables[Person] = map(:briefDesc to ...)
vtables[Student] = map(:briefDesc to ...)

因为只有类可以 override 它超类的虚方法，而实例只能是类的实例，所以所谓的虚表，和一个类是 1:1 的数量所有权关系。
具体暑假再讲 #task

另外我一开始喜欢上 Telegram 的频道功能是因为它可以很敏捷且可控，更关键的是它不用接受评论，也绝不是要小孩子从头到尾以各种高姿态无所不晓无所不能指点地来和我说「我希望你要谦虚」要如何如何。

现在的情况是，尽管频道不能评论，但却可以转发在另外的频道进行附加评论和断章取义、像孔乙己一般视人论断，这完全违背了我的初衷。

我无意与人辩驳，所以没有任何正面回应，因为面对小人，我去一一解释就是在浪费自己的时间和继续令其从我自己这边收获更多。总之就是难免又陷入絮絮叨叨，

我非常热爱工作和写代码，我要尽快恢复投入，因此不多说了，周末愉快！

—
画重点，很多我真的想加双引号、加问号、加方括号，真的有那么夸张么？公平一点好不好？
另外孔乙己那个是什么鬼，我是理科生，但我还是知道的，你说的应该是阿 Q 吧？鲁迅先生的《孔乙己》里有什么描述『孔乙己视人论断』的表达吗？《孔乙己》被很多人的总结到的就是

这篇小说描写孔乙己作为一个没有考上秀才的读书人，缺乏实际技能，只会诸如“‘茴’下面的‘回’字有几种写法[1]”这样的迂腐“知识”。他丧失了做人的尊严，沦落为小酒馆里人们嘲笑的对象，后来因为偷书而被打断了腿。根据小说的内容，因为他姓孔，别人便从描红纸《上大人》上的“上大人孔乙己”这半懂不懂的话里，替他取下一个绰号，叫作“孔乙己”。 

倒是阿 Q 里和王癞胡一类混的还蛮适用的，批判我正合适，比喻也得明确一点好不好？如果因为是『读书人的事能算是偷』这个表达这样，是否套在『我是孔乙己』上都太奇怪了呢？

=_=||||

#C #Windows 我来总结一下用了哪些 API 怎么用，方便背

首先，你需要 aero.h [@ysc3839's gist] 这个 undocumented API header 其中包括必须的数据类型和子程序定义

#CSharp 版：需要使用 C# 的 P/Invoke （System.Runtime.InteropServices）特性

1. 对于外部的 C 结构体，只需要使用 struct 关键字定义，然后加上 [StructLayout(LayoutKind.Sequential)] 特性避免压缩移动优化结构体就可以了
2. 对于外部的 C 子程序，只需要将在一个类里定义的静态方法用 extern 修饰，这个方法加上 [DllImport("user32.dll")] 之类的特性就可以了，如果要指定载入使用的字符编码，需要使用 CharSet(=CharSet.Ansi) 特性指定

Trumeet 的示例还用了一个 [STAThread] 方法特性，只是这个单元只能单线程执行，不过其实不必加在 Main 静态方法上，和 COM 交互的时候加就好了，这个知道就好

写好了。

说起来这是三个月之前的事情了，不过还是有价值

== 无关的 Win32 Form API

static Application.EnableVisualStyles();

static Application.SetCompatibleTextRenderingDefault(bool);
static Application.Run(Form);

—

namespace System.Windows.Forms { Form }
class Form {
  protected void OnLoad(EventArgs);
}

== 有关的 Aero API

首先这里的 Aero 就是 Windows 所谓的毛玻璃特效
既然都用过这个特效，那都知道这个特效有三个最重要的参数：

1. 毛玻璃的特效状态，比如是否启用
2. 毛玻璃的颜色(color)、毛玻璃的模糊度、边缘和渐变色什么的，这些统称为毛玻璃效果的属性(attribute)
3. 毛玻璃的大小矩形框（这个是作为一个矩形视图也要有的）
4. Aero 是可以指定窗口动画的

== 有关的 P/Invkoke 封送（System.Runtime.InteropServices.Marshal）API

static Int32 Marshal.SizeOf<T>(); 

[NET 4.5.1+]
static Marshal.AllocHGlobal(Int32); 其中 H 是 Handle 的意思... 总之 Unix 系 Programmer 的直觉还是有点无法和 Win32 MSVC 系无法统一啊（UNIX 是直接 void *malloc(size_t);
static Marshal.FreeHGlobal(Int32); 用完了别忘记放回去别人还得用
static void StructureToPtr<T>(T, IntPtr, Boolean); 就是 memmove，Rust 的 ptr::write，第三个参数的意思就是复制数据之前要不要先删掉那块地方旧的分配（如果是新分配到的内存就不需要）
注意：
1. 如果你使用 deleteOld，且 ptr output 没有被正确设置，则可能破坏原有有效数据
2. 如果你不使用 deleteOld，且 ptr output 本来就已经没用了，则可能导致内存泄漏 （滑稽）

此外，要使用 C# 的 FFI 特性，还有 new T {} where T: structure 和 ref T 拿到指针的特性

—
那实际上只需要用这两个 API，一个 Getter 一个 Setter，都 Take 一个 Window Handle，一个 struct _WINDOWCOMPOSITIONATTRIBDATA *



bool __stdcall pfnGetWindowCompositionAttribute(HWND, WINDOWCOMPOSITIONATTRIBDATA*);

bool __stdcall pfnSetWindowCompositionAttribute(HWND, WINDOWCOMPOSITIONATTRIBDATA*);

我实在不知道 typedef 还可以这么用 typedef int (*add2)(int);... 等于这个 type 的名字是 (*add2)(int), 看起来根本不是一个标识符... 或者说根本不存在名字（int (*)(int) 本身就是 C 的函数指针类型）... 奇妙
—

那

WINDOWCOMPOSITIONATTRIBDATA

这个类型又是啥子呢？它就是 Windows 的窗口混成器参数：

struct {
enum WINDOWCOMPOSITIONATTRIB Attrib;
void *pvData; size_t cbData;
}

其中 WINDOWCOMPOSITIONATTRIB 有很多单选项啦，比如 WCA_EXCLUDED_FROM_LIVEPREVIEW （不允许实时预览）、WCA_TRANSITIONS_FORCEDISABLED（不允许移动？）
后面的 void *pvData 和 size_t cbData 是一家的，它们指向一个内存切片（buffer; slice）一般可以被解释为

struct ACCENT_POLICY {
  enum ACCENT_STATE AccentState;
  DWORD AccentFlags;
  DWORD GradientColor;
  DWORD AnimationId;
}

enum ACCENT_STATE {
ACCENT_DISABLED = 0,
ACCENT_ENABLE_GRADIENT = 1,
ACCENT_ENABLE_TRANSPARENTGRADIENT = 2,
ACCENT_ENABLE_BLURBEHIND = 3,
ACCENT_ENABLE_ACRYLICBLURBEHIND = 4, // RS4 1803
ACCENT_ENABLE_HOSTBACKDROP = 5, // RS5 1809
ACCENT_INVALID_STATE = 6
}

一般直接用毛玻璃（BLUR BEHIND）

== 这个合成属性的使用

首先，准备好目标窗体 hwnd 和 Aero 参数 struct AccentPolicy

static int SetAero(IntPtr hwnd, ref AccentPolicy policy) {...}

准备数据

var wcaps = new WindowsCompositionAttributeData { Attribute = WindowCompositionAttribute.WCA_ACCENT_POLICY };

wcaps.SizeOfData = Marshal.SizeOf<AccentPolicy>();
wcaps.Data = policy;

Trumeet 是直接复制了别人的 SizeOf, AllocHGlobal, StructureToPtr, FreeHGlobal... 走了一遍 StructToNewAlloc 的流程，但是其实拿到此结构的指针传递数据就可以了，也不一定得堆分配。
然后直接使用 setter attributeDatas[AccentPolicy] = ...（拟

return SetWindowCompositionAttribute(hwnd, ref wcaps);

Aero 参数 AccentPolicy 怎么拿？首先我们得清楚，架构此结构体的方法不能返回一个本地分配的 AccentPolicy... 其次最好也不要返回一个 struct AccentPolicy，因为它要复制比较多的数据....
那既然如此为什么不把 SetAero 当成是 MakeAeroEffect 子程序的辅助者，然后直接在 MakeAeroEffect 里分配？

static int MakeAeroEffect(IntPtr hwnd, AeroState st, int aeroFlags = 0, int gradientColor = 0x00000000, int animId = 0) {...}

这里就对应到了之前的四个特效属性

var params = new AccentPolicy { AccentState=st, AccentFlags=aeroFlags, GradientColor=gradientColor, AnimationId=animId };

然后按照约定，调用 setAero

return setAero(hwnd, ref params);

就 OK 了

以上讲到的是 CSharp P/Invoke Windows 10 Aero Hidden API 的代码，不过 Windows 7 的（默认 Aero）要使用 DwmApi.dll 和 DwmExtendFrameIntoClientArea 来把 window 的某个 frame 化为新混成区域，因为默认有 Aero glass

你学到的应该是：
1. 使用 [DllImport(...)] extern ... 动态链接外部函数库；使用 [StructLayout(LayoutKind.Sequential)] 定义可以被正确传递给 C FFI 的结构体
2. 使用 IntPtr 和 ref （当然它们不如 SafeHandle，不过后者是只有真正的 C#+Windows CNI 原生接口 程序员才知道）
3. 如何使用 SetWindowCompositionAttribute 设置指定窗体混成属性
4. Windows 的 Aero 混成属性：AccentPolicy 和 enum AccentState，它的四个子属性（状态、特性标志、渐变、动画效果）