Browsed by
分类: 编程语言

类型的本质和函数式实现

类型的本质和函数式实现

(感谢 @文艺复兴记(todd) 投递此文)

在上一篇文章《二叉树迭代器算法》中,我介绍了一种基于栈的二叉树迭代器实现。程序设计语言和Haskell大牛@九瓜 在看过之后评论到:

这里用了 stack 来做,有点偷懒,所以错失了一个抽象思考机会。如果我们能够理解二叉树到线性表的转换过程,完全可以把 Iterator 当作抽象的线性表来看,只要定义了关于 Iterator 的 empty, singleton, 还有 append 操作,实现二叉树的 Iterator 就变得非常直观。

“错失了一个抽象思考机会”是什么意思呢?我理解九瓜的意思是基于栈的实现虽然是正确的,但它缺乏对于迭代器类型本质的理解,不具有通用性。如果能对迭代器进行合适地抽象就可以像二叉树递归遍历一样自然地得出二叉树迭代器,甚至其他更复杂的数据结构,只要我们能写出它的遍历算法,迭代器算法都可以自然推出。

类型的本质

九瓜提到了通过empty, singleton和append操作对Iterator进行抽象,我本来打算直接根据这个思路介绍函数式的二叉树迭代器实现,但是考虑到其实首要的问题在于理解类型的本质,而并不是所有人都具备这个基础,不如先普及一下类型基础再进入具体实现。那么下面我们就先来认识一下类型到底是什么?我们先以来看看表示元素对的Pair类型,可能有人一提到Pair类型马上就会在脑海中浮现出下面的结构:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (23 人打了分,平均分: 3.61 )
Loading...
C语言全局变量那些事儿

C语言全局变量那些事儿

(感谢网友 @我的上铺叫路遥 投稿)

作为一名程序员,如果说沉迷一门编程语言算作一种乐趣的话,那么与此同时反过来去黑一门编程语言就是这种乐趣的升华。今天我们就来黑一把C语言,好好展示一下这门经典语言令人抓狂的一面。

我们知道,全局变量是C语言语法和语义中一个很重要的知识点,首先它的存在意义需要从三个不同角度去理解:对于程序员来说,它是一个记录内容的变量(variable);对于编译/链接器来说,它是一个需要解析的符号(symbol);对于计算机来说,它可能是具有地址的一块内存(memory)。其次是语法/语义:从作用域上看,带static关键字的全局变量范围只能限定在文件里,否则会外联到整个模块和项目中;从生存期来看,它是静态的,贯穿整个程序或模块运行期间(注意,正是跨单元访问和持续生存周期这两个特点使得全局变量往往成为一段受攻击代码的突破口,了解这一点十分重要);从空间分配上看,定义且初始化的全局变量在编译时在数据段(.data)分配空间,定义但未初始化的全局变量暂存(tentative definition)在.bss段,编译时自动清零,而仅仅是声明的全局变量只能算个符号,寄存在编译器的符号表内,不会分配空间,直到链接或者运行时再重定向到相应的地址上。

我们将向您展现一下,非static限定全局变量在编译/链接以及程序运行时会发生哪些有趣的事情,顺便可以对C编译器/链接器的解析原理管中窥豹。以下示例对ANSI C和GNU C标准都有效,笔者的编译环境是Ubuntu下的GCC-4.4.3。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (29 人打了分,平均分: 3.86 )
Loading...
二叉树迭代器算法

二叉树迭代器算法

(感谢 @文艺复兴记(todd) 投递此文)

二叉树(Binary Tree)的前序、中序和后续遍历是算法和数据结构中的基本问题,基于递归的二叉树遍历算法更是递归的经典应用。

假设二叉树结点定义如下:

// C++
struct Node {
    int value;
    Node *left;
    Node *right;
}

中序递归遍历算法:

// C++
void inorder_traverse(Node *node) {
    if (NULL != node->left) {
        inorder_traverse(node->left);
    }
    do_something(node);
    if (NULL != node->right) {
        inorder_traverse(node->right);
    }
}

前序和后序遍历算法类似。

但是,仅有遍历算法是不够的,在许多应用中,我们还需要对遍历本身进行抽象。假如有一个求和的函数sum,我们希望它能应用于链表,数组,二叉树等等不同的数据结构。这时,我们可以抽象出迭代器(Iterator)的概念,通过迭代器把算法和数据结构解耦了,使得通用算法能应用于不同类型的数据结构。我们可以把sum函数定义为:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (24 人打了分,平均分: 3.13 )
Loading...
Alan Cox:单向链表中prev指针的妙用

Alan Cox:单向链表中prev指针的妙用

Alan Cox
Alan Cox

(感谢网友 @我的上铺叫路遥 投稿)

之前发过一篇二级指针操作单向链表的例子,显示了C语言指针的灵活性,这次再探讨一个指针操作链表的例子,而且是一种完全不同的用法。

这个例子是linux-1.2.13网络协议栈里的,关于链表遍历&数据拷贝的一处实现。源文件是/net/inet/dev.c,你可以从kernel.org官网上下载。

从最早的0.96c版本开始,linux网络部分一直采取TCP/IP协议族实现,这是最为广泛应用的网络协议,整个架构就是经典的OSI七层模型的描述,其中dev.c是属于链路层实现。从功能上看,其位于网络设备驱动程序和网络层协议实现模块之间,作为二者之间的数据包传输通道,一种接口模块而存在——对驱动层的接口函数netif_rx, 以及对网络层的接口函数net_bh。前者提供给驱动模块的中断例程调用,用于链路数据帧的封装;后者作为驱动中断例程底半部(buttom half),用于对数据帧的解析处理并向上层传送。

为了便于理解,这里补充一下网络通信原理和linux驱动中断机制的背景知识。从最底层的物理层说起,当主机和路由器相互之间进行通信的时候,在物理介质上(同轴、光纤等)以电平信号进行传输。主机或路由器的硬件接口(网卡)负责收发这些信号,当信号发送到接口,再由内置的调制解调器(modem)将数字信号转换成二进制码,这样才能驻留在主机的硬件缓存中。这时接口(网卡)设备驱动程序将通过硬中断来获取硬件缓存中的数据,驱动程序是操作系统中负责直接同硬件设备打交道的模块,硬中断的触发是初始化时通过设置控制寄存器实现的,用于通知驱动程序硬件缓存中有新的数据到来。linux卡设备驱动就是在中断处理例程(ISR)中将硬件缓存数据拷贝到内核缓存中,打包成数据链路帧进行解析处理,再向上分发到各种协议层。由于ISR上下文是原子性的、中断屏蔽的,整个步骤又较为繁琐,因此全部放在ISR中处理会影响到其它中断响应实时性,于是linux有实现一种bottom half的软中断处理机制,将整个ISR一分为二,前半部上下文屏蔽所有中断,专门处理紧急的、实时性强的事务,如拷贝硬件缓存并打包封装,后半部上下文没有屏蔽中断(但代码不可重入),用于处理比较耗时且非紧急事务,包括数据帧的解析处理和分发。下面要讲的net_bh就属于后半部。

我们主要关心的是将链路帧分发到协议层那一段逻辑,下面摘自net_bh函数中的一段代码:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (36 人打了分,平均分: 4.11 )
Loading...
Javascript 装载和执行

Javascript 装载和执行

一两个月前在淘宝内网里看到一个优化Javascript代码的竞赛,发现有不少的人对Javascript的执行和装载的基础并不懂,所以,从那天起我就想写一篇文章,但一直耽搁了。自上篇《浏览器渲染原理简介》,正好也可以承前启后。

首先,我想说一下Javascript的装载和执行。通常来说,浏览器对于Javascript的运行有两大特性:1)载入后马上执行,2)执行时会阻塞页面后续的内容(包括页面的渲染、其它资源的下载)。于是,如果有多个js文件被引入,那么对于浏览器来说,这些js文件被被串行地载入,并依次执行。

因为javascript可能会来操作HTML文档的DOM树,所以,浏览器一般都不会像并行下载css文件并行下载js文件,因为这是js文件的特殊性造成的。所以,如果你的javascript想操作后面的DOM元素,基本上来说,浏览器都会报错说对象找不到。因为Javascript执行时,后面的HTML被阻塞住了,DOM树时还没有后面的DOM结点。所以程序也就报错了。

传统的方式

所以,当你写在代码中写下如下的代码:

<script type="text/javascript"
        src="https://coolshell.cn/asyncjs/alert.js"></script>

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (64 人打了分,平均分: 4.31 )
Loading...
无锁HashMap的原理与实现

无锁HashMap的原理与实现

 (本文由投稿)

在《疫苗:Java HashMap的死循环》中,我们看到,java.util.HashMap并不能直接应用于多线程环境。对于多线程环境中应用HashMap,主要有以下几种选择:

  1. 使用线程安全的java.util.Hashtable作为替代。
  2. 使用java.util.Collections.synchronizedMap方法,将已有的HashMap对象包装为线程安全的。
  3. 使用java.util.concurrent.ConcurrentHashMap类作为替代,它具有非常好的性能。

而以上几种方法在实现的具体细节上,都或多或少地用到了互斥锁。互斥锁会造成线程阻塞,降低运行效率,并有可能产生死锁、优先级翻转等一系列问题。

CAS(Compare And Swap)是一种底层硬件提供的功能,它可以将判断并更改一个值的操作原子化。关于CAS的一些应用,《无锁队列的实现》一文中有很详细的介绍。

Java中的原子操作

在java.util.concurrent.atomic包中,Java为我们提供了很多方便的原子类型,它们底层完全基于CAS操作。

例如我们希望实现一个全局公用的计数器,那么可以:

 

private AtomicInteger counter = new AtomicInteger(3);

public void addCounter() {
    for (;;) {
        int oldValue = counter.get();
        int newValue = oldValue + 1;
        if (counter.compareAndSet(oldValue, newValue))
            return;
    }
}

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (30 人打了分,平均分: 3.40 )
Loading...
浏览器的渲染原理简介

浏览器的渲染原理简介

看到这个标题大家一定会想到这篇神文《How Browsers Work》,这篇文章把浏览器的很多细节讲得很细,而且也被翻译成了中文。为什么我还想写一篇呢?因为两个原因,

1)这篇文章太长了,阅读成本太大,不能一口气读完。

2)花了大力气读了这篇文章后可以了解很多,但似乎对工作没什么帮助。

所以,我准备写下这篇文章来解决上述两个问题。希望你能在上班途中,或是坐马桶时就能读完,并能从中学会一些能用在工作上的东西。

浏览器工作大流程

废话少说,先来看个图:

从上面这个图中,我们可以看到那么几个事:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (70 人打了分,平均分: 4.39 )
Loading...
疫苗:Java HashMap的死循环

疫苗:Java HashMap的死循环

在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障,并且这个事发生了很多次,原因是在Java语言在并发情况下使用HashMap造成Race Condition,从而导致死循环。这个事情我4、5年前也经历过,本来觉得没什么好写的,因为Java的HashMap是非线程安全的,所以在并发下必然出现问题。但是,我发现近几年,很多人都经历过这个事(在网上查“HashMap Infinite Loop”可以看到很多人都在说这个事)所以,觉得这个是个普遍问题,需要写篇疫苗文章说一下这个事,并且给大家看看一个完美的“Race Condition”是怎么形成的。

问题的症状

从前我们的Java代码因为一些原因使用了HashMap这个东西,但是当时的程序是单线程的,一切都没有问题。后来,我们的程序性能有问题,所以需要变成多线程的,于是,变成多线程后到了线上,发现程序经常占了100%的CPU,查看堆栈,你会发现程序都Hang在了HashMap.get()这个方法上了,重启程序后问题消失。但是过段时间又会来。而且,这个问题在测试环境里可能很难重现。

我们简单的看一下我们自己的代码,我们就知道HashMap被多个线程操作。而Java的文档说HashMap是非线程安全的,应该用ConcurrentHashMap。

但是在这里我们可以来研究一下原因。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (184 人打了分,平均分: 4.66 )
Loading...
“C++的数组不支持多态”?

“C++的数组不支持多态”?

先是在微博上看到了个微博和云风的评论,然后我回了“楼主对C的内存管理不了解”。

后来引发了很多人的讨论,大量的人又借机来黑C++,比如:

//@Baidu-ThursdayWang:这不就c++弱爆了的地方吗,需要记忆太多东西

//@编程浪子张发财:这个跟C关系真不大。不过我得验证一下,感觉真的不应该是这样的。如果基类的析构这种情况不能 调用,就太弱了。

//@程序元:现在看来,当初由于毅力不够而没有深入纠缠c++语言特性的各种犄角旮旯的坑爹细枝末节,实是幸事。为现在还沉浸于这些诡异特性并乐此不疲的同志们感到忧伤。

然后,也出现了一些乱七八糟的理解:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (52 人打了分,平均分: 4.25 )
Loading...
Unix考古记:一个“遗失”的shell

Unix考古记:一个“遗失”的shell

(感谢网友Leo投递此文)

谨以此文纪念伟大的计算机科学巨匠Ken ThompsonDennis Ritchie,并同时向其他所有为Unix发展做出贡献的黑客致敬。

历史的尘埃

Unix作为一个举世闻名的操作系统已有40余年的历史,围绕着这个古老的操作系统的发展又衍生出了一系列外围软件生态群,其中一个非常重要的组件就是shell。它是操作系统最外层的接口,负责直接面向用户交互并提供内核服务,包括命令行接口(CLI)或图形界面接口(GUI)两种形式。以CLI为例,它提供一套命令规范,是一种解释性语言,将用户输入经过解释器(interpreter)输出使其转化成真正的系统调用,实现人机交互的功能。

和操作系统一样,shell也经历了一个漫长的演变史。如今大部分资料讲述最古老的shell都是从1977年的Bourne Shell说起的,它最初移植到Unix V7上,被追认整个shell家族成员的鼻祖,后来的种群都是从其身上分支出来的。

Linux shells since 1977

对于1977年之前的历史很多资料大多一笔带过或略过不提。事实上,第一个移植到Unix上的shell却不是Steve Bourne写的,早在1975年5月,贝尔实验室就对外发布了第一个广泛传播的Unix版本——Unix V6(之前开发的版本只供内部研究之用),其根目录下的/bin/sh是第一个Unix自带的shell,由Ken Thompson写的,因此也被称为Thompson Shell。甚至,更早可以追溯到1971年的时候,Thompson Shell就作为一个独立于内核的应用程序而实现了,只不过从1975年正式问世到1977年被取代,短短两年的寿命使得它很少为大多数人所认识。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (39 人打了分,平均分: 4.15 )
Loading...