FunCoder

FunCoder

Posted on In Disqus: Word count in article: 3.1k Reading time ≈ 3 mins.

CSAPP 3 程序的机器层面表达

这一章主要从汇编程序和机器码的角度看程序。包括call stack, local variable, 以及一些基本的数据结构，比如array, structure, union 等等。

Fun fact: 64位寻址空间是2**48 而不是 2**64。为什么？

IA32机器码与C语言代码不同，可以接触到一些CPU 的计算状态：

  • 程序指针，PC
  • 寄存器文件，regiester file
  • 条件寄存器，
  • 浮点数寄存器
Read more »

Posted on In Disqus: Word count in article: 1.3k Reading time ≈ 1 mins.

Calculator I,II,III

问题：

1
2
3
Given a string s which represents an expression, evaluate this expression and return its value. 

The integer division should truncate toward zero.

例子：

Read more »

Posted on In Disqus: Word count in article: 2.6k Reading time ≈ 2 mins.

Leetcode Jump Game (1-3)

这个系列的三个题虽然名字很像，但是第一和第二个思路类似，属于贪心问题，而第三题其实是搜索问题。

55. Jump Game I

问题

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.

Read more »

Posted on In Disqus: Word count in article: 871 Reading time ≈ 1 mins.

CSAPP 1 概览

这本书之前非常简略的阅读过一次，过了这么一年多，重新拿起这本书反倒有了更多理解。可能这就是一本好书的特点把，他随着你的经验增加，提供给你更多的信息。给人的感觉就是，第一次读醍醐灌顶，第二次读，还是醍醐灌顶。。。

作者首先描述了一个 hello 程序是如何从源代码变成可以被执行的机器码，然后通过简单介绍计算机的硬件组成说明了程序是如何被执行的。在这个过程中有几个比较重要的点：

  • 编译器就是一个把一段程序（源代码）翻译成另一种程序（机器码）一个程序（机器码）
  • 计算机的主要操作就是读取指令（数据），运算，输出数据
  • 由于不同数据存储介质的读取速度和容量负相关，缓存机制尤其重要

随后引入了操作系统的三个重要抽象：

Read more »

Posted on In Disqus: Word count in article: 2.6k Reading time ≈ 2 mins.

CSAPP 2 信息的表达和操作

目前的计算机技术存储信息是二进制的，我们用0和1表达信息。最基本的信息有两种：整数和浮点数。字符串也会被编码成整数表达。从根本上说，我们规定了一些规则（向下文）来解释这些0和1。通过基本的代数法则就可以实现运算了。

为了方便人类阅读，常用的编码进制包括8进制和16进制。

Code

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
101
102
103
104
105
106
107
108
109
110
#include "csapp.h"
#include <stdio.h>

void print_int(int x) { printf("int: %d\n", x); }
void print_dbl(double x) { printf("double: %g\n", x); }
void print_int_arr(int a[]) {
    int i;
    printf("int array: [");
    for (i=0;i<=(sizeof(a))/sizeof(a[0]); i++) {
        printf("%d, ", a[i]);
    }
    printf("]\n");
}
void print_default() { puts("unknown argument"); }
#define print(X) _Generic((X), \
        int: print_int, \
        double: print_dbl, \
        int*: print_int_arr, \
        default: print_default)(X)

#define problem(x) printf("\n * Problem %s: \n", x)
#define comment(x) printf("%s\n", x)

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, int len) {
    int i;
    for (i=0; i<len; i++) {
        printf(" %.2x", start[i]);
    }
    printf("\n");
}

void show_int(int x) {
    show_bytes((byte_pointer) &x, sizeof(int));
}

void show_float(float x) {
    show_bytes((byte_pointer) &x, sizeof(float));
}

void show_pointer(void* x) {
    show_bytes((byte_pointer) &x, sizeof(void *));
}

void swap(int *x, int *y) {
    *y = *x^*y;
    *x = *x^*y; /*Step2*/
    *y = *x^*y; /*Step3*/
}

void reverse_array(int a[], int cnt) {
    // 1,2,3  -> 3,2,1
    int first, last;
    for (first=0, last=cnt-1;
        first < last;
        first++, last--) {
            swap(&a[first], &a[last]);
        };
}

int main()
{
    int x = 1;
    float y = 1.0;
    show_int(x);
    show_float(y);
    show_pointer(&x);
    printf("Sizeof float is %lu \n", sizeof(float));
    printf("Sizeof int is %lu \n", sizeof(int));
    // Problem 2.6
    problem("2.6");
    int a = 3510593;
    int b = 3510593.0;
    show_int(b);   // ? why this shows as same as a?
    show_int(a);   //        1101011001000101000001
    show_float(b); // 1001010010101100100010100000100
    // Problem 2.7
    const char *s = "abcdef";
    show_bytes((byte_pointer)s, strlen(s)); //  61 62 63 64 65 66

    /*
    a = 110
    b = 001

    b = a ^ b  -> b = 110 ^ 001 = 111
    a = a ^ b  -> a = 110 ^ 111 = 001
    b = a ^ b  -> b = 001 ^ 111 = 110
    */
    problem("2.10");
    int aa = 1;
    int bb = 2;
    swap(&aa, &bb);
    print(aa);
    print(bb);

    problem("2.11");
    comment("Note that a ^ a = 0");
    int a2[] = {1, 2, 3};
    print(a2);
    reverse_array(a2, 3);
    print(a2);

    problem("2.12");
    int x12 = 0x87654321;
    printf("%x\n", x12 & 0xFF);
    printf("%x\n", ~( x12 ^ 0xFF ));
    printf("%x\n", x12 | 0xFF);
    printf("%x\n", ~( 0x11 ^ 0xFF ));
}

Posted on In Disqus: Word count in article: 812 Reading time ≈ 1 mins.

nSum 问题

2 Sum

方法1：去重、排序、字典、穷举

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        cache = {}
        
        for i in range(len(nums)):
            residual = target - nums[i]
            
            if residual in cache:
                return [cache[residual], i]
            
            cache[nums[i]] = i
            
        return []

3 Sum

Read more »

Posted on In Disqus: Word count in article: 5.4k Reading time ≈ 5 mins.

动态规划问题

动态规划问题最鲜明的特点是求最值，问题本身一般可以用重复的、更小的子问题解决（递归特性）。解决方法通常是：递归、备忘录递归、迭代、备忘录迭代。要素是找到：

  • 重复子问题
  • 最优子结构
  • 状态转移方程

基本套路：写出 base -> 明确所有状态 -> 明确每个状态的选择 -> 定义 dp 数组 

1
2
3
4
5
6
7
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)
Read more »

Posted on In Disqus: Word count in article: 7.9k Reading time ≈ 7 mins.

Go 学习笔记 Memory Access Synchronization

Go 对并发有良好的支持，主要支持两种模式：CSP 和 MAS。前一种是大家熟知的Go常用模式（goroutine + chan），后面一种其实就是传统的带锁的并发编程（sync 包）。Go 对这两种并发都有良好的支持，同时也提倡在合适的时候混合使用他们，因为这两种并发的应用场景不太一样。

但是总体老说，MAS 不是 Go 并发的首选模式，应该在谨慎考虑后使用，尽量多使用 CSP 构造函数。Go 的基本哲学是：

在可能的场景下使用 channel，将 goroutine 视为非常廉价的操作。

何时（不）选择 MAS

Read more »

Posted on In Disqus: Word count in article: 8.9k Reading time ≈ 8 mins.

用Python重建Go并发模型 1

主要译自Go Concurrency from the Ground Up

通过实现 Go 的并发模型增加对并发的理解和使用。

本文一共四个部分，部分1 针对前两个，后面两个在部分2：

  • 设计：介绍 Go 的并发模型基本API
  • 实现1：实现一个非抢占、单线程的 goroutine 调度器
  • 实现2：带缓冲的 Channel
  • 实现3：Async/Await 范式实现
Read more »

Posted on In Disqus: Word count in article: 3.8k Reading time ≈ 3 mins.

Go 学习笔记5 并发编程

Go 的一个主要的特征是对多核并发的支持，特别是 CSP（Communicating Sequential Processes） 模型。Go 主要支持两类并发模型：CSP 和 共享内存。

CSP 模型

Go 的 CSP 模型主要是通过 goroutine 和 channel 两个基本模块完成的。

Goroutine （协程）

Read more »
0%