关于最小公倍数

求最大公约数的算法众所周知,使用辗转取余法(辗转相除法)

但怎么求n个数的最小公倍数呢,

常规解法有两种,

一种是质因数分解,设每个出现过的质因数 p[i]所出现的最大次数为a[i],则把所有Math.pow(p[i], a[i[)相乘即可,不过这种方法局限于

正整数

还有一种是假设两数分别为a, b,求出最大公约数gcd[0], a[1] = a/gcd[0], b[1] = b/gcd[0] ,再把a[i], b[i]这样处理直到a[i], b[i]互质为止,这是把所有的gcd[k] (k

(defn lcm [& nums]
  (let [index-of (fn [v l] 
    (loop [i 0] 
      ; get the index of value v in sequence l. assume v is in l
      (if (= (nth l i) v)
        i 
        (recur (inc i)))) ) 
    lcm-help (fn [now-nums origin-nums]
                (if (apply = now-nums)
                  (first now-nums)
                  (let [min-value (apply min now-nums)
                        min-value-index (index-of min-value now-nums)
                        origin-val (nth origin-nums min-value-index)
                        new-val (+ min-value origin-val)
                        now-nums-vector (vec now-nums)
                        new-now-nums-vector (assoc now-nums-vector 
                                              min-value-index new-val)
                        new-now-nums (seq new-now-nums-vector)]
                    (recur new-now-nums origin-nums))))]
      (lcm-help nums nums)))

(println (lcm 7 5/7 2 3/5))
(println (lcm 3/4 1/6))

输出结果为210, 3/2

PHP与Java中运行时获取调用类方法(静态方法)的类名的方法

因为看不惯FengOffice中的ORM框架(好像是Zend中的,不过没用过Zend,不清楚),觉得太繁琐,所以打算自己用PHP实现一个轻量级,方便,尤其要容易写Model和容易使用。

参考了Yii的orm框架的使用方式,或者说是ActiveRecord的使用方式,写了一个简单的orm,在实现的时候因为要在父类Model类中的静态方法中,动态获取调用它的是哪个类,从而知道使用的是Model的哪个子类。刚开始不清楚怎样获得,后来在一位学弟的提醒下知道了有get_called_class()这个方法可以动态获取调用者是哪个类,从而解决了这个问题。

果然,百度是百度不出什么东西的啊。这个orm框架在稍作完善后再放到github(zoowii)上吧,先不管这个。

因为学校学的主要语言是Java,所以想到Java中怎么解决这个问题,经过百度(因为十八大,谷哥不方便),找到了一篇帖子:
http://hi.baidu.com/kittopang/item/a04c9ed12ff32aefb2f77711

因为这篇帖子中的情况是获取当前类,而不是运行时使用父类的静态方法,在这个父类的静态方法中动态获取它的调用者的类名,两者情况还是不一样的。所以我写了点Java代码测试了一下。

// Test3.java
public class Test3 {
  // output the current class name of the source file, so always output Test3
  public static void f1() {
    String className = new Object() {
      public String getClassName() {
        String nm = this.getClass().getName();
        return nm.substring(0, nm.lastIndexOf(‘$’));
      }
    }.getClassName();
    System.out.println(className);
  }

  // also output Test3
  public static void f2() {
    String className = new SecurityManager() {
      public String getClassName() {
        return getClassContext()[1].getName();
      }
    }.getClassName();
    System.out.println(className);
  }

  public static void f3() {
    String clsName = new Throwable().getStackTrace()[1].getClassName();
    System.out.println(clsName);
  }

}
// Test4.java
public class Test4 extends Test3 {
  public static void main(String[] args) {
    f1();
    f2();
    f3();
  }
}

编译后执行java Test4后得到输出结果:

Test3

Test3

Test4

可见,只有第三种方法可以达到目的,也就是通过新建一个Throwable对象,调用getStackTrace()获取调用栈信息,对其中的第二个对象调用getClassName()方法。这种通过异常栈的方法获取信息的方法虽然能够达到目的,而且可以获取的信息很多,但到底不优雅,而且性能很差,但在不知道其他解决方案的情况下也只能这样了。如果有人知道其他方法的,请告诉我,谢谢。

Java执行机制

Java 源码编译—–javac将java源码编译为class

java源文件(.java)=>分析和输入到符号表=>注解(annotation)处理=>语义分析和生成class文件

class文件的内容

class文件的内容如下:

  • 结构信息:class文件格式版本号等信息=>所以高版本的jdk生成的.class文件低版本的jre无法运行,反之可以运行
  • 元数据:类继承、接口实现、属性和方法的声明、常量池等信息
    *方法信息:Java源文件中语句、表达式对应的信息,包括:字节码、异常处理器表、求值栈与局部变量区大小、求值栈的类型记录、调试用符号信息

例子:

// Hello.java
public class Hello {
    public static void sayHi() {
        System.out.println("Hello World!");
    }
    public static int add(int x, int y) {
        return x + y;
    }
    public static void main(String[] args) {
        sayHi();
        System.out.println(add(4, 5));
    }
}

使用javac -g Hello.java(使用javac Hello.java也可,但调试信息更少)产生Hello.class文件

再使用javap -c Hello可以反编译字节码,输出如下:

// Compiled from "Hello.java"
public class Hello {
public Hello();
    Code:
       0: aload_0
       1: invokespecial #1
       // Method java/lang/Object."":()V
       4: return        

  public static void sayHi();
    Code:
       0: getstatic     #2
       // Field java/lang/System.out:Ljava/io/PrintStream;
       3: ldc           #3
       // String Hello World!
       5: invokevirtual #4
       // Method java/io/PrintStream.println:(Ljava/lang/String;)V
       8: return        

  public static int add(int, int);
    Code:
       0: iload_0
       1: iload_1
       2: iadd
       3: ireturn       

  public static void main(java.lang.String[]);
    Code:
       0: invokestatic  #5
       // Method sayHi:()V
       3: getstatic     #2
       // Field java/lang/System.out:Ljava/io/PrintStream;
       6: iconst_4
       7: iconst_5
       8: invokestatic  #6
       // Method add:(II)I
      11: invokevirtual #7
      // Method java/io/PrintStream.println:(I)V
      14: return
}

类执行机制

  • 字节码解释执行
    jvm有一套中间码,如invokestatic(调用static方法)、invokevirtual(调用对象实例方法)、invokeinterface(调用接口的方法)和invokespecial(调用private方法和方法)等。
    因此,jvm可以把这写中间码的指令解释执行,就像类似于脚本语言执行。只不过脚本语言执行的源文件是可读的文本文件,
    而jvm解释执行执行的是不可读的.class文件。

  • 字节码编译执行
    解释执行效率低,所以jvm可以在运行时把.class文件编译成机器码执行,这就是JIT编译。
    所谓的Hotspot 就是执行时对执行频率高的代码编译执行,执行频率低的代码解释执行。

关于Java对象占用内存大小

附加:以下内容很多错误,Java对象中还有很多其他内容, 比如指向类的指针,Flags(哈希值等),形状(是否是数组),如果是数组还有数组长度。后面才是正文内容。并且如果是String对象的话,String对象的正文部分是一个指向char[]的指针,这个char[]数组本身也有上面说的类型,Flags,形状,数组大小等基本信息和实际内容。并且在32bit和64bit的JVM上Java对象的基本结构占用内存也是不同的

昨天面试有一道题是关于Java内存占用的。题目是求出new String("a")Map map = new HashMap(); map.put("a", "a");

回来之后我检测了一下,通过观察创建对象前后(创建大量一样的对象求均值)的已使用堆(runtime.totalMemory() - runtime.freeMemory())内存大小的变化来计算Java对象的内存占用情况 。

代码是网上找来的:

import java.util.HashMap;
import java.util.Map;
public class Test5 {
    public static void main(String[] args) throws Exception {
        // Warm up all classes/methods we will use
        runGC();
        usedMemory();
        // Array to keep strong references to allocated objects
        final int count = 100000;
        Object[] objects = new Object[count];
        long heap1 = 0;
        // Allocate count+1 objects, discard the first one
        for (int i = -1; i < count; ++i) {
            Object object = null;
            // Instantiate your data here and assign it to object
            // object = new Object();
            // object = new Integer (i);
            // object = new Long (i);
            // object = new String ("a");
            Map object1 = new HashMap();
            object1.put("a", "a");
            // object1.put(new String("a"), new String("a"));
            // object = new byte [128][1]
            if (i >= 0)
                objects[i] = object1;
            else {
                object1 = null; // Discard the warm up object
                runGC();
                heap1 = usedMemory(); // Take a before heap snapshot
            }
        }
        runGC();
        long heap2 = usedMemory(); // Take an after heap snapshot:
        final int size = Math.round(((float) (heap2 - heap1)) / count);
        System.out.println("'before' heap: " + heap1 + ", 'after' heap: "
                            + heap2);
        System.out.println("heap delta: " + (heap2 - heap1) + ", {"
                            + objects[0].getClass() + "} size = " + size + " bytes");
        for (int i = 0; i < count; ++i)
            objects[i] = null;
            objects = null;
        }

    private static void runGC() throws Exception {
        // It helps to call Runtime.gc()
        // using several method calls:
        for (int r = 0; r < 4; ++r)
            _runGC();
    }

    private static void _runGC() throws Exception {
        long usedMem1 = usedMemory(), usedMem2 = Long.MAX_VALUE;
        for (int i = 0; (usedMem1 < usedMem2) && (i < 500); ++i) {
            s_runtime.runFinalization();
            s_runtime.gc();
            Thread.currentThread().yield();
            usedMem2 = usedMem1;
            usedMem1 = usedMemory();
        }
    }

    private static long usedMemory() {
        return s_runtime.totalMemory() - s_runtime.freeMemory();
    }

    private static final Runtime s_runtime = Runtime.getRuntime();
}

运行结果表明:

  • new String(“a”)占用24Bytes,
  • Map map = new HashMap(); map.put(“a”, “a”); 占用168Bytes,
  • Map map = new HashMap(); map.put(new String(“a”), new String(“a”));占用216Bytes.

原理:Java 的String 对象有四个属性:

privatefinalcharvalue[];
/** The offset is the first index of the storage that is used. */
privatefinalintoffset;
/** The count is the number of characters in the String. */
privatefinalintcount;
/** Cache the hash code for the string */
private inthash;// Default to 0

再考虑Java对象的8字节对齐,java采用utf16编码,每个char 占用2个字节, 另外,java对象有两个字(每个字2字节) 的头部,分别表示垃圾收集、hash码信息以及指向对象的类,即占有4个字节。 24字节应该还是差不多的。

不过网上还有种说法是一个空字符串都占用40个字节,长为1的字符串也是占用40个字节,不清楚怎么算的,昨天面试官说的也是大概这个数据。

引用:http://www.javaworld.com/javaworld/javatips/jw-javatip130.html?page=1

浏览器中的Scheme解释器

前两天用javascript写了一个scheme解释器,已经可以运行在node.js和浏览器中。代码放在github上了。
http://github.com/zoowii/SchemeScript

Features

  • 另外,http://aboutzoowii.duapp.com/app/js/SchemeScript 中可以在线演示
  • 支持自然数,布尔值(true, false),字符串(“…”),变量定义
  • 可以定义函数了,并调用自定义函数,可以嵌套。示例中有求斐波那契数列的
  • 有list, cons, car, cdr, list-len, n-th, typeof, +, -, *, /等函数
  • 支持lambda表达式,柯里化
  • 所有合法的标识符都可以被重定义,包括内置函数名
  • 控制结构有if, cond[else],都是作为内置函数实现的,可以赋给其他标识符,也可以重定义为其他值;cond控制结构的每一个条件分支都可以是多个form,执行时依次执行并返回最后一个form的值
  • 定义变量用define,定义函数用defn,也可以用define+lambda表达式定义函数

关于我的web服务器nodejsws

之前,因为闲得无聊,用NodeJS写了一个web服务器,叫nodejsws(https://github.com/zoowii/nodejsws)

这几天把这个项目稍微做了一下,不过以前是以提供少量动态内容的静态资源服务器为目的的,现在编程了一个PHP的web服务器,已经成功的在nodejs上安装并运行wordpress了。
nodejs采用nodejs编写,使用php-cgi提供动态服务,不过因为不知道如何在php-cgi运行一次后不自动退出,又不打算使用php-fpm等开源项目(想自己造轮子),没有使用fastcgi,所以还是cgi模式,效率比较低,有空打算把nginx的fastcgi模块的源码看一下。另外nodejsws有空用其他语言改写,觉得nodejs和python一样,写写原型或者一些特定领域的应用比较好,其他的还是用其他语言吧。
nodejsws还有很多的BUG,有空再解决吧。暂时告一段落。