发表于

由于面试中经常遇到海量数据的相关问题，比如排序，比如选出topk，比如找出重复的元素等等

  1. 海量数据排序
  • 假如有１TB的数据，内存只有32GB

第一步是将１TB的数据分成40组，每组25GB； 然后分别读取40组数据，进行内部排序（可以用快排或者归并），然后写回磁盘； 接着从这40组数据中分别读取25GB/40=0.625GB，放在40个缓冲区里； 最后进行多路归并，可以每次将归并结果写满4GB就写回磁盘；并且一旦有缓冲区已经读完了，就从该缓冲区对应的组里读入新的0.625GB；

  1. 海量数据中选出最大的前k个数

一种方法：通过哈希将海量数据分成n个小文件（如果不够小，继续细分，直到文件大小小于内存）。然后为每个小文件建立一个小顶堆，这样就能选出n个topK，进行归并，选出最后的topK； 另外的方法：是直接建立一个k大小的大顶堆，然后依次读入数据，与堆顶元素比较，调整堆。当所有数据读完之后，得到最终的堆就是topK个数；

  1. 海量数据中选出频率最高的几个元素

与上面相同，先是将数据分成多个小文件，在每个小文件内利用hash_map去统计每个词的频率，选出topK频率的元素。最后再进程归并或者大顶堆统计；

  1. 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

首先是分别对这两个大文件进行哈希计算（用同一个哈希函数），得到多个小文件，这样相同的url就会被分到对应的小文件中；然后从a得到的小文件中找出url，存到hash_set中，然后遍历另外的对应小文件url，如果存在则输出到文件中

  1. 在海量数据中找出不重复的数

采用2bit法，00表示不存在该数字，01表示数字只出现一次，10表示数字重复多次。扫描完之后，输出对应为01的数字即可

  1. 判断一个数是否在海量数据中

一种方法是采用位图法，1个bit代表一个数，扫描一遍海量数据，得到扫描结果。之后进行判断； 另外的方法则是，把海量数据按照每个bit为0或者1分成两类，然后又按照次高位分成2类。。一次下去。这样，每次判断数是否存在于海量数据中花费时间为logN

参考

http://blog.csdn.net/FX677588/article/details/72471357 https://kb.cnblogs.com/page/95701/

发表于

Singleton

目的

在某些应用环境下，我们希望一个类只提供一个实例，用户只能使用一个实例

##　做法

一般来说，我们在类内维持一个静态的成员变量和静态成员函数，在函数内对成员变量进行初始化（准确点说应该是分配对象）

##　注意问题

  1. 所有函数都定义为static，并不是好的单例模式，一是因为我们无法保证静态变量的初始化顺序，加入是两个单例类互相使用，这样就无法保证互相的一来关系，另外的问题就是可能失去了面向对象的关键特性——多态

  2. 还有一个是如果我们的静态变量是一个对象，那么程序一开始运行，对象就已经存在了，镇不是我们需要的

  3. 如果我们希望灵活地使用不同的对象（以后拓展），可以在类内增加一个注册机制，根据环境变量返回不同类型的实例

  4. 最后返回指针可能会有一个问题就是，程序员可能会自行去销毁指针所指向的对象，这样就无法再次拥有这个实例了

代码示例

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
#include <iostream>

class Singleton {
public:
    static Singleton& Instance() {
        static Singleton p_Instance;
        //if (p_Instance == NULL)
        //    p_Instance = new Singleton();
        return p_Instance;
    }
    virtual void print(){
        std::cout << "Singleton " << std::endl;
    }
private:
    //static Singleton *p_Instance;
    Singleton(){}
    Singleton(const Singleton& ){}
    Singleton& operator=(Singleton const&){}
};

//Singleton* Singleton::p_Instance = NULL;

int main()
{
    Singleton::Instance().print();
    return 0;
}

发表于

Sort algorithms

冒泡排序

每次将最大的放在最后，代码：

1
2
3
4
5
6
7
8
9
void bubbleSort(vector<int>& arr)
{
    for (int i = 0; i < arr.size()-1; i++) {
        for (int j = 0; j < arr.size()-1-i; j++) {
            if (arr[j] > arr[j+1])
                swap(arr[j], arr[j+1]);
        }
    }
}

选择排序

整体比较，相对于冒泡排序，选择排序需要比较选择最小的放在前面，减少了交换次数。代码：

1
2
3
4
5
6
7
8
9
10
11
void selection_sort(vector<int>& arr)
{
    for (int i = 0; i < arr.size(); i++) {
        int min_idx = i;
        for (int j = i+1; j < arr.size(); j++) {
            if (arr[min_idx] > arr[j])
                min_idx = j;
        }
        swap(arr[min_idx], arr[i]);
    }
}

插入排序

插入排序类似于玩扑克牌，拿到一张牌，就把它插入到大小合适的位置，并保证其前面的牌已经按顺序排列好。代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
void insertion_sort(vector<int>& arr)
{
    int j;
    for (int i = 1; i < arr.size(); i++){
        int tmp = arr[i];
        j = i-1;
        while (j>=0&&tmp<arr[j]) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = tmp; 
    }
}

快速排序

来自于冒泡排序的思想，通过与基准比较，将小数排到一边，大数排到另外一遍。代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int partion(vector<int>& arr, int low, int high) 
{
    int pivot = arr[low];
    int pivotind = low;
    while (low < high) {
        while (low < high && arr[high] >= pivot) high--;
        while (low < high && arr[low] <= pivot) low++;
        swap(arr[low], arr[high]);
    }
    swap(arr[low], arr[pivotind]);
    return low;
}

void quick_sort(vector<int>& arr, int low, int high)
{
    if (low >= high) return;
    int pi = partion(arr, low, high);
    quick_sort(arr, low, pi-1);
    quick_sort(arr, pi+1, high);

}

##　归并排序

基于分而治之的思想，先递归划分成子问题，然后合并结果。简单来说就是先两两合并有序序列，然后再四四合并。。。

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
void merge(vector<int>& arr, int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    int lv[n1], rv[n2];
    for (i = 0; i < n1; i++)
        lv[i] = arr[l+i];
    for (j = 0; j < n2; j++)
        rv[j] = arr[m+1+j];
    
    k = l;
    i = j = 0;
    while (i < n1 && j < n2) {
        if (lv[i]<=rv[j])
            arr[k] = lv[i++];
        else
            arr[k] = rv[j++];
        k++;
    }

    while (i < n1) {
        arr[k] = lv[i++];
        k++;
    }
    while (j < n2) {
        arr[k] = rv[j++];
        k++;
    }
}

void merge_sort(vector<int>& arr, int l, int r)
{
    int m = l + (r - l) / 2;
    if (l < r) {
        merge_sort(arr, l, m);
        merge_sort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

堆排序

借助堆来实现选择排序，升序就用大顶堆，降序就用小顶堆。将有序数列建成堆，从第一个非叶元素开始依次建堆；调整成堆，每次将堆顶元素和最后一个元素交换，并调整堆。

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
void heapify(vector<int>& arr, int n, int root)
{
    int largest = root;
    int l = root * 2 + 1;
    int r = root * 2 + 2;
    if (l < n && arr[l]>arr[largest]) largest = l;
    if (r < n && arr[r]>arr[largest]) largest = r;

    if (largest != root) {
        swap(arr[largest], arr[root]);
        heapify(arr, n, largest);
    }
}

void heap_sort(vector<int>& arr, int n)
{
    for (int i = n / 2 - 1; i >=0; i--) {
        heapify(arr, n, i);
    }

    for (int i = n-1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

发表于

概念理解

  • 容器算法迭代器的关系

每个容器都有自己专属的迭代器，而算法则是通过迭代器来操作容器中的元素

容器通过模板实现，能够装下各种类型的元素

迭代是一种只能指针，通过*来解引用

  • 迭代器种类

5种：输入、输出、前向、双向、随机访问

  • 适配器种类

3种：容器适配器（例如stack，queue和priority_queue都是给予其它容器实现的）；迭代器适配器；函数适配器

sort算法

数据量大的时候选用快排，分段递归排序，一旦分段小于某个数据量之后采用的是插入排序。如果递归层次过深，又会转而调用堆排序。

发表于

基本概念

模板是一种支持参数化多态的工具，使得程序员能够编写与类型无关的代码

模板又分为两种：函数模板和类模板

模板特化

模板特化的提出是根据C++的设计，对于特定的类型，如果你能对某个功能有更好的实现，那么应该听你的。特化必须要在同一个命名空间下进行，函数模板只可以全特化（因为偏特化可以通过函数重载实现），而类模板则可以偏特化或者是全特化。

因此在模板实例化时，会优先匹配参数类型最匹配的那个特化版本。

  • 全特化

通过全特化模板，可以对某些特定参数集合自定义功能。此时模板参数为空。如：

1
2
3
4
5
6
7
8
9
10
11
12
//类模板
template <>
class A<int, double>{
    int data1;
    double data2;
};

//函数模板
template <>
int max(const int lhs, const int rhs) {  
    return lhs > rhs ? lhs : rhs;
}

注意：类模板需要在类名后面给出模板参数，而函数则不需要，它可以自动推导。

  • 偏特化

例如，针对vector进行偏特化

1
2
3
4
5
template <class T, class Allocator>
class vector { // … // };

template <class Allocator>
class vector<bool, Allocator> { //…//};

可变模板参数

这是C++11的新特性，支持模板的可变参数。可变模板参数的写法与原来有一点不同：

1
2
template <typename... T>
void f(T... args);

它需要在typename或者class后面加上省略号，带省略号的参数就是一个参数包，里面包含了０~N个参数。那么如何展开参数包呢？

两种方法

递归函数展开参数包

由于是递归调用，因此我们必须自定义递归的终止函数，保证其在参数为０时，停止递归。

1
2
3
4
5
6
7
8
9
10
11
12
//递归终止函数
void print()
{
   cout << "empty" << endl;
}
//展开函数
template <class T, class ...Args>
void print(T head, Args... rest)
{
   cout << "parameter " << head << endl;
   print(rest...);
}

逗号表达式展开参数包

不表

C++11中的std::tuple就是一个可变参数模板类

参考资料

http://harttle.land/2015/10/03/cpp-template.html

http://www.cnblogs.com/qicosmos/p/4325949.html

发表于

B+ 树

应用

在实际的数据库产品中，为了满足高效率的查找操作，我们需要实现某种索引来进行查找，索引又通常通过B+树或者B树去实现（一般不用红黑树）

为什么

考虑到索引文件一般也很大，不可能将它们全部存储在内存中，而是存储在磁盘上。又由于介质等原因的不同，磁盘的IO比主存的IO要慢很多。因此要想提高效率，必须要减少磁盘IO的次数。

为了达到这个目的，系统在发生缺页中断时都会直接读入一个block（page的整数倍）。假设B+树的高度为h，又因为通常设计成一个节点的大小对应于一个block，所以要查找特定的记录，最多只需要h次IO即可。

而红黑树的深度是远比B+树要高的，所以一般情况下都只会使用B+树

定义

一颗M阶B+树的定义

  • 根节点只有一个，子树有[2, m]

  • 除了根节点之外的非叶子节点，包含的子树为[[m/2],m]

  • 所有非根节点的key数目为[[m/2], m]

  • 叶子节点都在同一层，叶子节点才含有key的信息，其它只是索引

  • 所有非叶子节点的key等于其子数中最大或者最小的key

操作

插入时判断其是否不满足定义，按需进行分解操作

删除时判断其是否不满足定义，按需进行合并操作v

发表于

内存分配的５个区域

  • 堆

由操作符new分配的空间，它们的释放不由编译器管理，需要程序员手动释放，或者在程序结束时由操作系统回收释放。

  • 栈

一般存储局部变量和函数参数，由编译器去分配

  • 自由存储区

与堆类似，但它是由malloc

  • 静态存储区

在C++中，全局变量和静态变量都存储在这

  • 常量存储区

比较好理解，就是存储常量的区域

堆和栈的区别

  • 堆是由程序员控制的，而栈是由编译器控制的

  • 堆的空间大小一般为4G，而栈相对较小，比如１M

  • 堆有可能产生碎片，而栈是先进后出的模式，不会产生碎片

  • 堆是自下往上，往高地址生长的；而栈则相反

  • 栈分配效率较高，只需要从寄存器中找到存放栈的地址；而堆比较麻烦，需要通过一定的算法找到内存大小合适的空间（链表），或者因为碎片太多，先进行压缩抖动等

引用自： http://www.cnblogs.com/daocaoren/archive/2011/06/29/2092957.html

发表于

开始看这本神书，做一些笔记：

简单对象模型

第一个模型很简单，一个对象是由一系列slots组成，但是成员（对象和函数）都不是放在对象内的，而是把指针放在对象内，通常来说这不被应用于实际产品。

img

表格驱动对象模型

存储两个指针，分别指向data member table和function member table

img

C++对象模型

来看看重头戏——C++对象模型。有几个需要注意的：

  • 非静态数据成员放在类的对象中；

  • 静态数据成员和成员函数放在类对象之外；

  • 至于虚函数，则需要从类和对象两个方面考虑：每一个类都会有一个相关联的虚函数表；每一个对象都会有一个指针指向虚函数表，而表中的第一个slot通常是type_info object；

img

发表于

C++ class size

首先来看这个：

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
#include <iostream>

using namespace std;

class EmptyClass {

};

class intClass {
    private:
        int i;
};

class deriveClass : public intClass {

};

class AbstractClass {
    public:
        virtual void func() = 0;
};

class NotAbstractClass {
    public:
        void func();
};

class WithStaticClass {
    public:
        static int i;
        void func();
};

class CharClass {
    public:
        char c[7];
};

int main()
{
    cout << "EmptyClass size: " << sizeof(EmptyClass) << endl;
    cout << "intClass size: " << sizeof(intClass) << endl;
    cout << "deriveClass size: " << sizeof(deriveClass) << endl;
    cout << "AbstactClass size: " << sizeof(AbstractClass) << endl;
    cout << "NotAbtractClass size: " << sizeof(NotAbstractClass) << endl;
    cout << "WithStatic size: " << sizeof(WithStaticClass) << endl;
    cout << "CharClass size: " << sizeof(CharClass) << endl;
}

//结果：
/*
EmptyClass size: 1
intClass size: 4
deriveClass size: 4
AbstactClass size: 8
NotAbtractClass size: 1
WithStatic size: 1
CharClass size: 7
*/

类的大小有几点规则：

  • 为类的成员变量大小之和，同时需要满足一些对齐要求（例如上面的例子中对齐为１个字节）

  • 编译器额外加入的大小，例如虚函数的指针，虚继承，多重继承

  • 与类的构造析构和成员函数无关

  • 继承计算大小时会把私有变量计算在内

注意

1
2
3
4
5
6
class AbstractClass {
    public:
        virtual void func() = 0;
        char c[3];
};
//结果为１６
  • 虚继承：虚继承除了加上父类的大小之外，还需要一个指针指向虚基类，同时考虑对齐，例如：
1
2
3
4
5
6
7
8
9
class intClass {
    private:
        int i;
};

class deriveClass : virtual intClass {

};
//结果是16