AI and Big Data

Learning Akka

最近学习了scala,主要是跟着Functional Programming in Scala的课程学习的,scala主要的用处还是在spark上,关于spark也看了一些源码,处于继续探索中。

并发时的消息通信是处理spark这样的分布式系统的关键。spark主要依赖scala社区的akka进行消息通讯。在spark1.2的代码中可以看到很多actor的影子,然而spark1.4中,都是封装为EndPoint,但Actor的思想和模式还在。

基于Actor的消息通讯模型是akka的核心。Akka为处理并发、容错和可扩展性的分布式问题提供了一套基于Actor模型的库。并发的消息通讯中,抽象是关键的方面。Actor模型是1973年由Carl Hewitt在论文”Actor Model of Computation- Scalable Robust Information Systems”中提出, 后被应用于爱立信公司研发的Elang语言,爱立信公司应用Actor模型开发了高并发和可靠的通信系统。

Continue reading

位排序和快排

这已经不是一个新话题了,但是从开始实现一个C++位排序和快排,我还是花费了2个多小时,这里就记下自己的一点点体会啦。

首先,题目来自《编程珠玑》第一章,主要是做位排序,同时和快排做比较:

1. 实现位逻辑运算,实现位向量,并用该位向量实现1,000,000个数字的排序,数字最大是10,000,000

2. 实现1000,000个数字的快排序

3. 实现生成小于n且没有重复的k个整数,这里n=10,000,000, k = 1,000,000

Continue reading

Algorithm

查找两个排序数组的中位数

题目是:求两个排序数组的中位数。
设:两个排序的数组a[m], b[n],求a和b数组的中位数。
算法是:
mid_a是数组a的中位数index,同理mid_b是数组b的中位数索引
1. 如果a[mid_a] == b[mid_b] 中位数为a[mid_a]

2. 如果a[mid_a] < b[mid_b], 递归查找a(mid_a + 1, m - 1), b(0, mid_b),因为a[mid_a]比较小,不可能作为下一次查询的中位数

3. 如果a[mid_a] > b[mid_b], 递归查找a(0, mid_a), b(mid_b + 1, n - 1),因为b[mid_b]比较小,不可能作为下一次查询的中位数

4. 当只少于4个元素需要查找时递归停止,merge这少于4的元素,求出中位数。这里需要考虑奇偶数的情况,只剩下2个或3个元素,不如只考虑4个简单。

注意:这里求上中位数,当n为奇数时,中位数是唯一的,出现位置为n/2;当n为偶数时候,存在两个中位数,数组index从0开始,位置分别为n/2 - 1(上中位数)和n/2(下中位数)。

Continue reading