Long Long Ago


笔记: 算法图解:像小说一样有趣的算法入门书 (By Aditya Bhargava)

Yarco

  • Administrator
  • Full Member
  • *****
    • Posts: 114
    • View Profile
Code Path: https://github.com/egonschiele/grokking_algorithms

(第2遍, 2nd前缀为看第二遍时的感悟)

(2nd) 本贴知识点概览:
  • 算法思想
  • 二分查找
  • 数组和链表
  • 选择排序


第1章 算法简介

(2nd, 算法思想) 参考函数 y = f(x), 算法的本质是考虑/考察/找到合理的 f. 通过人为的方式可以清晰的分解问题找到 f, 那么 f 就是一个过程(简单的步骤, 像介绍算法时我们所最初接触到的一样, steps, 或是方法/函数); 如果问题可以归结为循环+较小规模的问题, 那么可以用递推/递归, 这应该是个分治问题; 如果需要辅助数据动态支持找到解决方案, 可以称这个 f 为 动态规划; 如果没有非常显示的处理办法并且若引入 x1 会影响到全局的解法 f (即有可能是NPC问题), 那么就可能需要通过构造数据组(深度学习)来解 f, 称为人工智能. 这些都属于相对精确有效的寻找解法的思想, 相对而言贪婪法与穷举法就显得暴力.

1.2 二分查找

针对的是有次序的静态序列. 有次序意味着有大小, 意味着可基于大小做排除.
(举个例子: 分词中的查字典 https://www.npmjs.com/package/seg-zhcn 多年前js写的分词 哈哈 这都能让我找出来~)

(2nd) c语言实现(我自己~ 当练习c, 感觉这里的难度是边界不好掌握, 参考: https://stackoverflow.com/questions/39221303/binary-search-algorithm-implementations?rq=1)
(我这里写  int right = strlen(s); 然后循环用小于 while (left < right) { 发现也是对的)
Code: [Select]
#include <stdio.h>
#include <string.h>

int binary_search(char ch, const char* s);

int main()
{
const char* const data = "abcdefghijklmnopqrstuvwxyz";

printf("---- data ----\n");
for(int i = 0; i < strlen(data); i++) {
printf("%d=%c\t", i, data[i]);
}
printf("\n");
printf("---- result ----\n");
printf("i=%d\n", binary_search('i', data));
printf("o=%d\n", binary_search('o', data));
printf("x=%d\n", binary_search('x', data));

return 0;
}

int binary_search(char ch, const char* s)
{
int left = 0;
int right = strlen(s) - 1;
int middle;

while (left <= right) {
middle = (left + right) / 2; // 看来这里 middle = left + (right - left) >> 1; 更好

if (ch == s[middle]) {
return middle;
} else if (ch < s[middle]) {
right = middle;
} else {
left = middle;
}
}

return -1;
}

1.3.4 一些常见的大 O 运行时间
O(log n), O(n), O(n log n), O(n^2), O(n!)
(有序的, 线性空间...)
像是降维:  低维度 <------ 线性世界 -------> 高维度

1.3.5 旅行商
(2nd) ??? 貌似O(n!)算法与积分之间存在某种关系, 需要思考?

第2章 选择排序

2.2 数组和链表
数组: 针对相对固定的情况, +随机访问, +索引(关键字,下标关系)
链表: 删减频繁

(2nd) 链表实现: https://www.learn-c.org/en/Linked_lists

2.3 选择排序
通常教选择排序会讲打牌这件事, 这里作者的例子是音乐播放次数的排序, 但我觉得另外一件事情可能更令人印象深刻.........择偶.

Mine with Numpy:
Code: [Select]
import numpy as np

arr = np.random.randint(10, size=10)

def findSmallest(arr):
    max = arr[0]
    idx = 0
    for i in range(1, len(arr)):
        if arr[i]<max:
            max = arr[i]
            idx = i
    return idx, max

findSmallest(arr)

## O(n)

print(arr)
def selectionSort(arr):
    ret = arr.copy()
    for i in range(0, len(ret)):
        idx, max = findSmallest(ret[i:])
        ret[i], ret[idx+i] = ret[idx+i], ret[i]
    return ret

print(selectionSort(arr))

书里的:
Code: [Select]
def findSmallest(arr):
  smallest = arr[0]  ←------存储最小的值
  smallest_index = 0  ←------存储最小元素的索引
  for i in range(1, len(arr)):
    if arr[i] < smallest:
      smallest = arr[i]
      smallest_index = i
  return smallest_index

def selectionSort(arr):  ←------对数组进行排序
  newArr = []
  for i in range(len(arr)):
      smallest = findSmallest(arr)  ←------找出数组中最小的元素,并将其加入到新数组中
      newArr.append(arr.pop(smallest))
  return newArr

print selectionSort([5, 3, 6, 2, 10])

(2nd) C语言版本: (注: 此为本人学习代码, 请勿用到产品环境, 不保证代码质量)
Code: [Select]
#include <stdio.h>
#include <stdlib.h>

void show_array(int* data, size_t s)
{
for(size_t i = 0; i < s; i++) {
printf("%d ", data[i]);
}
printf("\n");
}

size_t find_max(int* data, size_t s, size_t offset)
{
int max = data[offset];
size_t pos = offset;

for(size_t i = offset + 1; i < s; i++) {
if (max < data[i]) {
max = data[i];
pos = i;
}
}

return pos;
}

void selection_sort(int* data, size_t s) {
for(size_t sorted = 0; sorted < s; sorted++) {
size_t pos = find_max(data, s, sorted);
int tmp = data[pos];
data[pos] = data[sorted];
data[sorted] = tmp;
}
}

int main() {
int data[] = {3, 1, 4, 5, 7, 2, 8, 1};
show_array(data, sizeof(data)/sizeof(data[0]));
selection_sort(data, sizeof(data)/sizeof(data[0]));
show_array(data, sizeof(data)/sizeof(data[0]));
return 0;
}
« Last Edit: April 26, 2019, 08:01:45 pm by Yarco »


Yarco

  • Administrator
  • Full Member
  • *****
    • Posts: 114
    • View Profile
(2nd) 本帖知识点概览:

第3章 递归

Quote
我很喜欢 Leigh Caldwell 在 Stack Overflow 上说的一句话:“如果使用循环,程序的性能可能更高;如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。”
递归本质可以算一种循环, 只是借用了系统的栈做存储.

3.2 基线条件和递归条件
* 基线条件
* 递归条件

3.3 栈
push & pop
(2nd) 整型栈的 c语言代码(本人练习所用, 产品环境后果自负, 以下代码不再重复warning):
Code: [Select]
#include <stdio.h>
#include <stdlib.h>

typedef struct int_stack {
    unsigned int cap;
    unsigned int used;
    int* data;
} int_stack;

int init_stack(int_stack* s, unsigned int n)
{
    s->cap = n;
    s->used = 0;
    s->data = (int *)malloc(sizeof(int) * n);
    if (s->data == NULL) {
        return -1;
    }

    return 0;
}

void free_stack(int_stack* s)
{
    free(s->data);
    s->cap = 0;
    s->used = 0;
    s->data = NULL;
}

int push_stack(int_stack* s, int data)
{
    if (s->cap <= s->used) return -1; // or realloc
    s->data[s->used++] = data;
    return 0;
}

int pop_stack(int_stack* s, int* data)
{
    if (s->used <= 0) return -1;
    *data = s->data[--s->used];
    return 0;
}

void print_stack(int_stack* s)
{
    printf("STACK=cap:%d used:%d\nContains: ", s->cap, s->used);
    for(int i = 0; i < s->used; i++) {
        printf("%d ", s->data[i]);
    }
    printf("\n");
}

int main() {
    int data[] = {3,1,4,1,5,9,2,6};
    int_stack s;

    int ret = init_stack(& s, sizeof(data)/sizeof(data[0]));
    if (ret == -1) return -1;

    for(int i = 0;i < 8; i++) {
        push_stack(& s, data[i]);
    }
    printf("after push...\n");
    print_stack(& s);

    int d;
    pop_stack(& s, &d);
    printf("popped %d\n", d);
    printf("after pop...\n");
    print_stack(& s);

    free_stack(& s);
    printf("after free...\n");
    print_stack(& s);
    return 0;
}

第4章 快速排序

4.1 分而治之
(2nd) 本质是针对非生物形态(好吧...我这里可能会说的不够精确), 比如一块石头, 那么它的性质其实完全可以由被切割出来的更小的石头所表达, 当大问题的解决完全可以通过寻找规模更小的问题的解决方案得到解决时, 这就是分而治之的场景.

4.2 快速排序
Code: [Select]
def quicksort(arr):
    if len(arr) < 2:
        return arr
   
    pivot = arr[0]
    left = [i for i in arr[1:] if i < pivot]
    right = [i for i in arr[1:] if i >= pivot]
    ## O(2n)
    return quicksort(left) + [pivot] + quicksort(right)
## O(2n * log n)

print(arr)
print(quicksort(arr))

(2nd)快排(c版本), 快排难点在分区.
Code: [Select]
#include <stdio.h>

void quicksort(int* data, int l, int r);
int partition(int* data, int l, int r);
void showdata(const char* prefix, int* data, int l, int r);

int main()
{
    int data[] = {3, 1, 4, 1, 5, 9, 2, 6};
    showdata("Original:\n", data, 0, 8);
    quicksort(data, 0, 7);
    showdata("After:\n", data, 0, 8);
    return 0;
}

void quicksort(int* data, int l, int r)
{
    if (l < r) {
        int pos = partition(data, l, r);
        quicksort(data, l, pos-1);
        quicksort(data, pos+1, r);
    }
}

void showdata(const char* prefix, int* data, int l, int r)
{
    printf("%s", prefix);
    for(int i = l; i < r; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

int partition(int* data, int l, int r)
{
    int pivot = data[l];
    int pos = l;

    while (l < r) {
        while (l < r && pivot < data[r])  r--;
        if (l < r) {
            data[l] = data[r];
            data[r] = pivot;
            pos = r;
            l++;
        }

        while (l < r && pivot > data[l]) l++;
        if (l < r) {
            data[r] = data[l];
            data[l] = pivot;
            pos = l;
            r--;
        }
    }

    return pos;
}

第5章 散列表

(也称为字典或字值对)

5.1 散列函数
(2nd) 散列表的关键点是选取散列函数. (因为已经存在大量散列函数, 我们只需要选取就行了) 但是优良的散列函数必定: 存储空间效率 (不会有大量的空间闲置, 并且同时有大量的冲突, 某种程度上来说和压缩算法有关联)

5.4.1 填装因子
(一旦超过0.7, 就需要重新分配)
5.4.2 良好的散列
均匀分布
Sha()
« Last Edit: April 27, 2019, 05:51:50 pm by Yarco »


Yarco

  • Administrator
  • Full Member
  • *****
    • Posts: 114
    • View Profile
(2nd) 本帖知识点概览:
  • 队列

第6章 广度优先搜索
(BFS, breadth-first search)

6.1 图介绍
6.2 图是什么
图是节点与边的集合.

6.3 广度优先搜索
回答两类问题:
1. 是否存在A->B的路径
2. 具体的最短路径

6.3.2 队列
FIFO.

6.4 图的实现

有向图
无向图

书中用dict来存储图, 但是是单向关系.

第7章 狄克斯特拉算法

加权图
非加权图

适用于:有向无环图

(... ...)
« Last Edit: May 14, 2019, 04:56:16 pm by Yarco »


Yarco

  • Administrator
  • Full Member
  • *****
    • Posts: 114
    • View Profile
第8章 贪婪算法

8.1 教室调度问题
8.2 背包问题

局部最优解 得到 全局最优解 的近似值.

8.4 NP 完全问题

Quote
元素较少时算法的运行速度非常快,但随着元素数量的增加,速度会变得非常慢。
涉及“所有组合”的问题通常是 NP 完全问题。
不能将问题分成小问题,必须考虑各种可能的情况。这可能是 NP 完全问题。
如果问题涉及序列(如旅行商问题中的城市序列)且难以解决,它可能就是 NP 完全问题。
如果问题涉及集合(如广播台集合)且难以解决,它可能就是 NP 完全问题。
如果问题可转换为集合覆盖问题或旅行商问题,那它肯定是NP完全问题。
(个人认为 指的是 当增加一个条件时, 将影响所有可能的已知答案 -- 点~全局 关联时, 是NP问题)

第9章 动态规划

(个人思考, 适合的情况属于)
* 近似的离散型数据/整型(子问题独立)
* 具有聚合值, 而根据这个聚合值判断优先

9.3 最长公共子串
9.3.4 最长公共子序列


Yarco

  • Administrator
  • Full Member
  • *****
    • Posts: 114
    • View Profile
第10章 K 最近邻算法

KNN

将需要分析的对象根据不同的特征值描述成对应的多维坐标轴上的位置, 在根据距离公式计算出距离.

(数据统计中的主成分分析?)

挑选特征值................需要强大的对人性的了解.

10.3 机器学习简介

10.3.1 OCR
10.3.2 创建垃圾邮件过滤器
10.3.3 预测股票市场

第11章 接下来如何做

11.1 树

(早就感觉二分查找和二叉查找树拥有类似的逻辑, 只是没有合适的语言去描述.  其实唯一的差别就是构造数据的情况, 如果已有排序的数据, 那么用2分查找; 如果数据本来就是在构造之中, 那么显然用 二叉查找树, 数据库大部分索引是它的增强型类型)

11.2 反向索引


11.3 傅里叶变换*
11.4 并行算法*
* 并行性管理开销
* 负载均衡
(有道理)

11.5 MapReduce
...

11.10 线性规划

(完)

很不错的书!!!