Leaky Cauldron
0%

Posted on Edited on

问题

实现一个特殊的栈, 在实现栈的基本功能的基础上, 再实现返回栈中最小元素的操作

要求

  • pop 、push 、getMin 操作的时间复杂度均为 O(1)
  • 可使用现成的栈结构

题解

若使用变量来保存最小值, 在进行多次出入栈操作之后无法保证 getMin() 返回值正确.

使用 minStack 来保存最小值栈, 入栈时若小于 minStack 栈顶元素则压入新元素; 若大于则再压入一个 minStack 栈顶元素.

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
public class MinStack {
    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;

    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int newEle) {
        if (minStack.isEmpty()) {
            minStack.push(newEle);
        } else if (newEle < getMin()) {
            minStack.push(newEle);
        } else {
            minStack.push(getMin());
        }

        dataStack.push(newEle);
    }

    public int pop() {
        minStack.pop();
        return dataStack.pop();
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        if (minStack.isEmpty()) {
            throw new RuntimeException("Empty stack");
        }
        return minStack.peek();
    }
}

例题: LeetCode #155

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

  • push(x) – 将元素 x 推入栈中。

  • pop() – 删除栈顶的元素。

  • top() – 获取栈顶元素。

  • getMin() – 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.

Java

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
import java.util.Stack;

class MinStack {
    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;
    
    /** initialize your data structure here. */
    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int x) {
        if (minStack.isEmpty()) {
            minStack.push(x);
        } else if (x < getMin()) {
            minStack.push(x);
        } else {
            minStack.push(getMin());
        }

        dataStack.push(x);
    }
    
    public void pop() {
        minStack.pop();
        dataStack.pop();
    }
    
    public int top() {
        return dataStack.peek();
    }
    
    public int getMin() {
        if (minStack.isEmpty()) {
            throw new RuntimeException("Empty stack");
        }
        return minStack.peek();
    }
}

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
class MinStack:
    def __init__(self):
        self.data_stack = []
        self.min_stack = []
        
    def push(self, new_ele):
        if len(self.min_stack) == 0:
            self.min_stack.append(new_ele)
        elif new_ele < self.min_stack[-1]:
            self.min_stack.append(new_ele)
        else:
            self.min_stack.append(self.min_stack[-1])
        
        self.data_stack.append(new_ele)
        
    def pop(self):
        if len(self.data_stack) == 0:
            return None
        self.min_stack.pop()
        self.data_stack.pop()
        
    def top(self):
        return self.data_stack[-1]

    def getMin(self):
        if len(self.min_stack) == 0:
            return None
        return self.min_stack[-1]

Posted on Edited on

通过记录数组中实际元素数量 size 来判断队列状态, 仅考虑 start 和 end 与 size 的关系, 无需考虑 start 与 end 的关系.

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
public class ArrayQueue {
    private int[] arr;
    private int size;
    private int start;
    private int end;

    public ArrayQueue(int initSize) {
        arr = new int[initSize];
        size = 0;
        start = 0;
        end = 0;
    }

    public void enQueue(int newEle) {
        if (size == arr.length) {
            throw new ArrayIndexOutOfBoundsException("The queue is full");
        }
        size++;
        arr[end] = newEle;
        end = nextIndex(end);
    }

    public int deQueue() {
        if (size == 0) {
            throw new ArrayIndexOutOfBoundsException("The queue is empty");
        }
        size--;
        int tmp = arr[start];
        start = nextIndex(start);
        return tmp;
    }

    public Integer peek() {
        if (size == 0) {
            return null;
        }
        return arr[start];
    }

    public int nextIndex(int index) {
        return index == arr.length - 1 ? 0 : index + 1;
    }

    public static void main(String[] args) {
        Code_02_ArrayQueue arrayQueue = new Code_02_ArrayQueue(3);
        arrayQueue.enQueue(4);
        arrayQueue.enQueue(5);
        arrayQueue.enQueue(6);
        System.out.println(arrayQueue.deQueue());
        System.out.println(arrayQueue.deQueue());
        System.out.println(arrayQueue.deQueue());
    }
}

例题: LeetCode #622

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

以上的实现使 end 指向了队尾元素的下一个位置, 在数组存满时 Rear() 将返回队首元素, 需修改使 end 指向队尾元素

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
93
94
95
96
97
98
99
100
public class MyCircularQueue {
    private int[] arr;
    private int size;
    private int start;
    private int end;

    /**
     * Initialize your data structure here. Set the size of the queue to be k.
     */
    public MyCircularQueue(int k) {
        arr = new int[k];
        size = 0;
        start = 0;
        end = -1;
    }

    /**
     * Insert an element into the circular queue. Return true if the operation is
     * successful.
     */
    public boolean enQueue(int value) {
        if (size == arr.length) {
            return false;
        }
        size++;
        end = nextIndex(end);
        arr[end] = value;

        return true;
    }

    /**
     * Delete an element from the circular queue. Return true if the operation is
     * successful.
     */
    public boolean deQueue() {
        if (size == 0) {
            return false;
        }
        System.out.println("deQueue: " + arr[start]);
        size--;
        start = nextIndex(start);

        return true;
    }

    /**
     * Get the next index.
     */
    public int nextIndex(int index) {
        return index == arr.length - 1 ? 0 : index + 1;
    }

    /**
     * Get the front item from the queue.
     */
    public int Front() {
        if (size == 0) {
            return -1;
        }
        return arr[start];
    }

    /**
     * Get the last item from the queue.
     */
    public int Rear() {
        if (size == 0) {
            return -1;
        }
        return arr[end];
    }

    /**
     * Checks whether the circular queue is empty or not.
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Checks whether the circular queue is full or not.
     */
    public boolean isFull() {
        return size == arr.length;
    }

    public static void main(String[] args) {
        MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
        circularQueue.enQueue(1); // 返回 true
        circularQueue.enQueue(2); // 返回 true
        circularQueue.enQueue(3); // 返回 true
        circularQueue.enQueue(4); // 返回 false，队列已满
        circularQueue.Rear(); // 返回 3
        circularQueue.isFull(); // 返回 true
        circularQueue.deQueue(); // 返回 true
        circularQueue.enQueue(4); // 返回 true
        circularQueue.Rear(); // 返回 4
    }
}

Posted on Edited on

参考资料: https://www.cnblogs.com/onepixel/p/7674659.html

比较排序

00. 冒泡排序

算法描述

  1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  3. 针对所有的元素重复以上的步骤，除了最后一个；
  4. 重复步骤1~3，直到排序完成。

时间复杂度计算

算法实现

1
2
3
4
5
6
7
8
9
10
11
def bubble_sort(arr):
    length = len(arr)
    for i in range(length):
        for j in range(length - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


input_arr = [9, 10, 2, 44, 33, 5, 6, 0, 11]
bubble_sort(input_arr)
1
[0, 2, 5, 6, 9, 10, 11, 33, 44]

01. 插入排序

算法描述

插入排序都采用in-place在数组上实现。具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；
  6. 重复步骤 2~5。

算法实现

1
2
3
4
5
6
7
8
9
10
11
def insertion_sort(arr):
    for i in range(len(arr)):
        for j in range(i - 1, -1, -1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

    return arr


input_arr = [9, 10, 2, 44, 33, 5, 6, 0, 11]
insertion_sort(input_arr)
1
[0, 2, 5, 6, 9, 10, 11, 33, 44]

02. 希尔排序

算法描述

希尔排序也是一种插入排序, 它是简单插入排序经过改进之后的一个更高效的版本, 也称为缩小增量排序

简单插入排序很循规蹈矩, 不管数组分布是怎么样的, 依然一步一步的对元素进行比较, 移动, 插入, 如 [5,4,3,2,1,0] 这种倒序序列, 数组末端的 0 要回到首位置很是费劲, 比较和移动元素均需 n-1 次. 而希尔排序在数组中采用跳跃式分组的策略, 通过某个增量将数组元素划分为若干组, 然后分组进行插入排序, 随后逐步缩小增量, 继续按组进行插入排序操作, 直至增量为1. 希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序, 小的基本在前, 大的基本在后, 微调即可.

参考: https://www.cnblogs.com/chengxiao/p/6104371.html

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def shell_sort(arr):
    length = len(arr)
    gap = int(length / 2)

    while gap > 0:
        for i in range(gap, length):
            for j in range(i, -1, -gap):  # 相当于将插入排序的遍历的间隔由 1 改为 -gap, 即完成了分组
                if arr[j] < arr[j - gap] and j - gap >= 0:
                    arr[j], arr[j - gap] = arr[j - gap], arr[j]
        gap = int(gap / 2)


input_arr = [9, 10, 2, 44, 33, 5, 6, 0, 11]
shell_sort(input_arr)
print(input_arr)
1
[0, 2, 5, 6, 9, 10, 11, 33, 44]

03. 选择排序

算法描述

n 个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。具体算法描述如下：

  1. 初始状态: 无序区为 R[1..n]，有序区为空

  2. 第 i 趟排序 (i=1,2,3…n-1) 开始时, 当前有序区和无序区分别为 R[1..i-1] 和 R(i..n). 该趟排序从当前无序区中-选出关键字最小的记录 R[k], 将它与无序区的第 1 个记录 R 交换, 使 R[1..i] 和R[i+1..n] 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区

  3. n-1 趟结束，数组有序化了。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
def selection_sort(arr):
    length = len(arr)
    for i in range(length):
        min_index = i
        for j in range(i, length):
            min_index = j if arr[j] < arr[min_index] else min_index
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


input_arr = [9, 10, 2, 44, 33, 5, 6, 0, 11]
selection_sort(input_arr)
1
[0, 2, 5, 6, 9, 10, 11, 33, 44]

04. 堆排序

堆

堆需满足:

  1. 堆中某个节点的值总是不大于或不小于其父节点的值
  2. 堆总是一棵完全二叉树

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

算法描述

  1. 将初始待排序关键字序列 (R1,R2…Rn) 构建成大顶堆，此堆为初始的无序区

  2. 将堆顶元素 R[1] 与最后一个元素 R[n] 交换, 此时得到新的无序区 (R1,R2,…Rn-1) 和新的有序区 (Rn), 且满足 R[1,2…n-1] <= R[n]

  3. 由于交换后新的堆顶 R[1] 可能违反堆的性质, 因此需要对当前无序区 (R1,R2,…Rn-1) 调整为新堆, 然后再次将 R[1] 与无序区最后一个元素交换, 得到新的无序区 (R1,R2…Rn-2) 和新的有序区 (Rn-1,Rn). 不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成。

算法实现

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
def heap_sort(arr):
    heap_size = len(arr)
    for i in range(heap_size):
        heapify(arr, i)

    while heap_size > 0:
        heap_size -= 1
        arr[0], arr[heap_size] = arr[heap_size], arr[0]
        heap_adjust(arr, 0, heap_size)


# 将数组转化为堆, 若 index 处的节点大于父节点则交换, 循环直至满足堆条件
def heapify(arr, index):
    while arr[index] > arr[int((index - 1) / 2)]:
        arr[index], arr[int((index - 1) / 2)] = arr[int((index - 1) / 2)], arr[index]
        index = int((index - 1) / 2)


# 数组调整为最大堆
def heap_adjust(arr, index, heap_size):

    left = 2 * index + 1  # 当前节点的左孩子

    # 由堆的根节点开始向下调整，与其大孩子交换，逐层向下，使重新成堆
    while left < heap_size:
        # 求出左右子中较大的一个
        largest = left + 1 if left + 1 < heap_size and arr[left + 1] > arr[left] else left
        # 求孩子与父节点中较大的一个
        largest = largest if arr[largest] > arr[index] else index

        if largest == index:
            break

        arr[index], arr[largest] = arr[largest], arr[index]
        index = largest
        left = 2 * index + 1


input_arr = [9, 10, 2, 44, 33, 5, 6, 0, 11]
heap_sort(input_arr)
print(input_arr)
1
[0, 2, 5, 6, 9, 10, 11, 33, 44]

05. 归并排序

算法描述

  1. 把长度为n的输入序列分成两个长度为 n/2 的子序列；
  2. 对这两个子序列分别采用归并排序；
  3. 将两个排序好的子序列合并成一个最终的排序序列。

递归示例

1
2
3
4
5
6
7
8
9
10
11
12
# 递归查找最大值
def get_max(arr, L, R):  # L 和 R 为索引
    if (L == R):  # base case 问题划分到 base case 时停止划分
        return arr[L]
    mid = int((L + R) / 2)  # 写成 L + int((R - L) / 2) 可以防止溢出
    max_left = get_max(arr, L, mid)
    max_right = get_max(arr, mid + 1, R)
    return max(max_left, max_right)


input_arr = [9, 10, 2, 44, 33, 5, 6, 0, 11]
get_max(input_arr, 0, len(input_arr) - 1)
1
44

算法实现

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
# 递归过程
def sort_process(arr, L, R):
    if (L == R):
        return
    mid = L + int((R - L) / 2)
    sort_process(arr, L, mid)
    sort_process(arr, mid + 1, R)
    merge(arr, L, mid, R)


# 合并过程, 非递归
def merge(arr, L, mid, R):
    tmp = []
    p1 = L
    p2 = mid + 1

    while p1 <= mid and p2 <= R:  # p1 p2 均不越界时
        if arr[p1] < arr[p2]:
            tmp.append(arr[p1])
            p1 += 1
        else:
            tmp.append(arr[p2])
            p2 += 1

    while (p1 <= mid):
        tmp.append(arr[p1])
        p1 += 1

    while (p2 <= R):
        tmp.append(arr[p2])
        p2 += 1

    for i in range(len(tmp)):
        arr[L + i] = tmp[i]


input_arr = [9, 10, 2, 44, 33, 5, 6, 0, 11]
sort_process(input_arr, 0, len(input_arr) - 1)
print(input_arr)
1
[0, 2, 5, 6, 9, 10, 11, 33, 44]

小和问题

描述

在一个数组中, 每一个数左边比当前数小的数累加起来, 叫做这个数组的小和. 求数组 [1, 3, 4, 2, 5] 的小和.

  • 1左边比1小的数，没有
  • 3左边比3小的数, 1
  • 4左边比4小的数, 1, 3
  • 2左边比2小的数, 1
  • 5左边比5小的数, 1, 3, 4, 2

所以小和为 1+1+3+1+1+3+4+2=16

基于归并排序的实现
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
def sort_process(arr, L, R):
    if (arr[L] == arr[R]):
        return 0
    mid = L + int((R - L) / 2)
    return sort_process(arr, L, mid) +\
            sort_process(arr, mid + 1, R) + \
            merge(arr, L, mid, R)


def merge(arr, L, mid, R):
    tmp = []
    p1 = L
    p2 = mid + 1
    result = 0

    while p1 <= mid and p2 <= R:
        if arr[p1] < arr[p2]:
            result += (R - p2 + 1) * arr[p1] if arr[p1] < arr[p2] else 0
            tmp.append(arr[p1])

            p1 += 1
        else:
            tmp.append(arr[p2])
            p2 += 1

    while p1 <= mid:
        tmp.append(arr[p1])
        p1 += 1

    while p2 <= R:
        tmp.append(arr[p2])
        p2 += 1

    for i in range(len(tmp)):
        arr[L + i] = tmp[i]

    return result


def cal_small_sum(arr):
    if arr is None or len(arr) < 2:
        return 0
    print('小和为: %d' % sort_process(arr, 0, len(arr) - 1))


input_arr = [1, 3, 4, 2, 5]
cal_small_sum(input_arr)
1
小和为: 16

06. 快速排序

算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

  1. 从数列中挑出一个元素，称为 “基准”（pivot）
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

参考

算法实现

原始实现

单侧扫描, 将小于 p 的数字放到 p 的左边, 大于 p 的不动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def partition(arr: list, l: int, r: int):
    lp = l # 记录左指针位置, 每当有满足条件的值时就与 lp 交换位置, 并自增

    for i in range(l, r + 1):
        if arr[i] <= arr[r]:
            arr[lp], arr[i] = arr[i], arr[lp]
            lp += 1


def quick_sort(arr: list, l: int, r: int):
    for i in range(r, l - 1, -1):
        partition(arr, l, i)


input_arr = [9, 8, 7, 4, 8, 3, 5, 2, 4, 1]
quick_sort(input_arr, 0, len(input_arr) - 1)
print(input_arr)
1
[1, 2, 3, 4, 4, 5, 7, 8, 8, 9]
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def partition(arr: list, l: int, r: int):
    lp = l # 记录左指针位置, 每当有满足条件的值时就与 lp 交换位置, 并自增

    for i in range(l, r + 1):
        if arr[i] <= arr[r]:
            arr[lp], arr[i] = arr[i], arr[lp]
            lp += 1


def quick_sort(arr: list, l: int, r: int):
    if l < r:
        partition(arr, l, r)
        quick_sort(arr, l, r - 1)


input_arr = [9, 8, 7, 4, 8, 3, 5, 2, 4, 1]
quick_sort(input_arr, 0, len(input_arr) - 1)
print(input_arr)
1
[1, 2, 3, 4, 4, 5, 7, 8, 8, 9]
改进实现

两端扫描

  1. 使用两个变量 less 和 more, less 指向首元素的元素下一个元素(最左边的首元素为中轴元素), more 指向最后一个元素
  2. 从前往后找, 找到一个比中轴元素大的, 然后从后往前找, 找到一个比中轴元素小的, 然后交换这两个元素, 直到这两个变量交错 ( less > more ) (注意不是相遇 less == more，因为相遇的元素还未和中轴元素比较)
  3. 对左半数组和右半数组重复上述操作.
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
# 改进实现, 双侧移动, 取最左侧为中轴元素
def partition(arr: list, l: int, r: int) -> int:
    """
    r(在右侧找到比中轴小的元素) => l(中轴)
    l(在左侧找到比中轴大的元素) => r(在右侧找到比中轴小的元素)
                      中轴值 => l/r(此时 l == r, 即 l 和 r 均指向左右部分的交界)
    """
    p = arr[l]
    while l != r:
        while l < r and arr[r] >= p:
            r -= 1
        arr[l] = arr[r]  # 在右侧找到比中轴小的元素

        while l < r and arr[l] <= p:
            l += 1
        arr[r] = arr[l]  # 在左侧找到比中轴大的元素

    arr[l] = p  # 此时 L = R, 即把中轴值赋给左右部分的交界位置
    return l  # 返回中轴索引


def quick_sort(arr: list, l: int, r: int) -> list:
    if l < r:
        p_index = partition(arr, l, r)

        # 中轴已经排好, 递归时可去除中轴
        quick_sort(arr, l, p_index - 1)
        quick_sort(arr, p_index + 1, r)

    return arr


input_arr = [5, 3, 8, 5, 6, 7, 4, 9, 2]
quick_sort(input_arr, 0, len(input_arr) - 1)
print(input_arr)
1
[2, 3, 4, 5, 5, 6, 7, 8, 9]

随机快速排序

以上为经典快速排序, 在中轴值两侧数分布不均匀时, 时间复杂度很高, 所以一般使用随机快速排序

随机快速排序算法实现
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
import random


def partition(arr: list, l: int, r: int):
    # 随机选取一个数与中轴值上的数交换
    rand_index = random.randint(l, r)
    arr[rand_index], arr[l] = arr[l], arr[rand_index]

    p = arr[l]
    while l != r:
        while l < r and arr[r] >= p:
            r -= 1
        arr[l] = arr[r]  # 在右侧找到比中轴小的元素

        while l < r and arr[l] <= p:
            l += 1
        arr[r] = arr[l]  # 在左侧找到比中轴大的元素

    arr[l] = p  # 此时 L = R, 即把中轴值赋给左右部分的交界位置
    return l  # 返回中轴索引


def quick_sort(arr: list, l: int, r: int):
    if l < r:
        p_index = partition(arr, l, r)

        # 中轴已经排好, 递归时可去除中轴
        quick_sort(arr, l, p_index - 1)
        quick_sort(arr, p_index + 1, r)

    return arr


input_arr = [5, 3, 8, 5, 6, 7, 4, 9, 2]
quick_sort(input_arr, 0, len(input_arr) - 1)
print(input_arr)
1
[2, 3, 4, 5, 5, 6, 7, 8, 9]

衍生问题

荷兰国旗问题

现有红白蓝三种不同颜色的小球，乱序排列在一起，请重新排列这些小球，使得红白蓝三色的同颜色的球在一起。这个问题之所以叫荷兰国旗问题，是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。

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
def partition(arr, L, R):
    p = arr[L]
    while L != R:
        while L < R and arr[R] >= p:
            R -= 1
        arr[L] = arr[R]

        while L < R and arr[L] <= p:
            L += 1
        arr[R] = arr[L]

    arr[L] = p
    return L


def netherland_flag(arr, L, R):
    if L < R:
        p = partition(arr, L, R)

        netherland_flag(arr, L, p - 1)
        netherland_flag(arr, p + 1, R)


input_arr = [0, 2, 1, 0, 2, 1, 2, 2, 1, 0]
netherland_flag(input_arr, 0, len(input_arr) - 1)
print(input_arr)
1
[0, 0, 0, 1, 1, 1, 2, 2, 2, 2]
奇偶划分

给出一列数, 按奇偶划分, 左侧为奇数, 右侧为偶数, 要求不额外创建数组, 划分后奇数与奇数, 偶数与偶数之间顺序与划分前相同.

采用快排类似的算法, 需保证 partition 部分为稳定排序, 难以实现

非比较排序

01. 计数排序

算法描述

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为 i 的元素出现的次数, 存入数组 C 的第 i 项
  3. 对所有的计数累加(从 C 中的第一个元素开始, 每一项和前一项相加)
  4. 反向填充目标数组: 将每个元素i放在新数组的第 C(i) 项, 每放一个元素就将 C(i) 减去 1

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def counting_sort(arr):
    """
    原算法使用数组保存数据, 因使用下标所以有序
    本实现使用字典, 保存时无序, 输出时按序取出, 可减小一定的空间复杂度
    """
    bucket = dict()
    max_value = max(arr)
    min_value = min(arr)

    for i in arr:
        bucket[i] = bucket.get(i, 0) + 1

    index = 0

    for i in range(min_value, max_value + 1):
        if bucket.get(i) is not None:
            for j in range(bucket[i]):
                arr[index] = i  # 放回原数组, 减小空间复杂度
                index += 1


input_arr = [5, 3, 8, 5, 6, 7, 4, 9, 2]
counting_sort(input_arr)
print(input_arr)
1
[2, 3, 4, 5, 5, 6, 7, 8, 9]

02. 桶排序

算法描述

  1. 设置一个定量的数组当作空桶
  2. 遍历输入数据，并且把数据一个一个放到对应的桶里去
  3. 对每个不是空的桶进行排序
  4. 从不是空的桶里把排好序的数据拼接起来

算法实现

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
def bucket_sort(arr, bucket_size):
    max_value = max(arr)
    min_value = min(arr)

    # 桶的初始化
    buckets = []
    bucket_num = int((max_value - min_value) / bucket_size) + 1
    for i in range(bucket_num + 1):
        buckets.append([])

    for ele in arr:
        buckets[int((ele - min_value) / bucket_size)].append(ele)

    # 对桶内元素进行插入排序
    for bucket in buckets:
        for i in range(len(bucket)):
            for j in range(i - 1, -1, -1):
                if bucket[j] > bucket[j + 1]:
                    bucket[j], bucket[j + 1] = bucket[j + 1], bucket[j]

    index = 0
    # 将结果填回原数组
    for bucket in buckets:
        for i in bucket:
            arr[index] = i
            index += 1


input_arr = [5, 3, 8, 5, 6, 7, 4, 9, 2]
bucket_sort(input_arr, 5)
print(input_arr)
1
[2, 3, 4, 5, 5, 6, 7, 8, 9]

衍生问题

最大间隔问题 (leetcode 164)

给定 n 个实数 x1, x2, ..., xn, 求这 n 个实数在实轴上相邻两个数之间的最大差值, 要求设计线性的时间算法

时间线性, 故不能采用排序算法, 可采用抽屉原理, 即为桶排序, 在输入过程中找出数据的最大值 max_ 与最小值 min_, 在 (min_, max_) 区间内, 将最大值与最小值之间进行均分成 n-1 份, 每个区间的大小为 len = (max_ - min_)/(n-1) 即此时为 n-1 个桶, 将最大值最小值人为放置于第一个桶和最后一个桶中, 分别代表了各自桶的上限和下限. 根据这个判断剩余的 n-2 个元素放置的桶的位置, 因为有 n-1 个桶需要放置 n-2 个元素所以根据抽屉原理必定有一个桶是空的, 所以，最大间隙一定产生在两个不同区间之间(即两个桶之间, 就是跨区间的数才可能产生最大的间隙), 故最大的间隙一定是一个桶所放数据的最小值与另一个桶所放数据的最大值之间的差值.

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
def max_gap(arr):
    if len(arr) <= 1:
        return 0
    max_value = max(arr)
    min_value = min(arr)

    if max_value == min_value:
        return 0

    length = len(arr)

    # 创建 N + 1 个桶
    maxs = [0] * (length + 1)
    mins = [0] * (length + 1)
    has_num = [False] * (length + 1)

    for ele in arr:
        index = int((ele - min_value) * length / (max_value - min_value))
        mins[index] = ele if not has_num[index] else min(ele, mins[index])
        maxs[index] = ele if not has_num[index] else max(ele, maxs[index])
        has_num[index] = True

    max_gap = 0

    tmp_max = maxs[0]
    for i in range(1, length + 1):
        if has_num[i]:
            max_gap = max(mins[i] - tmp_max, max_gap)
            tmp_max = maxs[i]

    return max_gap


input_arr = [3, 1, 12, 111, 123, 44, 54, 66]
max_gap(input_arr)
1
45

03. 基数排序

算法描述

  1. 取得数组中的最大数，并取得位数
  2. arr 为原始数组, 从最低位开始取每个位组成 radix 数组
  3. 对 radix 进行计数排序(利用计数排序适用于小范围数的特点)

算法实现

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
# 获取指定位上的数字, 索引从 0 开始
def get_digit(x, digit):
    return x // 10 ** digit % 10


# 获取最大数的位数
def max_digit_length(arr):
    max_value = max(arr)
    length = 0

    while max_value != 0:
        length += 1
        max_value //= 10

    return length


def radix_sort(arr):
    max_length = max_digit_length(arr)

    for i in range(max_length):
        bucket_dict = dict()
        for ele in arr:
            digit = get_digit(ele, i)
            if bucket_dict.get(digit):
                bucket_dict[digit].append(ele)
            else:
                bucket_dict[digit] = [ele]

        index = 0
        for j in range(10):
            if bucket_dict.get(j):
                for ele in bucket_dict[j]:
                    arr[index] = ele
                    index += 1


input_arr = [999, 101, 22, 32, 45, 5, 14, 90, 1, 1, 2, 3, 44]
radix_sort(input_arr)
print(input_arr)
1
[1, 1, 2, 3, 5, 14, 22, 32, 44, 45, 90, 101, 999]

后记

在 Java, C++ 中使用的综合排序, 当输入数组的长度小于某值时采用的是插入排序, 当大于某长度时采用的是归并排序或快速排序.

当数组中要排序的元素是自定义类型时, 通常采用归并排序; 当元素为基本类型(如 int, double, char 等)时, 采用的是快速排序. 差别在于排序算法的稳定性, 归并排序可保证排序后的数组保留部分原有数组的顺序, 对基本类型来说相等元素的顺序并不重要, 但对自定义类型来说可能有一定的意义.

Posted on Edited on

Darknet

Darknet is an open source neural network framework written in C and CUDA. It is fast, easy to install, and supports CPU and GPU computation.

For more information see the Darknet project website.

环境部署

服务器环境信息

1
2
3
4
5
6
7
8
9
OS: Ubuntu 16.04
Kernel: x86_64 Linux 4.13.0-38-generic
CPU: Intel Xeon CPU E5-2620 v3 @ 3.2GHz
GPU: 双路 GeForce GTX 1080
RAM: 32 GB
CUDA: 8.0.61
cuDNN: 7.0.5
GCC: 4.9.4
Python: 3.5

CUDA 及 cuDNN 环境配置

1
vi ~/.bashrc

追加以下内容:

1
2
3
4
export PATH=/usr/local/cuda-8.0/bin:$PATH
# 服务器环境 cuDNN 配置可能存在问题, 故自行配置如下路径
export LD_LIBRARY_PATH=/path/to/your/cudnn-lib-files:$LD_LIBRARY_PATH
# 例: export LD_LIBRARY_PATH=/server_space/zhaoym/cuda/tmp:$LD_LIBRARY_PATH

使配置生效:

1
source ~/.bashrc

编译

克隆官方代码

1
git clone https://github.com/pjreddie/darknet

切换到 darknet 目录, 修改 Makefile

1
2
cd darknet
vi Makefile
1
2
3
4
5
6
7
8
9
10
11
GPU=1  
CUDNN=1  
OPENCV=0 # 若需检测视频等, 则修改为 1, OpenCV 配置方法略
. . . . . . .
COMMON+= -DGPU -I/usr/local/cuda/include/ # 需根据服务器 CUDA 安装路径修改  
CFLAGS+= -DGPU  
LDFLAGS+= -L/usr/local/cuda/lib64 -lcuda -lcudart -lcublas -lcurand   # 需根据 cuDNN 路径修改

例:   
COMMON+= -DGPU -I/usr/local/cuda-8.0/include/  
LDFLAGS+= -L/server_space/zhaoym/cuda/tmp -lcuda -lcudart -lcublas -lcurand
1
make    # 编译

若编译失败需执行 make clean, 修改后重新 make 即可

验证是否配置成功

下载官方预训练权重

1
wget https://pjreddie.com/media/files/yolov3.weights

修改配置文件

1
vi cfg/yolov3.cfg

进行如下修改后保存退出

1
2
3
4
5
6
7
[net]
# Testing
batch=1             # 取消注释
subdivisions=1      # 取消注释
# Training      
# batch=64          # 注释掉
# subdivisions=16   # 注释掉

检测测试

1
./darknet detect cfg/yolov3.cfg yolov3.weights data/dog.jpg

输出如下

1
2
3
4
5
6
7
8
9
10
11
12
layer     filters    size              input                output
    0 conv     32  3 x 3 / 1   416 x 416 x   3   ->   416 x 416 x  32  0.299 BFLOPs
    1 conv     64  3 x 3 / 2   416 x 416 x  32   ->   208 x 208 x  64  1.595 BFLOPs
    .......
  105 conv    255  1 x 1 / 1    52 x  52 x 256   ->    52 x  52 x 255  0.353 BFLOPs
  106 detection
truth_thresh: Using default '1.000000'
Loading weights from yolov3.weights...Done!
data/dog.jpg: Predicted in 0.029329 seconds.
dog: 99%
truck: 93%
bicycle: 99%

标注图片在项目根目录下, 名为 predictions.png

训练

下面以在西工大遥感数据集上训练模型为例演示如何训练自己的数据

数据集标注转换

下载数据集并放到 darknet 目录下, 解压并将文件夹中的空格替换

1
2
3
4
5
unrar x NWPU\ VHR-10\ dataset.rar
mv NWPU\ VHR-10\ dataset NWPU_VHR-10_dataset
cd NWPU_VHR-10_dataset
mv ground\ truth ground_truth
mv positive\ image\ set positive_image_set

转换标注, 代码见 Github

1
2
3
pip install numpy opencv-python scikit-image pillow    # 安装所需 Python 库
mkdir labels
python nwpu_vhr_label.py

输出如下

1
2
3
4
5
6
7
492     # 训练集数量


158     # 测试集数量


650     # 图片总数

输出文件有 tran.txt, val.txt 以及 labels 文件夹下的 650 个转换后的标注

darknet 默认标注文件与图片在同一目录, 故需将 labels文件夹下的 txt 复制到 positive_image_set 中

1
cp labels/*.txt positive_image_set

准备训练配置文件

1
2
3
4
5
6
cd ..
mkdir 0913_NWPU_v3
cd 0913_NWPU_v3
mkdir backup
cp ../cfg/yolov3-voc.cfg ./
cp ../NWPU_VHR-10_dataset/*.txt ./

创建 NWPU.data 文件并写入以下内容

1
2
3
4
5
classes= 10
train  = 0913_NWPU_v3/train.txt
valid  = 0913_NWPU_v3/val.txt
names  = 0913_NWPU_v3/NWPU.names
backup = 0913_NWPU_v3/backup/

classes 类别数量
train 训练集文件列表
valid 验证集文件列表
names 类别名称文件
backup 权重存放目录

创建 NWPU.names 文件并写入以下内容

1
2
3
4
5
6
7
8
9
10
aeroplane
ship
storage_tank
baseball_diamond
tennis_court
basketball_court
ground_track_field
harbor
bridge
vehicle

修改 yolov3-voc.cfg

1
2
3
4
5
6
7
8
9
10
11
12
[net]
# Testing
# batch=1           # 注释掉
# subdivisions=1    # 注释掉
#Training
batch=64            # 取消注释
subdivisions=16     # 取消注释
......
# 605, 689, 773 行的 filters
filters=45          # (4个位置 + 1个objectness + C个类别) * 3, 只改 [yolo] 层上一层中的filters
# 611, 695, 779 行的 classes
classes=10          # 类别数

训练

下载预训练文件

1
2
cd ..
wget https://pjreddie.com/media/files/darknet53.conv.74

开始训练

1
./darknet detector train 0913_NWPU_v3/voc.data 0913_NWPU_v3/yolov3-voc.cfg darknet53.conv.74 -gpus 0,1

-gpus 指定训练使用的 GPU, 这里使用了第 0 块和第 1 块显卡

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
layer     filters    size              input                output
    0 conv     32  3 x 3 / 1   416 x 416 x   3   ->   416 x 416 x  32  0.299 BFLOPs
    1 conv     64  3 x 3 / 2   416 x 416 x  32   ->   208 x 208 x  64  1.595 BFLOPs
    2 conv     32  1 x 1 / 1   208 x 208 x  64   ->   208 x 208 x  32  0.177 BFLOPs
    ......
  105 conv     45  1 x 1 / 1    52 x  52 x 256   ->    52 x  52 x  45  0.062 BFLOPs
  106 yolo
Loading weights from darknet53.conv.74...Done!
Learning Rate: 0.001, Momentum: 0.9, Decay: 0.0005
Resizing
320
Loaded: 0.000029 seconds
Region 82 Avg IOU: -nan, Class: -nan, Obj: -nan, No Obj: 0.539972, .5R: -nan, .75R: -nan,  count: 0
Region 94 Avg IOU: 0.527418, Class: 0.748367, Obj: 0.665674, No Obj: 0.590720, .5R: 1.000000, .75R: 0.000000,  count: 1
Region 106 Avg IOU: 0.204739, Class: 0.530762, Obj: 0.475587, No Obj: 0.427459, .5R: 0.142857, .75R: 0.000000,  count: 42
Region 82 Avg IOU: 0.334140, Class: 0.682158, Obj: 0.326366, No Obj: 0.540248, .5R: 0.000000, .75R: 0.000000,  count: 1
Region 94 Avg IOU: 0.279358, Class: 0.548496, Obj: 0.595618, No Obj: 0.589648, .5R: 0.333333, .75R: 0.166667,  count: 6
Region 106 Avg IOU: 0.175368, Class: 0.478585, Obj: 0.391913, No Obj: 0.430448, .5R: 0.000000, .75R: 0.000000,  count: 9
......

注:

  1. yolov3-voc.cfg 配置文件中的 batch 和 subdivisions 需根据 GPU 显存大小修改, 若显存较小, 应相应地减小 batch 增大 subdivisions

  2. 查看显存占用可用 nvidia-smi, 输出如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    Wed Mar 13 15:36:29 2019       
    +-----------------------------------------------------------------------------+
    | NVIDIA-SMI 384.111                Driver Version: 384.111                   |
    |-------------------------------+----------------------+----------------------+
    | GPU  Name        Persistence-M| Bus-Id        Disp.A | Volatile Uncorr. ECC |
    | Fan  Temp  Perf  Pwr:Usage/Cap|         Memory-Usage | GPU-Util  Compute M. |
    |===============================+======================+======================|
    |   0  GeForce GTX 1080    Off  | 00000000:02:00.0 Off |                  N/A |
    | 59%   83C    P2   104W / 180W |   2729MiB /  8112MiB |     93%      Default |
    +-------------------------------+----------------------+----------------------+
    |   1  GeForce GTX 1080    Off  | 00000000:03:00.0 Off |                  N/A |
    | 54%   81C    P2   133W / 180W |   6861MiB /  8114MiB |     18%      Default |
    +-------------------------------+----------------------+----------------------+                                                                            
    +-----------------------------------------------------------------------------+
    | Processes:                                                       GPU Memory |
    |  GPU       PID   Type   Process name                             Usage      |
    |=============================================================================|
    |    0     28529      C   python                                      2719MiB |
    |    1      2040      C   python3                                     6851MiB |
    +-----------------------------------------------------------------------------+

  3. 如果输出中全都是 -nan, count 全为 0 问题很有可能在数据集上

  4. 官方代码默认前 1000次, 每 100 次保存一次权重；1000 次之后每 10000 次保存一次权重, 可在 examples/detector.c 的 130 及 138 行自行修改, 重新编译即可生效

  5. 若训练中途停止, 将训练命令中的 darknet53.conv.74 改为已得到的最新的权重的路径即可继续训练

  6. 训练输出日志含义见此文

  7. 保存训练日志到文件追加 tee 命令, 例如

    1
    ./darknet detector train 0913_NWPU_v3/voc.data 0913_NWPU_v3/yolov3-voc.cfg darknet53.conv.74 -gpus 0,1 | tee -a 0913_train.log

评估

生成检测结果

修改 yolov3-voc.cfg

1
2
3
4
5
6
7
[net]
# Testing
batch=1             # 取消注释
subdivisions=1      # 取消注释
# Training      
# batch=64          # 注释掉
# subdivisions=16   # 注释掉

使用 valid 命令，将验证集结果批量生成

1
./darknet detector valid 0913_NWPU_v3/NWPU.data 0913_NWPU_v3/yolov3-voc.cfg 0913_NWPU_v3/backup/yolov3-voc_10500.weights

输出如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
results: Using default 'results'
layer     filters    size              input                output
    0 conv     32  3 x 3 / 1   416 x 416 x   3   ->   416 x 416 x  32  0.299 BFLOPs
    1 conv     64  3 x 3 / 2   416 x 416 x  32   ->   208 x 208 x  64  1.595 BFLOPs
    2 conv     32  1 x 1 / 1   208 x 208 x  64   ->   208 x 208 x  32  0.177 BFLOPs
    ......
  105 conv     45  1 x 1 / 1    52 x  52 x 256   ->    52 x  52 x  45  0.062 BFLOPs
  106 yolo
Loading weights from 0913_NWPU_v3/backup/yolov3-voc_10500.weights...Done!
Learning Rate: 0.001, Momentum: 0.9, Decay: 0.0005
eval: Using default 'voc'
4
8
12
......
160
Total Detection Time: 14.854030 Seconds

输出文件均保存在 results 目录下

计算 mAP

将西工大数据集转换为 VOC 格式, 代码: nwpu2voc.py

1
2
cd NWPU_VHR-10_dataset
python nwpu2voc.py  # 将 nwpu2voc.py 放到 NWPU_VHR-10_dataset 目录下

下载 reval_voc.py 和 voc_eval.py, 以下代码需在 Python2 环境下运行并预先装好 numpy, 推荐用 Miniconda 管理 Python 环境

1
2
cd ..
python reval_voc.py --voc_dir NWPU_VHR-10_dataset/VOCdevkit --year 2007 --image_set test --class ./0913_NWPU_v3/NWPU.names ./valid_results

输出如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Evaluating detections
VOC07 metric? Yes
AP for aeroplane = 0.9949
AP for ship = 0.8182
AP for storage_tank = 0.8013
AP for baseball_diamond = 0.9827
AP for tennis_court = 0.8040
AP for basketball_court = 0.8182
AP for ground_track_field = 0.9947
AP for harbor = 0.7442
AP for bridge = 0.8961
AP for vehicle = 0.8689
Mean AP = 0.8723

--------------------------------------------------------------
Results computed with the **unofficial** Python eval code.
Results should be very close to the official MATLAB eval code.
-- Thanks, The Management
--------------------------------------------------------------

更多信息参见 Darknet 评估训练好的网络的性能

其它参考资料

DarkNet-YOLOv3 训练自己的数据集 Ubuntu16.04+cuda8.0

YOLOv3批量测试图片并保存在自定义文件夹下

YOLO(v1)用自己的数据集训练模型

后记

IGARSS 代码及配置文件打包