什么是 CLR ?

作者:By Vance Morrison – 2007
原文链接:https://github.com/dotnet/coreclr/blob/master/Documentation/botr/intro-to-clr.md
翻译:dontpanic

什么是公共语言运行时(Common Language Runtime, CLR)?简单来说就是:

公共语言运行时(CLR)是一套完整的、高级的虚拟机,它被设计为用来支持不同的编程语言,并支持它们之间的互操作。

啊,有点绕口,同时也不太直观。不过这样的表述还是 有用的 ,它把 CLR 的特性用一种易于理解的方式分了类。由于 CLR 实在太过庞大和复杂,这是我们理解它的第一步——犹如从万米高空俯视它,我们可以了解到 CLR 的整体目标;而在这之后,我们就可以带着这种全局观念,更好地详细了解各个子模块。

CLR:一个(很少见的)完备的编程平台

每一个程序都有大量的运行时依赖。当然,一个程序需要由某种特定的编程语言编写而成,不过这只是程序员把想法变成现实的第一步。所有有意义的程序,都免不了需要与一些 运行时库 打交道,以便能够操作机器的其他资源(比如用户输入、磁盘文件、网络通讯,等等)。程序代码还需要某种变换(翻译或编译)才能够被硬件直接执行。这些依赖实在是太多了,不仅种类繁多还互相纠缠,因此编程语言的实现者通常都把这些问题交由其他标准来指定。例如,C++ 语言并没有制定一种 “C++可执行程序” 格式;相反,每个 C++ 编译器都会与特定的硬件架构(例如 x86)以及特定的操作系统(例如 Windows、Linux 或 macOS)绑定,它们会对可执行文件的格式进行描述,并规定要如何加载这些程序。因此,程序员们并不会搞出一个 “C++可执行文件”,而是 “Windows X86 可执行程序” 或 “Power PC Mac OS 可执行程序”。

通常来说,直接使用现有的硬件和操作系统标准是件好事,但它同样也会把语言规范与现有标准的抽象层次紧密捆绑起来。例如,常见的操作系统并没有支持垃圾回收的堆内存,因此我们就无法用现有的标准来描述一种能够利用垃圾回收优势的接口(例如,把一堆字符串传来传去而不用担心谁来删除它们)。同样,典型的可执行文件格式只提供了运行一个程序所需要的信息,但并没有提供足够的信息能让编译器把其他的二进制文件与这个可执行文件绑定。举例来说,C++ 程序通常都会使用标准库(在 Windows 上叫做 msvcrt.dll),它包含了大多数常用的功能(例如 printf),但只有这一个库文件是不行的。程序员如果想使用这个库,必须还要有与它相匹配的头文件(例如 stdio.h)才可以。由此可见,现有的可执行文件格式标准无法同时做到:1、满足运行程序的需求;2、提供使程序完整所必须的其他信息或二进制文件。

CLR 能够解决这些问题,因为它制定了一套非常完整的规范(已被 ECMA 标准化)。这套规范描述了一个程序的完整生命周期中所需要的所有细节,从构建、绑定一直到部署和执行。例如,CLR 制订了:

  • 一个支持 GC 的虚拟机,它拥有自己的指令集(叫做公共中间语言,Common Intermediate Langauge),用来描述程序所能执行的基本操作。这意味着 CLR 并不依赖于某种特定类型的 CPU。
  • 一种丰富的元数据表示,用来描述一个程序的声明(例如类型、字段、方法等等)。因此编译器能够利用这些信息来生成其他程序,它们能够从“外面”调用这段程序提供的功能。
  • 一种文件格式,它指定了文件中各个字节所表达的意含义。因此你可以说,一个 “CLR EXE”并没有与某个特定的操作系统或计算机硬件相捆绑。
  • 已加载程序的生命周期语义,即一种 “CLR EXE 引用其他 CLR EXE” 的机制。同时还制订了一些规则,指定了运行时要如何在执行阶段查找并引用其他文件。
  • 一套类库,它们能够利用 CLR 所支持的功能(例如垃圾回收、异常以及泛型)来向程序提供一些基本功能(例如整型、字符串、数组、列表和字典),同时也提供了一些与操作系统有关的功能(例如文件、网络、用户交互)。
Continue reading “什么是 CLR ?”

离去(二)

没想到这么快就要经历第二次离别。订了跟上次同一趟的航班,两小时后出发。

爷爷得阿尔茨海默症已经十多年了。那一刻我仍然记忆犹新——还在上初二的我放学回家,家里人正围坐在一起吃饭;爷爷神情茫然,转过头来看向我,叫出了我表哥的名字。爸爸又问了一遍,爷爷却还是想不起我的名字。他的左手已经不再灵便,勉强地端起饭碗送至嘴边,碗险些要掉下来。家人发觉不对,就急忙让爷爷在沙发上躺下休息,并叫来了120。

爷爷在得病之前,一直都是家里的大厨,逢年过节必定下灶,做出一大桌子的饭菜。过年之前要掂量好几天,得有鱼有肉、几荤几素、凉菜热菜一应俱全,全写在小纸条上。我印象最深的是虎皮椒里面塞肉馅,外面带着辣椒的清香,里面是满满的肉香。其他的鸡鸭鱼肉自不必说,虽然有点油腻,但是一定备受欢迎。刚得病的时候,我难以接受这个现实:爷爷还是那个爷爷,为什么一直躺在沙发上不再下厨了呢?我还拽着他起来,觉得他只是犯懒不再愿意干活了。似乎记得爸爸还试过让爷爷再做一次饭,但已然再无法掌握他以前做菜的秘诀。

小时候爷爷奶奶的重男轻女,在上一篇文章中已经可见一斑。听姑父回忆,当爷爷得知我是个男孩之后,直接出门买了只烧鸡、就着小酒,在家里独享其乐。还有一件事:大概我只有几岁的时候,有一天姑姑和大姐来想要带我去洗澡。我本来不想去;大姐说“不去以后就不带你玩”,小小的我权衡利弊决定还是跟去了。结果坐在自行车的后座上,我的脚就被车轮刮住,脚踝处受了伤。后来回家躺在床上,之间一只拖鞋从走廊飞了进来,那是爷爷生气在打姑姑。前有喝酒吃烧鸡、后有拖鞋飞进屋,外加反孙子集团,这就是我这个老幺在爷爷心中的地位。

然而从小到大,我却经常发孩子脾气,跟爷爷闹别扭。家里人,我似乎顶撞爷爷最凶,跟他喊、跟他嚷,却从来不曾这么顶撞过奶奶和爸爸妈妈。跟爷爷抢电视看,质问他“你听新闻听啥了”;其他的事由记不清了,但也一定是很大声;爷爷经常就嘟囔着骂一声,翻身躺在床上睡觉去了。然而闹归闹,晚上想要买零食,还是要跟爷爷要钱。爷爷就经常笑着把褥子掫开,拿出10块钱给我。我就跑下楼,一袋牛板筋、一小盒康师傅麻辣牛肉面。一定要小盒的,因为我总是觉得小盒的味道不一样。

爷爷在得病之前,曾经“走丢”过一次。那一晚爷爷没回家不知去向,急得家里人报了警。后面的事情我有点记不清了,总之最后平安归来。在那之后,爸爸就给爷爷配了一台手机,诺基亚直板。当时手机到了,卡还没办,爷爷愣是每次都揣在衬衫口袋里,出去溜达也要拿出来让朋友们看看他儿子送给他的东西。

爷爷退休之前,我觉得在区里肯定算得上是“叱诧风云”的人物,在教育局、民政局、粮食局、交通局(得加个等字,忘记是四个还是五个)都任过局长级别的职务,最后退休时回到了教育局。小时候家里虽然不富裕,但也绝不贫苦。也不知道我活到现在,有没有给爷爷丢脸呢。

还在住平房的时候,院子里有一个菜园,爷爷会在里面种一些茄子、辣椒、葡萄之类的蔬菜水果。除此之外,房子门前还种了两棵樱桃树和一棵沙果树,院子里还有一个地窖,可以储存蔬菜。 院子后面还有一个奇特的地道,从地上向地下延申,小时候跟表哥们进去探过险,但是没有走到头就害怕退了回来。院子后门出去就是十九中的操场,奶奶曾经在那当老师,那个操场也是我童年玩乐的“主战场”。后来爷爷奶奶搬去住了楼房,这个院子就卖掉了。现在想来,这个小院子,要不是诸如煤气、下水等一些基础设施不到位,真的是享受生活的好地方。

爷爷跟奶奶,在我有限的记忆中,总是伴随着争吵。但吵归吵,爷爷得病后,要是奶奶不在身边,就经常会找她。奶奶去世后,爷爷还经常会停留在柜子前面,看看上面摆放着的家里六个人的合照。巧合的是,在爷爷出殡前一天,我们烧完纸之后买了一提农夫山泉;它们的生产日期刚好是12月15日,正是奶奶离世的日子。

好想再吃一次虎皮辣椒裹肉馅啊。

长模式与 16 位程序

这是我在知乎的回答:https://www.zhihu.com/question/310785889/answer/58670983

首先我们要把 16 位程序分成两类来看:跑在实模式下的 16 位程序和跑在保护模式下的 16 位程序。长模式是支持兼容 16 位的保护模式的(x86-64 白皮书):

但由于在长模式下移除了虚拟 8086 模式,无法运行实模式的(直接访问硬件的)16位程序。

至于为什么移除了虚拟 8086 模式,只能认为是不想再多背包袱了。已经有的包袱甩不掉,但至少别给自己再找新麻烦…

其实 Intel 在 80286 添加保护模式时就不想带这个包袱了,它没有提供直接的方法从保护模式转换回实模式(即无法支持实模式 16 位程序) 。也许是大家怨声载道,而后在 386 中 Intel 添加了虚拟 8086 模式,允许直接在保护模式下虚拟一个实模式出来。这样在 32 位操作系统中,实模式的 16 位程序才能运行。所以到了 64 位,这样的包袱不再扔一次怎么行呢,实在不行再把它加回来就好了,毕竟这事 Intel 已经干过一回了 🤣

总而言之,长模式是可以运行 16 位程序的,但只兼容保护模式。不过 Windows 也无法运行 16 位保护模式下的程序,这是 Windows 本身不再支持了的原因,不是长模式的限制。

错误模型 – The Error Model

  • 原文链接:http://joeduffyblog.com/2016/02/07/the-error-model/
  • 作者:Joe Duffy
  • 翻译:dontpanic

译注:下文中所有的“我”、“我们”均指代原作者 Joe Duffy 或其所在团队。作者总结了目前主流编程语言中常见的错误模型的优缺点,同时分别给出了自己的针对不可恢复错误(Unrecoverable Error)和可恢复错误(Recoverable Error)的处理方案。由于本文有一些惯用语和专业词语,受限于我的水平,可能出现翻译错误、或措辞与主流方案不同等问题,欢迎指出以便修正。本文较长,请做好长时间阅读的准备。

译注:前情提要:原作者 Joe Duffy 曾在微软参与开发一款操作系统 Midori,这是一款研究型/孵化型项目。这款操作系统主要由一种 C# 的变种语言(有人称作 M# 语言)编写。

The Error Model

Midori 使用了一种基于 C# 的、支持 AOT 编译、类型安全的语言。除了我们的微内核,整个系统都是使用这种语言编写的,包括驱动程序、域内核(Domain Kernel),以及全部的用户代码。我在这段时间里收获了很多,现在是时候总结一下了。整个语言涵盖的东西太多了,我会分成几篇文章来阐述,就先从错误模型开始。错误(Errors)的传递与处理在任何编程语言中都是非常基础的部分,而对于用来编写高可靠操作系统的语言来说更是如此。就像 Midori 项目的其他部分一样,任何修改一部分都应该从全局的角度来考量,并进行不断地迭代。我经常从原来的同事那里听到说,错误模型是他们在 Midori 上开发程序时最怀念的部分。我也很怀念这部分。那么废话少说,我们这就开始。

错误模型简介

错误模型需要回答的最基本的问题是:“错误”应该如何传达给程序员和用户?这问题似乎很简单。

要回答这个问题,最大的阻碍之一是:如何定义什么是“错误”。很多语言把 Bug 和可恢复错误归为一类,用同样的机制来处理,比如把空指针引用错误、数组访问越界错误与网络连接错误、语法分析错误混为一谈。这种一致性初看起来很美好,但它有着深层次的问题——这种一致性会造成很大误解,并且通常会导致程序员写出不可靠的代码。

总的来说,我们的解决方法是同时提供两套错误模型。一方面,对于程序的 Bug,我们提供了快速失败(Fail-Fast)模型,在 Midori 中我们称其为放弃(Abandonment);另一方面,对于可恢复的错误,我们也提供了静态受检查异常(Statically Checked Exception)。这两种错误模型从编程模式到背后的机制都截然不同。放弃会无条件地立即终止整个进程,不会再运行任何用户代码(需要说明的是:一个典型的 Midori 程序会由很多个小的、轻量级的进程组成);异常则允许恢复用户代码的执行,在这个过程中类型系统会起到重要的检查和验证的作用。

我们的旅程漫长而曲折。为了讲好这段故事,这篇文章分为以下6个主要部分:

  • 野心和经验
  • Bugs 不是可恢复错误!
  • 可靠性、容错性和隔离性
  • Bugs:放弃(Abandonment)、断言(Assertions)和合约(Contracts)
  • 可恢复错误:类型导向的异常
  • 回顾与总结

现在看来,有些结论似乎很明显,尤其是在更现代的系统语言
(比如 Go 和 Rust)出现之后。但是一些结论还是让我们很惊讶。我会尽量省略废话,但也会提供足够的背景故事。我们走过很多弯路,但我觉得这些弯路甚至要比最终的结论更有趣。

Continue reading “错误模型 – The Error Model”

离去

周六这天,不知道哪来的勇气,我在邮件里怼了美国那边的一个Principal同事,晚上七点多才坐下来吃饭。吃到一半就接到爸爸的电话,连夜收拾了一下,坐着早上六点的飞机回家。

这是我这26年的人生历程当中第二次参加葬礼。我坐在一台依维柯的最后一排,车里面都是亲近的亲戚家属。前面是一辆小卡车,拉着一头纸牛和花圈纸钱金砖银元宝。里面坐着我爸,还有我奶奶的遗照。

车里面的亲戚们还在时不时地聊天,聊得我很烦。车开了一会,他们终于不聊了,车里面的广播又变得格外刺耳,广播节目在介绍生活小窍门,比如如何防止铁锅生锈。我时不时地回头从后车窗望去,想看看后面的车队有多长。

奶奶一共兄弟姐妹九个,她是老九,再加上爷爷这边的亲戚,我爸的表亲兄弟姐妹很多。所以我有好几个大姑,好几个老姑,大娘二大娘……逢年过节家里总少不了来串门的亲戚们。

在火葬场的门口,司仪在找人进门帮忙抬老人。我快步往前走了几步,还没走到里面,司仪就说人手已经够了。也许平时好好孩子守规矩惯了,我站在那迟疑了一会,还是想进去再多看奶奶两眼的,直到一个表哥说“你应该进去看看”,我才大步向前走去。

在上小学以前,我经常跟爷爷奶奶住在一起。那时候还住在一间平房,门口有一棵大沙果树。我有一个小小的三轮车,想骑的时候得找奶奶搬出来;我喜欢吃三鲜伊面,奶奶还搬了一箱回来过;没事的时候她经常在床上摆扑克,我就在旁边看,那个时候还学会过几种,不过现在已经全都忘得差不多了。由于爷爷奶奶太偏向,导致我的几个表哥和表姐成立了一个“反孙子集团”,由最大的表哥带头高举“反孙子集团 只在姥姥家”在院子里示威游行。我那时大概只有两三岁的样子,最愿意跟他们玩,还跑过去跟在他们后面一起走,把我爷爷气的不行。

奶奶已经被推到了吊唁厅的中间。也许是最后几个月瘦的,不太像平时的她。她身上盖着红布、放着花,头上还带着以前的那顶小红帽。戴孝带的家属们都站在吊唁厅的一侧,其他亲朋好友们绕着遗体走一圈,鞠个躬以表悼念。吊唁厅里异常寒冷,哀悼乐一响起,让人的心情更加沉重。

后来我上了小学,就跟爸爸妈妈住一起了。爷爷奶奶也搬进了楼房,每到寒假暑假我就住在那,跟奶奶睡一起。除了写寒假作业,我基本上就是跟奶奶看电视剧,什么《还珠格格》、《征服》、《重案六组》、《铁齿铜牙纪晓岚》……都是在那个时候看过的。平时大多是奶奶做饭,派系就是很典型的东北家常菜,土豆炖豆角、酸菜汤之类的。奶奶还会经常自己蒸馒头花卷,有时候碱放多了,馒头就会黄黄的,吃起来带着一股苏打味。

戴孝带的亲戚家属们也走过一圈,鞠过三次躬,奶奶就要被推进去火化了,爸爸和姑姑们几乎到了悲痛的极点。我看着奶奶的遗体,心情非常沉重,但几乎没有眼泪。大家坐在等候室里面,逐渐地开始聊起了天,悲伤的氛围才散去一些。我手里捧着奶奶的遗照,是她之前照的证件照,这是我熟悉的那个奶奶,美丽、开朗和自信。

奶奶一直都有糖尿病和高血压,降糖药、降压药一直都在吃,所幸的是一直没有发生明显的并发症。在爷爷得阿兹海默症之后的一段时间里,奶奶一个人还能照顾得了他。但是毕竟两个老人单独住不太放心,就让他们搬到姑姑家里,让姑姑帮忙照顾。自那以后,也许是觉得自己不再能独立生活,奶奶的心态就越来越差,唉声叹气的时候也越来越多。有一次她想收拾东西搬回去,爸爸和姑姑最终没同意。雪上加霜的是,奶奶开始需要每天打胰岛素来控制血糖,大概这让她更加觉得自己“没什么用”了吧。

捡过骨灰之后,我们就前往墓地了。墓地的工作人员出了点差错,墓还没打扫完,字也还没刻。等过一会,终于可以将骨灰盒下葬,墓碑前也摆好了遗照、贡果和烟酒,角落上放着两头手掌大的石狮子。后面的地上的两挂鞭炮劈里啪啦地响起来,我看着照片,眼泪止不住地留下来。

奶奶的病情恶化的很快。一开始还只是忘事、不爱说话,直到最后连我也认不出了;吞咽功能也受到了影响,从吃饭只能一点一点咽,到最后只能喝米汤。十一我回家的时候,奶奶已经基本不说话了,身体左半边也已经瘫痪无力。真的没想到,短短两个多月的时间,她就从我们的身边离去。

我跟我妈已经达成一致,准备给我爸买台车。我爷爷现在虽然有点糊涂,但生活上还能半自理,也还能走路。趁着现在,多带我爷出门转转,每次回去也能方便一点。

家里电视下面,还摆着爷爷奶奶、三个姑姑和爸爸六口人几年前在公园的照片。现在却已经少了一人。


WebApp for Desktop: 请不要滥用手型指针

这是一篇吐槽。最近想用Electron做点东西,大致浏览了几个UI库,又想起一些用Electron做的App的糟糕体验,实在是想吐槽一番。也不知道大家是不是也有类似的感觉,还是只是我个人吹毛求疵。如果是我的问题,还请打醒我。

首先,这里的WebApp指的是用基于Web的技术制作的客户端程序,比如VSCode、Microsoft Teams、Github Desktop等等。我在使用VSCode和Microsoft Teams时,在用户体验上会跟NativeApp有严重的割裂感。除了渲染性能这种客观问题之外,最主要的问题是,手型指针被滥用了

到处都是手型指针!

举例来说,在VSCode中,把鼠标放在一切能够点击的东西上,几乎都会变成手型,比如文件列表、文件Tabs、各种按钮等等:

然而,在主流的Windows/Gnome/KDE/macOS上,这些都不应该触发手型指针:

为什么在WebApp里面不应该大量使用手型指针?

因为滥用手型指针违背了各种Native UX设计指南——即,这就不是Native App的Feel。例如,在微软的Windows Desktop UxGuide中,明确说明了普通指针和手型指针的适用情况:

Normal Select – Used for most objects.
Link select – Used for text and graphics links because of their weak affordance.

在苹果的Human Interface Guidelines中,同样明确说明了普通指针和手型指针的适用情况:

Arrow – This is the standard pointer that’s used to select and interact with content and interface elements.
Pointing hand – The content beneath the pointer is a URL link to a webpage, document, or other item.

总结一下就是:只有在文本图片链接等情况下,才会推荐使用手型指针。所有一般情况,都应该使用普通的指针。

虽然手型指针为用户提供了额外的提示,表示这个元素可以被鼠标操作,但是在Native App中,很多时候不需要、也不应该依靠手型指针来增强操作提示。在微软的Windows App UxGuide中,有这样一段话:

Well-designed user interface (UI) objects are said to have affordance, which are visual and behavioral properties of an object that suggest how it is used.

也就是说,UI元素应当使用一些视觉和行为属性来表示它支持的操作——例如按钮应当做成看起来就可以被按下的样子、Slider应该有个槽槽来表示它可以被滑动,等等——而不是使用手型指针来提示这些操作。例子就像上面给出的Windows 资源管理器,以及QtCreator的侧边栏。

但为什么我不反感在普通网页中大量使用手型指针?

这里我也没有想的很清楚,可能的原因有:①在使用浏览器浏览网页时,我不期待网页会有Native的Look’n’Feel;②习惯了!

不过,我觉得主要的原因还是由于网页与客户端程序存在区别:

网页的本质是一篇文档。当我浏览一篇网页时,跟看一本杂志、看一本书很像。因此,网页上的交互组件应该优先与文档的整体风格保持一致,而不是优先显得“affordable”(不知道怎么翻译,可操作性?)。一个看起来就能够按下的按钮,且不说风格问题,更有可能喧宾夺主。所以我们可以弱化这些元素的affordance,而使用手型指针来增强操作提示。(说实话,很多Web UI Component的按钮,我就没什么按下去的欲望。)

然而客户端程序不是文档,尽管我们依然使用Web的技术来构建它,但它不是一篇文档。它的功能性更加重要,各类UI元素就是界面的主体。所以应该把各类UI元素在视觉上就设计得足够affordable,而不是去借助手型指针。上面贴出的VSCode中的各种button,有的甚至连hover效果都没有!

正例:Github Desktop

Github Desktop是我想举出的正例之一。它的下拉菜单、按钮、列表等等,全部使用普通鼠标指针,使用起来非常愉快:

结尾

其实除了手型指针这个问题之外,有些App还有一些小地方不够Native,比如Microsoft Teams中的一些图标存在延迟加载问题。在用Web技术做移动App时,大家都在往Native Look’n’Feel 靠拢;为什么到了Desktop,却不在意这些体验呢?

最后如果大家知道哪个UI库不滥用手型指针的,请推荐一个……

附:可以参考的其他讨论

https://ux.stackexchange.com/questions/105024/why-dont-button-html-elements-have-a-css-cursor-pointer-by-default

在 Medium.com 上查看

组织哈工大技术兴趣讨论班的心路历程

去年的秋季学期还没开始的时候,我就在考虑技术兴趣讨论班计划——让对某方面技术感兴趣的同学聚集在一起,定期轮流做一些分享。一晃眼今年都快过完了,想着把去年一年的经过和想法整理一下,如果将来有人还想办一办类似的活动的话,这就算作是宝贵的经验吧。

1

其实这是一连串的事件。办技术讨论班并不是我突然想做的,还有很多前戏。最最前的事件,大概就是IBM技术俱乐部暂停招新,随后 run.hit.edu.cn 镜像站又挂掉了。每次打开USTC Mirror,打开TUNA,心里面总是有一点嫉妒,现在仍旧如此。哈工大坐落在东北荒凉之地,哪有机会去参加Ubuntu Release Party,甚至连一个小小的镜像站都倒了。

所以,我想活跃一下校园里面的技术氛围。其实计算机和软件学院有很多的技术社团,也有很多人技术很不错的,但我总觉得差了点东西。

最开始大概在2015年,我想办一个技术社区。http://techo.io ,现在已经凉了,大家可以上去再给它续一续命。虽说当时本来就没有抱着办成功的态度去做,但还是有一点点的遗憾。把techo搭起来了之后,刚好学校Z老师有意向办一个技术咖啡馆,交给了我的基友们去做。线上线下联动,看起来甚至还有那么点希望。场地有了,线上讨论区有了,我甚至有着很多美好的设想:给各个技术社团提供线上讨论板块,线下活动场地,技术氛围搞起来啊。

2016年年中,线上论坛已经搭的差不多,咖啡店也已经装修完毕了。

2

每年的六七八月份,正是高考结束,考生撕书相庆的时节。高考结束之后就是填报志愿了,大概六月底七月初成绩公布,学生们未来的去处也就大致确定了。此时,多半会诞生新的新生群,诸如“2017级哈工大新生1群”。早就计划了要搞一点事情的我,必然要混进新生群去,因为之后的学院群的创建(比如“哈工大2017计算机”之类)多半可以从这样的新生群里面得知,同时还可以先混个脸熟,将来搞事情的时候不会冷场。

当然,技术兴趣讨论班不仅仅面向大一新生,但这是需要对大一新生做出的额外准备。因为大二大三大四这几届,在他们入学的时候,我已经基本做完了这些操作。

那一段时间,在跟学弟学妹们扯皮的同时,我也在思考讨论班究竟以什么样的形式来进行活动。哈工大大一的所有学生都在黄河路的二校区,大二以上年级的学生基本都在西大直街的一校区。一起活动吗?还是分开活动?让高年级的学生直接给大一同学开小灶吗?还是内部轮流分享?能做到每周都有东西可以拿来分享吗?

最终,我采取的方案是:讲书。比如我对CSAPP感兴趣,那么看看大家谁还对CSAPP感兴趣,组成一个“CSAPP讨论班”,大家一起来学,每周安排一个人将书中的一章或半章。不限制校区,地点安排服从多数人方便的标准。如果有人对SICP感兴趣,那么就组成另一个“SICP讨论班”,等等。

Continue reading “组织哈工大技术兴趣讨论班的心路历程”

Codeforces 869C The Intriguing Obsession

这是一道动态规划题。

首先来分析:题干中对于桥梁的限制,其实是在说:某个点不能与自己集合中的点相连,也不能同时与同一个集合中的两个点相连,即题目下方示例2中那两种不合法的连接方法。也就是说,对于红色点A来说,它可以与蓝色集合中至多一个点相连;同时,也可以与紫色集合中至多一个点相连。它是否与蓝色集合中的点相连并不影响其与紫色集合的点相连,即桥梁搭建的全部情况,应该等于红蓝相连的情况数×红紫相连的情况数×蓝紫相连的情况数。因为不论红紫、蓝紫之间如何相连,红蓝之间相连的情况数跟它们均无关。

现在我们把问题由三个集合简化到了两个集合。这两个集合之间的点相连接需要满足刚才那两个条件:

  • 集合内部的点不能相连
  • 集合A中的一个点要么与集合B中的一个点相连,要么就不连接集合B中的任何点

第二个条件其实就是动态规划的转移方程了。对于集合A中的第I个点:

  • 第一种情况,它不跟集合B中的任何一个点相连。此时即变为一个子问题:集合A中的i-1个点与集合B中的j个点搭建桥梁;
  • 第二种情况,他跟集合B中的某一个点相连。连接方法共有j种,连接后变为另一个子问题:集合A中剩余的i-1个点与集合B中剩余的j-1个点相连。

因此,转移方程为:

dp[i, j] = dp[i - 1, j] + dp[i - 1, j - 1] * j

dp[i, j]代表的就是当集合A中有i个点、集合B中有j个点时,桥梁的连接方法。

由于只用到了i – 1,因此只需要存储一行即可。不过由于每个集合中的点数最多只有5000,即便用long存也大概只有200MB,内存勉强够用。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _869C
{
    class Program
    {
        public static void Swap<T>(ref T lhs, ref T rhs)
        {
            T temp = lhs;
            lhs = rhs;
            rhs = temp;
        }

        static void Main(string[] args)
        {
            int[] tmp = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray();
            if (tmp[1] < tmp[0])
            {
                Swap(ref tmp[0], ref tmp[1]);
            }
            if (tmp[2] < tmp[0])
            {
                Swap(ref tmp[0], ref tmp[2]);
            }

            long[,] dp = new long[tmp[1] + 1, tmp[2] + 1];
            for (int i = 0; i <= tmp[1]; i++)
            {
                for (int j = 0; j <= tmp[2]; j++)
                {
                    if (i == 0 || j == 0)
                    {
                        dp[i, j] = 1;
                    }
                    else
                    {
                        dp[i, j] = (dp[i - 1, j] + dp[i - 1, j - 1] * j) % 998244353;
                    }
                }
            }

            long r = (((dp[tmp[1], tmp[0]] * dp[tmp[1], tmp[2]]) % 998244353) * dp[tmp[0], tmp[2]]) % 998244353;
            Console.WriteLine(r);
        }
    }
}