How the “Scan API” added in xiaodu-jsdelivr 1.3 works

I released the WordPress plugin “xiaodu-jsdelivr” months ago, which can be used to scan and replace references to static resources with jsDelivr CDN links. Details on how the plugin works can be found in the previous blog post. Yesterday, I released a new version 1.3, which contains a new feature called “Scan API”.

API Manager: https://xiaodu-jsdelivr-api.du9l.com/

What it is and why it is needed

“Scan API” is a hosted service, which can provide plugin users with pre-calculated scan results. Previous versions of the plugin used a more direct approach: Calculate local file hash, fetch CDN file and match their hashes. This obviously works, but it does slowly, because downloading remote files is a time-consuming job, which is the reason that initial scans after installing the plugin are always slow. Usually it took dozens of 30-second scanning sessions to complete an initial scan with the base WordPress, several plugins and themes. When you think about the fact that each website of all users has to go through the same process (there’s no import-export feature yet), it makes even less sense.

This is where the hosted API service becomes helpful. By pre-fetching and storing the hashes of WordPress and official plugins and themes (with all versions), and serving them to a client plugin when needed, the repetitive fetching and calculating can be avoided. That means the scanning process can be greatly accelerated, as long as the resources scanned are present in the API storage.

Flow chart of old and new processes

Current state and future development

The ultimate goal for the service is to provide scanning support for base WordPress versions, plugins and themes. As of now, both the service and plugin only implemented the first part, which is to provide hashes for all published (on GitHub) versions of WordPress. That means the client only uploads WordPress version, not plugin or theme versions; and the service only scans WordPress repository.

The remaining parts will be incrementally added in the future, which I have to think carefully. There are over 100,000 themes and plugins (combined) in the official SVN repositories, and it’s unrealistic to scan and store them all. So for the first future development goal may be to support the most popular of each category.

Also, as of right now the service is completely free. In the near future I don’t have a viable plan to charge users for the service, because with payments come payment gateway integrations and support requests. But I cannot guarantee that it will stay free forever – it may go paid or it may go away.

Technical details

Plugin users can stop reading here, because the following part is about technical details on how the service is built.

The API service is essentially a Python website built with Flask framework, with these main components:

  1. Authentication: This is provided by Auth0 (free plan), chosen for being relatively easy to use and the vast amount of login channels supported. It provides templates for a variety of languages, frameworks and applications, which can be downloaded and modified to fit the basic authentication needs. In my case (Python + Flask), Authlib is used in the template to provide the OAuth 2 functionality.
  2. Web UI: Written with React + React Router. It is not strictly necessary to use React, or even to build a single-page application, but I chose this path to get my skills up to date. For example, create-react-app is quite easy to use for creating a TypeScript-based project, while in the old days one had to configure TypeScript and Babel themselves. Also, React hooks is an interesting recent addition.
  3. API: There are two parts, one is the actual “Scan API” for the client plugin to query for stored data. The other is the backend API for the Web UI to manage API keys. MongoDB is used as permanent store for both scanning and user API key data.
  4. Scanner: Workers that regularly download and calculate remote hashes. A task queue (Celery) is used to manage scanning tasks, and the downloading part is handled by GitPython (later maybe PySVN will also be used).

The whole project is deployed in my private Kubernetes cluster, using Jenkins to build the frontend and backend and push the built images to an in-cluster docker registry. In the process of building the service, I am constantly amazed by how web development has evolved nowadays, with a lot of great tools and libraries available.

LeetCode 456: “132” Pattern

这个题是昨晚上回寝室前赶出来的,因为看到是Medium而且感觉不难(实际也不难)。

原题:https://leetcode.com/problems/132-pattern

题目意思是,判断一个数组是否包含子序列ai、aj、ak(i<j<k),满足ai<ak<aj

好像跟一般领奖台是反着的,但是可以直观理解题意。
好像跟一般领奖台是反着的,但是可以直观理解题意。

主算法

思路是遍历每一个可能的k值,然后找到它之前第一个(也就是距离最近的)比它大的数作为aj,然后再判断a0~aj-1之间的最小值是否小于ak

之所以要找到“第一个”比它大的数,理由也很明显:要尽量扩大找ai的范围,否则可能会有false negative的情况。

思路很简单,关键是如何做到O(n)。因为遍历每一个k的过程就是O(n)的,所以要求后面两个步骤都是O(1),也就是要预处理。预处理最小值很简单,开一个数组记录一下即可,空间复杂度O(n)。预处理“之前第一个比ak大的数(的位置)”就比较麻烦了,放在子算法里说,空间复杂度也是O(n)。

因此最终算法分三步:预处理a0~aj的最小值,预处理ak之前第一个大的数,遍历每一个可能的k。

子算法

要预处理每个数之前第一个比它大的数,用到了之前一个stack的奇技淫巧。方法是维护一个pair<数, 位置>的stack,其中数是递减的;对于数组从头到尾遍历,每个数先将栈顶比它小的数pop出去,如果pop完了栈空了,说明前面没有比它大的数,此时预处理结果为-1;否则预处理结果为栈顶数的位置。处理完之后将当前pair<数, 位置>也push进栈。

原理:因为要找到之前第一个比它大的数,如果栈顶的数比当前数还小,那对于它们之后的数来说,当前数更可能是比后面数大的结果,所以将栈顶pop出去。因为每个数最多进出栈一次,时间复杂度O(n)。

C++代码

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        if (nums.empty()) return false;
        int n = nums.size();
        vector<int> min1(n);
        min1[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            min1[i] = min(min1[i-1], nums[i]);
        }
        typedef pair<int, int> pii;
        stack<pii> s;
        vector<int> max1;
        for (int i = 0; i < n; ++i) {
            int I = nums[i];
            while (!s.empty() && s.top().first <= I) s.pop();
            if (s.empty()) {
                max1.push_back(-1);
            } else {
                max1.push_back(s.top().second);
            }
            s.push(make_pair(I, i));
        }
        for (int i = n-1; i >= 0; --i) {
            int I = nums[i];
            int j = max1[i];
            if (j == -1 || j == 0) continue;
            if (min1[j-1] < I) return true;
        }
        return false;
    }
};

因为写的很赶,好多边界都没care,其实应该还有能优化的地方(因为运行时间才到beat 55%的位置……)

理解 React Native 的 FlexBox 排版模型

这两天尝试用 React Native 写了一个 APP,总体感觉是个好东西。目前没有 macOS 环境,没法测试 iOS 上的表现,但是安卓上是不错的。

在设计界面的过程中,如何正确排版、正确使用 FlexBox 模型就成了一个关键问题。其实这里的 FlexBox 跟 CSS3 中新加的那个 FlexBox (Flexible Box) 基本上是一样的,所以通过 MDN 上的这篇文章可以了解 FlexBox 的基础知识,例如主轴和侧轴、每个轴的元素排列等。另外,SegmentFault 上有一篇关于 React Native 布局的文章也不错,介绍了 FlexBox 排列元素时,遇到多个 flex 元素或有固定大小的(不 flex 的)元素,会怎样安排他们的大小。

假定读者阅读了上面两篇文章,明白了基础知识。接下来我结合 APP 中的实例来讲一下使用 FlexBox 过程中遇到的问题、解决方法和对 FlexBox 模型的理解。

考虑如图所示的 UI,上面是一个固定高度的标题栏,其中包含左右各一个固定大小的按钮,中间的文字填满剩余空间;下面是很长的内容,可以上下滚动,滚动时标题栏一直在最上面不动。

首先整个界面的顶层 <View> 标签,其 style 应该包括:{flex: 1, flexDirection: 'column',} ,这样内部元素就会上下排布。标题栏我额外定义了一个 Header 类(class Header extends Component {} ),因此 <View> 的第一个子元素就是 <Header style={...}>(标题栏子元素)</Header> 。这里要注意的是,给 Header 定义 style 本身没有任何效果,应该在 Header 类的 render() 方法中,将其实际顶级元素的 style 附加上 this.props.style,即 <View style={[header_styles.basic, this.props.style]}>...</View>

然后看 <Header> 对应的 <View> 的 style。由于 <Header> 本身是固定高度的,因此可以肯定它不是 {flex: 1} 的。但是我们又想使用 FlexBox 中的排版功能,对标题栏中的元素横向排版,所以在顶层 <View> 中再嵌套一层 <View>,它的 style 应该是这样的:

container: {
  flex: 1,
  flexDirection: 'row', // 子元素横向分布
  justifyContent: '', // 这个无所谓,因为子元素要占满整行
  alignItems: 'center', // 竖向居中线排列
},

接下来看内层 <View> 的子元素。首先是左上角、右上角的图标,这里我用的是 react-native-vector-icons,就是两个 <Icon> 元素,它们都是固定大小的(其实就是一个特殊字符),因此我们需要中间的标题 <Text style={{flex: 1}}> 以填满剩余空间。这里就看出来,{flex: 1} 的意思就是这个元素的长宽可以任意放大(或缩小),以适应排版的需要。

这样 <Header> 部分就搞定了,接下来看正文的滚动部分,这里用的是 React Native 的 <ScrollView> 元素。通过文档中看出,ScrollView 是由一个外层短元素包含一个内层长容器,外层短元素可以是固定高度(height)的或 flex 填满剩余高度的,但内层容器应该是内容的实际高度,而不应该是 flex 的。这里文档写的很迷茫(“把 flex 从视图栈向下传递”,并没有看明白哪里是栈、哪里是下……),我是踩了很多坑才搞明白这是什么意思。主要代码如下:

<ScrollView style={{flex: 1}}
    contentContainerStyle={{...}}>
  <View>...很长的内容...</View>
</ScrollView>

这个 <ScrollView> 在顶层 flex <View> 中,将其设为 {flex: 1} 即可填满除 <Header> 以外的剩余屏幕高度。但是 contentContainerStyle 控制的内层样式绝不应该有 {flex: 1},否则会被缩小到与外层元素一样高,裁剪掉多余的内容,因此无法实现滚动。这里与 <Header> 中类似,内部长内容可能还有更复杂的排版(比如进一步上下/左右分割),所以可以在 <View> 子元素的 style 上下功夫,比如设为 {flex: 1, flexDirection: 'row',} 即可将内部元素再左右排列。

下面提供一些我的 APP 中实现上述布局的代码(省略了逻辑和内容,只保留排版相关的代码,最终效果类似于 Material Design),供读者参考:

class Header extends Component {
  render() {
    return <View style={header_styles.header}>
      <View style={header_styles.container}>
        {this.props.children}
      </View>
    </View>;
  }
}

const header_styles = StyleSheet.create({
  header: {
    backgroundColor: "#2196F3",
    height: 60,
    paddingLeft: 20,
    paddingRight: 20,
    shadowRadius: 2,
    shadowOffset: {width:0, height:2},
    shadowOpacity: 0.7,
    shadowColor: 'black',
    elevation: 2,
  },
  container: {
    flex: 1,
    flexDirection: 'row',
    flexWrap: 'nowrap',
    justifyContent: 'flex-start',
    alignItems: 'center',
  },
});


class Single extends Component {
  render() {
    return <View style={single_styles.container}>
      <Header>
        <TouchableOpacity>
          <Icon
            name="arrow-left"
            size={20}
            color="#E3F2FD"
          />
        </TouchableOpacity>
        <Text style={single_styles.title} numberOfLines={2}>
          ...
        </Text>
        (注意:我的标题栏中只用了左侧图标,没有右侧图标。)
      </Header>
      <ScrollView style={single_styles.scroll}
        contentContainerStyle={single_styles.scroll_container}>
        <View>
          ...
        </View>
        <View style={single_styles.list}>
          <SingleLeft />
          <SingleRight />
        </View>
      </ScrollView>
    </View>;
  }
}

const single_styles = StyleSheet.create({
  container: {
    flex: 1,
  },
  scroll_container: {
  },
  list: {
    flexDirection: 'row',
    alignItems: 'flex-start',
  },
  scroll: {
    flex: 1,
  },
  title: {
    fontSize: 20,
    color: '#E3F2FD',
    marginLeft: 10,
    flex: 1,
    flexWrap: 'wrap',
  },
});

 

回忆今天的华为上机考试题

今天下午参加了华为在济南的上机考试(据说上午也有一批,题不一样)。回忆一下考的题目,总体还是很水,但是最后一题还是可耻的 WA 了……

  1. 初级题(100分,6个点):送分,输入a和b,输出[a,b]之间的素数,没有时间、空间限制,而且题干用中文把算法都给描述出来了,考验你是否会打开VS或Eclipse、编译、运行……
  2. 中级题(200分,4个点):输入一串逗号分隔(脑残)的数,不超过1000且无重复,输出这串数中可以被其它数整除的数,要求按输入顺序。基本也是送分,除了输入比较恶心(一般都是输入n,然后输入n个数;这个我只能用字符串一位一位处理了)。
    样例:输入”3,4,2,6″,输出”4 6″。
  3. 高级题(300分,4个点):有N个岛,给出岛间距离,全部连通最少需要多少距离的桥?输入n(3<=n<=1000),再输入n*n的邻接矩阵表示距离(没有给出距离的范围……都没说是不是整数……),输出最短桥距离。
    明显是MST,写完贪心(Kruskal,只记得这一种,也不让上网搜)交上去WA 2/4,而且只能提交五次,改了4种版本之后依然稳定的2/4,最后就只拿到一半分。交完最后一次才想到,是不是距离可能有浮点数……
    样例输入(自己编的):
    3
    0 123 456
    123 0 789
    456 789 0
    输出:579

总之是很水的题目,而且要吐槽的是做完之后不能走(15分钟做完前两题、45分钟败完5次提交,剩下一小时就瞪着监考老师),还要做职业测试(精神病测试),做完一遍因为做的太水又被迫做了第二遍……呵呵哒。

PS: 考场上有个孩子,可怜兮兮的给监考老师说,老师我没用过VS,我只会用Code::Blocks,这个VS简单的程序也报错,blah blah……当时我就傻了,还真有只用过Code::Blocks的大神orz……

PSS: 蒋震机房的XP+VS2005真是亮瞎了朕的氪金狗眼,新建工程Debug报缺少DLL,必须先修改一个“FAT32什么什么”的选项才能用……

回忆一下 360 实习编程题

现在两批人都考完了,来透个题。规定上说不能用笔抄,没说不能用脑子记。省略全部废话,只说题干。总体来说就是一个字:

1. 两个人A、B,从一个整数范围(说是N,目测是[1,N],题出的非常模糊)里面各选一个数a和b,然后用一个均匀随机生成器在范围里生成一个数c,看谁离c近赢,相同距离算b赢。

现在输入是N和a,求b选几的时候胜率最大,相同胜率取最小。

样例:3 1 (输出2)、4 3 (输出2),完美的避开了是0还是1开始的问题……

</题干> 卤煮做了40%(还做出过20%,应该是5个点),还想出一个边界条件没写对,不知道剩下的错在哪里。

2. 给定字符串s,由a~z和小数点“.”组成,定义操作a(s),表示将s中最早出现的连续两个点替换成一个点;定义函数f(s),表示进行多少次操作a可以使得字符串中没有连续的点。

输入为n(字符串长度),m(字符串替换操作);第二行为n长字符串;第3行开始的m行,每行有k和c,表示将s中第k个字符(从1开始数,傻叉)替换为c。要求在每次替换后,输出替换后s’当前f(s’)的值。

样例:原来的巨长无比,我就随便编一个:4 1 a..b 4 . (输出2)。

</题干> 水题,只要注意是1开始这个大坑。读入后先计算原始的f(s),然后每次操作后,拿出操作位左右各一位,判断这三位在变化前后的diff,加到原始f(s)即可(当然,过后要真的替换)。

————————————————

2/5的WA啊,哪有这么多边界条件啊,我猜是大数据点输出的时候变成了科学记数法,但是我安装了跟OJ一样的g++版本,并没有被科学……天知道为什么,呵呵哒。

另外理论题考了好多设计模式、算法、数据库的细节题,理论渣表示全靠蒙,不服跑个分。