Welcome to MDGSF's Blog!

This is my github blog

[算法学习][智力题] 锦标赛排序算法

2018-04-11

Art

问题：

假定有二十五名短跑选手比赛竞争金银铜牌，赛场上有五条赛道，因此一次可以有五个人同时比赛。比赛并不计时，只看相应的名次。假如选手的发挥是稳定的，也就是说如果约翰比张三跑得快，张三比凯利跑得快，那么约翰一定比凯利跑得快。最少需要几组比赛才能决出前三名？

答案见底部
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|/

答案：7次。

分析：

一、将 25 名选手分为五个组，每组五个人，为了便于说明，我们不妨把这 25 个人根据所在的组进行编号，A1-A5 在 A 组，B1-B5 在 B 组….最后 E1-E5 在最后的 E 组。

然后让每个组分别比赛，排出各组的名次来。不失一般性，我们假设他们的名次就是他们在小组中的编号，即 A 组的名次是 A1、A2、A3、A4、A5，B 组和其它组的名次也是类似（如下图）：

A组	B组	C组	D组	E组
A1	B1	C1	D1	E1
A2	B2	C2	D2	E2
A3	B3	C3	D3	E3
A4	B4	C4	D4	E4
A5	B5	C5	D5	E5

二、让各组的第一名，也就是 A1、B1、C1、D1、E1 再比一次，这样就能决出第一名。不是一般性，我们假设 A1 在这次比赛中获胜，这样我们就知道了第一名。

三、由于 A1 是第一名，那么第二名和第三名呢？我们假设在第二步中，也就是第 6 组比赛中，名次为 A1、B1、C1、D1、E1 。那么很明显，D1 和 E1 就已经失去了竞争前 3 名的资格了。

四、第二名的候选人就是比 A1 慢的人，比其他人都快的人，就只能是 A2 和 B1 了。

五、第三名的候选人就是刚好比第二名慢的人，就只能是 A3、B2、C1 了。

六、那第二名的候选人和第三名的候选人加起来一共 5 个人，刚好一组比赛。

来源： 吴军老师的得到课程

Read All

[GO] chan 内部实现

2018-04-11

GO

GO

源码地址: go/src/runtime/chan.go

//TODO

Read All
[GO] map 内部实现

2018-04-09

GO

GO

源码地址: go/src/runtime/hashmap.go

就是一个哈希表，不过和以前看到的哈希表好像有点不同。

哈希表复习： http://mdgsf.github.io/c/2016/07/01/c-hashtable.html

//TODO

Read All

[Nginx] 反向代理配置

2018-03-19

mdgsf

nginx

Nginx

nginx.conf 文件配置

#user  nobody;
worker_processes  1;

error_log /usr/local/nginx/logs/nginx_error.log crit;
pid logs/nginx.pid;

worker_rlimit_nofile 65535;
events {
    use epoll;
    worker_connections 65535;
}

http {
    include       mime.types;
    default_type  application/octet-stream;

    log_format  main  '$remote_addr - $remote_user [$time_local] "$request" '
                      '$status $body_bytes_sent "$http_referer" '
                      '"$http_user_agent" "$http_x_forwarded_for"';

    access_log  logs/access.log  main;

    sendfile on;
    tcp_nopush on;
    tcp_nodelay on;
    keepalive_timeout  65;
    gzip on;
    gzip_min_length 1k;
    gzip_buffers 4 16k;

    upstream webservers {
        server 111.230.34.80:12345 weight=10;
        server 111.230.34.80:12346 weight=10;
    }

    server {
        listen 80 default;
        server_name  localhost;

        location /server1 {
            proxy_pass http://127.0.0.1:12345;
            #proxy_pass http://webservers;
            proxy_redirect    off;
            proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
            proxy_set_header X-Real-IP $remote_addr;
            proxy_set_header Host $http_host;
        }
        location /server2 {
            proxy_pass http://127.0.0.1:12346;
            #proxy_pass http://webservers;
            proxy_redirect    off;
            proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
            proxy_set_header X-Real-IP $remote_addr;
            proxy_set_header Host $http_host;
        }
   }
}

在 URI 的末尾加上斜杠也同样有效。

    server {
        listen 80 default;
        server_name  localhost;

        location /server1 {
            proxy_pass http://127.0.0.1:12345/;
            #proxy_pass http://webservers;
            proxy_redirect    off;
            proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
            proxy_set_header X-Real-IP $remote_addr;
            proxy_set_header Host $http_host;
        }
        location /server2 {
            proxy_pass http://127.0.0.1:12346/;
            #proxy_pass http://webservers;
            proxy_redirect    off;
            proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
            proxy_set_header X-Real-IP $remote_addr;
            proxy_set_header Host $http_host;
        }
   }

在 location 的末尾加上斜杠也同样有效。

    server {
        listen 80 default;
        server_name  localhost;

        location /server1/ {
            proxy_pass http://127.0.0.1:12345;
            #proxy_pass http://webservers;
            proxy_redirect    off;
            proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
            proxy_set_header X-Real-IP $remote_addr;
            proxy_set_header Host $http_host;
        }
        location /server2/ {
            proxy_pass http://127.0.0.1:12346;
            #proxy_pass http://webservers;
            proxy_redirect    off;
            proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
            proxy_set_header X-Real-IP $remote_addr;
            proxy_set_header Host $http_host;
        }
   }

在 location 和 URI 的末尾同时加上斜杠也同样有效。

    server {
        listen 80 default;
        server_name  localhost;

        location /server1/ {
            proxy_pass http://127.0.0.1:12345/;
            #proxy_pass http://webservers;
            proxy_redirect    off;
            proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
            proxy_set_header X-Real-IP $remote_addr;
            proxy_set_header Host $http_host;
        }
        location /server2/ {
            proxy_pass http://127.0.0.1:12346/;
            #proxy_pass http://webservers;
            proxy_redirect    off;
            proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
            proxy_set_header X-Real-IP $remote_addr;
            proxy_set_header Host $http_host;
        }
   }

HTTP server 代码

package main

import (
    "fmt"
    "io"
    "log"
    "net/http"
)

//HelloServer server1
func HelloServer(w http.ResponseWriter, req *http.Request) {
    io.WriteString(w, "server1\n")
}

func main() {
    fmt.Println("vim-go")

    http.HandleFunc("/", HelloServer)
    err := http.ListenAndServe(":12345", nil)
    if err != nil {
        log.Fatal("ListenAndServe: ", err)
    }
}

Read All

[Nginx] 负载均衡配置

2018-03-19

mdgsf

nginx

Nginx

nginx.conf 文件配置

#user  nobody;
worker_processes  1;

error_log /usr/local/nginx/logs/nginx_error.log crit;
pid logs/nginx.pid;

worker_rlimit_nofile 65535;
events {
    use epoll;
    worker_connections 65535;
}

http {
    include       mime.types;
    default_type  application/octet-stream;

    log_format  main  '$remote_addr - $remote_user [$time_local] "$request" '
                      '$status $body_bytes_sent "$http_referer" '
                      '"$http_user_agent" "$http_x_forwarded_for"';

    access_log  logs/access.log  main;

    sendfile on;
    tcp_nopush on;
    tcp_nodelay on;
    keepalive_timeout  65;
    gzip on;
    gzip_min_length 1k;
    gzip_buffers 4 16k;

    upstream webservers {
        server 111.230.34.80:12345 weight=10;
        server 111.230.34.80:12346 weight=10;
    }

    server {
        listen 80 default;
        server_name  localhost;

        location /server {
            proxy_pass http://webservers;
            proxy_redirect    off;
            proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
            proxy_set_header X-Real-IP $remote_addr;
            proxy_set_header Host $http_host;
        }
   }
}

HTTP server 代码

package main

import (
    "fmt"
    "io"
    "log"
    "net/http"
)

//HelloServer server1
func HelloServer(w http.ResponseWriter, req *http.Request) {
    io.WriteString(w, "server1\n")
}

func main() {
    fmt.Println("vim-go")

    http.HandleFunc("/", HelloServer)
    err := http.ListenAndServe(":12345", nil)
    if err != nil {
        log.Fatal("ListenAndServe: ", err)
    }
}

Read All

[Network] 缩略语

2018-03-19

mdgsf

Network

Network

ACK (Acknowledgment) TCP 首部中的确认标志

API (Application Programming Interface) 应用编程接口

ARP (Address Resolution Protocol) 地址解析协议

ARPANET (Defense Advanced Research Project Agency NETwork) 美国国防部远景研究规划局

AS (Autonomous System) 自治系统

ASCII (American Standard Code for Information Interchange) 美国信息交换标准码

ASN.1 (Abstract Syntax Notation One) 抽象语法记法1

BER (Basic Encoding Rule) 基本编码规则

BGP (Border Gateway Protocol) 边界网关协议

BIND (Berkeley Internet Name Domain) 伯克利 Internet 域名

BOOTP (BOOTstrap Protocol) 引导程序协议

BPF (BSD Packet Filter) BSD 分组过滤器

CIDR (Class InterDomain Routing) 无类型域间选路

CIX (Commercial Internet Exchange) 商业互联网交换

CLNP (ConnectionLess Network Protocol) 无连接网络协议

CRC (Cyclic Redundancy Check) 循环冗余校验

CSLIP (Compressed SLIP) 压缩的 SLIP

CSMA (Carrier Sense Multiple Access) 载波侦听多路存取

DCE (Data Circuit-terminating Equipment) 数据电路端接设备

DDN (Defense Data Network) 国防数据网

DF (Don’t Fragment) IP 首部中的不分片标志

DHCP (Dynamic Host Configuration Protocol) 动态主机配置协议

DLPI (Data Link Provider Interface) 数据链路提供者接口

DNS (Domain Name System) 域名系统

DSAP (Destination Service Access Point) 目的服务访问点

DSLAM (DSL Access Multiplexer) 数字用户线接入复用器

DSSS (Direct Sequence Spread Spectrum) 直接序列扩频

DTS (Distributed Time Service) 分布式时间服务

DVMRP (Distance Vector Multicast Routing Protocol) 距离向量多播选路协议

EBONE (European IP BackbONE) 欧洲 IP 主干网

EOL (End of Option List) 选项清单结束

EGP (External Gateway Protocol) 外部网关协议

EIA (Electronic Industries Association) 美国电子工业协会

Read All

26/97

Welcome to MDGSF's Blog!

[算法学习][智力题] 锦标赛排序算法

[GO] chan 内部实现

[GO] map 内部实现

[Nginx] 反向代理配置

nginx.conf 文件配置

在 URI 的末尾加上斜杠也同样有效。

在 location 的末尾加上斜杠也同样有效。

在 location 和 URI 的末尾同时加上斜杠也同样有效。

HTTP server 代码

[Nginx] 负载均衡配置

nginx.conf 文件配置

HTTP server 代码

[Network] 缩略语