数据结构与算法浅思:思考排序

相比无序数据,人类更喜欢有序的,比如我们会整理房间,我们会努力组织语言以便让别人更容易理解,等等。提升效率当然是一个原因,比如字典(很难想象一本乱序的字典要如何使用),但还有个我个人觉得很重要的因素是:人是智能体。减熵是智能的一种表现,人类有一种几乎是本能去降低无序性和不确定性的趋向。因为计算机需要供人类使用,排序自然就是一个非常基本且重要的任务了。事实也是如此,我们平时在用代码完成特定任务时,排序也经常会出现在其中,而且往往是处理和分析的第一步。而对计算机本身来说其实并不在乎,就像 ”人工智能“ 也是我们强加给他们的一样,只是因为我们希望他们能够理解人类并为人类服务。所以我们这节主要探讨一下计算机中的排序。为了能够更简单地说明问题,我们假定要排序的是一系列正整数,且按升序排列。

More

自然语言计算机形式分析的理论与方法笔记(Ch03)

第三章:基于短语结构语法的形式模型

语法的 Chomsky 层级

  • W. Wundt 1990 年《大众心理学》提出把句子为成层次的思想;与此同时,传统的欧洲语法研究单词之间的关系,而不是单词所表示的成分之间的关系。
  • Leonard Bloomfield 1914 年在《语言研究导论》中将关于组成性的思想引入语言学。
  • 1933 年《语言论》时,“直接成分分析法” 已经成为完善的方法。欧洲的句法学家仍然强调以词为基础的语法(依存语法)。
  • Z. Harris 使用 “可替换性” 试验检验单独的单位 “分布相似性”:如果一个简单形式可以替换一个复杂结构,这个复杂结构就可能是一个成分。
  • 1956 年 N. Chomsky 定义短语结构语法,最早地形式化描述这种层次成分思想。

More

数据结构与算法浅思:导论

什么是数据结构和算法?

先不考虑有关计算机的一切,我们思考一个问题:假设你所在的公司有员工上万人,如何编写一本能随身携带的通讯录?你可能首先需要搜集整理所有员工的个人信息,当然在此之前你得知道通讯录里面需要有哪些信息。我们假定需要以下员工个人信息:姓名、公司、部门、职务、手机号、电子邮箱、家庭地址,然后经过一番折腾,你终于把所有员工的这些信息搞到手了,你拥有的可能是部分电子表格、部分打印版的、部分手写的,电子表格同样的字段还有各种不同的格式,比如有的手机号是文本格式,有的又是数字格式等等。于是,你心里默默确认好各个字段的格式,然后新建了一张大表,把所有的电子表、非电子表信息全部整合到这一张表中。这时候我们需要考虑下一个问题,按什么顺序显示通讯录?你跟领导确认后得知需要先放公司领导,然后是各个职能部门及分公司,再是各个事业部及下面的子公司。你发现自己的信息表中压根就没考虑事业部,好吧,你可能需要在表中新插入一列 “事业部” 的字段。接下来呢?你还需要确认事业部下面公司的排序方式,每个公司部门的排序方式,每个部门员工的排序方式,你不能想当然地按照姓氏笔画或拼音,因为部门领导一般都要放在第一个然后是副职、主管这样一路下来,所以你还需要按职务大小排序。又经过一番折腾,你终于搞完了,在打印前你还需明确打印出来的小册子尺寸有多大,每个上面要显示多少位员工,然后才能在电子表中设置页面。你还可能需要考虑设置索引,至少到公司层面吧,如果贴心点你可能还会在公司分割线处做一些处理以便使用者可以快速翻到那一页。这看起来好像挺复杂的,但其实还有很多细节问题我们没有考虑,随便举几个例子:如果一个公司或部门正好只有个表头在某一页的最下方,要求这种直接把表头换到下一页;不同的字段要求不同的字体;字段内容太长的要求换行或缩小字体填充;所有人员信息以某个时间点为准,否则随时的人员进进出出会让你的通讯录永远无法完成;不同员工拿到的通讯录人员名单可能不同,你得根据权限设置。这些例子涉及到边界、格式、版本、权限等。噢,这还只是很普通的一个任务,实际中的任务(哪怕是做通讯录)都可能会比这更加复杂。

More

绘制文本分类数据

问题的起因是最近做的一个项目需要在后端绘制 Scatter,横轴是 float 数据,纵轴是分类的文本标签。具体的要求是:

  • 每个数据集可能有若干个主体,也就是一个画布可能需要绘制多幅图;
  • 每幅图的分类类型并不一定相同,但整体类别是知道的;比如:共有 8 种颜色 ”红橙黄绿青蓝紫“,但主体 1 的类别可能是 ”红橙黄“,主体 2 的类别可能是 ”红黄绿“;
  • 要保证同一种类别在图中的颜色标记是一样的,比如:红色类别是红色,那么如果某一个主体的类别中没有红色类别,其他类别在画图时也不应使用红色;
  • 要保证类别的顺序按给定的顺序;比如给定的顺序是 ”红橙黄绿青蓝紫“,主体 1 的类别是 ”红橙黄“,那绘制出来的图像 y 轴必须是按照这个顺序下来的,如果是 ”红黄蓝“ 也是类似。

本来项目是用 NodeJS 写的,后端画图找了不少工具都不太好用(前端工具巨多),后来用了 plotly/plotly-nodejs,但是表现力方面差强人意,而且由于是调用 RESTFul API,数据点太多时会超时,本身也会有网络请求耗时。最后就想到用 Python 在内部起一个 server,使用 Matplotlib 或 Seaborn 绘图。

Seaborn 一行命令就可以绘制,而且参数可以自动把不同的主体区分开;Matplotlib 就稍微麻烦些,不能直接实现预期的目的,后来经过试验,发现可以将类别转为数字然后再将数字的 y 轴转为 string 即可。

Notebook 在这里:text-classification-data,或用 nbviewer 打开:Jupyter Notebook Viewer

数据结构与算法浅思:前言

数据结构和算法是计算机领域的基础,其思想运用在计算机科学的各个方面。这么重要的内容,其书籍和课程也汗牛充犊、数不胜数,书籍比如经典的《算法导论》、《算法》、《数据结构与算法:X 语言描述》等等;课程有 MIT、斯坦福、清华、北大、浙大等优秀精品。那作为一个非计算机专业的小白,又在这里能做些什么呢?此事说来也简单,主要是源自与朋友一起学习的约定,我们一致认为应该用输出来判断是否学过,那这个输出自然就是教程了。

当然,这个只是表面的、直接的原因,还有一些更深层次的原因。首先,由于我自己是完全自学 CS,所以默默刷了不少课程,也都认认真真做了笔记(主要记录课程重点和自己的想法),但是总感觉对工作没起到什么明显的作用,或者说总感觉学完了后并不能把所学的东西很快运用到工作中。这一方面是因为学到的东西不一定马上就正好能用(比如我学了 C 语言,但工作中可能暂时不用写 C 语言代码);另一方面是在学习过程中主观上没有把知识关联起来,学到的都是一个一个的点(比如 C 语言就学习课程教授有关 C 语言的东西)。

因此我觉得需要重新认真审视自己的学习过程:应该主动地去将某门课程与已知的知识点甚至思想串联起来、应该主动地寻找已学到知识点的应用场景(不是只做个作业)。这种情况下,记录就显得非常重要了,因为我们不再是单点突破,而是想要通过一个点带动一个面,任何一门单独的课程都不能够满足我们的需要,所以要写教程,这是第一个深层次的原因。如果说第一个深层次的原因是 “学”,那么另一个更深层次的原因就是 “教”,我是个经济学专业硕士毕业 HR 岗位工作 5.5 年然后转行的 NLP 工程师,认识很多同样是转行的小伙伴,也认识很多想转行但是担心自己 ¥%……&*(此处省略一万种原因),我希望自己的经历能够帮助到一些伙伴,让他们能少走一些弯路;此外,这几天正在阅读费曼的相对论讲义,对他关于 “教” 的理念非常赞同和倾慕,他想让大一大二的学生能够在已掌握内容和对已掌握内容进行演绎的基础上能够学到他要求学生们能够学到的内容。所以,我们需要明确目的,也就是我们为什么要学习数据结构和算法?以及我们到底要从中学到什么?我知道每个人可能都有自己的答案,当然也有不少人可能没想过,不过在这里我觉得我至少可以明确一下。这个目的就是:运用最少的基础知识(熟悉基本的数学和一门编程语言)学习数据结构和算法,理解计算机的思想、甚至解决问题的思想。从中可以学习到:每种数据结构和算法适用于什么问题,如何实现,核心和本质是什么,是否可以迁移到其他领域等等。

丰满的理想谈完了,我需要特别申明一下骨感的现实:我不光是非 CS 专业,还没有完完整整学过任何一门数据结构或算法的课程(感觉有点托大……),说心里话我自己是底气不足的,非常不足,我甚至已经有放弃的打算了,因为我甚至完全不知道应该如何开始,但我已经准备开始了……那,就这样硬上吧,就当是自己学习的一次新的尝试了。By The Way,这里没有提纲或者目录之类的,因为我也刚开始学,不管了,干着看吧。

西蒙《人工科学》笔记

目录

More