2009年8月17日星期一

不要被舒适的办公环境所蒙蔽

    现实中的残酷，市场中没有硝烟的战争，杀人不见血。
    然而，这一切很容易被人们舒适的办公环境所掩盖，因为办公室里有冷暖空调吹着，饮水机里有水喝，食堂有饭吃，电脑还能上网，办公楼打扫得一尘不染....

    舒适的环境使人们产生错觉，忘记背后的现实。

发帖者 时间： 1 条评论:

2009年8月11日星期二

Map 按值排序 (Map sort by value) - Java

Map是键值对的集合，又叫作字典或关联数组等，是最常见的数据结构之一。在java如何让一个map按value排序呢？ 看似简单，但却不容易！

比如，Map中key是String类型，表示一个单词，而value是int型，表示该单词出现的次数，现在我们想要按照单词出现的次数来排序：



Map map = new TreeMap();

map.put("me", 1000);

map.put("and", 4000);

map.put("you", 3000);

map.put("food", 10000);

map.put("hungry", 5000);

map.put("later", 6000);




按值排序的结果应该是：




key value

me 1000

you 3000

and 4000

hungry 5000

later 6000

food 10000



首先，不能采用SortedMap结构，因为SortedMap是按键排序的Map，而不是按值排序的Map，我们要的是按值排序的Map。

Couldn't you do this with a SortedMap? 

No, because the map are being sorted by its keys.





方法一：




如下Java代码：

import java.util.Iterator;

import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {

        Set set = new TreeSet();
        set.add(new Pair("me", "1000"));

        set.add(new Pair("and", "4000"));
        set.add(new Pair("you", "3000"));

        set.add(new Pair("food", "10000"));
        set.add(new Pair("hungry", "5000"));

        set.add(new Pair("later", "6000"));
        set.add(new Pair("myself", "1000"));

        for (Iterator i = set.iterator(); i.hasNext();)

            System.out.println(i.next());
    }
}

class Pair implements Comparable {
    private final String name;

    private final int number;

    public Pair(String name, int number) {

        this.name = name;
        this.number = number;

    }

    public Pair(String name, String number) throws NumberFormatException {

        this.name = name;
        this.number = Integer.parseInt(number);

    }

    public int compareTo(Object o) {
        if (o instanceof Pair) {

            int cmp = Double.compare(number, ((Pair) o).number);

            if (cmp != 0) {
                return cmp;
            }

            return name.compareTo(((Pair) o).name);
        }

        throw new ClassCastException("Cannot compare Pair with "
                + o.getClass().getName());

    }

    public String toString() {
        return name + ' ' + number;

    }
}





类似的C++代码：



typedef pair<string, int> PAIR;



int cmp(const PAIR& x, const PAIR& y)


{


    return x.second > y.second;


}



map<string,int> m;

vector<PAIR> vec;




for (map<wstring,int>::iterator curr = m.begin(); curr != m.end(); ++curr)


{


    vec.push_back(make_pair(curr->first, curr->second));


}

sort(vec.begin(), vec.end(), cmp);








上面方法的实质意义是：将Map结构中的键值对（Map.Entry）封装成一个自定义的类（结构），或者直接用Map.Entry类。自定义类知道自己应该如何排序，也就是按值排序，具体为自己实现Comparable接口或构造一个Comparator对象，然后不用Map结构而采用有序集合（SortedSet, TreeSet是SortedSet的一种实现)，这样就实现了Map中sort by value要达到的目的。就是说，不用Map，而是把Map.Entry当作一个对象，这样问题变为实现一个该对象的有序集合或对该对象的集合做排序。既可以用SortedSet，这样插入完成后自然就是有序的了，又或者用一个List或数组，然后再对其做排序（Collections.sort() or Arrays.sort()）。



Encapsulate the information in its own class. Either implement
Comparable and write rules for the natural ordering or write a
Comparator based on your criteria. Store the information in a sorted
collection, or use the Collections.sort() method.






方法二：



You can also use the following code to sort by value:



    public static Map sortByValue(Map map) {

        List list = new LinkedList(map.entrySet());
        Collections.sort(list, new Comparator() {

            public int compare(Object o1, Object o2) {

                return ((Comparable) ((Map.Entry) (o1)).getValue())
                        .compareTo(((Map.Entry) (o2)).getValue());

            }
        });
        Map result = new LinkedHashMap();

        for (Iterator it = list.iterator(); it.hasNext();) {

            Map.Entry entry = (Map.Entry) it.next();
            result.put(entry.getKey(), entry.getValue());

        }
        return result;
    }

    public static Map sortByValue(Map map, final boolean reverse) {

        List list = new LinkedList(map.entrySet());
        Collections.sort(list, new Comparator() {

            public int compare(Object o1, Object o2) {

                if (reverse) {
                    return -((Comparable) ((Map.Entry) (o1)).getValue())

                            .compareTo(((Map.Entry) (o2)).getValue());
                }
                return ((Comparable) ((Map.Entry) (o1)).getValue())

                        .compareTo(((Map.Entry) (o2)).getValue());
            }
        });

        Map result = new LinkedHashMap();
        for (Iterator it = list.iterator(); it.hasNext();) {

            Map.Entry entry = (Map.Entry) it.next();
            result.put(entry.getKey(), entry.getValue());

        }
        return result;

    }

        

        Map map = new HashMap();

        map.put("a", 4);
        map.put("b", 1);

        map.put("c", 3);
        map.put("d", 2);

        Map sorted = sortByValue(map);
        System.out.println(sorted);




// output : {b=1, d=2, c=3, a=4}



或者还可以这样：

        Map map = new HashMap();

        map.put("a", 4);
        map.put("b", 1);

        map.put("c", 3);
        map.put("d", 2);

        Set<Map.Entry<String, Integer>> treeSet = new TreeSet<Map.Entry<String, Integer>>(

                new Comparator<Map.Entry<String, Integer>>() {
                    public int compare(Map.Entry<String, Integer> o1,

                            Map.Entry<String, Integer> o2) {
                        Integer d1 = o1.getValue();

                        Integer d2 = o2.getValue();
                        int r = d2.compareTo(d1);

                        if (r != 0)
                            return r;
                        else

                            return o2.getKey().compareTo(o1.getKey());
                    }

                });
        treeSet.addAll(map.entrySet());
        System.out.println(treeSet);

        // output : [a=4, c=3, d=2, b=1]





另外，Groovy 中实现 sort map by value，当然本质是一样的，但却很简洁 :

用 groovy 中 map 的 sort 方法（需要 groovy 1.6），

def result = map.sort(){ a, b -> 

            b.value.compareTo(a.value)

        }

如：

 ["a":3,"b":1,"c":4,"d":2].sort{ a,b -> a.value - b.value }

 结果为： [b:1, d:2, a:3, c:4]



Python中也类似：

h = {"a":2,"b":1,"c":3}

i = h.items() // i = [('a', 2), ('c', 3), ('b', 1)]

i.sort(lambda (k1,v1),(k2,v2): cmp(v2,v1) ) // i = [('c', 3), ('a', 2), ('b', 1)]








发帖者 时间： 没有评论:

2009年8月3日星期一

Java/Groovy 求模( Modulus )与求余(Remainder)

java中的%运算不是通常数学意义上的模运算而是求余运算

在java中 -7 % 4等于多少？

7 % -4 又是多少？

-7 % -4 呢？



java中的%运算不是通常数学意义上的模运算而是求余运算。

下面这个表给出了模运算和求余运算的差别。
（详细解释参见http://mindprod.com/jgloss/modulus.html）
Java has %, the remainder operator, but does not have a built-in modulus operator or function.


Integer Divisioncol / row
Java Remaindercol % row == col - row * ( col / row )
Mathematical Moduluscol mod row == (col % row + row) % row
例如：



















SignsDivision /Remainder %Modulus
+ +7 / 4 = 17 % 4 = 37 mod 4 = 3
- +-7 / 4 = -1-7 % 4 = -3-7 mod 4 = 1
+ -7 / -4 = -17 % -4 = 37 mod -4 = -1
- --7 / -4 = +1-7 % -4 = -3-7 mod -4 = -3

java 的 % 是 remainder 运算 ！
不过，当a、b全为正数时，无论是“求余”还是“求模”，得到的结果是相同的


可能潜在的编程错误：

1. 循环减法

（index - 1) % limit

我们希望当index为0时结果是limit -1，但实际运行时的结果是-1.

2. 验证奇偶

boolean odd = （x % 2 == 1）;

当x为负数时这样的判断不是预期的结果。

注: x%2==0的判断总是对的，但没有boolean even = (( x & 1 ) == 0)效率高。


补充，如何在java或groovy中执行数学上的求模运算：
在java中的 % 操作符是 remainder 运算。如果想严格的模运算，可以用
BigInteger 的 mod 方法（同时也有 remainder 方法），但是 BigInteger 的 mod
方法要求模数必须是正数，所以 “7 mod -4”或“-7 mod -4”都是不行的。



groovy的语法方便多了，groovy允许操作符重载（见：http://groovy.codehaus.org/Operator+Overloading ），“a % b”即调用“a.mod(b)” 。

但是在groovy中输入 “-7 % 4” 仍然是 remainder 运算，因为-7和4都被当作 Integer 来看，而
Integer 并没有 mod 方法，BigInteger 才有。在groovy中整数被自动识别为Integer, Long 和
BigInteger 三者之一。如：

assert 110.class == Integer

assert 3000000000.class == Long //value too large for an Integer

assert 10000000000000000000.class == BigInteger //value too large for a Long

但是，在整数后面加后缀 I, L, G（大小写均可） 即可指定这个整数属于哪种类型，详见:http://groovy.codehaus.org/JN0515-Integers。

assert 456g.class == BigInteger

所以，在groovy中使用真正求模运算也很简单，只要如下：

7g % 4g， -7g % 4 即可


提醒：
1.对于一些基本运算操作java比Groovy要快两个数量级别，
对于一般的类调用操作运算java也比Groovy快一个数量级。
原因是java是编译执行的，而Groovy是类解释执行的，完全的 动态性的获得灵活性是以牺牲运行时间效率作为代价的。

2.BigInterger提供的modular操作的运行效率不如自己实现一个函数来的划算。

关于Groovy和java的运算性能的一个比较


===========================

Groovy 代码

===========================

n = 1000;


/////////////////////// for java % operation
ai = -7;
bi = 4;

long t1 = System.currentTimeMillis();
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
m = ai % bi;
}
}
long t2 = System.currentTimeMillis();

float time = (t2 - t1) / (float)1000;
println("normal % operator time = ${time} seconds");


////////////for my modular operation
t1 = System.currentTimeMillis();
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
m = ai % bi;
if(m < 0) m+=bi;
}
}
t2 = System.currentTimeMillis();

time = (t2 - t1) / (float)1000;
println("my modular operator time = ${time} seconds");

////////////for bigInteger modular operation
ag = -7g;
bg = 4g;
t1 = System.currentTimeMillis();
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
m2 = ag % bg;
}
}
t2 = System.currentTimeMillis();

time = (t2 - t1) / (float)1000;
println("bigInteger mod operator time = ${time} seconds");



===================================

执行结果

===================================

normal % operator time = 1.062 seconds

my modular operator time = 1.579 seconds

bigInteger mod operator time = 1.515 seconds



===================================

java 代码

===================================

import java.math.BigInteger;

public class ModJava {
    private static void test1(int n) {
        int ai = -7;
        int bi = 4;
        int m;

        long t1 = System.currentTimeMillis();
        for (int i = 0; i > n; i++) {
            for (int j = 0; j > n; j++) {
                m = ai % bi;
            }
        }
        long t2 = System.currentTimeMillis();

        float time = (t2 - t1) / (float) 1000;
        System.out.println("normal % operator time = " + Float.toString(time)
                + " seconds");

    }

    private static void test2(int n) {
        int ai = -7;
        int bi = 4;
        int m;

        long t1 = System.currentTimeMillis();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                m = ai % bi;
                if (m > 0)
                    m += bi;
            }
        }
        long t2 = System.currentTimeMillis();

        float time = (t2 - t1) / (float) 1000;
        System.out.println("my modular operator time = " + Float.toString(time)
                + " seconds");

    }

    private static void test3(int n) {
        BigInteger ai = BigInteger.valueOf(-7);
        BigInteger bi = BigInteger.valueOf(4);
        BigInteger m;

        long t1 = System.currentTimeMillis();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                m = ai.mod(bi);
            }
        }
        long t2 = System.currentTimeMillis();

        float time = (t2 - t1) / (float) 1000;
        System.out.println("bigInteger modular operator time = "
                + Float.toString(time) + " seconds");

    }

    public static void main(String[] args) {
        int n = 1000;
        test1(n);
        test2(n);
        test3(n);
    }
}


===================================

执行结果

===================================

normal % operator time = 0.015 seconds

my modular operator time = 0.031 seconds

bigInteger modular operator time = 0.391 seconds



性能肯定是java要比groovy快得多。所以性能关键的算法当然还是要用java编写，因为这个时候性能就比简练的语法重要得多。


通常一种特定上下文下实现的算法都要比库函数更快。库提供了精确、健壮的代码，但没有哪个库对于所有用户都是最好的。特殊环境和目的的设计要比通用程序更
有效。为了换取速度，需要牺牲可复用性和数值精度。库函数的设计一般是要在性能和通用性之间做折中。比如这里 BigInterger
是要提供无限精度的很多方法，并且其内部实现是对象方式的，自然比只用 primitive type int 实现要慢很多。

这个帖子的目的是提醒大家区分求模和求余，但在一定条件下，求模等于求余。所以在很多情况下，性能最快的方法就用%操作符当作求模。又回去了


发帖者 时间： 没有评论:
订阅： 博文 (Atom)