路由器时间同步服务器 最近路由器重启了之后时间总是卡在 1970 年不能自动同步。还以为是路由器哪里设置错了，后来发现应该是同步服务器连不上，换了新的服务器好了，摘下一些常用的列表： ntp.sjtu.edu.cn 202.120.2.101 (上海交通大学网络中心NTP服务器地址） s1a.time.edu.cn 北京邮电大学 s1b.time.edu.cn 清华大学 s1c.time.edu.cn 北京大学 s1d.time.edu.cn 东南大学 s1e.time.edu.cn 清华大学 s2a.time.edu.cn 清华大学 s2b.time.edu.cn 清华大学 s2c.time.edu.cn 北京邮电大学 s2d.time.edu.cn 西南地区网络中心 s2e.time.edu.cn 西北地区网络中心 s2f.time.edu.cn 东北地区网络中心 s2g.time.edu.cn 华东南地区网络中心 s2h.time.edu.cn 四川大学网络管理中心 s2j.time.edu.cn 大连理工大学网络中心 s2k.time.edu.cn CERNET桂林主节点 s2m.time.edu.cn 北京大学

Manacher 马拉车算法 马拉车算法可以在线性时间复杂度内求出一个字符串的最长回文字串。其核心思想跟 KMP 相似，即反复利用已掌握的情况。视频推荐看这个，觉得是最清晰易懂的：整体思路这个算法的主要思路是维护一个跟原串 str 一样长的数组 lens。lens[i] 表示以 str[i] 为中点的回串其中一边的长度。这里有的人把中点算进去，有的人记录两边的长度，其实都一样，我这里是只记录一边的长度，不包括中点。比如 "CDCDE"str: [C, D, C, D, E] lens: [0, 1, 1, 0, 0]那么 lens 里最大的自然就对应最长回串的中点了。所以这个算法的核心就是如何快速计算 lens。预处理回文有奇偶长度两种情况，通过补充间隔符可以将这两种情况化简为奇数长度。比如 ABA 补充为 #A#B#A# 中点还是 B，ABBA 补充为 #A#B#B#A# 中点为 #，最后可以去掉。算法用 JavaScript 写，我将原串转为数组，间隔符就用 null。最后在两侧补上哨兵点方便遍历中止。我用了 NaN。所以看起来是这样var arr = [NaN, null] for (let i = 0; i iRight - i。整合可以看到，我们复制镜面值要考虑三种情况，范围内、右贴界、左越界，其中左越界又包含了右贴界。于是简洁起见，我们全部当右贴界处理，因为如果在范围内比较下去自然不相等，相当于去掉了 if 判断。然后整合范围内和左越界，范围内指 lens[iMiiror] iRight - i，取 iRight - 1。故整合为 min(iRight - i, lens[iMirror])。完整算法所以完整算法如下function manacher (str) { str = String(str) var arr = [NaN, null] for (let i = 0; i

巧妙监测元素尺寸变化 在往下读之前不妨先想一下，你会怎么实现？如何知道元素的尺寸发生变化了？相信很多人第一反应是 resize 事件，但这个只是 document view 变化才会触发。然后就是轮询，反复查询值变化了没有。开销不是一般的大，但像这样的库（比如这个七年前的）现在还有人用。最后便是这个，号称 event based 无性能问题，便去观摩了一番源码。代码本身没什么惊喜，所以本文不会像之前一样逐行逐块地分析，而是着重原理，对应这部分的源码。整体思路这个方法的主要思想是在被监测元素里包裹一个跟元素位置大小相同的隐藏块。隐藏块可以滚动，并有一个远远大于它的子元素。当被监测元素尺寸变化时期望能触发隐藏块的滚动事件。这个方法听起来很简单是不是，但如果你直接这么实现会发现时而行时而不行，问题就在于触发滚动事件的条件。如何计算滚动？这是我觉得这个话题值得写成文章的一个有趣点。我们理所当然地看待滚动，但有没有想过它是怎么计算的呢？发生滚动的时机有问题当然要去请教规范老师。第一步我们需要知道什么时候才会发生滚动，首先一个题外话，overflow 为 hidden 也是可以滚动的，另外一篇分析里也遇到过。在这里提到滚动事件发生的时机，但说得有点笼统Whenever an element gets scrolled (whether in response to user interaction or by an API)但从这段我们可以知道，每次发生滚动的时候，浏览器会先收集起来，在下次 event loop 到达时统一地处理。滚动的描述在这里：To scroll an element element to x,y optionally with a scroll behavior behavior (which is "auto" if omitted) means to: Let box be element’s associated scrolling box. If box has rightward overflow direction Let x be max(0, min(x, element scrolling area width - element padding edge width)). If box has leftward overflow direction Let x be min(0, max(x, element padding edge width - element scrolling area width)). If box has downward overflow direction Let y be max(0, min(y, element scrolling area height - element padding edge height)). If box has upward overflow direction Let y be min(0, max(y, element padding edge height - element scrolling area height)). Let position be the scroll position box would have by aligning scrolling area x-coordinate x with the left of box and aligning scrolling area y-coordinate y with the top of box. If position is the same as box’s current scroll position, and box does not have an ongoing smooth scroll, abort these steps. Perform a scroll of box to position, element as the associated element and behavior as the scroll behavior. 最后一步“perform a scroll”才会真正触发滚动事件。第五步便是问题关键，位置相同的时候，滚动事件不会发生。重排根据前面的整体思路，当被监测元素尺寸发生变化时，隐藏元素也跟着变化。于是引发了 Layout/Reflow 使到重新计算滚动位置 position。但这时也许你会发现 position 根本没有变化，如图一。 .parent { height: 100px; width: 100px; overflow: scroll; background: red; position: absolute; top: 0; left: 0; bottom: 0; right: 0; margin: auto; } .child { height: 200%; width: 200%; background: blue; } .msg { position: absolute; top: 370px; left: 50%; transform: translateX(-50%); text-align: center; } var parent = document.querySelector('.parent') var child = document.querySelector('.child') var msg1 = document.querySelector('.msg1') var msg2 = document.querySelector('.msg2') parent.scrollTop = 1000 parent.scrollLeft = 1000 var eventCount = 0 function log () { msg1.innerText = `scrollTop:${parent.scrollTop}, scrollLeft:${parent.scrollLeft}` msg2.innerText = `${eventCount}scroll event${eventCount > 1 ? 's were' : ' was'}triggered` } log() parent.addEventListener('scroll', () => { eventCount += 1 log() }) 为什么？上面的第二、三步有答案。一般来说，我们的设备都是上到下、左到右，所以属于右下方向溢出，对应上面的 2.1 和 3.1 公式。每次计算滚动距离都会跟可滚动的空间比较取最小值。因为子元素的尺寸是固定的，且远远大于容器，故两者的差非常大，所以最小值一直是 x 和 y，每次重排都会在同个位置，触发了上面的第五步。同时根据公式易得：当可滚动空间一开始不比 x 和 y 大，且随滚动不断变小时，就可以让 position 发生变化。于是，我们先让元素滚到最尽头，那么 x 和 y 达到了最大值。当容器尺寸变大时，因为子元素的尺寸是固定的，故 scrolling area 的大小不变，所以两者的差变小了，x 和 y 得到新的最小值，发生了滚动。见图二。/* ... */ .child { height: 200px; width: 200px; } /* ... */// ..... var msg2 = document.querySelector('.msg2') parent.scrollTop = 1000 parent.scrollLeft = 1000 var eventCount = 0 // ....初始的 1 个事件就是上面提到的 event loop 导致的。可以观察滚动发生，我们期望容器达到最大时 x 和 y 都没有达到最小值，所以子元素的大小须比容器最大值要大。动图同时也可观察到容器变小时没反应。按上面的公式也很容易知道，容器变小了，差值变大了，所以最小值还是 x 和 y，故不触发滚动。怎么办呢？物尽其用再看回公式，我们希望容器变小时，差值也变小。那么只能是让 scrolling area 也跟着变小了。如果子元素大小改为百分比行不？我们来证明一下。设容器宽度为 x1 或者 x2，其中 x2 > x1，子元素大小为 n * x1 或 n * x2，因我们不设 padding，则有n * x1 - x1 = 1 ↓ n >= 2故我们只需让子元素大小至少为 200% 就可以！见图三/* ... */ .child { height: 200%; width: 200%; } /* ... */// ..... var msg2 = document.querySelector('.msg2') parent.scrollTop = 1000 parent.scrollLeft = 1000 var eventCount = 0 // ....同时也说明百分比不能监测容器变大，因为 0 < n < 1 与 n >= 1 + 1/Max 矛盾，可自行证明。所以，结合两个方式就可以监测元素扩大与缩小变化。代码原理搞通之后代码就不难了，我这里另外重新实现了一遍，修改了隐藏块的创建方式以及加入 passive events 优化滚动。Demo 里拖动一个块改变大小另一个会同步变化，可以看到非常的流畅。

prototype 与 __proto__ 的爱恨情仇 经历了上次的《JavaScript This 的六道坎》 发现编故事有点上瘾，而且记忆效果也不错哈哈，今天继续唠叨一下 prototype 与 __proto__ 的爱恨情仇。先理解两者的一个本质区别，prototype 是函数独有的，是人为设定的；__proto__ 是所有对象都有的，是继承的。然后来看一个两个神的故事：首先在 ECMAScript 星球，万物起源于 the Engineers，哦不，是一个叫 %ObjectPrototype% 的 intrinsic object，也就是 Object.prototype。它是万物的尽头，继承于虚无， Object.prototype.__proto__ 为 null。接着由其衍生出第二神，另外一个 intrinsic object %FunctionPrototype%，也就是 Function.prototype。于是有Function.prototype.__proto__ === Object.prototype // trueFunction.prototype 本身也是个函数对象，这是为了兼容 ES5。也估计是让人引起误解的源头。但两者还是不同的，这是个特殊的函数对象，它忽略参数总是返回 undefined，且没有 [[Construct]] 内部方法。搞清楚了这两个 Ancient Gods 接下来就很容易了，相信也听过“函数在 JS 里是一等公民”这类的说法，其实是因为它们都是 %FunctionPrototype% 的子民（这里不用 Function.prototype 是为了避免混淆，记得 prototype 是人为设定的），包括 Function 本身。所以你可以看到，Object、Function、String、Number、Boolean 等等等的 __proto__ 都是 Function.prototype。所以接下来的问题就更容易了，比如 Object instanceof Object。前面我们知道 Object.__proto__ 是 %FunctionPrototype%，而它的 __proto__ 是万物之源 %ObjectPrototype%，恰好也是 Object.prototype，所以就是 true 啦。其它的也是同理，举一反三很简单了。

检测 DOM 结点插入 闲逛 Github 时碰见一个叫 SentinelJS 的库，声称能检测 DOM 结点的插入，顿时引起了好奇。因为以前无聊时也想过一下，没什么头绪，便不了了之。当时第一反应是该不会用轮询吧（比这粗暴的实现也不是没见过）。但看到 682 bytes (minified + gzipped) 大小时感觉一定又是用了什么奇淫怪巧，个人对这种东西很感兴趣（见另一篇《巧妙监测元素尺寸变化》），便顺便看了看源码，很短，但一看到 animation 时便拍大腿了！通过检测 animationstart 事件来检测插入，机智！代码很短，就是维护了一个事件队列。核心在 onFn 和 offFn 上。后者同理，便主要看 onFn 的实现。/** * Add watcher. * @param {array} cssSelectors - List of CSS selector strings * @param {Function} callback - The callback function */ function onFn(cssSelectors, callback, extraAnimations) { if (!callback) return; // initialize animationstart event listener if (!isInitialized) init(); // listify argument cssSelectors = Array.isArray(cssSelectors) ? cssSelectors : [cssSelectors]; // add css rules and cache callbacks cssSelectors.map(function(selector) { var animId = selectorToAnimationMap[selector]; if (!animId) { // add new CSS listener var css, i; animId = 'sentinel-' + Math.random().toString(16).slice(2); // add keyframe rule css = '@keyframes ' + animId + '{from{transform:none;}to{transform:none;}}'; i = styleSheet.cssRules.length; styleSheet.insertRule(css, i); styleSheet.cssRules[i]._id = selector; // add selector animation rule css = selector + '{animation-duration:0.0001s;animation-name:' + animId; if (extraAnimations) css += ',' + extraAnimations; css += ';}'; i += 1; styleSheet.insertRule(css, i); styleSheet.cssRules[i]._id = selector; // add to map selectorToAnimationMap[selector] = animId; } // add to callbacks var x = animationCallbacks[animId] = animationCallbacks[animId] || []; x.push(callback); }); }先生成一个随机的带前缀的 animId 来区分每个事件。animId = 'sentinel-' + Math.random().toString(16).slice(2);styleSheet 为一个事先挂载的 元素，所有的 animation 样式都会插入到这里。插入 @keyframes 之后在这条规则上面以选择器做了一个私有的标记 _id，为了在移除事件的时候找到这条规则。// add keyframe rule css = '@keyframes ' + animId + '{from{transform:none;}to{transform:none;}}'; i = styleSheet.cssRules.length; styleSheet.insertRule(css, i); styleSheet.cssRules[i]._id = selector;接下来再插入一个持续 0.0001s 的动画，监听搞定。接下来初始化的时候在 document 上监听 animationstart 事件：doc.addEventListener(event, animationStartHandler, true);通过事件的 animationName 来匹配 animId，成功则取消其它监听这个事件的回调。/** * Animation start handler * @param {Event} ev - The DOM event */ function animationStartHandler(ev) { var callbacks = animationCallbacks[ev.animationName] || [], l = callbacks.length; // exit if a callback hasn't been registered if (!l) return; // stop other callbacks from firing ev.stopImmediatePropagation(); // iterate through callbacks for (var i=0; i