技术杂笔 – Rancho Wang

HyperLogLog 算法（二）——LogLog 与 HpyerLogLog

LogLog 算法在上一篇 HyperLogLog 算法（一）——Bitmap 与 LinearCounting中介绍了 Linear Counting 的算法，缺点在于从渐进复杂性的角度看，空间复杂度仍为 O(Nmax)，其空间利用效率依旧不高。基于 Linear Counting 算法，LogLog Counting 算法的空间复杂度仅有 O(log2(log2(Nmax)))，使得通过KB级内存估计数亿级别的基数成为可能。考虑如下伯努利过程 A ：不停抛掷一枚均匀硬币，出现反面则继续抛掷，出现正面则停止抛掷，抛掷出的反面次数为 \( k\) ，那么可以容易得出： \[ P_A(x=k)=(\frac{1}{2})^k \quad k=0,1,2,3,4,5,…\] 考虑如下问题 1：进行 \( n\) 次 A 过程，每一次过程的总抛掷次数都不大于某常数 \( k_{max}\) 的概率是多少？容易得出： \[ P_1(x\leq k_{max}) = [1-(\frac{1}{2})^{k_{max}}]^n\] 进行 \( n\) 次 A 过程，至少有一次过程，其抛掷次数等于常数 \( k_{max}\) 的概率是多少？容易得出： \[ P_2(x = … Continue reading “HyperLogLog 算法（二）——LogLog 与 HpyerLogLog”

No Comments so far

HyperLogLog 算法（一）——Bitmap 与 LinearCounting

从计数谈起在漫长的求职刷 leetcode 的过程中，会遇到一个普遍的情景，但是苦于所学的语言没有封装数据结构去描述这一情景，所以一直以来都是自己在代码里实现。直到某一天看到关于 hyperloglog 的算法，才发现本问题比想象的要复杂得多，那就是计数的问题。所谓计数，用来统计一个集合中出现的各个不同元素的个数，由于在 leetcode 中太普遍，以至于一时间没有找到什么特别有代表性的问题可以贴在这里，但是普遍情况下使用 HashMap 实现，例如： class Counter<T>{ private HashMap<T, Integer> countMap; public Counter<T>(){ HashMap<T, Integer> countMap = new HashMap(); } public void add(T t){ countMap.put(this.get(t) + 1); } public int get(T t){ return countMap.getOrDefault(t, 0); } } 如果计数类型是正整数，还可以考虑直接用 Index 数组计数，即数组的 Index 为计数的元素，但是前提是元素不能太大。 class Counter{ private int[] countMap; public Counter(int … Continue reading “HyperLogLog 算法（一）——Bitmap 与 LinearCounting”

1 Comment so far

MyBatis 原理探析

本文主要简单盘点 MyBatis 用法, MyBatis 源码解读, 以及 Mybatis / Hibernate 比较基本概念 MyBatis 是一种 Java ORM (Object Related Map) 框架, 所谓 ORM 是指对象关系映射, 即将数据库的一张表和 POJO 对应起来, ORM 模型即描述了二者的映射关系. 传统操作数据库的方法是通过 JDBC 来实现的, 但是 JDBC 只是定义了接口规范, 具体实现是数据库厂商实现的, 例如 MySQL 的 JDBC 连接器可能是 Oracle 自己实现, SQLServer 的 JDBC 连接器可能就是靠微软来实现. 传统的 JDBC 存在一个问题, 即重复代码量大, 严格按照一定的顺序连接->打开->执行->读取->转换->关闭. MyBatis 这种 ORM 框架就出现了. MyBatis … Continue reading “MyBatis 原理探析”

No Comments so far

流处理平台 Spark Streaming 与 Storm

早在一年前, 就调研过主流的流处理平台, 但是对于其原理一直知之甚少, 借着实践的机会, 特意整理一些流处理的内容以供学习在交易系统, 物联网, 电信系统中广泛用到流处理系统. 流处理的特点是处理的数据特点在于数据流的规模是无限的, 反馈是实时的, 关注的对象应该是其服务, 而不是数据本身的联系. 典型的流处理平台有 Spark Streaming, Storm, Flink, Samza 等等. 本篇主要总结一下 Spark Streaming 与 Storm 的区别. 描述一个流处理系统时, 我们常常用有向无环图描述其拓扑结构一般的流处理系统基本不是单机系统, 基本都会把拓扑结点放到分布式平台上. 在总结之前, 先介绍如下几个概念: 编程模型/运行时模型运行时模型是流处理系统最大的特点, 也是 Spark Streaming 与 Storm 最大的不同, 其差异均来自于这个特性. 原生的流处理系统实现的都是原生流处理模型, 每一个记录到达之后会立即被处理. 非原生的流处理系统实现的是批处理模型, 数据会被人为的按照一定规则分成一批一批的数据, 每一批数据到达之后会进行统一处理. 原生流处理系统批处理系统 Storm 是典型的原生流处理系统, 但是也可以支持批处理, Spark Streaming 将 Spark 中的 … Continue reading “流处理平台 Spark Streaming 与 Storm”

No Comments so far

大型网站系统与 Java 中间件实践

终于支持markdown了, 排版突然变化望见谅大型网站系统与 Java 中间件实践分布式系统为什么要使用分布式系统? 升级单机处理能力的性价比越来越低单机处理能力存在瓶颈稳定性与可用性多种并发执行模式生产者消费者模型是一种典型的基于共享容器的多线程工作方式通过事件协同的模式, 例如触发事件(中断) 多进程模式, 涉及到进程间通信, 序列化与反序列化等等, 但单进程不可用, 整体可能部分可用 BIO/NIO/AIO BIO 阻塞, 方式是一个 socket 需要一个线程, 建立, 读, 写都会产生阻塞 NIO 基于事件驱动, 采用反应堆模式, 可以在一个线程中处理多个 socket (较为常用) AIO 异步IO, 采用 Proactor 模式, 通知发生在动作之前, Selector 发现事件后调用 Handler 处理. 控制器硬件负载均衡 LVS (Linux Virtual Server) 名称服务 (Name Server) 规则服务器主从模式 … Continue reading “大型网站系统与 Java 中间件实践”

No Comments so far

如何向浏览器的复杂组件（如远程终端）中粘贴？

问题的发生大概是这样的：配置搭建本博客所在的虚拟主机的SSH时，发生了一件比较尴尬的事情。在新建主机的时候仅仅上传了本人在实验室的Ubuntu PC的SSH公钥，而没有上传在宿舍的Windows PC的SSH公钥。所以在宿舍无法远程登录，而由于Digital Ocean蛋疼的设置，在主机新建之后，无法通过监控的页面添加新的SSH公钥。不过还好，Digital Ocean的Support页面给出了如何添加SSH的教程，然而，仔细阅读之后发现，这完全是在创建主机时完成的，但是Support还是给出了链接如何在创建主机之后添加SSH公钥，并且链接到如何使用Putty远程登录主机。最头疼的就在这里，试图用Putty远程登录添加SSH时发现登录的验证方式只能用SSH进行验证，于是毫无意外的成了一个类似于WinRar.rar的死循环。（补充说明，后来才知道在/etc/ssh/sshd_config文件中，PasswordAuthentication no被设置了）当然，这个问题自然不是这么解决的，如果是这么解决的不足以用一篇博客的篇幅来记述。本人于是在Digital Ocean的主机管理页面，打开了网页版的Console，这个Console是用Canvas构成的，大概直接传输的是Console的画面，加上服务器的位置是在国外，所以一直在以极其高的延时在Console中操作。每当Console出现大量刷新时，画面便会卡很久。我小心翼翼的打开了位于 ~/.ssh目录下的公钥文件，Ubuntu主机的公钥肚子静静地躺在文件中，当我右键准备复制本地PuttyGen产生的公钥时，（补充说明，Putty似乎只支持自己生成的非对称加密的私钥，因为其后缀是.pkk，无法使用大部分操作系统默认的无后缀名的那种。）发现并没有让我粘贴的选项，而是出现的是右键浏览器空白面经常出现的内容。摆在我面前的似乎只有一个方案了，那就是把长达256位的公钥敲进去。当我敲到1/3的时候，发现我真的不能这么干，因为我还要检查几遍对于我来说是毫无意义乱码的公钥是否输入正确，那么小的Console页面估计会让我把眼睛瞅瞎了，于是还是决定找一找有没有其他的往终端中粘贴的解决方案，终于在Digital Ocean的Community中找到了这个解决方案：右键浏览器检查元素，在Console中输入： JavaScript学的不是很好，这段代码大致就是定义了一个往浏览器中发送字符串的函数，也就是帮你完成了输入某个特定的字符串的功能。使用时只用继续在检查元素的Console中输入：sendString(‘The String You Wanna Paste’)，然后就实现了向远程终端中粘贴的功能。不过值得注意的是，似乎公钥里的所有的”+”都会自动转换成”=”（没有深究为什么），因为这个还浪费了很多时间。不过还好，有了这个复制方法，Xftp与Putty都顺利的连接上了远程主机，可以远程操作系统的文件目录与Console，操控变得十分便利。

No Comments so far