#cs #algorithm #algor #share #scarper

[DuangSUSE@duangsuse]~% nokogiri -EGBK https://open.163.com/movie/2010/12/7/S/M6UTT5U0I_M6V2TTJ7S.html

Your document is stored in @doc...

... 人家是动态 JS 生成的，好吧... 不对啊，Nokogiri 有问题...

还是有问题... 算了，上静态下载好的

kate ~/下载/scarper/麻省理工学院公开课：算法导论_跳跃表_网易公开课.html

（这里有 encconv 工具可以转换编码，但是上次使用导致了不知缘由的死机，现用 Kate 转换到 UTF-8）
（Nokogiri 貌似的一个 bug ？ 导致使用本地文件时编码指定参数无效）

nokogiri 下载/scarper/麻省理工学院公开课：算法导论_跳跃表_网易公开课.html



list = @doc.at_xpath("/html/body/div[6]/div/div[3]/div")
videos = list.children[1..45]

lessons = videos.find_all { |it| it.is_a? Nokogiri::XML::Element }

class Lesson
  def initialize(element)
    @label = parseLabel(element)
    @name = parseName(element)
    @desc = parseDesc(element)
  end

  def self.parseLine(tag, second)
    tag.children.find { |it| it.name == 'p' }.children.find { |it| it.name == second }.children.first
  end

  def parseLabel(tag)
    self.class.parseLine(tag, 'span')
  end

  def parseName(tag)
    self.class.parseLine(tag, 'a')
  end

  def parseDesc(tag)
    tag.children.find_all { |it| it.name == 'p' }.last.children.first
  end

  def to_s
    "#{@label} #{@name}\n\t#{@desc}"
  end

  attr_accessor :name, :label, :desc
end

parsed_lessons = lessons.map do |it|
  begin
    Lesson.new(it)
  rescue
  end
end

puts parsed_lessons

[第1课] 课程简介及算法分析
课程简介及算法分析
[第2课] 渐近符号、递归及解法
渐近符号、递归及解法
[第3课] 分治法（1）
分治法（1）
[第4课] 快排及随机化算法
快排及随机化算法
[第5课] 线性时间排序
线性时间排序
[第6课] 顺序统计、中值
顺序统计、中值
[第7课] 哈希表
本课为我们引入了一种简单而高效的数据结构——哈希表（又译作散列表）。课堂上，教授为我们介绍了哈希表的基础知识，讲述除法哈希法、乘法哈希法以及开放寻址法，并对它的复杂度做了分析。除此之外，他还就如何高效地运用哈希表、如何处理可能遇到的“碰撞”问题等进行了讨论。
[第8课] 全域哈希和完全哈希
本课继续深入学习哈希表，这节课的内容主要是哈希表的高级运用。为了应对哈希表发生“碰撞”的问题，教授这次给我们带来了全域哈希和完全哈希。这节课里涉及到了很多美妙的数学知识，算法的证明过程相当有趣。学习这节课的内容，将会使你的哈希表更为高效、更为稳定。
[第9课] 二叉搜索树
本课为我们带来了一种常用的数据结构——二叉搜索树。这种数据结构有着媲美快速排序的速度，同时又能完成插入、删除和查找等动态化的操作，高效而又易于实现。教授将在本节课为我们讲解二叉搜索树的原理，运用巧妙的数学知识来证明它的高效性。二叉搜索树有什么优缺点，随机化二叉树又如何解决问题，这节课都会一一为你解答。
[第10课] 平衡搜索树
如果搜索树的结构不能保持平衡，它的运行效率将会大打折扣。这节课上，我们将会着重学习一种著名而实用的平衡树算法——红黑树。教授将会从红黑树的运行效率入手，再扩展到实际构造和维护红黑树。讲解过程中加入了大量的图例，更加方便大家消化吸收。
[第11课] 扩充的数据结构、动态有序统计和区间树
在实践中，我们对数据结构的功能需求并不仅仅局限于基本的插入、删除和查询操作。为了使数据结构能满足我们的需求，第11课里，教授给我们讲授了如何扩展一个现有的数据结构。教授以红黑树的几种扩展算法为例，讲解了的扩展的方法论以及策略。掌握了这些以后，你实现新功能起来将会更加得心应手。

[第13课] 平摊分析，表的扩增，势能方法
有时候，就算是再大的困难，只要人人都愿意出一份力，也能大事化小。而算法的分析也有这种情况。有时候某几步操作相当复杂，但是如果将一系列操作平均起来，它的代价可能也并不是那么的高。《算法导论》第13课里，教授就给我们讲授了几种平摊分析的方法，包括聚集法、记账法还有势能法。这些都是算法分析的重要方法，掌握它们将能让我们更加准确地评估算法优劣性。
[第14课] 竞争性分析，自组织表
我们将要关注一种在线算法的分析方法——竞争分析。实际应用中，数据不会总是全部出现在我们面前，而是一个接一个地出现。这样我们就不能安排最好的对策来处理问题。但是我们也可以证明，在线算法并不会跟最优算法差太远。这节课上，教授将会结合上一节课中平摊分析的内容，给我们展示这一个相当精彩的分析过程。
[第15课] 动态规划，最长公共子序列
我们将会学到一个常用的优化算法的技术——动态规划。它是一种解决最优解问题的一种方法，它还是信息竞赛选手必须掌握的技能。在这一节课上，教授会围绕最长公共子序列（LCS）的实现问题来讲解可动态规划算法的特征，还有动态规划的一般优化思路和方法。通过应用动态规划，我们的程序性能将会获得显著的提升。
[第16课] 贪婪算法，最小生成树
《算法导论》第16课中，教授给我们带来了一种新的算法思想－－贪婪算法的思想。和动态规划一样，贪婪算法是一种求解最优问题的方法。它强调通过寻找局部的最优解，从而节省大量的时间和资源。这次课里，教授会围绕图的最小生成树的问题，分析贪婪算法的思想和应用条件。我们还会看到一个贪婪算法实例－－Prim算法，看看它又是如何为AT＆T公司取得垄断的地位。
[第17课] 最短路径算法：Dijkstra算法，广度优先搜索
从第17节的《算法导论》开始，MIT的教授将会为我们上演精彩的最短路径三部曲。在第一乐章里，我们会学习到一个非常著名的求解最短路径算法－－Dijkstra算法。教授首先会给我们讲解最短路径的特殊性质，然后针对一种非负权值的的最短路径问题，给我们详细讲解Dijkstra算法的做法，以及对它的正确性进行深度的分析。
[第18课] 最短路径算法：Bellman和差分约束系统
承接上一回，《算法导论》第18集是最短路径三部曲的第二乐章。在这一节课上，教授给我们讲解的是能够处理负权值最短路径问题的算法——Bellman-Ford算法。Bellman-Ford算法不仅能够检测图中的负权环，同时它还能解决线性规划的差分约束问题。教授将给我们详细讲解Bellman-Ford算法的流程，并证明它的正确性。这些内容都会跟下一节课的内容息息相关。
[第19课] 最短路径算法：点的最短路径
《算法导论》的第19课终于到了最短路径三部曲的高潮。这次我们将会着眼于全点对最短路径问题，教授将会给我们用三种算法来解决这个问题。除了上节课我们学到Bellman-Ford，我们还会用一个精彩的技巧，将问题与矩阵乘法联系起来，也就是Floyd-Warshall算法。而最后，我们将会学习最强大的Johnson算法，来为最短路径三部曲唱响最华丽的解答。
[第20课] 高级课题 并行算法（一）
《算法导论》课程的最后将介绍一些高级课题。本课介绍的是并行算法。解答了1、面对多核处理器技术的不断革新，对算法如何优化，使得效率可以倍增；2、如何来分析并行算法对运行速度的提升；3、著名的国际象棋人工智能“深蓝”曾经的宿敌是谁。
[第21课] 高级课题 并行算法（二）
《算法导论》第23课将承接上一回，这一次教授将给我们介绍并行算法的实际应用，讲解如何使用多线程来实现算法的并行化。课上教授将会用矩阵相乘以及归并排序为例子，从算法框架到运行时间分析来教大家实际认识多线程并行算法。
[第22课] 高级课题 缓存参数无关算法
承接上一课，本课教授介绍了缓存敏感算法和缓存参数无关算法的概念，首先从计算机的缓存-内存分层存储模型引入，讨论了缓存参数无关算法的性质和分析上的优越性，并且具体讨论了在分层存储模型中的算法性能分析和存储设计。
[第23课] 缓存无关算法2
《算法导论》课程的最终章将继续深入分析缓存参数无关算法，教授将在本次课上为我们讲解多路归并排序算法是如何与缓存参数无关算法模型相结合。他将用一种名为K漏斗的特殊数据结构从实现到分析来给我们展示如何更高效地利用缓存来优化算法设计。

语法由于 Nokogiri 那贫瘠的 API 非常难看且不简洁，由于我很累所以懒得优化
逻辑十分简单，但由于 Nokogiri 贫瘠的包装写得很难看

没有做容错处理，所以老是出现解析错误。
权当玩玩。本身也没什么复杂的逻辑

#life 好了，那又回到 duangsuse 的四日常（看问题讨论、说笔记、写文档做设计、写代码）之一了... 今天一行代码不写，最近一行代码都不写。主要还是逻辑弄明白... 🐸

Gekyll 啊、Pickle 啊、dio 啊
都不是今天的事，因为我最好不要熬夜，至少是目前

#android #dev 啥时候 duagnsuse 也学学 Android 开发...

现在算是入门了吧... 入门即被踢出门？（

反正就是那种菜到爆炸的样子... 虽然别人往往都很菜吧... 或者说大佬都比我多一两年的经验
... 有什么意义呢... 自己还是很菜啊，身边的人是什么水平尚且不能了解，怎么能以别人菜为由给自己优越感呢？ 😶

是呢... 反正就是那种大佬一大堆的情况下系统管理都不会 Docker 也不会 ReactiveX 也没了解过的样子，啥是 Flowable 啊，啥是 Observer 啊

GoF 的 23 种 OOP 模式我又记住了几种呢？创建型的模式，工厂、构建器、抽象工厂外... 还有至少 3 个没记住啊... 不是天才呢... 为什么不能是天才... 那样一下子就什么都想到了 什么都明白了... 太菜了

（第一次见抱怨自己不是天才的，hhhhhhhh

不是天才也能活啊，连 PC 是啥都不知道的人、把 Android 平板当成 iPad 的人、成天晚上偷偷开着班上教学一体白板给自己的充电宝充电的人、把顶撞老师哗众取宠作为自己爱好的人、兴奋好奇地围观别人跳楼的人，不都还活着么...

不是天才的话 1k 小时定律依然是有效的啊，只要一直努力用心的做某件事情，一定就能得到想要的效果吧...

虽然这一切精力啊，都要分散到超过 10 个的子科目，子知识范畴里面去呢... 那就要 10k 个小时呢，就是两年也没关系，只要能做到想要的水平

偶尔想回去看看曾经与 @drakeet 撕过的 B... 我真是无聊...

如果要这么做，内心肯定是抱着不服气并且想偷偷批判一番的情绪做的

因为啊，drakeet 可能是那个时候技术其实也不怎么样（当然现在也不怎么样）的我所觉得有点偏向「骄傲」的人呢...

... 好好想想，有什么意义呢？事实上我也没有做过这种事...
看不起就看不起嘛... 我不这么想就好了

其实后来发现我大概也是有错误的，没有了解他，人们各有各的性格，有些人受不了对自己的批评，有些人无法接受对自己软件的建议，可能有几个建议是错的就会比较恼火，实属正常。只不过自己不是这样的，就不容易交互角度思考

所谓大佬啊... 所谓神乎其技的「杂学」后端... 其实能活好，做到什么并没有什么差别？不过有些人想做一些其他方向更好的东西，就要学习一些可能是比较多、比较难理解或者由于谣传让人不敢碰的知识点，有何优越可言？都是一样的事情

算了算了开始说笔记（

（有人说晚上人们更偏向情绪化、感性化一些，果然如此？）跑

得做且做嘛（逃

说起来再来个老掉牙的推荐... 我上上周打印资料的时候也去那里过了，可惜没墨水了...

CTF Wiki，目前比 OI Wiki 完善

https://ctf-wiki.github.io/ctf-wiki/executable/elf/elf_structure/

不过啊，虽然现在偏向数学性、偏向理论性的一些东西还是不好理解，至少其他的都还不错，能用了，可喜可贺。上次对 Telegram $RICH 这个标签的分析就是一个例子，不管怎么样是不是天才（笑）技术进步都是在那里的（指背书）所以值得庆祝？（（（（不到能手写红黑树的程度绝不罢休

我感觉这次再让我花个两天时间逆向 CoolApk 的 liba.so （密钥生成算法）已经不是问题了

#blog #share #cs #pl #plt #agda #recommended
https://ice1000.org/lagda/

顺推一波冰封哥新出的 LAgda 博客，大部分代码都是用 Agda 写的，连文章目录都是 😶

「中间表示」博客维护良好，经常更新并且作者往往都全天在线
主要内容设计 Java/Kotlin、C/C++、程序设计语言理论、编译原理、静态分析、算法优化等...

大概内容主要可以由编译原理系的同学理解使用

哦我突然想起来上次那个 foldl（其实是 foldr... 喷，我误解了，其实... wiki 上的是错的）

哦突然又想起来我还不知道啥是 Functor... 管他呢，会定义就好了

前面几个出错主要是因为我太蠢<del>萌</del> 了，少给自然递归传递了几个参数（当然因为 Currying 的原因不会说啥 arity mismatch 参数长度错误），结果 Haskell 弄出了个啥 Infinite type 错误，和 Kotlin 的类型错误一样迷

mfold init op xs = init
mfold init op (x:xs) = op (mfold init op xs) x

然后我们知道 mfold 的类型（可以用 ghci 指令 :set +t 显示推导出的类型）肯定是

mfold :: a -> (a -> b -> b) -> [a] -> b

呃.. 第一个 a 是说 init
(a -> b -> b) 是说 op
[a] 是说 xs b 是说整个 mfold 的返回值...

当然，把 b 换成 a 也可以通过检查... 之所以引入一个 b 大概是为了... 呃...

其实 a -> (b -> a -> b) -> [a] -> b 也可以... 总之,,, 怎么描述这种纯纯的自然递归类型呢... 我觉得还是 a -> (a -> b -> a) -> [a] -> a 好

因为... 更多限制？（算了还是上面那个限制最小

不过... 我觉得其实也没啥卵用嘛... 想不到有谁会怎么使用这个多出来的 b

a -> b 是匿名函数（可以认为是 Kotlin 里的 lambda）的参数，代码块返回 b

首先一步步看此递归函数... 猜类型

op (mfold init op xs) :: a x :: b :: b

... 那这就奇怪了，看起来 (mfold init op xs) 好像是 b 类型才对... 算了不看了，以后有的是时间

#life #school 唉... 现在真的是没时间啊... 我还什么都没说就 11 点了
明天早上又要上学
然后下周六才回来，我看这笔记队列要爆炸的，迟早药丸