By

下午买菜的时候闻到了阵阵红烧肉土豆的香味，忍不住去菜场也买了这道菜 ^_^ 的材料（7块钱的肉，3块钱的土豆，10快拿取不用找，谢谢！）

红烧肉炖土豆：

  1. 将五花肉切片，也不能太细，并且最好要带有一点点肥肉才好吃
  2. 销小土豆（小土豆要比大得好吃），蛮难销的，差点手都销开了 -_-
  3. 起油锅，放一点点油
  4. 将糖放入沸腾的油锅中，炒至红色（几秒就好了）
  5. 放入五花肉，爆炒1分钟，（这个时候肉的颜色很深很有胃口）
  6. 此时倒水，没过肉，这时候加一些老抽和料酒，还有茴香，八角之类的
  7. 煮40分钟左右
  8. 放入准备就绪的小土豆（这个时候可能要加点水）
  9. 再煮20分钟，看到收汁即可

Read More

By

“将一个对象编码成一个字节流”，这个过程称为对象序列化，相反的过程称为反序列化。

第74条：谨慎地实现Serializable接口

只要添加implements Serializable，就可以使一个类可被序列化，写法上虽然看上去很简单，但是如果你认为真的这么简单的话就会付出很大的代价：

  • 一旦一个可序列化类被发布，就大大降低了“改变这个类的实现”的灵活性。
    1. 一旦一个类实现Serializable接口，它的字节流编码就变成了导出API的一部分，一旦这个类被广泛使用，往往必须永远支持这种序列化形式。
    2. 如果接受了默认的序列化形式，并且以后又要改变这个类的内部实现，结果可能会导致序列化形式不兼容
    3. 序列化会使类的演变受到限制，这种限制与序列化版本UID有关，每个可序列化的类都有一个唯一标识符serialVersionUID，如果没有指定，则系统会根据类的具体实现来进行自动生成，所以你修改了类，并且没有显示的指定UID，那么兼容性就会被破坏。
  • 它增加了Bug和安全漏洞的可能性
    序列化机制是一种语言之外的对象创建机制，所以反序列化是一个“隐藏的构造器”，具体与其他构造器相同的特点，所以反序列化过程也必须保证有构造器建立起来的约束关系，并且不允许攻击者在访问构造器过程中的内部对象，所以默认的反序列化机制很容易是对象约束遭到破坏，以及遭受非法的访问。
  • 随着类发行新的版本，相关测试的负担也增加了
    新的版本发布之后，要检查是否可以“在新版本中序列化一个实例，然后在旧版本中依然可以反序列化”，这个测试除了二进制兼容性以外，还要测试语义兼容性。所有测试的难度都是相当大啊！

Read More

By

关于TeraSort的思想其实是非常简单的，但是查了网上好多资料，感觉把它的实现复杂化了（指的在Hadoop中），它们要自定义InputFormat，RecordReader等，其实我想说，实现一个TeraSort根本不需要这么麻烦，所以本文就将实现一个非常简单、非常简单、非常简单的实现记录下来，额，重要的事情说三遍。^_^

TeraSort简介

1TB排序通常用于衡量分布式数据处理框架的数据处理能力。TeraSort是Hadoop中的的一个排序作业，在2008年，Hadoop在1TB排序基准评估中赢得第一名，耗时209秒。(其实现在在TeraSort上Spark已将Hadoop甩在后面-_-)

在看排序之前，先来看一下Map-Reduce的一张非常经典的流程图：
Map-Reduce流程图

从图种可以了解到Map-Reduce执行的整个过程中会进行两次排序，一次是在Map端的shuffle，另一次是在Reduce端的shuffle，TeraSort正好是利用这种特性来进行排序

注意，这里的排序仅仅是针对key的。

Read More

By

猪蹄黄豆汤的流程：

  1. 切猪蹄（真难切。。。）
  2. 将切好的猪蹄和黄豆在水中浸泡好几个小时
  3. 起油锅，放一点点油
  4. 将猪蹄炒30秒左右
  5. 加水没过猪蹄，
  6. 等水开了，放入黄豆
  7. 放入料酒，八角，茴香
  8. 一直煮2小时，期间加了一些水 -_-

    Read More

By

线程机制是允许同时进行多个活动，并发程序设计比单线程程序设计要困难的多，因为有更多得东西可能会出错，也很难以重现失败。

第66条：同步访问共享的可变数据

关键字synchronized可以保证在同一时刻，只有一个线程可以执行某一个方法，或者某一个代码块，关于这点，有两方面的意义：

  1. 当一个对象被一个线程修改的时候，可以阻止另一个线程观察到内部不一致的状态
  2. 它可以保证进入同步方法或者代码块的每个线程，都可以看到同一个锁保护之前所有的修改
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    private static boolean stopRequented;

    public static void main(String[] args) throws InterruptedException 
    {
    	Thread backgroundThread=new Thread(new Runnable(){
    		
    		@Override
    		public void run()
    		{
    			int i=0;
    			while(!stopRequented)
    				i++;
    			
    			System.out.println("the thread stop now!");
    		}
    	});
    	
    	backgroundThread.start();
    	Thread.sleep(3000);
    	
    	stopRequented=true;
    }

看上面的代码，你运行的时候并没有按你期望的在3秒之后终止程序，这是因为stopRequented这个变量并没有同步，不能进行线程共享
虚拟机将那段循环代码可以转为

Read More

By

充分发挥异常的优点，可以提高程序的可读性、可靠性和可维护性。如果使用不当，它们也会带来负面影响。

第57条：只针对异常的情况下使用异常

先看下如下代码：

1
2
3
4
5
6
7
8
9
try
{
	int i=0;
	while(true)
		range[i++].climd();
}catch(ArrayIndexOutOfBoundsException e)
{
	
}

此代码看的如此蛋疼，使用异常来跳过数组越界，其实完全可以用下面的代码代替

1
2
for(Mountain m:range)
			m.climb();

简单明了（我想上面的例子大家都能看出孰优孰劣）
不推荐第一种写法的原因是：

  1. 因为异常机制的设计初衷是用于不正常情形，所以很少会有JVM实现试图对它们进行优化，使得与显示的测试一样快速
  2. 把代码放在try-catch块中反而阻止了现代JVM实现本来可能要执行的某些特征优化
  3. 对数组进行遍历的标准模式并不会导致冗余检查。有些现代的JVM实现会将它们优化掉

所以，异常应该只用于异常的情况下，它们永远不应该用于正常的控制流

Read More

By

题目

现有矩阵：
0, -2, -7,  0, 3
9,  2, -6,  2, 5
-4, 1, -4,  1, 6
-1, 8,  0, -2, 2
求该矩阵的一个子矩阵，使子矩阵所有元素的和最大

最大子序列

在看最大子矩阵之前，先来看一下最大子序列的求解：

给定一个长度为n的一维数组a，请找出此数组的一个子数组,使得此子数组的和sum＝a[i]+a[i+1]+……+a[j]最大（0<=i<=j<=n-1）
比如在序列-2,11,-4,13,-5,-2中，最大子序和为11+(-4)+13=19

求解该方法一般使用动态规划b[j]=max{b[j-1]+a[j],a[j]}，简化后的程序为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int maxSubSum(int[] a)
{
	int maxSum=0,curSum=0;
	for(int i=0;i<a.length;i++)
	{
		curSum+=a[i];
		if(curSum>maxSum)
		{
			maxSum=curSum;
		}else if(curSum<0)
		{
			curSum=0;
		}
	}
	
	return maxSum;
}

该解法的复杂度为O(n)

Read More

By

题目

Instance的格式是：
Lineid show clk fea1:slot1 fea2:slot2 …
Feature的格式是：
Fea1\tweight
Fea2\tweight

现在要求计算每个instance的feature权重之和，但是feature数量极多，可能几千万或者几亿，总之无法放入内存。

分析

  1. 这是一道很典型的Join操作题目，但是由于是百度的面试题，肯定不会那么简单
  2. 假如将Instance作为大表，Feature作为小表，但是Feature已经无法放入内存了，就无法用map-silde来做Join了
  3. 所以只能用reduce-silde来做，但是这种方式在Reducer端输入的迭代器中会混杂着Feature的权重和LineId，并且是无序的，所以一般会遍历迭代器，然后将两者分离，但是问题就出在这里了，分离的时候要将LineId保存到一个容器里，这时候极有可能出现OOM，也就是在Reducer端内存不足

Read More

By

原因

昨天将此题使用标签传播版PageRank法（标签合并）得到了正确地结果，但是今天想想这个效率也还是蛮低啊：

  1. 虽然关于标签的存储使用了位图法，但是海量数据下这个标签的存储仍然是一个大得问题
  2. 迭代过程中多次对两两标签集合进行合并，还不时的需要clone操作，时间空间开销都是很大
  3. 关于迭代停止是判断两个标签集合里面的内容是否相等，需要O（n）的复杂度
  4. 最后在判断连通子图时，进行Join的key计算时使用了hashCode，这种方法偷懒的方法很容易造成结果不准确，但是也的确很难用一个唯一的数字来表示一个HashMap了呀

所以

今天想到了这些标签集合完全可以使用集合中标签的最小值的代替，比如（接上文的cookie）cookeiA的最小值是1，cookeB的最小值是1，cookeC的最小值是3，在迭代时cookieB将消息发给cookieC，cookeC将自己的标签由3更新到了1，这样就很判断cookieA，B,C就是一个人了，而且只需要一个int类型就可以了，不需要额外的开销。

Read More

By

题目

在百度网站上有很多作弊者，现在百度已经使用某种技术将他们标记起来，比如：
cookieA和cookieB的标签都为1，他们是代表同一个用户，而cookieB可能又有一个标签2与cookieC相同，此时cookieB和cookieC也是同一个用户，这样其实cookieA,cookieB,cookieC就是一个用户而已，但是百度的数据量很大，现需要找出这批大量数据中的所有作弊者，请使用分布式的方法来求解此问题（可以使用Hadoop,Spark或者其他的任何一种平台）

当时面试官也说了这个其实就是找连通子图问题

采样+多源最短路径（失败）

我最初以为这个图里每个连图子图规模较大，但是个数却不是很多，所以一下子想到的就是：

  1. 先对大图采样
  2. 以采样顶点为起始顶点，利用Spark的Pregel模块来跑多源最短路径
  3. 每个源跑完之后标记形成的图就是连通子图

Read More