xiaobaoqiu Blog

Think More, Code Less

Java Collection

Collections

Collection的工具类

List sort

调用数组的排序,即Arrays.sort,可以自定义Comparator

1
2
3
4
5
6
7
8
9

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
}

List binarySearch

对于随机访问的List(如ArrayList)及数据量比较小的非随机访问List(小于5000),采用基于下标的binarySearch,其他(比较大的非随机访问List),采用基于iterator的binarySearch

1
2
3
4
5
6
7

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        //BINARYSEARCH_THRESHOLD = 5000
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
}

基于下标的binarySearch,和数组的binarySearch很相似:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

private static <T>
    int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key)
    {
    int low = 0;
    int high = list.size()-1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        Comparable<? super T> midVal = list.get(mid);   //不一定是随机访问的get
        int cmp = midVal.compareTo(key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // 找到
    }
    return -(low + 1);  // 没找到
}

采用基于iterator的binarySearch:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

private static <T>
    int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
    {
    int low = 0;
    int high = list.size()-1;
    ListIterator<? extends Comparable<? super T>> i = list.listIterator();

    while (low <= high) {
        int mid = (low + high) >>> 1;
        Comparable<? super T> midVal = get(i, mid); //Iterator i开始的第mid个元素
        int cmp = midVal.compareTo(key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid;
    }
    return -(low + 1);
}

List reverse

对于随机访问的List(如ArrayList)及数据量比较小的非随机访问List(小于18),采用基于下标的翻转,其他(比较大的非随机访问List),采用基于iterator的翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static void reverse(List<?> list) {
    int size = list.size();
    //REVERSE_THRESHOLD = 18
    if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
            swap(list, i, j);
    } else {
        ListIterator fwd = list.listIterator();
        ListIterator rev = list.listIterator(size);
        for (int i=0, mid=list.size()>>1; i<mid; i++) {
        Object tmp = fwd.next();
            fwd.set(rev.previous());
            rev.set(tmp);
        }
    }
}

List shuffle

List的打乱顺序,需要一个全局的随机数发生器(Random),打乱的逻辑就是将第i个元素和[0, i)之间的随机位置元素交换.对于随机访问List或者大小很小的List(小于5),直接进行交换,对于比较大的非随机访问List,将其转换为数组再进行shuffle过程.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    //SHUFFLE_THRESHOLD = 5
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

List fill

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public static <T> void fill(List<? super T> list, T obj) {
    int size = list.size();
    //FILL_THRESHOLD = 25
    if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
        for (int i=0; i<size; i++)
            list.set(i, obj);
    } else {
        ListIterator<? super T> itr = list.listIterator();
        for (int i=0; i<size; i++) {
            itr.next();
            itr.set(obj);
        }
    }
}

List copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static <T> void copy(List<? super T> dest, List<? extends T> src) {
    int srcSize = src.size();
    if (srcSize > dest.size())
        throw new IndexOutOfBoundsException("Source does not fit in dest");
    //COPY_THRESHOLD = 10
    if (srcSize < COPY_THRESHOLD ||
        (src instanceof RandomAccess && dest instanceof RandomAccess)) {
        for (int i=0; i<srcSize; i++)
            dest.set(i, src.get(i));
    } else {
        ListIterator<? super T> di=dest.listIterator();
    ListIterator<? extends T> si=src.listIterator();
        for (int i=0; i<srcSize; i++) {
            di.next();
            di.set(si.next());
        }
    }
}

Collection min max

List rotate

旋转,可以左旋或者右旋,第二参数为正数表示右旋,负数表示左旋. 如list = [t, a, n, k, s],则Collections.rotate(list, 1)之后变为[s, t, a, n, k]. Collections.rotate(list, 1)等效于Collections.rotate(list, -4)

随机访问或者小于100的非随机访问List,采用循环设置的方法.

比较大的非随机访问List采用三次reverse的方法,在编程珠玑中专门介绍了这种方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

public static void rotate(List<?> list, int distance) {
    //ROTATE_THRESHOLD = 100
    if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
        rotate1((List)list, distance);
    else
        rotate2((List)list, distance);
}

private static <T> void rotate1(List<T> list, int distance) {
    int size = list.size();
    if (size == 0)
        return;
    distance = distance % size;
    if (distance < 0)
        distance += size;
    if (distance == 0)
        return;
    //总共肯定只有size次设置
    for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
        T displaced = list.get(cycleStart);
        int i = cycleStart;
        do {
            i += distance;
            if (i >= size)
                i -= size;
            displaced = list.set(i, displaced);
            nMoved ++;
        } while(i != cycleStart);
    }
}

private static void rotate2(List<?> list, int distance) {
    int size = list.size();
    if (size == 0)
        return;
    int mid =  -distance % size;
    if (mid < 0)
        mid += size;
    if (mid == 0)
        return;

    reverse(list.subList(0, mid));      //左侧翻转
    reverse(list.subList(mid, size));   //右侧翻转
    reverse(list);                      //全部翻转
}

List replaceAll

List indexOfSubList lastIndexOfSubList

indexOfSubList : target子序列在source序列中第一次出现的位置 lastIndexOfSubList : target子序列在source序列中最后一次出现的位置

unmodifiable系列

指元素不可变更的集合,是对原始集合的一个包装,需要支持原始集合的所有方法. unmodifiableCollection,unmodifiableSet,unmodifiableSortedSet,unmodifiableList等 实现原理都是使用内部类,不支持的操作(如List的add,remove等)直接抛出UnsupportedOperationException异常.

1
2
3
4
5
6
7
8
9
10
11

static class UnmodifiableList<E> extends UnmodifiableCollection<E>
                      implements List<E> {
    final List<? extends E> list;
    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }
    public E remove(int index) {
        throw new UnsupportedOperationException();
    }
    //其他方法
}

synchronized系列

指保证同步的集合,原理是对原始集合的一个包装,另外加上一个mutex,对原始集合每个方法的操作都会用synchronized(mutex)保证同步. synchronizedCollection,synchronizedSet,synchronizedSortedSet,synchronizedList等.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//注意SynchronizedCollection定义了mutex
tatic class SynchronizedCollection<E> implements Collection<E>, Serializable {
    final Collection<E> c;  // Backing Collection
    final Object mutex;     // Object on which to synchronize
    //...
}
static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> {
    final List<E> list;
    public E get(int index) {
        synchronized(mutex) {return list.get(index);}
    }
    public E set(int index, E element) {
        synchronized(mutex) {return list.set(index, element);}
    }
    //...
}

checked系列

获取一个集合的保证类型安全的试图,任何一个试图向集合中插入错误类型的元素会抛出ClassCastException异常 实现原理很简单,构造函数需要传入集合及一个类型(Class),每次插入操作是会额外增加一次类型检查的操作.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

static class CheckedCollection<E> implements Collection<E>, Serializable {
    final Collection<E> c;
    final Class<E> type;    //支持的类型
    //类型检查
    void typeCheck(Object o) {
        if (!type.isInstance(o))
            throw new ClassCastException("Attempt to insert " +
               o.getClass() + " element into collection with element type "
               + type);
    }
}

static class CheckedList<E> extends CheckedCollection<E> implements List<E>
{
    final List<E> list;

    public E set(int index, E element) {
        typeCheck(element); //类型检查
        return list.set(index, element);
    }

    public void add(int index, E element) {
        typeCheck(element);
        list.add(index, element);
    }
    //...
}

empty系列

EMPTY_LIST, EMPTY_MAP 对get和contain等获取元素操作重写.

singleton系列

值包含一个元素的聚合 SingletonSet, singletonList, singletonMap等

List nCopies

返回一个包含n个o的List, 用一个类CopiesList实现,特制了get等操作

1
2

public static <T> List<T> nCopies(int n, T o) {
}

Comparator reverseOrder

获取一个比较器的反向比较器,ReverseComparator实现,实现很简单,compare的顺序颠倒一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

private static class ReverseComparator<T>
    implements Comparator<Comparable<Object>>, Serializable {
    public int compare(Comparable<Object> c1, Comparable<Object> c2) {
        return c2.compareTo(c1);
    }
}
private static class ReverseComparator2<T> implements Comparator<T>,
        Serializable
{
    private Comparator<T> cmp;

    ReverseComparator2(Comparator<T> cmp) {
        assert cmp != null;
        this.cmp = cmp;
    }

    public int compare(T t1, T t2) {
        return cmp.compare(t2, t1); //比较顺序颠倒一下
    }
}

Collection frequency

集合中对象出现的次数,支持对象为null

Collection disjoint

判断两个集合是否无交集,即无相同的元素

Collection addAll

AsLIFOQueue

即返回Deque的一个后进先出(Last-in-first-out, Lifo)的视图.

1
2
3

public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
        return new SetFromMap<E>(map);
    }

Java List

ArrayList

1.数组实现:

1
2
3
4
5

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private transient Object[] elementData;
}

为什么不写成 private transient E[] elementData;??

默认大小

1
2
3

public ArrayList() {
    this(10);
}

扩容策略

在add操作中会进行扩容. 扩容策略是:新的大小是原始容量的1.5倍,如果还是不足,就参数指定的大小:

1
2
3
4
5
6
7
8
9
10
11
12

public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
        newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

Arrays

排序

包含了一些操作数组的方法,如排序搜索等; 基本类型的数据排序采用快速排序,其中对于long,int,byte等整形直接调用sort1,float和double调用sort2. 一段有趣的代码,通过这个可以知道NaN和-0.0特殊性.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

private static void sort2(double a[], int fromIndex, int toIndex) {
        final long NEG_ZERO_BITS = Double.doubleToLongBits(-0.0d);
        /*
         * 排序过程分为三个阶段,目的是为了在排序的主流乘避免出现NaN和-0.0
         */

        /*
         * 阶段1 预处理过程 : 将NaN移到数组尾部,计算-0.0的数目,并将-0.0变为0.0
         */
        int numNegZeros = 0;    //-0.0的数目
        int i = fromIndex, n = toIndex;
        while(i < n) {
            if (a[i] != a[i]) {     //a[i] != a[i]表示NaN
        double swap = a[i];
                a[i] = a[--n];
                a[n] = swap;
            } else {
                //表示-0.0
                if (a[i]==0 && Double.doubleToLongBits(a[i])==NEG_ZERO_BITS) {
                    a[i] = 0.0d;
                    numNegZeros++;
                }
                i++;
            }
        }

        // 阶段2 : 排序主流程: quicksort
    sort1(a, fromIndex, n-fromIndex);

        // 阶段3: 将原始的-0.0变回去(numNegZeros个)
        if (numNegZeros != 0) {
            int j = binarySearch0(a, fromIndex, n, 0.0d); // posn of ANY zero
            do {
                j--;
            } while (j>=0 && a[j]==0.0d);

            // j is now one less than the index of the FIRST zero
            for (int k=0; k<numNegZeros; k++)
                a[++j] = -0.0d;
        }
    }

quicksort流程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

private static void sort1(int x[], int off, int len) {
    // 小数组直接插入排序
    if (len < 7) {
        for (int i=off; i<len+off; i++)
        for (int j=i; j>off && x[j-1]>x[j]; j--)
            swap(x, j, j-1);
        return;
    }

    // 选择划分元素 v, 
    int m = off + (len >> 1);       // 中间元素
    if (len > 7) {
        int l = off;
        int n = off + len - 1;
        if (len > 40) {        // 大数组, 9取中
        int s = len/8;
        l = med3(x, l,     l+s, l+2*s);
        m = med3(x, m-s,   m,   m+s);
        n = med3(x, n-2*s, n-s, n);
        }
        m = med3(x, l, m, n); // 中等大小的划分元素 : 三取中
    }
    int v = x[m];

    // 最后结构 : v* (<v)* (>v)* v* ,即头部和尾部均为若干个v, //中间分为三部分:小于v的部分,v,大于v的部分
    int a = off, b = a, c = off + len - 1, d = c;
    while(true) {
        while (b <= c && x[b] <= v) {
        if (x[b] == v)
            swap(x, a++, b);
        b++;
        }
        while (c >= b && x[c] >= v) {
        if (x[c] == v)
            swap(x, c, d--);
        c--;
        }
        if (b > c)
        break;
        swap(x, b++, c--);
    }

    // 将划分元素换回到中间位置
    int s, n = off + len;
    s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
    s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

    // 递归完成子数组的排序
    if ((s = b-a) > 1)
        sort1(x, off, s);
    if ((s = d-c) > 1)
        sort1(x, n-s, s);
    }

对象数组的排序采用mergesort:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

private static void mergeSort(Object[] src,
                  Object[] dest,
                  int low,
                  int high,
                  int off) {
    int length = high - low;

    // 小数组插入排序
        if (length < INSERTIONSORT_THRESHOLD) { //INSERTIONSORT_THRESHOLD = 7
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
             ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

        // 递归排序左右子数组
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // 已序(左边最大元素小于等于右边最小元素)
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // merge
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

对于long,int,byte等整形:
private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                     long key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        long midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

double和float,对于==的处理,采用的是Double.doubleToLongBits值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

private static int binarySearch0(double[] a, int fromIndex, int toIndex,
                     double key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        double midVal = a[mid];

            int cmp;
            if (midVal < key) {
                cmp = -1;   // Neither val is NaN, thisVal is smaller
            } else if (midVal > key) {
                cmp = 1;    // Neither val is NaN, thisVal is larger
            } else {
                long midBits = Double.doubleToLongBits(midVal);
                long keyBits = Double.doubleToLongBits(key);
                cmp = (midBits == keyBits ?  0 : // Values are equal
                       (midBits < keyBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
                        1));                     // (0.0, -0.0) or (NaN, !NaN)
            }

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

数组判等equals

其中对double和float元素的判等用Double.doubleToLongBits(Float.floatToIntBits)

数组填充fill

数组拷贝copyOf,copyOfRange

调用System.arraycopy这个native方法

数组hashCode

数组转List方法asList

参数为可变长度数组

数组toString

LinkedList

双向循环链表 注意其中取第i个元素,并不是我们通常想的那样从头开始往下便利,而是根据i偏向于头部还是偏向于尾部来决定从头开始往后找还是从尾开始往前找:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry<E> e = header;
        if (index < (size >> 1)) {  //前半部分
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {    //后半部分
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
}

Vector

数组实现

是一种RandomAccess,数组实现:

1
2
3
4
5
6
7

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    protected Object[] elementData;
}
###默认容量

java public Vector() { this(10); }

1
2

###扩容策略
成倍增长(2倍原始容量)

java private void ensureCapacityHelper(int minCapacity) { int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object[] oldData = elementData; int newCapacity = (capacityIncrement > 0) ? (oldCapacity + capacityIncrement) : (oldCapacity * 2); if (newCapacity < minCapacity) { newCapacity = minCapacity; } elementData = Arrays.copyOf(elementData, newCapacity); } }

1
2
3
4

###同步策略
每个方法都加了synchronized关键字,导致性能不高.
#Stack
用vector实现

java public class Stack extends Vector { } ```

Ubuntu增加启动栏图标

环境:Ubuntu 13.10 接上文,我们搞定了sublime的中文输入问题,但是每次都需要命令行启动我们的sublime.现在我们给sublime加个启动栏图标,其他的应用加启动图标类似.

desktop文件

我们所有的desktop文件(就是我们通常看到图标)都放在目录下:

1

/usr/share/applications

以desktop结尾的文件.

我们新建一个sunlime.desktop,内容如下

1
2
3
4
5
6
7
8

[Desktop Entry]
Type=Application
Name=Sublime
Comment=Sublime
Icon=/usr/local/SublimeText2/Icon/128x128/sublime_text.xpm
Exec=sublime
Terminal=false
Categories=Development;IDE;

比较重要的就两个属性:Icon和Exec,其中Icon决定了图标长什么样,Exec决定了这个点这个图标代表执行什么命令.

Icon

Icon必须是xpm格式,sublime提供了png格式的图标(在/usr/local/SublimeText2/Icon下),我们只需要利用工具转换一下,我使用的是截图工具Shutter.

Exec

我们之前的解决sublime中文输入之后,是在.bashrc中自定义了一个别名

1
2

#sublime
alias sublime='LD_PRELOAD=/usr/local/bin/libsublime-imfix.so sublime_text &'

但是,事实上,我们whereis sublime的时候走的不适我们定义的这个

1
2

xiaobaoqiu@xiaobaoqiu:/usr/local/SublimeText2$ whereis sublime
sublime: /usr/local/bin/sublime

在/usr/local/bin/下建立了一个软链:

1

lrwxrwxrwx  1 root root      34  7月  1 12:37 sublime -> /usr/local/SublimeText2/sublime_text

我们只需要改一下这个就ok了,即在/usr/local/SublimeText2下见一个sh文件(注意需要可执行的属性,即chmod a+x sublime.sh):

1
2
3
4

xiaobaoqiu@xiaobaoqiu:/usr/local/SublimeText2$ cat sublime.sh 
#!/bin/sh

LD_PRELOAD=/usr/local/bin/libsublime-imfix.so sublime_text &

然后将/usr/local/bin指向这个sublime.sh既可.

1

lrwxrwxrwx  1 root root      34  7月  1 12:37 sublime -> /usr/local/SublimeText2/sublime.sh*

之后在搜索里面输入sublime就可以看到我们创建的图标,把它拖到左侧启动栏就ok了.

数据结构与算法分析第二章

<<数据结构与算法分析-C语言描述>>

1.最大子序列和

O(n3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
* 时间复杂度O(n^3)
*/
int Chapter2::maxSubSeqSum1(const int A[], int N)
{
    int maxSum = 0;
    for(int i=0; i<N; i++)
        for(int j=i; j<N; j++)
        {
            int thisSum = 0;
            for(int k=i; k<=j; k++)
                thisSum += A[k];
            if(thisSum > maxSum) maxSum = thisSum;
        }

        return maxSum;
}

O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
*   算法1的最里层循环不是必须的
*   时间复杂度:O(n^2)
*/
int Chapter2::maxSubSeqSum2(const int A[], int N)
{
        int maxSum = 0;
        for(int i=0; i<N; i++)
        {
                int thisSum = 0;
                for(int j=i; j<N; j++)
                {
                        thisSum +=A[j];
                        if(thisSum > maxSum)    maxSum = thisSum;
                }
        }

        return maxSum;
}

分治,O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**
* 分治,划分为作用两个字数组
* A[l,...,M], A[M+1,...,R]
* 则最大子序列和来自三部分:左侧的最大子序列和,右侧的最大子序列和,跨越A[M]和A[M+1]的最大子序列号
* 1,2情况递归可以完成,情况三其实就是求最测以A[M]结尾的最大和,右侧就是以A[M+1]开头的最大和
*
* 时间复杂度:T(n) = 2T(n/2) + O(n)
* 即 O(nlogn)
*/
int Chapter2::maxSubSeqSum3(const int A[], int L, int R)
{
        if(L == R) return A[L] < 0 ?0 : A[L];
        int M = (L + R) >> 1;
        int maxSumL = maxSubSeqSum3(A, L, M);
        int maxSumR = maxSubSeqSum3(A, M+1, R);
        int maxL = 0, sumL = 0;
        for(int i = M; i>=L; i--)
        {
                sumL += A[i];
                if(sumL > maxL) maxL = sumL;
        }
        int maxR = 0, sumR = 0;
        for(int i = M+1; i<=R; i++)
        {
                sumR += A[i];
                if(sumR > maxR) maxR = sumR;
        }

        return max(max(maxSumL, maxSumR), maxL+maxR);
}

O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/**
* 时间复杂度 O(n)
*/
int Chapter2::maxSubSeqSum4(const int A[], int N)
{
        int maxSum = 0, thisSum = 0;
        for(int i=0; i<N; i++)
        {
                thisSum += A[i];
                if(thisSum > maxSum) maxSum = thisSum;
                else if(thisSum < 0) thisSum = 0;
        }

        return maxSum;
}

2.gcd

1
2
3
4
5
6
7
8
9
10
11

unsigned int Chapter2::gcd(unsigned int L, unsigned int R)
{
        unsigned rem;
        while(R > 0)
        {
                rem = L % R;
                L = R;
                R = rem;
        }
        return L;
}

3.快速幂

递归

1
2
3
4
5
6
7

long Chapter2::pow1(long x, unsigned n)
{
        if(n == 0) return 1;
        if(n == 1) return x;
        if(isEven((n))) return pow(x*x, n>>1);
        else return pow(x*x, n>>1) * x;
}

非递归

1
2
3
4
5
6
7
8
9
10

long Chapter2::pow2(long x, unsigned n)
{
        long base = x, ret = 1L;
        while(n > 0)
        {
                if(isEven(n)) {base *= base; n>>=1;}
                else {ret *= base; n-=1;}
        }
        return ret;
}

4.随机置换

1
2
3
4
5
6
7
8
9
10
11
12
13

/**
* 生成前N个数的随机置换
* 如 N = 3, 生成 [2 1 3]
*/
void Chapter2::randomSeq(int* A, int N)
{
        for(int i=0; i<N; i++)
                A[i] = i+1;
        for(int i=1; i<N; i++)
        {
                swap(A[i], A[random(N)]);
        }
}

5.出现次数超过一半的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
* 寻找数组的主要元素:即一个N个元素的数组中,某一个元素出现次数 >= N/2次
* 如 [6, 8, 8, 2, 3, 4, 8, 8, 8]中8是主要元素
* 思路:比较A1和A2,相等则将A1放入一个新的数组B,不想等则放弃;同样比较A3,A4...
* 递归处理数组B
*
* 注意这里只是返回了一个候选解,如果存在,则一定是这个元素
* 不存在的情况需要再扫描一遍数组
*/
 int Chapter2::mainElement(const int* A, int N)
 {
    int Candidata, nTimes = 0, i=0;
    while(i < N)
    {
        if(nTimes==0) { Candidata = A[i]; nTimes = 1; }
        else
        {
            if(A[i] != Candidata) --nTimes;
            else ++nTimes;
        }
        ++i;
    }
    return Candidata;
}

Java Concurrency in Practice 6 : 任务执行

第六章：任务执行

1.在线程中执行任务

服务器应用:良好的吞吐量和快速的响应性.应用程序应该在负荷过载时候平缓地劣化.

2.Executor框架

将任务的提交和任务的执行体解藕.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class TaskExecutionWebService {
    /**
     * 线程池大小
     */
    private static final int POOL_SIZE = 100;

    private static final Executor executor = Executors.newFixedThreadPool(POOL_SIZE);

    public static void main(String[] args) throws IOException {
        ServerSocket serverSocket = new ServerSocket(80);
        while(true){
            final Socket socket = serverSocket.accept();
            Runnable runnable = new Runnable() {
                @Override
                public void run() {
                    handRequest(socket);
                }
            };

            executor.execute(runnable);
        }
    }

    private static void handRequest(Socket socket){
        //TODO
    }
}

线程池

优点:重用存在的线程;任务达到时候,不需要等待线程创建;

Executors提供了一些静态方法: 1. newFixedThreadPool(int nThreads):最多nThreads个线程,当某一个线程由于非预期的Exception而结束,线程池会补充一个新的线程; 2. newSingleThreadExecutor():创建一个单线程化的executor,如果这个线程异常结束,会有量外一个取代它; 3. newCachedThreadPool():创建可缓存的线程池,如果当前线程池的长度超过处理的需要时候,它可以灵活的收回空闲的线程;当需求增加时候,它可以灵活的添加新的线程,不对池的长度做任何限制; 4. newScheduledThreadPool(int corePoolSize):创建一个定长的线程池,支持定时的周期性的任务执行,类似与Timer;

Executor的生命周期

Executor是异步的执行任务,所有在任何时间里,所有之前提交的任务的状态都不可能立即可见,这些任务中,有些可能已经完成,有些可能正在运行,有些还可能还在队列中等待执行;

关闭应用程序时,程序会出现很多种情况:最平缓的关闭(任务全部完成而且没有任何新的工作)到最唐突的关闭(拔掉电源),以及介于这两个极端之前的各种可能.

为了解决执行服务的声明周期问题,ExecutorService接口扩展了Executoe,添加了一些用于生命周期管理的方法.

1
2
3
4
5
6

public interface ExecutorService extends Executor {
    void shutdown();

    List<Runnable> shutdownNow();
    ...
}

ExecutorService暗示了声明周期的3种状态:运行,关闭和终止.ExecutorService创建后的初始状态是运行状态.shutdown()方法会启动一个平缓的关闭:停止接受新的任务,同时等待已提交的任务执行完成,包括尚未开始的任务.shutdownNow()方法会启动一个强制的关闭过程:尝试取消所有运行中的任务和排在队列中尚未开始的任务.

我们可以awaitTermination()等待ExecutorService到达中止状态,也可以轮询isTerminated()判断ExecutorService是否已经终止.

延迟的并据周期性的任务

考虑用ScheduledThreadPoolExecutor代替Timer,ScheduledThreadPoolExecutor可以用Executors.newScheduledThreadPool()工厂方法创建一个ScheduledThreadPoolExecutor.

调度线程池(Scheduled Thread Pool)让我们可以提供多个线程来执行延迟的周星任务,而Timer是单线程的.

Timer的另外一个问题是如果TimerTask异常会终止timer线程.

DelayQueue管理着一个包含Delayed对象的容器,每个Delayed对象都与一个延迟时间相关联:只有在元素过期胡,DelayQueue才能让你执行take获取元素.从DelayQueue中返回的对象将依据它们所延迟的时间进行排序.

3.寻找可强化的并行性

可携带结果的任务:Callable和Future

1
2
3
4
5
6
7
8
9
10
11
12
13

public interface Future<V> {

    boolean cancel(boolean mayInterruptIfRunning);

    boolean isCancelled();

    boolean isDone();

    V get() throws InterruptedException, ExecutionException;

    V get(long timeout, TimeUnit unit)
        throws InterruptedException, ExecutionException, TimeoutException;
}

ExecutorService的所有submit方法都返回Future:

1
2
3
4
5
6
7
8
9

public interface ExecutorService extends Executor {
    ...
    <T> Future<T> submit(Callable<T> task);

    <T> Future<T> submit(Runnable task, T result);

    Future<?> submit(Runnable task);
    ...
}

CompletionService

CompletionService整合了Executor和BlockingQUeue的功能.可以将Callable任务提交给它执行,染红使用类似于队列的take和poll方法,在结果完整(Future的get正确返回)可用时获得这个结果.ExecutorCompletionService是实现CompletionService接口的一个类,它将计算任务委托给一个Executor.

1
2
3
4
5
6
7
8
9
10
11
12

public interface CompletionService<V> {

    Future<V> submit(Callable<V> task);

    Future<V> submit(Runnable task, V result);

    Future<V> take() throws InterruptedException;

    Future<V> poll();

    Future<V> poll(long timeout, TimeUnit unit) throws InterruptedException;
}

使用CompletionService完成页面渲染器(包含文本渲染,图片渲染,图片需要先下载):每需要下载一个图像,就创建一个独立的任务,在线程池中执行,将顺序的图片下载转换为并行.从CompletionService中获取结构,只要任何一个图像下载完成,就立刻展示.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

public class Render {

    private ExecutorService executorService;

    public Render(ExecutorService executorService) {
        this.executorService = executorService;
    }

    /**
     * 渲染页面,包括文本和图片
     * 
     * @param source
     */
    void renderPage(CharSequence source) {
        final List<ImageInfo> imageInfoList = scanImageInfoList(source);
        CompletionService<ImageData> completionService = new ExecutorCompletionService<ImageData>(executorService);

        /** 建立下载图片的任务,提交到CompletionService */
        for (final ImageInfo imageInfo : imageInfoList) {
            completionService.submit(new Callable<ImageData>() {
                @Override
                public ImageData call() throws Exception {
                    return imageInfo.downloadImage();
                }
            });
        }

        /** 渲染文本 */
        renderText(source);

        /** 获取图片下载结果,渲染图片 */
        try{
            for (int i = 0; i < imageInfoList.size(); i++) {
                Future<ImageData> future = completionService.take();
                renderImage(future.get());
            }
        }catch(InterruptedException ie){
            Thread.currentThread().interrupt();
        }catch(ExecutionException ee){
            //TODO
        }
    }
}

为任务设置时限

某些任务需要在一定时间内返回结构,超时则结果无意义.

Future的带限时版本的get方法满足需求,超时会抛出TimeoutException.

使用限时任务的另外一个问题是,当它们超时的时候,应该停止他们无意义的继续计算.Future.get()抛出TimeoutException异常,则可以通过Future取消任务.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**
 * 带广告的页面渲染,广告超时未获得则不显示广告
 */
Page getRenderPageWithAd() {
    long endNanos = System.currentTimeMillis() + TIME_BUDGET;
    /** 获取广告的future */
    Future<Ad> future = executorService.submit(new FetchAdTask<Ad>());

    /** 获取原始待渲染页面 */
    Page page = getRenderPage();

    /** 获取广告 */
    Ad ad;
    try {
        long  timeLeft = endNanos - System.currentTimeMillis();
        ad = future.get(timeLeft, TimeUnit.MILLISECONDS);
    } catch (InterruptedException ie) {
        ad = DEFAULT_AD;
        Thread.currentThread().interrupt();
    } catch (ExecutionException ee) {
        ad = DEFAULT_AD
    }catch (TimeoutException te){
        /** 超时,放弃广告,并取消获取广告的任务 */
        ad = DEFAULT_AD;
        future.cancel(true);
    }

    page.setAd(ad);
    return page;
}