海屿文章列表

git push -f 的找回

首先使用 Github’s Events API 来拿到丢失提交的 SHA。如果是 Private 项目需要配置 token 等。
curl https://api.github.com/repos/<user>/<repo>/events

然后用 Github’s Refs API 用这个提交的 SHA 新建一个 recover 分支.

curl -i -H "Accept: application/json" -H "Content-Type: application/json" -X POST -d '{"ref":"refs/heads/recover", "sha":"<orphan-commit-id>"}' https://api.github.com/repos/<user>/<repo>/git/refs

这一步如果遇到 "message": "Not Found" 错误,则需要到 Developer settings > Personal access tokens > 勾选repo 生成一个 token,然后用查询字符串拼在URL后面 ?access_token=

返回 201 则表示成功, pull一下就会出现 recover 分支。

参考文章:https://stackoverflow.com/questions/10098095/git-can-i-view-the-reflog-of-a-remote/35273807#35273807

一种使用倒排索引和位图的快速SKU选择方法

使用所有有货的SKU组合生成该SKU到该组合的索引。如 [A-B,B-C] 即生成 {A:[1],B:[1,2],C:[2]}
映射到视图时只需要判断当前选中项的SKU索引的交集(默认为全集),例如选中B,则[1,2,3][1,2]的交集[1,2],然后依次遍历SKU,判断SKU对应的索引与当前选中索引是否有交集。如果有则可选,没有则置灰。

索引可以使用位图数据结构,在判断是否为交集使用位运算提升性能。

   const sku = [];
    const revertIndex = {};
    const size = 8;
    // 随机sku
    for (let i = 0; i < size; i++) {
        sku[i] = new Set();
        for (let j = 0; j < size; j++) {
            const v = j * size + RandomNumBoth(0, size);
            sku[i].add(v)
        }
    }

    for (let i = 0; i < sku.length; i++) {
        sku[i].forEach((e) => {
            if (!revertIndex[e]) revertIndex[e] = 0;
            revertIndex[e] |= 1 << i
        })
    }

判断是否选中使用 (revertIndex[(line-1)*size + e -1] & union)

下面是一个简单的例子,取消选择和选中逻辑是一样的,所以就暂时没写:

See the Pen SKU Demo by zhangchen (@zhangchen915) on CodePen.

Preact isomophic style 实现 CSS 同构

logo.svg

实现SSR不仅需要输出HTML字符串,还要包括关键渲染路径的CSS插入到HTML中,如果样式需要浏览器加载完 CSS 后才会加上,这个样式添加的过程就会造成页面的闪动,SSR也就没有意义了。

在服务端我们不能使用style-loader,因为它只能在浏览器环境将CSS插入到页面中,我们采用isomophic style load在服务器端输出 html 字符串的同时,也将页面用到的样式抠出来,然后插入到 html 字符串当中,将结果一同传送到客户端。

下面是webpack中用到了loader部分。

    var insertCss = require(${stringifyRequest(this, `!${insertCss}`)});
    var content = typeof css === 'string' ? [[module.id, css, '']] : css;
    
    exports = module.exports = css.locals || {};
    exports._insertCss = function() { return insertCss(css) };
    exports._toString = css.toString;
    exports._module_id = id

我们实现同构 css 函数 insertCss,这里只展示服务端部分,函数接收style参数,这是css-loader生成的style对象,包括

  const [module, css, media, sourceMap] = style[0]

  // Generate Id based on length of css , because css module give different id between browser and node
  const dev = process.env.NODE_ENV === 'development'
  const id = dev ? module : style.locals._module_id

  // Server Side
  if (typeof window === 'undefined' || typeof document === 'undefined') {
    return {id, css}
  }

最后我们在服务端实现一个insertCss函数收集用到的style,然后使用<StyleContext.Provider value={insertCss}>将插入该函数注入。

const isomorphicStyle = new Map();
const insertCss = (styles) => styles.forEach(style => {
    const {id,css} = style._insertCss();
    isomorphicStyle.set(id,css)
});

我们使用 withStyles 方法装饰组件,使用useContext拿到服务端中的insertCss函数,然后调用该函数将页面导入的style 对象传进去,该函数返回移除样式的方法removeCss ,我们在componentWillUnmount 是移除CSS。

constructor(props) {
      super(props)
      const insertCss = useContext(StyleContext)
      this.removeCss = insertCss(styles)
    }

    componentWillUnmount() {
      if (this.removeCss) setTimeout(this.removeCss, 0)
    }

项目地址

https://github.com/zhangchen915/preact-isomorphic-style-loader
安装 npm i preact-isomorphic-style-loader

iOS Safari 中 Fix 定位元素在滚动时闪烁的解决

如果你不得不在滚动时固定元素,则可能是iOS Safari(和其他移动设备)存在问题。元素通常会闪烁,然后消失,直到滚动完全停止为止。

只需通过添加transform: translate3d(0,0,0);来强制开启GPU加速。

如果要在固定元素中设置元素的样式,则需要将transform3d hack应用于嵌套元素,以使其不会闪烁/消失。

.Element-header {
  transform: translate3d(0,0,0);
}

.Element-header--fixed {
  top: 0;
  position: fixed;
}

原文地址: https://muffinman.io/ios-safari-scroll-position-fixed/

不相交集合元素的数据结构——并查集

不相交集合有两种基本操作:合并(union)和查询(find)。

并查集保持了一组不相交的动态集合,每个集合通过一个代表来识别,代表即集合中的某个成员。

数组实现Quick Find

我们可以直接用数组来存储集合的标识,这样查找操作直接返回对应数组的值即可,复杂度为O(1);而合并操作每次都需要遍历整个数组,复杂度为O(n)

     0   1   2   3   4   5   6   7   8   9
     -------------------------------------
 id  0   1   2   3   4   5   6   7   8   9

union(1, 4)
union(1, 5)

     0   1   2   3   4   5   6   7   8   9
     -------------------------------------
 id  0   1   2   3   1   1   6   7   8   9

有根树表示 Quick Union

为了降低合并操作的复杂度,我们可以用多个有根树表示集合,每个结点存储指向其父亲结点的指针,根节点指向自己。判断是否属于同一个集合时,我们只需要判断元素所属的树根是否相同。

批注 2019-10-08 010040.jpg

这种方式实际上并没有本质提高,而且如果一些极端情况下会退化成一个链表,查找操作的复杂度反而上升了,上面的例子中就是这样。

查找和合并的时间复杂度都为O(h),h表示树高。

所以我们需要对合并操作进行优化,优化方式一般为以下两种。

按秩合并(union by rank)

秩(Rank)就是一颗树的结点数,即使包含较少结点的树根指向包含较多结点的树根。
所以上面的例子中union(1, 2)操作会让 2 节点会指向 1 。
批注 2019-10-08 010145.jpg

这样查找操作最坏情况的时间复杂度为O(logN)

路径压缩

在查找所在位置是我们会进行递归,那么我们可以利用递归回溯的过程进行路径压缩。所谓压缩表示的就是将从x结点搜索到祖先结点所经过的结点都指向该树的根节点结点。
DSU_path_compression.png

在压缩之后树的高度低了,所以查找复杂度也降低了。

同时使用按秩合并和路径压缩

复杂度为反阿克曼函数,具体的证明比较复杂,可以参科下面这篇讲义。
这里简单介绍下阿克曼函数,他表示f(n) = 2 ^2^2^…^2,可见其增长速度极快,其反函数用lg*n表示,其值可以认为小于5。

https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/UnionFind.pdf

批注 2019-10-08 010145.jpg
参考文章:
https://cp-algorithms.com/data_structures/disjoint_set_union.html
https://algs4.cs.princeton.edu/15uf/