小毛的胡思乱想

凡走过,必留痕迹.

数独随机生成探讨

| Comments

思路

数独游戏应该很多人都玩过,规则也很简单。以前写过数独的程序解法,最近考虑了一下数独的随机生成。毕竟,每个数独一开始都是残缺的,它是怎么生成的?

如果通过正向生成的话,还需要判断剩余的空格是否能够满足数独的问题。所以,我认为应该通过反向来创建,意思是通过一个完整的数独,然后随机从上面抠取,抠得越多,表明完成的难度越大。

具体方案

问题就变成,如何生成一个完整的随机的数独?根据数独的特点,我认为可以通过一个已有的数独来生成其他数独。方案如下:

row1

  1. 首先看看上面的图案,对于一个完整的数独,1,2,3行调换次序,仍然可以保证变换后的数独是成立。 同理,456,789也是同样的道理。行是如此,列也是可以成立的,abc,def,ghi的内部调换都是可以成立的。 row2
  2. 还有上图所示的情况,123和456整三行一起调换也是可以的。同样,在列上面也是一样的道理。
  3. 还有其他一些思路,例如进行旋转操作,或者反过来的做法。

关于重复性

对于上述1,2两种方案,会不会出现重复的情况呢?我们进行下面的分析:

row3

  1. 假设A1是x,B1是y,C1是z,我们想找到某个变化可以达到同样的效果。
  2. 如果通过行变换的话,因为数独的限制,不可能有某一行在同样的列上有xyz存在,所以不能做到。
  3. 同理,如果是列变化的话,在第一行的位置也不可能再有xyz存在,所以也是不能做到的。

意思就是说,如果从某个变化开始,每做一次变换,都能得到一个新的数独,这样我们可以统计一下,一共可以有多少种变换方式。每三行中的行内的变化有6种排列,三行三行的也是有6中排列,计算上列的变换,就有 6X6X6X6X6X6X6X6=1679616种。

从流关闭说起

| Comments

基本原则: 谁生产谁销毁

这个是用来解决责任权的问题,例如你的方法接收一个InputStream作为参数,通常就不应该在方法内去关闭它,而由客户端代码去处理。如果要关闭,通常应该在方法签名上明确说明,具体样例参考commons-io的IOUtils类。

还有另外一个例子,就是经常使用的Servlet的输入输出流,根据这个原则,也是不应该在代码中进行关闭的,这个工作是由Web容器负责的。

关闭的是什么?

java本身是带GC的,所以对象在消除引用之后,按正常是能够被回收的,那么为什么会有关闭操作?

这是为了回收系统资源,主要是端口(网络IO),文件句柄(输入输出)等,通常涉及的场景也是操作文件,网络操作、数据库应用等。对于类unix系统,所有东西都是抽象成文件的,所以可以通过lsof来观察。

为了更详细的说明这点,我们可以测试一下下面的代码:

1
2
3
4
5
6
7
8
9
10
11
12
public class Hello {
    public static void main(String[] args) throws Exception {
        for (int i = 0; i < 100; i++) {
            FileInputStream is = new FileInputStream("/tmp/data/data"+i);
            byte[] bs = new byte[512];
            int len;
            while ((len = is.read(bs)) != -1) ;
            Thread.sleep(1000L);
        }
        Thread.sleep(10000L);
    }
}

运行之后,通过losf或进程目录查看相关的文件句柄数量是不断增长的:

1
2
3
4
5
lsof -p 25945 |grep /tmp/data | wc -l
88

ls  /proc/25945/fd | wc -l
93

如果有关闭操作的话,就会发现打开文件数一直都处于很低的位置。如果持续出现未关闭的情况,积累到一定程度就可能超过系统限制,出现too many open files的错误。

如何确保关闭

关闭通常是调用close()方法来实现的,并且需要在finally来进行处理。另外,我们经常会遇到多个资源的关闭情况,因为IO库是采用修饰器模式的,所以基本原则是先关闭外层对象,再关闭内层对象,每个close调用都需要处理异常情况,例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
InputStream is = null;
OutputStream os = null;
try{
   // ...
}
finally{
  if(is != null)
     try{
       is.close();
     }
     catch(IOException e){}

  if(os != null)
     try{
       os.close()
     }
     catch(IOException e){}
}

实践

  • 上面的关闭处理的确是比较繁琐的,可以考虑进行封装或者直接使用IOUtils.closeQuietly方法,节约不少代码行。
  • 自从JDK5之后,需要进行关闭处理的对象可以考虑实现java.io.Closeable接口。这个可以让资源关闭使用同一套代码。

JDK7改进及其他思路

在JDK7里,你只需要将资源定义在try()里,Java7就会在readLine抛异常时,自动关闭资源。 但是资源类必须实现java.lang.AutoCloseable接口,同时支持管理多个资源,释放次序与声明次序相反。

1
2
3
try (BufferedReader br = new BufferedReader(new FileReader(path)) {
    return br.readLine();
}

虽然感觉总是很繁琐,语法糖味道重,但比以前倒是进步不少了。 不过我们还是来看看Go中的做法,它提供了defer操作,用于在脱离方法作用域的时候自动调用,有点析构的味道。 看下面的示例:

1
2
3
4
5
6
7
8
func main() {
    files, err := os.Open("testqq.txt")
    if err != nil {
        fmt.Printf("Error is:%s", "Game Over!")
        return
    }
    defer files.Close()
}

说说字符串拼接

| Comments

String对象是无状态的

String的内部属性在初始化的时候就固定好了,也没有提供方法进行修改(反射等极端方法除外),并且类被定义成final,所以String对象都是是实实在在的无状态对象,是不可变的。

在通常的字符串拼接中,如果采用+运算符的话,通常会产生一个字符串对象,并把两个字符串的内部字符数组拷贝过去。 因此,在一个常见的频繁修改字符串的场景中,字符数组的拷贝开销是很大的,随之字符串的加长会越到后面越慢,例如下面的代码。

1
2
3
4
5
String sb = "";
for(String str : strs){
  sb += str;
}
return sb;

StringBuffer与StringBuilder

jdk早就考虑了这种场景,于是提供了StringBuffer,简单来说,就是一个可变的字符数组,开辟了一个字符数组缓冲区,增加(Append)时只是往缓冲区的空余地方写字符,当然也有可能缓冲区不够用,它的开销就集中在不够用的缓冲区扩展中(每次在现有基础上扩展一倍空间)。所以,最好能提前估计字符串的最终长度,减少扩展造成的消耗。不过,即便如此,通常也要把直接用String拼接的效率高许多,例如下面的代码。

1
2
3
4
5
StringBuffer sb = new StringBuffer();
for(String str : strs){
  sb.append(str);
}
return sb.toString();

到了jdk5,增加了StringBuilder,相对于StringBuffer来说,虽然它不是线程安全的,但在绝大多数场景下都是适用的,并且理论效率更佳(从oracle jdk的实现看,两个类除了是否同步这点,实现是一致的)。因此,习惯使用StringBuffer的童鞋,应该多关注一下StringBuilder。

字符串拼接的编译优化

再回到+操作符,本身java是没有运算符重载的,+只会对基本数学运算有效,而字符串,这么写只是语法糖而已,会变成StringBuilder操作(jdk5之前是StringBuffer)。例如下面的代码:

1
2
3
public String test(String a){
   return a + "b";
}

通过javap查看,可以看到是这样的(大意就是new一个StringBuilder对象然后用append进行连接);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public java.lang.String test(java.lang.String);
  Code:
   Stack=2, Locals=2, Args_size=2
   0:   new     #2; //class java/lang/StringBuilder
   3:   dup
   4:   invokespecial   #3; //Method java/lang/StringBuilder."<init>":()V
   7:   aload_1
   8:   invokevirtual   #4; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
   11:  ldc     #5; //String b
   13:  invokevirtual   #4; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
   16:  invokevirtual   #6; //Method java/lang/StringBuilder.toString:()Ljava/lang/String;
   19:  areturn
  LineNumberTable:
   line 3: 0

因此,如果是像上面的情况,直接用+是合理的,对于其他情况,得考虑StringBuilder,同时要避免无意生成多余字符串的情况,例如append(”s” + a)的写法,编译器是不会自动优化的,写代码的时候应该换成append(”s”).append(a)。

更多关于字符串不变量的讨论,请见初探Java字符串

关于split的坑

| Comments

经常在一些文本处理、字符串拆解的逻辑中,需要对字符串按照一定的分隔符进行拆解。这样的功能,大多数时候我们会求助于String的split方法。关于这个方法,有几个坑是需要注意的,而掉坑想象在代码中已经出现许多次,值得大家注意。

split的参数是正则表达式

一个很常见的问题,就是忘记了split的参数不是普通的字符串,而是正则表达式,例如下面这么下是达不到预期目的的:

1
2
"a.b.c".split(".");
"a|b|c".split("|");

因为.和|都是正则表达式里边的特殊字符,应该用转义字符先进行处理:

1
2
"a.b.c".split("\\.");
"a|b|c".split("\\|");

类似的api在String类里边好几处出现了,例如replaceAll。

还有没有其他办法处理这个问题呢,因为我不想手动转换或者分隔符本来就是动态的。 这个的确没有直接的方法,但split的实现是调用Pattern的split方法,所以可以直接构造一个Pattern对象来调用, 如下所示,其中LITERAL参数就是表示把字符串当成普通字符串,而不是当成正则表达式来构建。

1
2
Pattern pattern = Pattern.compile(".", Pattern.LITERAL);
pattern.split("a.b.c");

split可能会忽略分隔后的空串

很多人只是用带一个参数的split方法,但是一个参数的split方法只会匹配到最后一个有值的地方,后面的会忽略,例如:

1
2
3
"a_b_c_d".split("_"); // ["a", "b", "c", "d"]
"a_b__".split("_"); // ["a", "b"]
"a__c_".split("_"); // ["a", "", "c"]

这样其实是有点反常识的,因为像文件上传,有些字段可能是允许为空的,这样在程序处理上就会造成麻烦。

其实,split是有带两个参数的重载方法的。第二个参数是整形,代表最多匹配上多少个,用0表示只匹配到最后一个有值的地方(就是上述split真正调用的参数),要强制全部匹配,用个负数吧(我通常选择-1)。换成下面的写法,代码就更期望的结果是一样了。

1
2
"a_b__".split("_", -1); // ["a", "b", "", ""]
"a__c_".split("_", -1); // ["a", "", "c", ""]

关于字符串切割的其他API

对于字符串切割,早在jdk1.0就存在一个叫StringTokenizer的类,大概的用法如下所示(同样有带分隔符的构造方法):

1
2
3
4
StringTokenizer st = new StringTokenizer("this is a test");
while (st.hasMoreTokens()) {
  System.out.println(st.nextToken());
}

不过,这个类是历史产物,属于遗留类来的,javadoc上已经说明了这一点,并且推荐使用String的split方法。

另外,如果对字符拼接有兴趣,请移步说说字符串拼接

怎么理解java参数传递只是传值方式

| Comments

Java参数传递只是传值

一开始学java,就有人告诉你,Java参数传递,只有传值,没有传引用。但是我在平时仍然发现,在面试时有不少人搞混, 也见过有人写出问题代码,特别是许多习惯c++编程习惯的童鞋。为了让大家都能理解,我们还是再来复习一遍。

什么是传引用

首先我们来看看什么是传引用方式? 这个概念在C++里边很常用,例如下面的代码:

1
void handle(const char* filename, int left, Callback& cb);

使用引用(第三个参数),就相当于直接使用实参一样,可以直接改变对象的内容,甚至可以让它指向另外一个对象。 相对于传值(第二个参数)来说,可以减少拷贝对象带来消耗,相对于传递指针方式(第一个参数),无需担心空指针问题,还能够改变对象的引用。

看上去,传递引用好像是集大成的功能,但实际使用上并不是每个参数都会这么搞。为什么? 因为它赋予子函数的权利太大, 对参数的任何修改都会受影响,特别是改变引用这种极端操作。

于是,Java大大减少了语法的灵活性,只保留了传值方式(因为没有指针,所以也没有所谓的指针传递)。

从内存布局看传值

因为没有指针,而且有基本类型和类类型的区别,所以有些童鞋对传值的理解有偏差。下面在从内存布局上看看。 在Java中,new出来的对象都是在heap里边生成,但是本地变量是在方法栈里边的。考虑下面的代码:

1
2
3
4
5
6
7
8
9
A a = new A();
a = call(a);

A call(A a){
   a.setName("a");
   a = new A();
   a.setName("b");
   return a;
}

看图,从左到右,从上到下,其中左边的是本地变量列表,右边的是堆空间,每行一个小图,其他不解释。 test

传的是什么值?

上面列举的情况是类类型的情况,实际上传值做的是本地变量的拷贝,而不是堆对象的拷贝。有些人会产生疑惑, 主要是因为java在语法上隐藏了指针,其实,对于类类型的参数传递,和c++中传指针方式是一个道理的,只有基本类型才是实实在在的传值方式。