如何设计一个平衡树结构

(感谢”杀出一条蟹路“同学帮忙复核数学推理) 昨天在群里和一些同学讨论算法,扯到平衡树。突然想写点东西,给同学们分享分享。但是我今天要分享的不是有多少种平衡树实现,而是如何设计一种平衡树。 希望通过这个分享,能让同学们有一些基础的认识,一种数据结构/算法是如何设计出来的。 而我们今天的话题,就是如何在树节点上,通过附加一个size来进行树平衡。 0. 开始之前 当我写这篇文章的时候,我希望对算法有所了解的同学都能看懂。数据结构设计相对于算法来说,还是有那么一点点的偏难。有些概念可能大家都是第一次接触,因此我在这里先进行一些基础概念的讲解。 约束 数据结构设计和一般性的算法有一个非常大的差异,就是: 数据结构是一个在一段时间内存在,并持续维护的结构。而不是一次性运行结束的...
点我阅读更多...

牛刀杀鸡:用pytorch实现牛顿迭代

搞这个博客本来是打算写点机器学习文章啥的。但是没办法撒,市面上机器学习的文章实在太多了。 要写点有价值的东西又实在得下一番时间啊,然后没事干就开始水,然后这博客就彻底被我变成水桶了。 既然都已经这样了,那就继续水吧,啊哈哈哈哈。 这年头,谁隔三岔五不需要解个方程什么的呢。解方程,除非需要精确值,像我这种懒人,肯定首选二分法啊。方便简洁可靠,是吧,哈哈哈。但你说人吧,总有无聊的时候是吧,例如我现在。。。 撸牛顿迭代大部分时候其实就是为了求值,当然也有时候是为了观察牛顿迭代的收敛。每次撸牛顿迭代唯一烦的地方就是求导。这个时候祭出pytorch的auto grad简直是爽歪歪啊。 牛顿迭代公式: 代码: import torch def newtons_method(fn,...
点我阅读更多...

lowerBound和upperBound

话说lowerBound和upperBound真是一对神奇的函数。如果说一个人把quick sort写了十遍,当他第十一遍开始写quick sort的时候,那绝对叫一个轻车熟路啊,绝对是soso的。 但是lowerBound和upperBound这对函数,我去年刷leetcode的时候写了n遍,简直到了闭眼都能墨写的程度。这两天又刷leetcode,拿起来竟然又一脸楞比。 于是乎我打算“一劳永逸”的解决这个问题 —- 记下来,哈哈哈 lowerBound/upperBound 的含义 lowerBound/upperBound的含义是:在一个排序好的数组里找一个位置插入,使得插入后数组仍然是排序好的。 lowerBound/upperBound的区别在于,lowerBound...
点我阅读更多...

WSL快速设置

这段时间一直在搞个unity webplayer的项目。尝试了各种组合方案,包括Windows+Linux虚拟机,Linux+unity测试版,Windows+Linux双机器。但无论怎么倒腾,都感觉难受。 正好前几天过十一,就顺便倒腾了一下传说中的WSL(Windows Subsystem for Linux),没想要甚是惊艳,就顺便写下来,分享分享,当个笔记。 如果实在无法避免双系统开发的话,那么WSL可能是目前最舒服的方案了。 WSL优点/缺点 要说WSL最大的优点的话,那么就是无缝了。Linux程序直接在Windows上,可以直接访问Windows的磁盘,和Windows共享端口池。要说用户体验,的确是秒杀虚拟机几条街。 要说缺点,如果作为一个开发系统,那么真的可以称...
点我阅读更多...

是否存在一个函数,它的三阶导是函数本身

“众所周之”,指数函数的求导是函数自身,而sin(x)的4阶求导(也就是求导四次的啦)是sin(x)本身,表示成数学公式就是: 一直很好奇,是否存在一个函数,它的二阶求导是函数本身。如果存在这么一个函数的话,是否还存在一个函数,它的三阶求导是函数本身呢?那如果推导到更广泛的n阶呢? 本来只是无聊的好奇,没想到经过一顿搜索之后,竟然找到了超乎意料的漂亮的解,相当的意外,板砖过来给大家围观。 参考资料传送门, 太长,懒得看传送门 什么函数的二阶求导是函数本身 在研究探讨三阶求导是函数本身之前,先琢磨一下一个更简单的问题是有好处的。毕竟对于问题n=1和n=4都存在的情况下,n=2存在的可能性明显是比n=3存在的可能性要高很多的。 首先,作为这个问题的趣味性,我们是肯定要先...
点我阅读更多...

如何制作一个"好用"的音量控制滑槽

音量控制滑槽啥的,我相信对每个“经验丰富”的程序员来说都是分分钟的事情。但是我今天为啥要拿出来谈这个事情呢?因为再小的东西都有细节。而且吧,还一定会有人踩进去。 相信同学们一定一定有过这种体验:到了晚上,音量拖到最小的一格仍然太大,再往左一拖就静音了。白天吧,音量区右边的一大半都没太大区别。 线性空间/对数空间 为啥会有这样的问题:人对音量的感知的范围非常的大,通常上来说一个正常人的耳朵在 20dB - 90dB 之间的范围都处于“比较舒适”的状态,但是这个范围足足有倍。如果再算上不太舒适区域的话,上个十万倍都是轻轻松松的。 但很多人写程序的时候并没有去考虑这么多,往往直接把这么大的空间直接线性的映射到音量控制滑槽上。导致的直接结果就是:音量大的区域,拉半天也没啥变化,音量小的...
点我阅读更多...

从include到require - 论node require设计

由于“工作”需要,在上周的某个月黑风高的夜晚,“新建”了一个vue项目。当然了,像我这种不做死就会死星人,自然“一不小心”就把webpack升级到了3.x。 然后惊喜的发现var Vue = require('Vue');竟然不工作了???然后再发现var MyComponent = require('./MyComponent');竟然也不工作了??? 然后就是一路的Google,WHY??? 回头换来一个说法竟然是为了“全方位”的兼容import/export,从babel xxx版本开始,require必须后面跟个.default才能导入export的结果。 我擦,我这是瞬间要炸毛的节奏啊。以牺牲require用户体验的方式,强制“退休”require。你们真的“赢了”。 ...
点我阅读更多...