发表于 | 分类于 |
字数统计: | 阅读时长 ≈

linkedlist

  1. 底层采用双向链表实现，插入O(1)，查找On)
  2. 实现了deque接口，可以进行队列操作，在此不做分析
  3. fail-fast机制，防止结构意外改变

基础结构

linkedlist内部采用双向链表结构存储数据，其内部定义了Node数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   private static class Node<E> {
//值
       E item;
//前向指针
       Node<E> next;
//后向指针
       Node<E> prev;

       Node(Node<E> prev, E element, Node<E> next) {
           this.item = element;
           this.next = next;
           this.prev = prev;
       }
   }

构造方法

linkedlist有两个构造方法，一种用于构造空链表，一种用传入的集合创建链表

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

/**
 * Constructs an empty list.
 */
public LinkedList() {
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

添加元素

add(E e)

把新节点加入到链表末尾，所以调用linklast

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
   public boolean add(E e) {
       linkLast(e);
       return true;
   }

   /**
    * Links e as last element.
    */
   void linkLast(E e) {
//获取原来最后一个元素
       final Node<E> l = last;
//创建新元素对应的node，并将前向指针指向原来最后一个元素
       final Node<E> newNode = new Node<>(l, e, null);
//把last指向新插入的元素
       last = newNode;
       if (l == null)
    //如果原来最后一个元素是null，说明新加入的元素是第一个元素，所以first也指向该元素
           first = newNode;
       else
    //如果原来链表中存在元素，则把倒数第二个元素的后向指针指向新元素	
           l.next = newNode;
       size++;
       modCount++;
   }

add(int index, E element)

在传入的位置上添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   public void add(int index, E element) {
//检查index是否合法
       checkPositionIndex(index);

       if (index == size)
    //如果是在最后一个位置增加元素，则调用linklast方法
           linkLast(element);
       else
    //否则调用linkBefore
           linkBefore(element, node(index));
   }


   private void checkPositionIndex(int index) {
       if (!isPositionIndex(index))
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }

   private boolean isPositionIndex(int index) {
//下标范围[0,size]
       return index >= 0 && index <= size;
   }

调用linkBefore

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
   //根据下标查找node
   Node<E> node(int index) {
       // assert isElementIndex(index);
//如果是前半部分，则从前向后查找
       if (index < (size >> 1)) {
           Node<E> x = first;
           for (int i = 0; i < index; i++)
               x = x.next;
           return x;
       } else {
//如果是后半部分则从后向前查找
           Node<E> x = last;
           for (int i = size - 1; i > index; i--)
               x = x.prev;
           return x;
       }
  }

   /**
    * Inserts element e before non-null Node succ.
    */
   void linkBefore(E e, Node<E> succ) {
       // assert succ != null;
//找到succ前向节点
       final Node<E> pred = succ.prev;
//新建节点，并连接前后节点
       final Node<E> newNode = new Node<>(pred, e, succ);
//改变succ节点的前向指针
       succ.prev = newNode;
       if (pred == null)
           first = newNode;
       else
   //改变pre的后项指针
           pred.next = newNode;
       size++;
       modCount++;
   }

删除元素

remove(Object o)

删除指定元素

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
   public boolean remove(Object o) {
       if (o == null) {
	//如果是值等于null，从first开始遍历，依次查找node的值是否为null
           for (Node<E> x = first; x != null; x = x.next) {
               if (x.item == null) {
                   unlink(x);
                   return true;
               }
           }
       } else {
	//如果不是null，从fist开始遍历，用equals判断是否相等
           for (Node<E> x = first; x != null; x = x.next) {
               if (o.equals(x.item)) {
                   unlink(x);
                   return true;
               }
           }
       }
       return false;
   }

//删除某个节点
 /**
    * Unlinks non-null node x.
    */
   E unlink(Node<E> x) {
       // assert x != null;
       final E element = x.item;
       final Node<E> next = x.next;
       final Node<E> prev = x.prev;

       if (prev == null) {
           first = next;
       } else {
           prev.next = next;
           x.prev = null;
       }

       if (next == null) {
           last = prev;
       } else {
           next.prev = prev;
           x.next = null;
       }

       x.item = null;
       size--;
       modCount++;
       return element;
   }

remove(int index)

移除指定位置元素

1
2
3
4
5
6
   public E remove(int index) {
//检查index是否合法
       checkElementIndex(index);
//删除改位置节点
       return unlink(node(index));
   }

remove()

删除头节点

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
public E remove() {
    return removeFirst();
}

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

removeFirstOccurrence(Object o)

删除第一次出现的元素

1
2
3
4
//底层借助remove实现
   public boolean removeFirstOccurrence(Object o) {
       return remove(o);
   }

removeLastOccurrence(Object o)

删除最后一次出现的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean removeLastOccurrence(Object o) {
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

查找元素

get(int index)

1
2
3
4
5
6
   public E get(int index) {
//检查下标是否合法
       checkElementIndex(index);
//根据下标查找到对应node并返回该节点的元素值
       return node(index).item;
   }

indexOf(Object o)

从前向后遍历，返回改元素第一次出现的下标位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   public int indexOf(Object o) {
       int index = 0;
//目标元素是null的情况
       if (o == null) {	
	//从头向尾遍历节点
           for (Node<E> x = first; x != null; x = x.next) {
               if (x.item == null)
                   return index;
               index++;
           }
       } else {
           for (Node<E> x = first; x != null; x = x.next) {
	//使用equals判断对象是否相等
               if (o.equals(x.item))
                   return index;
               index++;
           }
       }
       return -1;
   }

lastIndexOf(Object o)

从后向前遍历，返回该元素第一次出现的位置，如果没有匹配元素返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

迭代器

linkedlist可返回的迭代器和arraylist类似，都有Itr和ListItr，但是linkedlist能返回DescendingIterator，DescendingIterator用于反向遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
//基于ListItr实现
   private class DescendingIterator implements Iterator<E> {
       private final ListItr itr = new ListItr(size());
       public boolean hasNext() {
           return itr.hasPrevious();
       }
       public E next() {
           return itr.previous();
       }
       public void remove() {
           itr.remove();
       }
   }

clone

linkedlist实现了cloneable接口，表明linkedlist可以复制
linkedlist的clone方法调用了Object的clone，该方法为浅复制；链表复制时，add方法也只是拿到了x的指针，所以linkedlist的clone方法也是浅复制

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
   public Object clone() {
//产生新链表
       LinkedList<E> clone = superClone();
//初始化新链表
       // Put clone into "virgin" state
       clone.first = clone.last = null;
       clone.size = 0;
       clone.modCount = 0;
//复制链表
       // Initialize clone with our elements
       for (Node<E> x = first; x != null; x = x.next)
           clone.add(x.item);

       return clone;
   }

   @SuppressWarnings("unchecked")
   private LinkedList<E> superClone() {
       try {
	//浅克隆
           return (LinkedList<E>) super.clone();
       } catch (CloneNotSupportedException e) {
           throw new InternalError(e);
       }
   }

发表于 | 分类于 |
字数统计: | 阅读时长 ≈

ArrayList源码解读

增加元素

add(E e)

首先检查容量是否满足要求，不满足扩容，满足则在后面的位置上添加元素

1
2
3
4
5
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

add(int index,E e)

首先检查索引，不能小于0，大于size，确保容量满足要求，使用System.arraycopy进行复制，插入数据，最后增加size

1
2
3
4
5
6
7
8
9
public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

addAll(Collection c)

与add方法类似，首先把c转化为数组，确保容量满足要求，然后用System.arraycopy进行复制，把数据插入到尾部，增加size

1
2
3
4
5
6
7
8
public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

addAll(int index, Collection<? extends E> c)

首先检查索引，确保容量，判断是否有数据需要右移，使用System.arraycopy移动、增加谁，增加size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean addAll(int index, Collection<? extends E> c) {
       rangeCheckForAdd(index);

       Object[] a = c.toArray();
       int numNew = a.length;
       ensureCapacityInternal(size + numNew);  // Increments modCount

       int numMoved = size - index;
       if (numMoved > 0)
           System.arraycopy(elementData, index, elementData, index + numNew,
                            numMoved);

       System.arraycopy(a, 0, elementData, index, numNew);
       size += numNew;
       return numNew != 0;
   }

扩容

每次扩容1.5倍，如果容量还不够，则使用最小容量，最小容量=现在容量+插入容量

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

查找对象

indexof()

先判断是是否是null，然后从前往后依次查找，返回第一个目标元素的下标,如果没有匹配目标返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
		//用了equals，只判断值是否相等
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

lastIndexOf()

先判断是否是null，然后从后向前依次查找，返回第一个目标元素下标，如果没有匹配目标返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
public int lastIndexOf(Object o) {
       if (o == null) {
           for (int i = size-1; i >= 0; i--)
               if (elementData[i]==null)
                   return i;
       } else {
           for (int i = size-1; i >= 0; i--)
	//用equals，只判断值是否相等
               if (o.equals(elementData[i]))
                   return i;
       }
       return -1;
   }

删除

remove(int index)

删除指定位置的元素，首先检查索引不能小于0大于size，计算是否有需要左移的数据，把删除位置的元素置null，该方法会返回旧值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

remove(Object o)

删除指定对象，首先检查对象是否是null，然后从前向后查找对象，并调用fastRemove删除

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

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

fastRemove与remove类似，但是省掉了范围检查和返回旧值

1
2
3
4
5
6
7
8
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

remove(Collection<?> c)

删除集合

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
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

clear()

清空列表

1
2
3
4
5
6
7
8
9
public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

迭代器

ArrayList可以得到两种迭代器，iterator()和listIterator()。iterator()中返回的迭代器只能从前向后遍历，而listIterator()迭代器不仅能反向遍历，还能从指定位置开始遍历。
在操作迭代器时，中途调用了ArrayList的其他改变结构的方法，会抛出异常，即fast-fail机制。在初始化迭代器时，保存当前的modCount，然后在每个操作时，检查当前modCount是否与初始化时的一致，如果不一致，说明进行了改变结构的操作，那么会抛出异常。

iterator()

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

listIterator()

返回的迭代器可指定迭代下标起始值

1
2
3
4
5
6
7
8
9
public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}

public ListIterator<E> listIterator() {
    return new ListItr(0);
}

listIterator迭代器实现，既可以实现前向遍历，也可以实现后项遍历，并且除了删除方法还能够添加、更改数据

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
54
55
56
57
   private class ListItr extends Itr implements ListIterator<E> {
       ListItr(int index) {
           super();
           cursor = index;
       }

       public boolean hasPrevious() {
           return cursor != 0;
       }

       public int nextIndex() {
           return cursor;
       }

       public int previousIndex() {
           return cursor - 1;
       }

       @SuppressWarnings("unchecked")
       public E previous() {
           checkForComodification();
           int i = cursor - 1;
           if (i < 0)
               throw new NoSuchElementException();
           Object[] elementData = ArrayList.this.elementData;
           if (i >= elementData.length)
               throw new ConcurrentModificationException();
           cursor = i;
           return (E) elementData[lastRet = i];
       }

       public void set(E e) {
           if (lastRet < 0)
               throw new IllegalStateException();
           checkForComodification();

           try {
               ArrayList.this.set(lastRet, e);
           } catch (IndexOutOfBoundsException ex) {
               throw new ConcurrentModificationException();
           }
       }

       public void add(E e) {
           checkForComodification();

           try {
               int i = cursor;
               ArrayList.this.add(i, e);
               cursor = i + 1;
               lastRet = -1;
               expectedModCount = modCount;
           } catch (IndexOutOfBoundsException ex) {
               throw new ConcurrentModificationException();
           }
       }
}

需要注意remove()方法的重载

假设有这样的场景：遍历list，删除指定元素

首先想到的方式是下面的方式

1
2
3
4
5
6
7
8
9
List<Integer> list = new ArrayList<Integer>();
     for (int i = -3; i < 3; i++) {
         list.add(i);
     }
     for (int i = 0; i < 3; i++) {
     	//期望删除0，1，2
         list.remove(i);
     }
     System.out.println(list);

但是结果却如下：

1
[-2, 0, 2]

这段程序并没有按照预期移除偶数元素。出现这种情况的原因是arraylist重载了remove方法，此处程序调用了remove(int index)方法移除了对应下标元素，并没有按照预期调用remove(Object o)方法。remove重载的问题在《effective java》第41条慎用重载中也提及，并指明是由于Java添加范型和自动装箱后破坏了List接口导致。那么如何才能移除偶数元素呢？答案是转换为包装类。

1
2
3
4
5
6
7
8
List<Integer> list = new ArrayList<Integer>();
        for (int i = -3; i < 3; i++) {
            list.add(i);
        }
        for (int i = 0; i < 3; i++) {
            list.remove((Integer)i);
        }
        System.out.println(list);

对于add方法

我们通常使用Arrays.asList(T t)方法产生List，但是该方法产生的list不能使用add、remove方法

1
2
3
List<Integer> integers = Arrays.asList(1,2,3,4);
integers.add(5);
System.out.println(integers);

输出

1
2
3
4
5
Exception in thread "main" java.lang.UnsupportedOperationException
	at java.util.AbstractList.add(AbstractList.java:148)
	at java.util.AbstractList.add(AbstractList.java:108)
	at self.collection.ListTest.add(ListTest.java:67)
	at self.collection.ListTest.main(ListTest.java:36)

这是因为Arrays里实现了一个内部类，也叫做ArrayList，其形式如下

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
private static class ArrayList<E> extends AbstractList<E>
       implements RandomAccess, java.io.Serializable
   {
       private static final long serialVersionUID = -2764017481108945198L;
       private final E[] a;

       ArrayList(E[] array) {
           a = Objects.requireNonNull(array);
       }

       @Override
       public int size() {
           return a.length;
       }

       @Override
       public Object[] toArray() {
           return a.clone();
       }

       @Override
       @SuppressWarnings("unchecked")
       public <T> T[] toArray(T[] a) {
           int size = size();
           if (a.length < size)
               return Arrays.copyOf(this.a, size,
                                    (Class<? extends T[]>) a.getClass());
           System.arraycopy(this.a, 0, a, 0, size);
           if (a.length > size)
               a[size] = null;
           return a;
       }

       @Override
       public E get(int index) {
           return a[index];
       }

       @Override
       public E set(int index, E element) {
           E oldValue = a[index];
           a[index] = element;
           return oldValue;
       }

       @Override
       public int indexOf(Object o) {
           E[] a = this.a;
           if (o == null) {
               for (int i = 0; i < a.length; i++)
                   if (a[i] == null)
                       return i;
           } else {
               for (int i = 0; i < a.length; i++)
                   if (o.equals(a[i]))
                       return i;
           }
           return -1;
       }

       @Override
       public boolean contains(Object o) {
           return indexOf(o) != -1;
       }

       @Override
       public Spliterator<E> spliterator() {
           return Spliterators.spliterator(a, Spliterator.ORDERED);
       }

       @Override
       public void forEach(Consumer<? super E> action) {
           Objects.requireNonNull(action);
           for (E e : a) {
               action.accept(e);
           }
       }

       @Override
       public void replaceAll(UnaryOperator<E> operator) {
           Objects.requireNonNull(operator);
           E[] a = this.a;
           for (int i = 0; i < a.length; i++) {
               a[i] = operator.apply(a[i]);
           }
       }

       @Override
       public void sort(Comparator<? super E> c) {
           Arrays.sort(a, c);
       }
   }

该类继承了AbstractList，并实现了其中的部分方法，其中不包括add、remove方法，所以调用两者时实际上调用的是抽象类AbstractList的remove，add方法，而这两个方法在AbstractList的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void add(int index, E element) {
     throw new UnsupportedOperationException();
 }

 /**
  * {@inheritDoc}
  *
  * <p>This implementation always throws an
  * {@code UnsupportedOperationException}.
  *
  * @throws UnsupportedOperationException {@inheritDoc}
  * @throws IndexOutOfBoundsException     {@inheritDoc}
  */
 public E remove(int index) {
     throw new UnsupportedOperationException();
 }

所以会抛出UnsupportedOpreationExcetion异常，这个特性让Arrays.asList返回的结果是只读的，不能修改。

发表于 | 分类于 |
字数统计: | 阅读时长 ≈

垃圾收集器与内存分配策略

对象是否死亡

  判断对象是否已死亡有两种方法,一种是引用计数法,另一种是可达性分析.

引用计数法

  给对象添加一个引用计数器,每当有一个地方引用它时,计数器值就加1;当引用失效时,计数器值就减1.但是这种方法不能解决对象之间循环引用的问题.

可达性分析

  通过一系列的称为“GC ROOT”的对象为起始点,从这些结点开始向下搜索,搜索走过的路径称为引用链,当一个对象到GC Roots没有任何引用链相连时,则证明这个对象是不可用的.

  Java中,可作为GC Roots的对象包括:

  • 虚拟机栈(栈帧中的本地变量表)中引用的对象
  • 方法区中静态属性引用的对象
  • 方法区中常量引用的对象
  • 本地方法栈中JNI引用的对象

引用

  Java中对引用的定义很传统：如果reference类型的数据中存储的数值代表的是另外一块内存的起始地址，就称这块内存代表着一个引用。但是我们希望描述这样一类对象：当内存空间还足够时，则能保留在内存中，如果内存空间在进行垃圾收集后还是很紧张，则可以抛弃这些对象。

  引用分为以下几种：

  • 强引用：在程序代码中普遍存在的，类似”Object obj = new Object()“这类的引用，只要强引用还存在，垃圾收集器永远不会回收掉被引用的对象。

  • 软引用：描述一些有用但非必须的对象。对与软引用关联着的对象，在系统将要发生内存溢出异常之前，将会把这些对象列进回收范围之中进行二次回收。如果这次回收还没有足够的内存，才抛出内存溢出异常。

  • 弱引用：描述非必须对象，但是它的强度比软引用更弱一些，被弱引用关联的对象只能生存到下次垃圾收集发生之前。当垃圾收集器工作时，无论当前内存是否足够，都会回收掉只被弱引用关联的对象。

  • 虚引用：最弱的一种引用关系。一个对象是否有虚引用的存在，完全不会对其生存时间构成影响，也无法通过虚引用来取得一个对象示例。为一个对象设置虚引用关联的唯一目的在于这个对象被收集器回收时收到一个系统通知。

生存还是死亡

  真正宣告一个对象死亡，至少要经历两次标注过程：如果对象在进行可达性分析后没有发现GC Roots相连结的引用链，那么它将会被第一次标记并且进行一次筛选，筛选的条件是次对象是否有必要执行finalize()方法。当对象没有覆盖finalize()方法，或者finalize()方法已经被调用过，虚拟机将这两种情况视为“没有必要执行”。
  如果这个对象被判定为有必要执行finalize()方法，那么这个对象将会被放置在一个叫做F-Queue的队列中，并在稍后由一个虚拟机自动建立的、低优先级的Finalizer线程去执行。
  GC将对F-Queue中的对象进行第二次小规模标记，如果对象要在finalize方法中成功拯救自己-只要重新与引用链上的任何一个对象关联即可，譬如把自己复制给某个类变量或者对象的成员变量，那么在第二次标记时它将被移除出“即将回收集合”；如果对象这时候还没有逃脱，那基本上就真的会被回收了。

回收方法区

  永久代垃圾回收主要回收：废弃常量和无用的类。判断无用的类条件：

  • 该类的所有实例都已经被回收，也就是Java堆中不存在该类的任何实例
  • 加载该类的ClassLoader已经被回收
  • 该类对应的java.lang.Class对象没有任何地方被引用，无法在任何地方通过反射访问该类的方法。

垃圾收集算法

标记清除算法

  最基础的算法，分为两个阶段：标记和清除。首先标记出所有需要回收的对象，在标记完成后统一回收所有被标记的对象。

  不足之处：一是效率问题，标记和清除两个过程的效率不高；另一个是空间问题，标记清除后产生大量不连续的内存碎片，空间碎片太多可能会导致以后在程序中需要分配较大对象时，无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。

复制算法

  为了解决效率问题而产生，将可用内存分为大小相等的两块，每次只用其中的一块。当这一块内存用完了，就将还存活的对象复制到另外一块，然后把已使用过的内存空间清理一次。但是这种算法的代价是内存缩小为了原来的一半。

  现在的商业虚拟机都采用这种收集算法来回收新生代，将内存分为一块较大的Eden空间和两块较小的Survivor空间，每次使用Eden和其中一块Survivor。当回收时，将Eden和Survivor中还存活的对象一次性地复制到另外一块Survivor空间上，最后清理掉Eden和刚才用过的Survivor空间。

标记整理算法

  复制算法在对象存活率较高时要进行较多的复制操作，效率降低另外，如果不想浪费50%的空间，就要分配额外空间进行分配担保，以应对被使用内存中所有对象都100%存活的极端情况，。所以老年代一般不能直接选用这种算法。

  标记过程不变，然后让所有存活的对象都向一端移动，然后直接清理掉边界以外的内存。

分代收集

  把Java堆划分为新生代和老年代。新生代使用标记复制算法，老年代使用标记清理或者标记整理算法。

垃圾收集器

Serial收集器

  单线程收集器，只会开一个收集线程去完成垃圾收集工作，而且在进行垃圾收集时，必须暂停其他所有工作线程，直到收集结束。目前是虚拟机运行在Client模式下的默认新生代收集器。优点：简单高效，没有线程交互开销，可以获得最高单线程效率。

ParNew收集器

  是Serial收集器的多线程版本，除了使用多条线程进行垃圾收集外，其余与Serial完全一样。

  是Server模式下的虚拟机中首选的新生代收集器，除了Serial收集器外，目前它只能与CMS收集器配合工作。

Parallel Scavenge收集器

  Parallel Scavenge收集器是一个新生代收集器，也是使用复制算法的收集器。它的目标是达到一个可控制的吞吐量，所谓吞吐量就是CPU用于执行用户代码的时间与CPU总消耗时间的比值，即吞吐量=运行用户代码时间/（运行用户代码时间+垃圾回收时间）

Serial Old收集器

  Serial Old是Serial收集器的老年代版本，同样是单线程收集器，使用“标记-整理”算法，主要给Client模式下的虚拟机使用。

  它有两大用途：

  • 在JDK 1.5以及之前版本中与Parallel Scavenge收集器搭配使用
  • 作为CMS收集器的后备使用方案，在并发收集发生Concurrent Mode Failure时使用。

Parallel Old收集器

  Parallel Old 是Parallel Scavenge收集器的老年代版本，使用多线程和“标记-整理”算法。在注重吞吐量和CPU资源的敏感的场景，可以优先考虑Parallel Scavenge和Parallel Old收集器

CMS收集器

  CMS(Concurrent Mark Sweep)收集器是以获取最短回收停顿时间为目标的收集器。服务端一般比较重视响应速度，使用CMS收集器非常符合要求。

  CMS收集器基于“标记-清除”算法实现，整个过程分为4个步骤：

  • 初始标记：需要stop the work，仅标记一下GC Roots能直接关联的对象，速度很快；
  • 并发标记: 需要stop the work，GC Roots tracing过程;
  • 重新标记：为了修正并发标记期间因用户程序继续运作导致标记产生变动的那部分对象标记录;
  • 并发清除

  CMS优点：并发收集、低停顿。

  缺点：

  • 对CPU资源十分敏感，虽然重新标记和并发清除不需要停止用户线程，但是会占用CPU资源，导致吞吐量降低

  • 无法处理浮动垃圾，CMS并发清理阶段用户线程还在运行，伴随程序运行自然还会有新的垃圾不断产生，这部分垃圾出现在标记过程之后，CMS无法在当次收集中处理掉他们，只好留到下一次垃圾收集再清理，这一部分垃圾被称为“浮动垃圾”。

  • 采用“标记-清除”算法，会产生大量内存碎片

G1收集器

  G1(garbage first)是一款面向服务端应用的垃圾收集器

  • 并发与并行：G1可以使用多个CPU来缩短Stop The World停顿的时间，并且让Java程序不中断执行
  • 分代收集：可以独立管理整个堆
  • 空间整合：整体上看是“标记-整理”算法实现的收集器，从局部看是基于“复制”算法实现的。其运行期间不会产生空间碎片。
  • 可预测停顿：G1除了追求低停顿外，还能建立可预测的停顿时间模型，能够让使用者明确指定在一个长度为M毫秒的时间片段内，消耗在垃圾收集上的时间不得超过N毫秒。

  使用G1收集器时，Java堆的内存布局与其他收集器有很大差别。它将整个Java堆分为大小相等的独立区域Region。
emsp;emsp;G1能够预测停顿时间是因为：G1可以有计划地避免在整个Java堆中进行全区域的垃圾收集。它可以跟踪各个Region里面的垃圾堆积的价值大小（回收所获得的空间大小及回收所需时间的经验值），在后台维护一个优先列表，每次根据允许的收集时间，优先回收价值最大的region。这种使用region划分内存空间以及有优先级的区域回收方式，保证了G1收集器可以在有限的时间里获得尽可能高的效率。

内存分配与回收策略

对象优先在Eden分配

  对象在新生代Eden区中分配，当Eden区中没有足够空间进行分配时，虚拟机将发起一次Minor GC。

大对象直接进入老年代

  大对象是指需要内存连续空间的Java对象，最典型的大对象就是长字符串和数组。

长期存活的对象直接进入老年代

  虚拟机给每个对象定义了一个对象年龄计数器，如果对象在Eden出生并且经过第一次Minor GC后仍然存活，并且能被Survivor容纳的话，将被移动到Survivor空间，并且对象年龄设为1。对象在Survivor区中每经过一次Minor GC，年龄就加1岁，当年龄增加之一定程度（默认是15岁），就会被移动到老年代中。

动态对象年龄判定

  为了更好地适应不同程序的内存情况，虚拟机并不是永远地要求对象的年龄必须达到设置的年龄才进入老年代。如果在Survivor空间中相同年龄所有对象大小的总和超过Survivor空间的一半，年龄大于等于该年龄的对象就可以直接进入老年代。

空间分配担保

  在发生Minor GC之前，虚拟机会检查老年代最大可用的连续空间是否大于新生代所有对象空间的总和，如果这个条件成立，那么Minor GC可以确保是线程安全的，如果不成立则虚拟机会查看是否允许担保失败，若允许，那么会继续检查老年代最大可用的连续空间是否大于历次晋升到老年代对象的平均大小，如果大于将尝试进行一次Minor GC，如果小于就会进行一次Full GC。

发表于 | 分类于 |
字数统计: | 阅读时长 ≈

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

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

  设计良好的api不应该强迫它的客户端为了正常的控制流而使用异常

  可以使用“状态测试方法”或“可识别的返回值方法”避免异常滥用。

  • “状态测试方法”

      当类具有“状态相关”的方法，即只有在特定的不可预测的条件下才可以被调用的方法，这个类应该设置单独的“状态测试”方法，用来指示是否可以调用这个状态相关的方法。

  最典型的例子就是iterator中hasNext()方法。

  并发场景下“状态测试”方法有可能出现状态不一致的情况

  • “返回值方法”

  当“状态相关”的方法被调用时，当该对象处于不适当的状态时，返回一个可识别的值，如null。

  如果单独的“状态测试”必须重复“状态相关”方法的工作，从性能角度考虑，就应该使用可被识别的返回值

  如果其他条件一样，“状态测试”方法优于“返回值”方法，因为前者可读性更强。

第58条 对于可恢复的情况使用受检异常，对于编程错误使用运行时异常

  Java三种可抛出结构：受检异常（checked Exception)、运行时异常（runtime Exception）、错误（error）。

  • 受检异常：期望调用者能够适当地恢复
  • 运行时异常：表明编程错误

第59条 避免不必要地使用受检异常

  过分使用受检异常会让api使用起来变得不方便
  把受检异常变成未受检异常的方法：把抛异常的方法分成两个方法，一个返回boolean表示是否应该抛异常

1
2
3
4
5
6
7
//invocation with checked exception
try{
	obj.action(args)
}catch(Exception e){
// handle exceptional condition
	...
}

改为

1
2
3
4
5
6
7
//invocation with state-testing method and unchecked exception
if(obj.actionPermitted(args)){
	obj.action(args)
}else{
	//Handle exceptional condition
	...
}

优先使用标准的异常

好处：

  1. 让API更加易于学习和使用
  2. 可读性会很好
  3. 异常类少，意味着内存印迹（footprint）越小，装载这些类的时间开销越少

常用异常

异常 使用场合
IllegalArgumentException 非null的参数值不正确
IllegalStateException 对于方法调用而言，对象状态不合适
NullPointerException 在禁止使用null的情况下参数值为null
IndexOutOfBoundsException 下标参数值越界
ConcurrentModificationException 在禁止并发修改的情况下，检测到对象的并发修改
UnsupportedOperationException 对象不支持用户请求的方法

第61条 抛出与抽象相对应的异常

  底层异常经过传播，当高层方法捕捉异常后会出现异常与任务没有明显联系的情况，解决方案：

  1. 异常转译
       catch底层异常后new一个新的对应的高层异常
  2. 使用异常链
      使用新异常接收cause的构造器构建新异常

第62条 每个方法抛出的异常都要有文档

  如果一个方法抛出多个异常类，不要抛出异常类的超类，如“throws Exception”

文档自觉吧。。。

第63条 在细节消息中包含能捕获失败的信息

  异常的细节信息应该包含“对该异常有贡献”的参数和域的值，例如IndexOutOfBoundsException异常的细节消息应包含下界、上界以及没有落在界内的下标值
  在异常构造器中引入造成失败的参数

第64条 努力使失败保持原子性

  失败的方法调用应该使对象保持在被调用之前的状态

实现方法：

  • 设计一个不可变对象，如果操作失败，可能会阻止创建新对象，永远也不会使已有对象处于不一致的状态中。
  • 在可变对象上获得失败原子性的方法：在执行操作之前进行参数有效性检查
  • 调整计算顺序，把可能失败的操作放在对象状态修改操作之前
  • 写恢复代码，不常用
  • 在临时拷贝上执行操作，在用临时拷贝对象内容代替对象内容

第65条 不要忽略异常

  不要空置catch块，若不得不空置，需要注释这样做的原因

发表于 | 分类于 |
字数统计: | 阅读时长 ≈

第45条 将局部变量的作用与最小化

  要是局部变量的作用与最小化，最有力的方法就是在第一次使用它的地方声明。

  for循环优于while循环，for循环定义的变量作用与仅限于循环内，while需要初始化变量

  对局部变量作用域最小化的循环做法：

1
2
3
for( int i = 0 , n= computeSize(); i<n; i++){
...
}

第46条 for-each循环优于传统for循环

  使用for-each循环不会有性能损失，对于数组也一样

  三种情况不适用for-each：

  1. 过滤集合元素
  2. 改变集合元素
  3. 平行迭代，如集合a,b，每次迭代顺序取得a,b第n个元素

第47条 了解使用类库

  熟悉java.lang, java.utils, java.io

如果需要精确答案，避免使用float和double

  float和double是为了在广泛的数值上提供较为精确结果的场合设计的， 不能提供完全精确的结果，尤其不适合货币计算

  如果计算小数，使用bigdecimal，但是使用繁琐、性能较差；若对性能有要求，可以改变单位使用int或者long。

第49条 基本类型优于装箱基本类型

  对装箱基本类型运用==操作符几乎总是错误的
装箱基本类型导致高开销和不必要的对象创建

第50条 如果其他类型更合适，避免使用字符串

  金科玉律，在做工作时能明显感受到字符串操作造成的性能影响

  1. 字符串不适合代替其他类型
  2. 字符串不适合代替聚集类型，如String key = className + “#” + i.next();
  3. 字符串不适合代替能力表（unforgeable key, 也被叫做能力表capability）

第51条 当心字符串链接的性能

  不要使用“+”连接字符串，使用StringBuilder

第52条 使用接口引用对象

  如果有合适的接口类型存在，那么对于参数、返回值、变量和域来说，都应该使用接口类型声明。

第53条 接口优先于反射机制

反射缺点：

  1. 无法进行编译时类型检查（checked exception），包括异常检查
  2. 实现反射功能的代码复杂（是否考虑实现内部反射模块，降低反射代码编写成本）
  3. 性能损失

第54条 谨慎的使用本地方法

尽量少使用JNI方法，弊端如下：

  1. 本地语言不安全，可能受到内存损坏错误影响
  2. 本地语言与平台相关，使程序不可跨平台执行
  3. 程序难以调试
  4. 如果功能简单，本地语言会使性能下降
  5. 程序阅读性变差

第55条 谨慎地进行优化

  不要因为性能牺牲合理的结构。

  1. 在设计过程中，应避免那些限制性能的设计决策。
  2. 要考虑API设计决策的性能后果。公有类如果可变，会造成大量保护性拷贝。

第56条 遵守普遍接受的命名惯例

  1. 包的名称应该是层次状的，用句号分割每部分。其名称以你的组织的internet域名开头，且顶级域名放在前面。
  2. 包名称的其他部分应该包括一个或多个描述该包的组成部分，通常不超过8个字符
  3. 类和接口的名称首字母大写，尽量避免使用缩写，除非是通用缩写。类名通常用一个名词或名词短语命名。
  4. 方法和域名与类和接口命名方式一样，只不过首字母要小写。方法通常用动词短语命名，对于返回boolean类型的方法，往往以is开头；类型转换通常被命名为toType；返回视图往往被命名为asType。
  5. 常量域包含一个或多个大写的单词，中间用下划线隔开，这是唯一推荐使用下划线的场景

发表于 | 分类于 |
字数统计: | 阅读时长 ≈

第38条 检查参数有效性

  对于开放方法，使用exception

  对于私有方法，可以使用assert

第39条 必要时进行保护性拷贝

  在与对外接口交互过程中，确保接收或返回的对象是不可变的。

  对于赋值时传入的对象，可以把关键信息重新赋值给新对象，防止外部对该对象进行修改时随之改变

  对于使用get访问一个对象时，为了防止拿到对象的类对其进行修改，可以把关键信息放在一个新对象里并返回（与创建试图思想一致）进行保护性拷贝会造成性能损失，对于同一个项目里，只在内部用到的类，只需确保编码时不会对其用到的参数类进行修改即可，对于与外界交互的类，需要注意该条建议

第40条 谨慎设计方法签名

  1. 方法名称符合规范
  2. 避免过长参数列表，4个为最佳。多于4个可以采取分解方法、创建辅助类（抽象公共实体代替多个字段）、使用建造者模式
  3. 参数类型优先使用接口，如传入Map，而不是HashMap。（与面向接口编程思想契合）

第41条 慎用重载

  重点：重载方法的选择时静态的，被覆盖的方法的选择是动态的。

  解释：重载方法是根据编译后的类型进行方法查找的，而被覆盖的方法是根据具体类型查找待执行方法的。

  表现：当有多个重载方法，每个方法参数类型又有公共接口的时候，只会执行传入公共接口的方法；当有多个子类重写父类方法时，会执行具体子类中的方法，而不会执行父类的方法。

  安全保守的原则：不要编写两个具有相同参数数目的重载方法，如果必须那就给出不同的名字。

重载的好例子

1
2
3
4
5
6
7
8
9
10
11
12
Set<Integer> set = new TreeSet<>();
      List<Integer> list = new ArrayList<>();
      for (int i = -3; i < 3; i++) {
          set.add(i);
          list.add(i);
      }
      for (int i = 0; i < 3; i++) {
          set.remove(i);
          list.remove(i);
      }
      System.out.println(set);
      System.out.println(list);

输出：[-3,-2,-1]
[-2,0,2]

1
2
3
4
5
6
7
8
9
10
11
12
Set<Integer> set = new TreeSet<>();
      List<Integer> list = new ArrayList<>();
      for (int i = -3; i < 3; i++) {
          set.add(i);
          list.add(i);
      }
      for (int i = 0; i < 3; i++) {
          set.remove(i);
          list.remove((Integer)i);
      }
      System.out.println(set);
      System.out.println(list);

输出：[-3,-2,-1]
[-3,-2,-1]

java加入泛型和自动装箱后，破坏了List接口

第42条 慎用可变长参数

可变长参数是为prinf函数设计的
  可变长参数方法的每次调用都会导致进行一次数组分配和初始化，造成一定性能损耗。
  方案：确定对某个方法95%的调用，会有3个或者更少的参数，就声明5个重载方法，每个方法有0到3个普通参数，多余3个参数使用一个可变长参数

返回零长度的数组或者集合，而不是null

返回数组时：

1
2
3
4
List<Object> list = new ArrayList<>();
Object[] a = new Object[0];
Object[] tes = list.toArray(a);
//即使list有值，abstractCollection中的toArray方法也会重新产生一个数组放list中的数据

返回集合时

1
2
if(list.isEmpty())
	return Collections.emptyList();

第44条 写文档

自觉吧。。。。

发表于 | 分类于 |
字数统计: | 阅读时长 ≈

##运行时数据区域
  运行时数据区域主要包括堆、虚拟机栈、本地方法栈、程序计数器、方法区。

###程序计数器
  程序计数器可以看作是当前线程所执行的字节码的行号指示器。每条线程都有独立的程序计数器。该区域是唯一一个在Java虚拟机规范中没有规定任何OutOfMemeryError情况的区域

###Java虚拟机栈
  栈是线程私有的，生命周期与线程一样。其描述的是Java方法执行的内存模型，每个方法在执行期间会创建一个栈帧(stack frame)，用于存储局部变量表、操作数栈、动态链接、方法出口等信息。

  局部变量表存放了编译器可知的各种基本数据类型、对象引用、returnAddress类型。其内存空间在编译阶段完成分配，方法运行期间不会改变局部变量表的大小。

  这个区域规定了两种异常状况。

  • 线程请求的栈深度超过最大虚拟机所允许的深度，会抛出StackOverflowError异常

  • 虚拟机栈可以动态扩展，若扩展时无法获得足够的内存，会抛出OutOfMemoryError异常

###本地方法栈
  与虚拟机栈作用类似，区别在于虚拟机栈为执行java方法服务，本地方法栈为Native方法服务。

###Java堆
  Java堆(Heap)是Java虚拟机管理内存中最大的一块，被所有线程共享。其唯一作用就是存放对象实例。

  绝大多数对象示例及数组要在堆上分配，但是随着JIT编译器的发展和逃逸分析技术逐渐成熟，栈上分配、标量替换优化技术导致一些微妙变化的发生，所有对象都分配在堆上也不那么绝对了

  堆是垃圾收集器管理的主要区域，基本都采用分代收集算法。

  Java堆可以处于物理上不连续的空间中，只要逻辑连续就可以。

###方法区
  方法区与堆一样，是线程共享的，它用于存储已经被虚拟机加载的类信息、常量、静态变量、即时编译后的代码等数据。

  垃圾收集行为在这个区域比较少见，其主要的内存回收目标是针对常量池的回收和对类型的卸载。

###运行时常量池
  是方法区的一部分，主要用于存放编译期生成的各种字面量和符号引用。

###直接内存
  不是虚拟机运行时数据区的一部分，也不是java虚拟机规范中定义的内存区域。NIO类引入了基于通道（Channel）与缓冲区（Buffer）的I/O方式，它可以使用Native函数直接分配堆外内存，然后通过一个存储在Java堆中的DirectByteBuffer对象作为这块内存的引用进行操作。这样能显著提高性能，因为避免了在Java堆和Native堆中来回复制数据。

##HotSpot虚拟机对象探秘

###对象的创建
  对象创建过程如下：

  1. 类加载检查：当虚拟机遇到new指令时，首先去检查指令的参数是否能在常量池中定位到一个类的符号引用，并检查这个符号引用代表的类是否已经被加载、解析和初始化过。如果没有，那必须执行相应的类加载过程。

  2. 分配内存：对象所需内存的大小在类加载完成后便可完全确定，为对象分配空间的任务等同于把一块确定大小的内存从Java堆中划分出来。划分空间方案：

    • 指针碰撞：堆内存连续，用过的内存放在一边，空闲的放在另一边，中间放指针作为分界点的指示器，分配内存就是把指针挪动对象大小的距离。Serial、ParNew等带Compact过程的收集器，采用指针碰撞。

    • 空闲列表：对内存不连续，无法使用指针碰撞，虚拟机必须维护一个列表记录哪些内存可用哪些不可用。CMS这种基于Mark-Sweep算法的收集器，采用空闲列表。

      除划分可用空间外，还要考虑线程安全问题。可能出现正在给A分配内存，指针还没来得及修改，对象B又同时使用了原来指针分配内存的情况。解决方案有两种：

    • 对内存空间的动作进行同步处理，虚拟机采用CAS加失败重试的方式保证更新操作的原子性

    • 把内存分配的动作按照线程划分在不同的空间之中进行，即每个线程在Java堆中预先分配一小块内存，成为本地线程分配缓冲（Thread Local Allocation Buffer，TLAB）。哪个线程要分配内存，就在哪个线程的TLAB上进行分配，只有TLAB用完并分配新的TLAB时，才需要同步。

  3. 内存初始化为零值：把分配到的内存空间都初始化为零值（不包括对象头），这步操作保证了对象的实例字段在Java代码中可以不赋初值就直接使用。

  4. 对对象进行设置：设置对象头，如对象是哪个类的实例，如何找到类的元数据信息、对象的hashcode、对象gc分代年龄等信息。
  5. 对象初始化：执行new指令后会执行init方法，把对象初始化。

  经过以上步骤，一个对象就被产生出来。

###对象内存布局
  对象在内存中的布局分为3块区域：对象头（Header）、实例数据（Instance Data）、对齐填充（Padding）。

####对象头
  包含两部分信息

  • 存储对象自身运行时数据，如HashCode、GC分代年龄、锁状态、线程持有的锁、偏向线程ID、偏向时戳。这部分数据称为“Mark Word”
  • 类型指针，即对象指向它的类元数据的指针，虚拟机通过这个指针确定类是哪个类的实例，但并不是所有虚拟机都必须在对象数据上保留类型指针。如果对象是一个数组，还需要记录数组长度。

###对象访问定位
  有两种方式：

  • 句柄访问：Java堆中划分出一部分内存作为句柄池，栈里的reference存储的是对象句柄的地址，句柄中包含了实例数字与类型数据的具体地址信息。好处：reference中存储稳定的句柄地址，对象被移动时只改变句柄中的实例数据指针，而reference中的地址不需要改变。
  • 直接指针：reference直接存放指针。好处：速度快，节省了一次指针定位的开销。

发表于 | 分类于 |
字数统计: | 阅读时长 ≈

  上一篇博客介绍了knn算法，以及简单的python实现代码，其中使用了线形扫描(linear scan)方式逐一计算输入实例与训练数据间的距离，复杂度较大，本篇博客将介绍knn算法的另一种高效实现方式–kd树。

简介

  kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树每个节点对应一个k维超矩形区域。在进行k近邻查找时，遍历kd树，实现减少计算量的目的。

原理

构建kd树

定义节点

  • 算法描述

  首先需要定义二叉树节点Node，其中需要包括的信息有

域名 数据类型 描述
point 数据矢量 数据集中的一个数据点，是一个k维矢量
split 正整数 分割维度
left kd树 左子树
right kd树 右子树
label 字母或数字 标签值
  • python实现
1
2
3
4
5
6
7
8
9
10
11
12
13
#encoding:utf8
class Node(object):
	def __init__(self,point,left,right,split,label):
		#左子树
		self.left = left
		#右子树
		self.right = right
		#数据节点
		self.point = point
		#分割维度
		self.split = split
		#标签
		self.label = label

构建平衡kd树

算法描述

  • 输入：K维空间数据集$T=\lbrace x_1,x_2,…,x_n\rbrace$，其中$x_i = (x_i^{(1)},x_i^{(2)},…,x_i^{(k)})^T$，$i=1,2,…,N$

  • 输出：kd树

  • 过程：

  1. 构造根节点，根据点对应于包含T的k维空间的超矩形区域
  2. 选择方差最大的维度$m$为分割维度，以T中所有实例的$x^m$坐标中位数N为切分点，将根节点的超矩形区域分割为深度为1的两个左右子节点。左子节点对应坐标$x^m$小于N的子区域，右子节点对应于坐标$x^m$大于N的子区域。将切分点保存在根节点。
  3. 在左右子区域上分别重复执行步骤2，直到两个子区域没有实例存在时停止，完成kd树的构建

python实现

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
#encoding:utf8
import numpy as np
from node import Node

def constructKDTree(dataset,datalabel):
	length = len(dataset)
	if length == 0:
		return
	median = length/2
	#计算维度个数
	dimension = len(dataset[0])
	#求每个维度的方差，axis=0是按列运算的意思，axis=1是按行运算
	vars = np.var(dataset,axis=0)
	#求方差最大的维度索引，即分割维度
	index = np.argmax(vars)
	#按照方差最大的维度进行排序
	sorted_index = dataset[:,index].argsort()
	sorted_data = dataset[sorted_index]
	sorted_label = datalabel[sorted_index]
	#左子树是小于中位数的部分
	left_data = sorted_data[:median]
	left_label = datalabel[:median]
	#父节点是中位数
	median_data = sorted_data[median]
	median_label = datalabel[median]
	#右子树是大于中位数的部分
	right_data = sorted_data[median+1:]
	right_label = datalabel[median+1:]
	#递归建立kd树
	return Node(median_data,constructKDTree(left_data,left_label),constructKDTree(right_data,right_label),index,median_label)

搜索kd树

  kd树相当于给训练数据建立了索引，所以利用kd树可以快速搜索到距离输入实例最近的训练数据点。

算法描述

  • 输入：构造好的kd树，输入实例x
  • 输出：x的最近邻
  • 过程：
  1. 在kd树中搜索包含输入实例x的叶子结点：从根节点向下递归访问kd树，若输入实例当前维度的坐标小于切分点坐标，则移动到左子树；否则，则移动到右子树。直到子节点为叶子结点为止。
  2. 以叶子结点为“当前最近结点”
  3. 递归回溯，在每个节点上进行下列操作：
    • 如果该节点保存的实例点比当前最近距离目标更近，则以该实例点为“当前最近结点”
    • 检查其子节点对应的区域是否有更近的点，即检查子节点对应的区域是否与以目标点为中心、以”当前最近距离”为半径形成的超球体相交。如果相交，则在对应的区域内可能存在距目标点更近的点，则移动到该结点，递归地进行搜索。若不相交，则向上回退。
  4. 当回退到根节点，搜索结束，最后的“当前结点“即为x的最近邻。

python实现

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
def find_nearest_neighbor(target,tree):
	#记录到叶子结点节点前搜索过的节点
	path_deque = path_to_leaf_node(target,tree,deque()) 
	#回溯第一个节点
	kd_node = path_deque.pop()
	#假设第一个节点为最近邻
	nearest_point = kd_node.point
	#计算最近邻节点与输入实例间距离
	nearest_dist = distance(target,nearest_point)
	#最近邻节点的标签
	nearest_label = kd_node.label
	#回溯
	while path_deque:
		kd_node = path_deque.pop()
		#计算实例点与最近邻节点父节点的距离
		node_dist = distance(target,kd_node.point)
		#更新最近邻节点
		if node_dist < nearest_dist:
			nearest_point = kd_node.point
			nearest_dist = node_dist
			nearest_label = kd_node.label
		#获取分割维度
		s = kd_node.split
		#判断是否需要进入最近邻节点的左右子空间进行搜索
		if abs(target[s] - kd_node.point[s]) < nearest_dist:
			#进入右子树
			if target[s] <  kd_node.point[s]:
				path_deque = path_to_leaf_node(target,kd_node.right,path_deque)
			#进入左子树
			else:
				path_deque = path_to_leaf_node(target,kd_node.left,path_deque)

	return nearest_point,nearest_label,nearest_dist

  代码详见kdtree

示例

  以《统计学习方法》中的例题为例，直观地解释kd树的构建和搜索。

问题描述

给定一个二维空间的数据集$T=\lbrace(2,3)^T,(5,4)^T,(9,6)^T,(4,7)^T,(8,1)^T,(7,2)^T\rbrace$，其在二维空间中的位置如图所示，求点(2.1,3.1)和(2,4.5)的最近邻。



构建kd树

  首先，计算x、y方向上的方差，其中var(x)=5.805,var(y)=4.472，x方向上的方差更大所以先选取x方向为分割方向。
  其次，选择x方向上的中位数，即(4,7)^T，空间划分如下图




  以此类推，经过三次划分构建好kd树，如gif所示



  构建的树形结构如下图所示


搜索kd树

点(2.1,3.1)的最近邻

  首先在kd树上搜索距离点(2.1,3.1)最近的叶子结点，结果为(2，3)，距离为0.1414，搜索过程如下所示



  但是叶子结点不一定是离点(2.1,3.1)最近的结点，所以向上进行回溯。先回溯到父节点(5,4)，计算距离为3.036，不满足最近邻要求。接下来判断是否需要进入父节点的其他子节点空间，以(2.1,3.1)为圆心，0.1414为半径画圆，发现该圆与切分超平面y=4不相交，因此不进入(5,4)右子节点搜索。

  继续向上回溯到父节点(7,2)，计算距离为5.022，不满足最近邻要求。接下来判断是否需要进入父节点的其他子节点空间，以(2.1,3.1)为圆心，0.1414为半径画圆，如下图所示发现该圆与切分超平面x=7不相交，因此不进入(7,2)右子节点搜索。



  至此，搜索路径中的结点已经完全回溯完，返回最近邻节点(2，3)，距离为0.1414。

点(2,4.5)的最近邻

  同理先搜索叶子结点，过程如下所示




  叶子结点为(4,7)，距离为3.202。回溯到父节点(5,4)，计算距离为3.041，最近邻更新为该点。接下来判断是否需要进入父节点的其他子节点空间，以(2,4.5)为圆心，3.041为半径画圆，如下图所示，发现该圆与切分超平面y=4相交，因此进入(5,4)左子节点搜索。



  计算与点(2,3)距离为1.5，最近邻更新为当前节点。

  继续向上回溯到父节点(7,2)，计算距离为5.59，不满足最近邻要求。接下来判断是否需要进入父节点的其他子节点空间，以(2,4.5)为圆心，1.5为半径画圆，发现该圆与切分超平面x=7不相交，因此不进入(7,2)右子节点搜索。



  至此，搜索路径中的结点已经完全回溯完，返回最近邻节点(2，3)，距离为1.5。

参考

发表于 | 分类于 |
字数统计: | 阅读时长 ≈

  跟着Udacity课程学完了无人驾驶第一个term，本来想深入研究一下机器视觉，但是视觉方向不能很好地与工作项目契合，所以决定先巩固一下传统机器学习算法。这个系列基于《机器学习实战》和《统计学系方法》展开，既有理论推导，又有代码实例，这样督促自己形成完备的知识体系。

简介

  KNN(k-nearest neighbour)，也成为k近邻算法，是一种最简单实用的机器学习分类算法。该算法本质是通过距离函数在向量间进行相似性检索，从而确定待分类点类别。之所以称之为最简单的分类算法，是因为k近邻算法没有显式的学习过程，其关键参数的含义较其他算法容易理解。

  KNN核心思想是“相近相似”，一般认为两个物体距离越近其关系越紧密，如果两个向量距离很近那么它们两个大概率属于同一类。有很多算法核心思想都是基于这个理论，比如反距离权重差值法等。

算法模型

语言描述

  给定一个训练数据集，对于新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。

数学描述

  • 输入

  训练数据集
$$T = \lbrace (x_{1},y_{1}),(x_{2},y_{2}),…,(x_{N},y_{N}) \rbrace \tag1$$
其中，$x_{i} \in X \subseteq R^{n}$为实例的特征向量，$ y_{i} \in Y =\lbrace c_{1},c_{2},…,c_{k}\rbrace $为实例类别，$i=1,2,…,N$

  • 输出

  实例$x$所属的类$y$

  1. 根据给定的距离度量，在训练集$T$中找出与$x$最邻近的$k$个点，涵盖这$k$个点的$x$邻域计作$N_{k}(x)$
  2. 在$N_{k}(x)$中根据分类规则，一般为多数表决，来决定$x$的类别$y$：
    $$y=arg\mathop{max}\limits_{c_{j}}\sum_{x_{i} \in N_{k}(x)}I(y_{i}=c_{j}) , i=1,2,…,N, j=1,2,…,K \tag2 $$
    其中，$I$为指示函数，即当$y_{i} = c_{i}$时$I$为1，否则$I$为0。

关键参数

距离度量

  特征空间中两个实例点的距离是两个实例点相似程度的反映，k近邻模型特征空间一般采用$n$维实数向量空间$R^{n}$，使用的距离是欧式距离，除此之外还可以使用其他距离。

闵可夫斯基距离(MinKowski distance)

  闵可夫斯基距离也叫$L_{p}$距离，假设特征空间$X$是$n$维实数向量空间$R^{n}$，$x_{i},x_{j} \in X$，$x_{i} = (x^{1}_{i},x^{2}_{i},…,x^{n}_{i})^{T}$，$x_{j} = (x^{1}_{j},x^{2}_{j},…,x^{n}_{j})^{T}$，则$x_i$，$x_j$的$L_{p}$距离的定义为：
$$L_{p}(x_i,x_j)=(\sum_{l=1}^{n}|x^{(l)}_{i}-x^{(l)}_{j}|^p)^{\frac{1}{p}} \tag3$$

欧式距离

  当闵可夫斯基距离中的参数$p=2$时，称为欧式距离，即
$$L_{2}(x_i,x_j)=(\sum_{l=1}^{n}(x^{(l)}_{i}-x^{(l)}_{j})^2)^{\frac{1}{2}} \tag4$$

曼哈顿距离

  当闵可夫斯基距离中的参数$p=1$时，称为曼哈顿距离，即
$$L_{1}(x_i,x_j)=\sum_{l=1}^{n}|x^{(l)}_{i}-x^{(l)}_{j}|\tag5$$

当$p=\infty$时，是各个坐标距离的最大值，即
$$L_{\infty}(x_i,x_j)= \mathop{max}\limits_{l}|x^{(l)}_{i}-x^{(l)}_{j}|\tag6$$

  其实闵可夫斯基距离的定义与p-范数概念一致，向量的范数可以理解为向量的长度，或者是两个点之间的距离。

$k$值的选择

  k值的选择对k近邻的结果产生较大影响。

  • $k=1$

  当$k=1$时，k近邻成为最近邻，只有与输入实例最近的点才会影响预测，即最近的实例点的类别就是输入实例的类别。

  • 较小$k$值

  只有与输入实例较近的训练实例才会对结果起作用，预测结果会对临近的实例点非常敏感，如果一旦临近的实例点恰好是噪声，那么预测就会出错。这样做的好处是训练误差会减小，但是估计误差会增大，简而言之就是容易出现过拟合。

  • 较大$k$值

  相当于选择较大邻域的训练实例进行预测，这时与输入实例较远的训练实例也会对预测起作用。这么做优点是可以减少估计误差，但是训练误差会增大。

  • $k=N$

  当$k=N$时，即k与类别个数一致，那么无论输入实例是什么，都会把输入实例的类别判断为训练实例中类别最多的的类，这样是不对的。

  应用中，$k$值一般取一个比较小的值，通过交叉验证的方式选取最优的k值。

分类决策规则

  k近邻算法的分类决策规则一般采用多数表决，即由输入实例的k个临近的训练实例中的多数类决定输入实例的类别。

多数表决规则(majority voting rule)的数学描述

  如果分类的损失函数为0-1损失函数，分类函数为
$$f:{\bf{R}}^n\to\lbrace c_1,c_2,…,c_K\rbrace \tag7$$
那么误分类的概率是
$$P(Y\not=f(X)) = 1 - P(Y=f(X)) \tag8$$
对给定的实例$x \in X$，其最邻近的$k$个训练实例点构成集合$N_k(x)$，假设输入实例的类别是$c_j$，那么误分类率是：
$$\frac{1}{k}\sum_{x_i \in N_k(x)}I(y_i \not = c_j)=1-\frac{1}{k}\sum_{x_i \in N_k(x)}I(y_i = c_j) \tag9$$
要让误分类率最小，就让$\sum_{x_i \in N_k(x)}I(y_i = c_j)$最大，即$c_j$取个数最多的类别。

python代码示例

  示例为《机器学习实战》手写体的例子

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#encoding:utf8
import numpy as np
import glob
import os

#knn算法主体
def knn_classifier(x_train,y_train,x_test,k):
	#计算向量拘留
	dis = distance(x_train,x_test)
	#根据距离排序
	sort_index = dis.argsort()
	classCount = {}
	#取前k个邻近的点
	for i in range(k):
		#获取第i个点的类别
		label = y_train[sort_index[i]]
		classCount[label] = classCount.get(label,0) + 1
	#进行多数表决投票
	classCount = sorted(classCount.items(),lambda x,y:cmp(x[1],y[1]),reverse=True)
	return classCount[0][0]


#欧式距离计算函数
def distance(x_train,x_test):
	datasize = x_train.shape[0]
	#tile可以把一个向量重复叠加为一个矩阵
	diff = np.tile(x_test,(datasize,1)) - x_train
	squareDiff = diff ** 2
	squareSum = squareDiff.sum(axis = 1)
	dis = np.sqrt(squareSum)
	return dis

#把手写体32*32的像素矩阵转化为1*2014的向量
def img2Vector(filename):
	returnVector = np.zeros((1,1024))
	file = open(filename)
	for i in range(32):
		lineString = file.readline()
		for j in range(32):
			returnVector[0,32 * i + j] = int(lineString[j])
	return returnVector


def load_train_data():
	train_data_file_path = glob.glob('./digits/trainingDigits/*.txt')
	train_label = []
	filenum = len(train_data_file_path)
	train_data = np.zeros((filenum,1024))
	for i in range(filenum):
		file_path = train_data_file_path[i]
		label = os.path.basename(file_path).split('_')[0]
		train_label.append(label)
		train_data[i:] = img2Vector(file_path)
	return train_data,train_label

def hand_writing_class_test():
	train_data,train_label = load_train_data()
	test_data_file_path = glob.glob('./digits/testDigits/*.txt')
	error = 0.0
	count = 0
	for file_path in test_data_file_path:
		file = open(file_path)
		test_label = os.path.basename(file.name).split('_')[0]
		test_data = img2Vector(file_path)
		predict_label = knn_classifier(train_data,train_label,test_data,3)
		count += 1
		if predict_label!=test_label:
			print "predict_label: ",predict_label,", test_label: ",test_label
			error += 1
	print 'error rate: ',error/count

def main():
	hand_writing_class_test()

if __name__=='__main__':
	main()

  输出为分类错误的示例类别及最终的分类错误率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
predict_label:  1 , test_label:  8
predict_label:  3 , test_label:  8
predict_label:  7 , test_label:  9
predict_label:  9 , test_label:  3
predict_label:  1 , test_label:  8
predict_label:  1 , test_label:  9
predict_label:  1 , test_label:  8
predict_label:  9 , test_label:  3
predict_label:  7 , test_label:  1
predict_label:  6 , test_label:  5
predict_label:  3 , test_label:  5
predict_label:  6 , test_label:  8
error rate:  0.0126849894292
[Finished in 23.7s]

代码示例详见KNN代码示例

总结

  简单介绍了knn算法的基本思想和关键参数，并根据书中的例子进行了实践，过程并不复杂。但是，这个代码示例用穷举法一一计算输入实例与训练数据之间的距离，复杂度较高，缺点比较明显。针对这个问题，下篇文章将介绍kd树方法。

参考

  • 统计学习方法，李航，清华大学出版社

  • 机器学习实战，Peter Harrington，人民邮电出版社

发表于 | 分类于 |
字数统计: | 阅读时长 ≈

简介

  p5从车道检测升级为车辆检测，课程目的是检测行驶过程中遇到的车辆，属于目标检测范畴。这篇文章主要介绍如何使用传统计算机视觉方法进行车辆识别，比较基础。当然实现车辆识别的方案还有其他高大的方案，如yolo等，后面我会开另一篇文章介绍基于深度学习的车辆检测方案。

处理流程

  本节课程处理流程如下图所示



HOG特征提取

  梯度直方图(Histogram of Oriented Gradient)，简称HOG，它是一种特征描述符。其原理是把图像分成很多个部分，然后计算每个部分的梯度，HOG特征描述符能为特征匹配和目标检测提供非常重要的信息。

  为了判断是否是车辆，我们需要分别提取车辆的HOG和非车辆物体的HOG。这里我们使用skimage的hog方法进行图像的特征提取，经过特征提取后的效果如下



  贴上这部分代码

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
import cv2
import numpy as np
from skimage.feature import hog
import glob
import matplotlib.pyplot as plt

#读取car data
def load_car_data():
	vehicles = glob.glob('./vehicles/*/*.png')
	return vehicles
#读取non car data
def load_non_car_data():
	non_vehicles = glob.glob('./non-vehicles/*/*.png')
	return non_vehicles

#提取HOG特征
def extract_feature(img,orient,pix_per_cell,cell_per_block,vis=False,feature_vec = True):
	if vis == True:
		features,hog_image = hog(img,orientations = orient,pixels_per_cell=(pix_per_cell,pix_per_cell),
			cells_per_block = (cell_per_block,cell_per_block),transform_sqrt=False,visualise=vis,feature_vector=feature_vec)
		return features,hog_image
	else :
		features = hog(img,orientations = orient,pixels_per_cell=(pix_per_cell,pix_per_cell),
			cells_per_block = (cell_per_block,cell_per_block),transform_sqrt=False,visualise=vis,feature_vector=feature_vec)
		return feature
#显示对比
def show_hog():
	vehicles = load_car_data()
	non_vehicles = load_non_car_data()
	vehicle_img = plt.imread(vehicles[5])
	non_vehicle_img = plt.imread(non_vehicles[5])
	_,vehicle_hog_image = extract_feature(vehicle_img[:,:,2],9,8,8,vis=True,feature_vec=True)
	_,non_vehicle_hog_image = extract_feature(non_vehicle_img[:,:,2],9,8,8,vis=True,feature_vec=True)
	f,((ax1,ax2),(ax3,ax4)) = plt.subplots(2,2,figsize=(7,7))
	ax1.imshow(vehicle_img)
	ax1.set_title('car')
	ax2.imshow(vehicle_hog_image)
	ax2.set_title('car hog feature')
	ax3.imshow(non_vehicle_img)
	ax3.set_title('non car')
	ax4.imshow(non_vehicle_hog_image)
	ax4.set_title('non car hog feature')
	plt.show()

svm模型训练

  我们刚刚获取了车辆和非车辆的hog特征，接下来用这些特征去训练svm模型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def split_data():
	car_data = load_car_data()
	car_features = extract_features(car_data)
	non_car_data = load_non_car_data()
	non_car_features = extract_features(non_car_data)
	x = np.vstack((car_features,non_car_features)).astype(np.float64)
	y = np.hstack((np.ones(len(car_features)),np.zeros(len(non_car_features))))
	rand_state = np.random.randint(0,100)
	X_train,X_test,y_train,y_test = train_test_split(x,y,test_size = 0.2,random_state=rand_state)
	return X_train,X_test,y_train,y_test

def train_model(X_train,y_train):
	svc = LinearSVC()
	svc.fit(X_train,y_train)
	return svc

图像搜索

  接下来进行车辆搜索，其原理是使用滑动窗口截取图像部分区域，然后用刚刚训练好的svm模型判断是否是车辆，如果是就保存该区域坐标。

定义滑动窗口

  首先定义滑动窗口，其中有这样几个概念cell、block、window，step。cell是抽取hog特征时的最小单位，这里定义为16个像素。block由cell组成，这里定义为2*2个cell。window是滑动窗口大小，定义为64个像素。step是步长，即每次滑动的长度，定义为2个cell。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#x方向上block个数
nxblock = (ch1.shape[1]//pix_per_cell) + 1
#y方向上block个数
nyblock = (ch1.shape[0]//pix_per_cell) + 1
#定义window大小
window = 64
#每个window的cell个数，为了后续计算，剪掉1
nblocks_per_window = (window//pix_per_cell) - 1
#步长
cells_per_step = 2
#x方向上需要移动的次数
nxstep = (nxblock - nblocks_per_window)//cells_per_step
#y方向上需要移动的次数
nystep = (nyblock - nblocks_per_window)//cells_per_step

  滑动窗口滑动过程如下



分类

  抽取窗口内图像特征，并进行分类，若为车辆，保存其窗口坐标。

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
#获取特征
hog1 = get_hog_feature(ch1,orient,pix_per_cell,cell_per_block, feature_vec = False)
if hog_channel == 'ALL':
	hog2 = get_hog_feature(ch2,orient,pix_per_cell,cell_per_block, feature_vec = False)
	hog3 = get_hog_feature(ch3,orient,pix_per_cell,cell_per_block, feature_vec = False)
#滑动抽取每个窗口特征
for xb in range(nxstep):
	for yb in range(nystep):
		ypos = yb * cells_per_step
		xpos = xb * cells_per_step
		hog_feat1 = hog1[ypos:ypos+nblocks_per_window,xpos:xpos+nblocks_per_window].ravel()
		if hog_channel == 'ALL':
			hog_feat2 = hog2[ypos:ypos+nblocks_per_window,xpos:xpos+nblocks_per_window].ravel()
			hog_feat3 = hog3[ypos:ypos+nblocks_per_window,xpos:xpos+nblocks_per_window].ravel()
			hog_features = np.hstack((hog_feat1, hog_feat2, hog_feat3))
		else : hog_features = hog_feat1

		xleft = xpos * pix_per_cell
		ytop = ypos * pix_per_cell
		hog_features = hog_features.reshape(1,-1)
		test_prediction = svc.predict(hog_features)
		#若是车辆
		if test_prediction == 1 or show_all_rectangle:
			xbox_left = np.int(xleft * scale)
			ytop = np.int(ytop * scale)
			win = np.int(window * scale)
			#保存窗口坐标
			rectangles.append(((xbox_left,ytop + ystart),(xbox_left + window,ytop+win+ystart)))

  检测效果



车辆标记

  有时候同一辆车可能存在于几个窗口中，需要将其合并，这个过程与非最大抑制类似。我们这里使用heatmap的方式合并窗口，即搜索到车辆的窗口内的像素点计数加1，设置一个阈值，最后只取大于阈值范围像素点构成的窗口。



处理视频

  • 原始视频



  • 处理后视频



总结

  本节课程主要使用传统计算机视觉方法进行目标检测，其中使用到的技术与常见滑动窗口、图像金字塔和非最大抑制很相似。除了传统计算机视觉方法，还可以使用深度学习进行目标检测，后续再单独开文章进行介绍。这部分代码详见p5-vehicle-detection