Frank's Weblog

  • 2019 Fall 美国CS Master申请总结

    2019Fall的申请季基本结束了。对于各位CS玩家来说，今年申请季非常惨烈。在此记录一下我在这个申请季中的一些感想和踩过的一些坑。如果你也是一名在准备申请美国CS master的准留学生，希望这篇文章能够或多或少给你一些启发。

    我的申请结果如下：

    AD

    • Syracuse CE, WPI CS, Stevens CS, BU MET CS

    REJ

    • USC CS General, NYU CS, UCI MCS, UCD CS, NEU CS, Rutgers CS, Stony Brook CS, UCSC CS, Syracuse CS

    前期准备

    前期的准备基本在于标准化成绩，GPA，各种竞赛实习，选校等等。

    我从2017年暑假开始准备托福起一共考了三次，分别是100->101->108。总体来说还算顺利。相比之下，GRE考试就艰难了很多。我一共考了4次GRE，分数分别为153+160，153+166，149+162和150+164，呈现出非常迷的波动。然而AW则非常稳定，每一次都是3.5。

    我从2018年寒假开始学习GRE，背单词，刷题，从零开始准备到首考大约经过了3个月的时间。4月份首考GRE出现了严重翻车：我理解错了一道数学题的意思，结果在一个题上卡了太长时间导致数学没有做完，只得了160。

    (more…)
    Read more: 2019 Fall 美国CS Master申请总结

  • 动态规划算法

    动态规划是一种分治(Divide&Conquer)的思想。在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。

    适用于动态规划的问题，需要满足最优子结构和无后效性两种情况。

    • 最优子结构性即如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。
    • 无后效性即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

    动态规划最重要的两个要点在于找到状态和状态转移方程，也就是递推关系。

    如果不记录每一步的结果，动态规划的时间复杂度与Brute Force无异。动态规划实质上是一种以空间换时间的方法，通过存储过程中每一步骤的状态来降低时间复杂度。

    举个栗子

    我们以Leetcode的Climbing Stairs题目为例：

    当前位置为第i级台阶时，有两种途径到达当前的状态：

    • 从第i-1级台阶走一步而来
    • 从第i-2级台阶走两步而来

    因此，到达第i级台阶的途径为到达第i-1级台阶和到达第i-2级台阶的途径数量之和。我们可以得出如下的状态转移方程：

    (more…)
    Read more: 动态规划算法

  • Leetcode笔记

    最近开始刷leetcode，在这里记录一下做题的过程，不定期更新。

    GitHub：https://github.com/frankgx97/leetcode

    Two Sum(Easy)

    https://leetcode.com/problems/two-sum/

    Given an array of integers, return indices of the two numbers such that they add up to a specific target.

    You may assume that each input would have exactly one solution, and you may not use the same element twice.

    解法1：暴力搜索

    题目本身很简单，使用两个for循环遍历即可。需要注意的是同一元素不能使用两次，因此在遍历时，内层循环需要直接从外层循环+1处开始，而不是从头开始。

    Solution：https://github.com/frankgx97/leetcode/blob/master/TwoSum.py

    解法2：哈希表

    新建一个哈希表（Python中使用字典即可），遍历数组，以数组中的值为哈希表的键，以数组中的键为哈希表的值，将数组中的内容存入哈希表。

    在遍历的同时检查(target-当前遍历到的值)是否存在哈希表的键中，如果存在则返回哈希表中的值和当前遍历到的键。这样复杂度由O(n^2)降低至O(n)。

    Solution：https://github.com/frankgx97/leetcode/blob/master/TwoSum(Hashmap).py

    (more…)
    Read more: Leetcode笔记

  • 基于Docker的GitLab配置

    我原来使用的Git托管软件是Gogs，近期我迁移到了GitLab。GitLab除了Git托管之外，还包括CI/CD，Registry，Pages等一系列功能。Omnibus Installer使GitLab的安装和配置简化了很多，但是要使用更多的功能，仍然需要手工配置一些服务。

    本文记述了使用Docker部署GitLab后开启CI/CD，Registry，Pages等功能的步骤和配置。

    硬件需求

    官方给出的硬件需求是1Core CPU+ 512MB RAM + 1.5GB SWAP是运行GitLab的最低要求。我使用的是Digital Ocean的5$/月的1C1G实例，开启了4G的Swap。

    GitLab本体

    Omnibus包包含了GitLab依赖一系列的软件和组件，如ruby, rails, Sidekiq, PostgreSQL等。在Docker中，这些服务都运行在同一个容器中。容器中已经包含了nginx，无需手动配置nginx反向代理。使用如下的compose文件启动GitLab。

    web:
  image: 'gitlab/gitlab-ce:latest'
  restart: always
  hostname: 'git.example.com.'
  environment:
    GITLAB_OMNIBUS_CONFIG: |
      external_url 'https://git.example.com'
  ports:
    - '80:80'
    - '443:443'
    - '22:22'
  volumes:
    - './data/config:/etc/gitlab'
    - './data/logs:/var/log/gitlab'
    - './data/data:/var/opt/gitlab'

    当external_url参数被设置为以https://打头时，GitLab默认使用Let’s Encrypt签发证书。当http及https被暴露到标准端口时，Let’s Encrypt会通过http challenge方式执行自动签发。

    当容器启动后，GitLab的基本功能就可以使用了。

    (more…)
    Read more: 基于Docker的GitLab配置

  • 从Gogs迁移项目至GitLab

    我以前使用的代码托管系统是Gogs，近期我切换到了更知名的代码托管系统GitLab。因此，我需要将原来托管在Gogs实例上的项目迁移到GitLab实例。

    GitLab中提供了一些迁移工具，其支持的平台如下图：

    其中，Gitea是Gogs的一个分支版本，我试着通过Gitea选项从Gogs导入项目，虽然GitLab能够正常列出Gogs上的项目列表，但是在导入时则会引发500错误。

    经阅读文档得知，Gogs和GitLab均提供了操作代码仓库的API。因此，我可以编写一个Python脚本来迁移项目。

    (more…)
    Read more: 从Gogs迁移项目至GitLab

  • 从Docker容器中访问宿主机网络

    在使用Docker部署应用时，Docker推荐的方式是将应用及其所依赖的服务（MySQL，Redis等）均使用Docker部署，并通过link或自定义网络相连接。但是，当应用所依赖的服务被安装在宿主机上时，我们需要让容器中的应用能够访问到部署在宿主机上的服务。本文将介绍实现这一目的的几种方案，并分析其优缺点。

    首先我们需要了解一些关于Docker网络的基础知识。

    Docker网络

    Docker提供了5种网络类型，这里介绍其中常见的两种：bridge及host

    Bridge

    Bridge是Docker默认使用的网络类型。如图，网络中的所有容器可以通过IP互相访问。Bridge网络通过网络接口docker0 与主机桥接，可以在主机上通过ifconfig docker0查看到该网络接口的信息。

    Host

    Host模式下，容器的网络接口不与宿主机网络隔离。在容器中监听相应端口的应用能够直接被从宿主机访问。host网络仅支持Linux。

    (more…)
    Read more: 从Docker容器中访问宿主机网络

  • Matomo通过SMTP发送邮件时报错’mail from address must be same as authorization user’的分析与解决方案

    我之前一直使用Google Analytics来统计网站访问量。近期，我切换到了Matomo（原名Piwik），一个开源的网站统计系统。

    Matomo提供了一个“电子邮件报表”功能，可以定期生成一份统计报表，定时或手动发送到管理员的邮箱中。

    问题

    我将Matomo设置为通过SMTP发送邮件。Matomo提供的SMTP设置项目如下：

    (more…)
    Read more: Matomo通过SMTP发送邮件时报错’mail from address must be same as authorization user’的分析与解决方案

  • Laravel实现微信小程序支付

    准备工作

    微信小程序支付流程

    首先我们需要大致了解微信小程序的支付的流程，主要分为如下几个步骤。这里以一次下单购买商品的场景为例。

    1. 用户在小程序中选购商品，点击提交订单。
    2. 小程序请求业务服务器，传入订单相关信息。
    3. 业务服务器将订单信息写入数据库，然后请求微信支付统一下单API，传入将订单相关数据和小程序相关id及签名。
    4. 微信支付统一下单API返回下单结果，支付订单号，签名等。业务服务器将这些信息返回给小程序。
    5. 小程序拉起微信支付，用户输入密码支付。
    6. 小程序获得支付结果，请求业务服务器更新订单数据。
    7. （可选）微信支付服务器访问业务服务器的回调URL，更新支付结果。

    阅读文档

    在开始开发前，请首先认真阅读微信支付官方文档及EasyWechat文档的微信支付部分。

    (more…)
    Read more: Laravel实现微信小程序支付

  • Laravel Eloquent ORM 关系查询

    在信息系统中有很多一对多的关系，常见的一个例子是一个订单（order）中包含多种商品（product）。我们通常会使用一个order表来存储订单，同时使用一个product表来存储商品，并在product表中加入order_id外键来将产品关联到订单中。

    在以前开发项目时，我一直使用先查询order，再通过order_id查询product，并遍历查询到的order对象，将product插入order中的做法。但是这样做非常不优雅，并且会严重影响性能。同时，由于数据库中没有外键约束，一旦业务代码中出现bug，则会影响数据的一致性。

    在这次的项目开发中，我使用Laravel的Eloquent ORM来实现外键的关系查询。

    一些概念

    我们首先来复习一些数据库系统导论中的一些概念

    主键(Primary Key)

    主关键字(Primary Key)是表中的一个或多个字段，它的值用于唯一地标识表中的某一条记录。主键通常名为id，并且为自增。

    外键(Foreign Key)

    外键(Foreign Key)的作用是建立两个表之间的关联。下面这张图可以直观地展示外键的作用。

    外键

    连接(Join)

    连接(Join)将两张表中能关联起来的数据连接后返回。关于连接的更多内容请参考这篇文章：图解 SQL 里的各种 JOIN — 码志。

    Laravel的Eloquent ORM中并没有实现Join，如果需要在Laravel中使用Join则需要在Query Builder中完成。请注意不要将本文所述内容和join混淆，Eloquent中的with方法的实现是通过模型中定义的关系另外进行一次查询，并没有使用join。

    (more…)
    Read more: Laravel Eloquent ORM 关系查询

  • Drone持续集成

    Drone是一个用Go语言开发的基于容器运行的持续集成软件。

    请注意，目前Drone1.0.0rc已经发布，但是本文所有内容均基于Drone0.8.0。

    安装

    Drone可以通过Docker安装，请参考https://0-8-0.docs.drone.io/installation/

    运行时需要通过环境变量设置与Drone集成的版本控制系统。drone支持的版本控制系统包括GitHub，Gogs，GitLab等。我使用的是Gogs。

    你可以修改后使用下面的compose文件。

    version: '2'
services:
  drone-server-gogs:
    image: drone/drone:0.8
    ports:
      - 8020:8000
      - 9000
    volumes:
      - ./drone-gogs-data/:/var/lib/drone/
    restart: always
    environment:
      - DRONE_OPEN=false
      - DRONE_HOST=https://drone-ci.example.com
      - DRONE_ADMIN=admin
      - DRONE_GOGS=true
      - DRONE_GOGS_URL=https://git.example.com/
      - DRONE_SECRET=secret
drone-agent-gogs:
    image: drone/agent:0.8
    command: agent
    restart: always
    links:
      - drone-server-gogs
    depends_on:
      - drone-server-gogs
    volumes:
      - /var/run/docker.sock:/var/run/docker.sock
    environment:
      - DRONE_SERVER=drone-server-gogs:9000
      - DRONE_SECRET=secret
    (more…)
    Read more: Drone持续集成