本文是为了加深自己对各种算法的理解，部分摘自维基百科，这里主要介绍较为常用的排序方法，一些生僻的算法不做介绍。
.
总结各种算法之前，现介绍下几个概念：
1、稳定度：稳定排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的串行中R出现在S之前，在排序过的串行中R也将会是在S之前。
2、计算的复杂度（最差、平均、和最好表现），依据串行（list）的大小（n）。一般而言，好的表现是O(n log n)，且坏的行为是O(n2)。对于一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O(n log n)。
.
稳定排序：
* 泡沫排序（bubble sort） — O(n²)
* 插入排序 （insertion sort）— O(n²)
* 桶排序 （bucket sort）— O(n); 需要 O(k) 额外空间
* 计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外空间
* 合并排序 （merge sort）— O(n log n); 需要 O(n) 额外空间
* 二叉排序树排序 （Binary tree sort） — O(n log n)期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
* 基数排序 （radix sort）— O(n·k); 需要 O(n) 额外空间
.
不稳定排序
* 选择排序 （selection sort）— O(n²)
* 希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本
* 堆排序 （heapsort）— O(n log n)
* 快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序
多线程程序可能存在很多潜在的bug，如data race，dead lock，信号bug等，而这些bug一向很难调试，现在有很多论文都是基于多线程程序的调试技术的，比如model check，死锁检测，replay技术等，也有很多对应的工具，如intel的pinplay，微软的Zing等。关于这些技术和工具，如果感兴趣可以 google相应的论文进一步了解。这里我主要讲述的是我在对二进制翻译下多线程程序调试中经常使用的一些方法以及一些调试经验，虽然我的调试的是二进制翻译器，但是这些方法也同样适用于大多数多线程程序。
问题1：安装guest addition时遇到如下问题
.. .. Building the Virtualbox Guest Additions kernel modules [FAILED] (Your system does not seem to be set up to build kernel modules. Look at /var/log/vboxadd-install.log to find out what went wrong) .. |
/var/log/vboxadd-install.log里面错误内容如下
Makefile:23: *** Error: Unable to find the sources of your current Linux kernel. Specify KERN_DIR=<directory> and run MAKE again.. Stop. |
在Linux中，内核的页面映射机制分为三层，页面目录和页面表中间设有一个“中间目录”。中间目录是为了对64位CPU兼容而设计的。在内核代码中，页面目录称为PGD，中间目录称为PMD，页面表成为PT， PT中的表项称为PTE， 是“page table entry的缩写”。
一个进程的线性地址从高位到低位划分为4个段，各占若干位，分别作用为目录PGD中的下标，中间目录PMD的下标、页面表的下标以及物理页面内的位移。因此，给定一个线性地址，利用其前面三个段，就可以得到这个线性地址对应的pte。本文将分别阐述如何在X86以及龙芯2f下通过线性地址来得到对应的pte。
数组名和指针是两个往往很容易让人们混淆的概念，很多人以为数组名就是一个指针，也有很多人知道数组名不同于指针但是仅知道数组名的值不能像指针一样改变，例如你可以写出下面这样的代码：
int *p;
p++;
却不能写这样的代码：
int a[];
a++;
那么数组名跟指针之间到底有什么区别呢？
Gentoo下默认无线网卡是没有配置好的（至少在我机器上是这样），并且手动配置的过程会遇到各种各样的问题，每个版本，每个型号的电脑、网卡遇到的问题也不尽相同。这里把在我的IdeaPad Y450笔记本下所遇到的这种和那种的问题，并给出我的解决方案和一些个过程，希望其中一条能解决你的问题。
评测一个程序的性能有多种方法，对目前大多数benchmark，程序执行时间是一个很重要的标准。但大多数情况下时间仅仅能给出一个结果，却给不了更多的信息，如cache miss, CPU功能部件的利用率，访存指令，分支预测等。这些信息对于知道一个程序的优化往往会起到很重要的作用。因此，cpu中的性能计数器这时就显得尤为重要。本文主要介绍龙芯2F性能计数器的使用方法，并给出了一个可以通过简单的write系统调用改变技术事件的模块的代码。
最新回复评论