那时候感觉Computer算法还是有一点像数学.

// 堆排序
void sort_heap(int a[], int len);

// 返回分隔的文件数
static int _data_split_sort(FILE * txt, int a[], int len) {
    int i, n, rt = 1, ti = 0;
    char npath[255];
    FILE * ntxt;

    do {
        // 得到数据
        for (n = 0; n < len; ++n) {
            rt = fscanf(txt, "%d\n", a + n);
            if (rt != 1) {
                // 读取已经结束
                break;
            }
        }

        if (n == 0)
            break;

        // 开始排序
        sort_heap(a, n);

        // 输出到文件中
        snprintf(npath, sizeof npath, "%d_%s", ++ti, _STR_DATA);
        ntxt = fopen(npath, "wb");
        if (NULL == ntxt) {
            fprintf(stderr, "fopen wb npath = %s error!\n", npath);
            exit(EXIT_FAILURE);
        }
        for (i = 0; i < n; ++i)
            fprintf(ntxt, "%d\n", a[i]);
        fclose(ntxt);
    } while (rt == 1);

    return ti;
}

quick sort + small insert sort. 那高速排序是怎么着子呢,
看如下一种高效落到实处

堆排序单独讲一节, 在于它在基础件开采应用中拾壹分布满.
举例有个别机械漏刻选择小顶堆结构完结,

正文 – 来个实际的向外排水序案例

以上便是大家常被面试进程中问及的大数据瞎搞难题, 一种简陋的减轻方案.
当然事情远远才刚刚先导!

攻下系统函数栈, 单独分出来, 系统占用的栈大小小一点. 微小进步安全性.
看到此间, 希望今后境遇别人

 

 

  等自作者归家 
– http://music.163.com/\#/song?id=477890886

  这段日子很向往陈胜吴广, 未来深不可测. 如果大家都以直男癌,
一定毫无忘记有过的血气方刚 ~  

末段收获数码 output.txt

前言 – 来个诡异的堆排序

 

View Code

切割成八份, 每份也就仿佛200MB. 完整的构建代码如下

  scrand
https://github.com/wangzhione/simplec/blob/master/simplec/module/schead/scrand.c

*  图片 1*

后记 – 等自个儿回家

   本文子禽举一些实施中排序所用的地点, 分析那一个年用过的排序套路, 
这里先来个插入排序

有时机单独开文扯随机算法, 水也很深.
究竟随机算法是一个钱打二十几个结机史上十大首要算法, 排序也是.

它是从redis上拔下来深加工的私自算法, 质量和随机性方面比系统提供的要好.
最大的需借使平台一致性.

图片 2图片 3

如上是拍卖的总流程, 对于构建和销毁部分显得在底下

#define _STR_DATA        "data.txt"
// 28 -> 1.41 GB (1,519,600,600 字节) | 29 -> 2.83 GB (3,039,201,537 字节)
#define _UINT64_DATA    (1ull << 28)

static FILE * _data_rand_create(const char * path, uint64_t sz) {
    FILE * txt = fopen(path, "wb");
    if (NULL == txt) {
        fprintf(stderr, "fopen wb path error = %s.\n", path);
        exit(EXIT_FAILURE);
    }

    for (uint64_t u = 0; u < sz; ++u) {
        int num = rand();
        fprintf(txt, "%d\n", num);
    }

    fclose(txt);
    txt = fopen(path, "rb");
    if (NULL == txt) {
        fprintf(stderr, "fopen rb path error = %s.\n", path);
        exit(EXIT_FAILURE);
    }

    return txt;
}

都打包的那么好了. n年后懂了点, 学那是为了用的, 哪有何目标,
有的是月落日升, 风吹云动~ _φ( °-°)/

1 – 8 _data.txt 数据是相隔排序后输出数据.
随后载开端拍卖数据实行外排序输出最后结果文件.

// 大顶堆中加入一个父亲结点索引, 重新构建大顶堆
static void _sort_heap_adjust(int a[], int len, int p) {
    int node = a[p];
    int c = 2 * p + 1; // 先得到左子树索引
    while (c < len) {
        // 如果有右孩子结点, 并且右孩子结点值大, 选择右孩子
        if (c + 1 < len && a[c] < a[c + 1])
            c = c + 1;

        // 父亲结点就是最大的, 那么这个大顶堆已经建立好了
        if (node > a[c])
            break;

        // 树分支走下一个结点分支上面
        a[p] = a[c];
        p = c;
        c = 2 * c + 1;
    }
    a[p] = node;
}

// 堆排序
void 
sort_heap(int a[], int len) {
    int i = len / 2;
    // 线初始化一个大顶堆出来
    while (i >= 0) {
        _sort_heap_adjust(a, len, i);
        --i;
    }

    // n - 1 次调整, 排好序
    for (i = len - 1; i > 0; --i) {
        int tmp = a[i];
        a[i] = a[0];
        a[0] = tmp;

        // 重新构建堆数据
        _sort_heap_adjust(a, i, 0);
    }
}
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

//
// 大数据排序数据验证
//
int main(int argc, char * argv[]) {
    int tl;
    FILE * txt = fopen(_STR_DATA, "rb");

    puts("开始构建测试数据 _data_rand_create");
    // 开始构建数据
    if (NULL == txt)
        txt = _data_rand_create(_STR_DATA, _UINT64_DATA);

    puts("数据已经到位, 开始分隔数据进行排序");
    tl = _data_txt_sort(txt);
    fclose(txt);

    // 这里分拨的数据构建完毕, 开始外排序过程

    return EXIT_SUCCESS;
}

迅猛获得近年来内需实施的结点. 堆结构也能够用于向外排水序.
还会有堆在管理范围内极值难题特意有效.

第一步操作切割数据, 分别保存在一定种类文件中

上述正是数额营造进度. 要多大只必要调节宏大小. 太大日子有个别长.
管理难点的思绪是

那边科学普及一下为什么把 _sort_quick_partition 单独包装出来. 主要缘由是
_sort_quick 是个递归函数,

试行上边切割代码, 最后生成会得到如下数据内容

而是脑英里常思虑同类难题,
那有哪些用吧(土冒实践派对装B高校派的敬意鄙视). 不恐怕让您去写.

#define _INT_TXTCNT    (8)

static int _data_txt_sort(FILE * txt) {
    char npath[255];
    FILE * ntxt;
    // 需要读取的数据太多了, 直接简单监测一下, 数据是够构建完毕
    snprintf(npath, sizeof npath, "%d_%s", _INT_TXTCNT, _STR_DATA);
    ntxt = fopen(npath, "rb");
    if (ntxt == NULL) {
        int tl, len = (int)(_UINT64_DATA / _INT_TXTCNT);
        int * a = malloc(sizeof(int) * len);
        if (NULL == a) {
            fprintf(stderr, "malloc sizeof int len = %d error!\n", len);
            exit(EXIT_FAILURE);
        }

        tl = _data_split_sort(txt, a, len);

        free(a);

        return tl;
    }

    return _INT_TXTCNT;
}

双重输出 1<<28回, 二十四位 -> 1.41 GB (1,519,600,600 字节) 字节.

总的套路能够看成下边那样数组索引 [0, 1, 2, 3, 4, 5, 6, 7, 8] – >

void 
output_delete(struct output * put) {
    if (put) {
        for (int i = 0; i < put->cnt; ++i)
            fclose(put->a[i].txi);
        free(put);
    }
}

struct output * 
output_create(int cnt, const char * path) {
    FILE * ntxt;
    struct output * put = malloc(sizeof(struct output) + cnt * sizeof(struct node));
    if (NULL == put) {
        fprintf(stderr, "_output_init malloc cnt = %d error!\n", cnt);
        exit(EXIT_FAILURE);
    }

    put->cnt = 0;
    for (int i = 0; i < cnt; ++i) {
        char npath[255];
        // 需要读取的数据太多了, 直接简单监测一下, 数据是够构建完毕
        snprintf(npath, sizeof npath, "%d_%s", _INT_TXTCNT, _STR_DATA);
        ntxt = fopen(npath, "rb");
        if (ntxt) {
            put->a[put->cnt].txi = ntxt;
            // 并初始化一下数据
            if (_node_read(put->a + put->cnt))
                fclose(ntxt);
            else
                ++put->cnt;
        }
    }

    // 这种没有意义, 直接返回数据为empty
    if (put->cnt <= 0) {
        free(put);
        exit(EXIT_FAILURE);
    }

    // 构建数据
    ntxt = fopen(path, "wb");
    if (NULL == ntxt) {
        output_delete(put);
        fprintf(stderr, "fopen path cnt = %d, = %s error!\n", cnt, path);
        exit(EXIT_FAILURE);
    }
    put->out = ntxt;

    return put;
}

  一早先介绍插入排序,  主要为了介绍系统内置的良莠不齐排序算法 qsort. qsort
多数落到实处是

顺带扯一点地方出现系统随机函数 rand, 不要紧再多说一点,
上边是近年来写的49人随机算法 scrand

  这里不要紧来消除地点这一个标题, 首先是构建数据. 假定’大数据’为 data.txt.
一个 int 加 char 类型,

// 插入排序
void 
sort_insert(int a[], int len) {
    int i, j;

    for (i = 1; i < len; ++i) {
        int tmp = a[i];
        for (j = i; j > 0; --j) {
            if (tmp >= a[j - 1])
                break;
            a[j] = a[j - 1];
        }
        a[j] = tmp;
    }
}

单元测量检验(白盒测量试验)是工程质量的保证, 不然要好都大吃一惊本人的代码.
软件功底2成在于测量检验功力是不是到位.

宗旨排序算法 output_sort ,

unsafe code 很要求测验框架, 这里为本文轻易写了个测验套路如下

   堆排序的笔触好神奇, 营造二叉树’回忆’的习性来管理排序进度中的有序性.
它是冒泡排序的极品进化. 

void array_rand(int a[], int len);
void array_print(int a[], int len);

//
// ARRAY_TEST - 方便测试栈上数组, 关于排序相关方面
//
#define ARRAY_TEST(a, fsort) \
    array_test(a, sizeof(a) / sizeof(*(a)), fsort)

inline void array_test(int a[], int len, void(* fsort)(int [], int)) {
    assert(a && len > 0 && fsort);
    array_rand(a, len);
    array_print(a, len);
    fsort(a, len);
    array_print(a, len);
}

// 插入排序
void sort_insert(int a[], int len);

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

#define _INT_ARRAY    (64)
//
// test sort base, sort is small -> big
//
int main(int argc, char * argv[]) {
    int a[_INT_ARRAY];

    // 原始数据 + 插入排序
    ARRAY_TEST(a, sort_insert);

    return EXIT_SUCCESS;
}

#define _INT_RANDC (200)
void 
array_rand(int a[], int len) {
    for (int i = 0; i < len; ++i)
        a[i] = rand() % _INT_RANDC;
}
#undef _INT_SORTC

#define _INT_PRINT (26)
void 
array_print(int a[], int len) {
    int i = 0;
    printf("now array[%d] current low:\n", len);
    while(i < len) {
        printf("%4d", a[i]);
        if (++i % _INT_PRINT == 0)
            putchar('\n');
    }
    if (i % _INT_PRINT)
        putchar('\n');
}
#undef _INT_PRINT

引言 – 从最简易的插入排序开始

/*
 问题描述:
      存在个大文件 data.txt , 保存着 int \n ... 这种格式数据. 是无序的.
 目前希望从小到大排序并输出数据到 ndata.txt 文件中

 限制条件: 
      假定文件内容特别多, 无法一次加载到内存中.     
      系统最大可用内存为 600MB以内.
 */

末端大家会选取堆排序来管理个大文件向外排水序难题.

聊基础也能扯几句了,  高效的操作许多是应情形而多样办法的组合取舍.
突然感觉大家还是能够翻~

// 28 -> 1.41 GB (1,519,600,600 字节) | 29 -> 2.83 GB (3,039,201,537 字节)
#define _UINT64_DATA    (1ull << 28)

// 开始排序构建
void 
output_sort(struct output * put) {
    int i, cnt;
    uint64_t u = 0;
    assert(put && put->cnt > 1);

    cnt = put->cnt;
    // 开始构建小顶堆
    i = cnt / 2;
    while (i >= 0) {
        _node_minheap(put->a, cnt, i);
        --i;
    }

    while (cnt > 1) {
        ++u;
        // 输出数据, 并且重新构建数据
        fprintf(put->out, "%d\n", put->a[0].val);
        if (_node_read(put->a)) {
            --cnt;
            // 交换数据, 并排除它
            struct node tmp = put->a[0];
            put->a[0] = put->a[cnt];
            put->a[cnt] = tmp;
        }
        _node_minheap(put->a, cnt, 0);
    }

    // 输出最后文件内容, 输出出去
    do {
        ++u;
        fprintf(put->out, "%d\n", put->a[0].val);
    } while (!_node_read(put->a));

    printf("src = %llu, now = %llu, gap = %llu.\n", _UINT64_DATA, u, _UINT64_DATA - u);
}
// 快速排序
void sort_quick(int a[], int len);

// 快排分区, 按照默认轴开始分隔
static int _sort_quick_partition(int a[], int si, int ei) {
    int i = si, j = ei;
    int par = a[i];
    while (i < j) {
        while (a[j] >= par && i < j)
            --j;
        a[i] = a[j];

        while (a[i] <= par && i < j)
            ++i;
        a[j] = a[i];
    }
    a[j] = par;
    return i;
}

// 快速排序的核心代码
static void _sort_quick(int a[], int si, int ei) {
    if (si < ei) {
        int ho = _sort_quick_partition(a, si, ei);
        _sort_quick(a, si, ho - 1);
        _sort_quick(a, ho + 1, ei);
    }
}

// 快速排序
inline void 
sort_quick(int a[], int len) {
    _sort_quick(a, 0, len - 1);
}

 

图片 4

    1. 数据切割成合适份数N
    2. 每份内排序, 从小到大, 并输出到特定文件中
    3. 采用N大小的小顶堆, 挨个读取并输出, 记录索引
    4. 那个索引文件输出, 那个索引文件输入, 最终输出一个排序好的文件

插入排序在Mini数据排序中很常用! 也是链式结构首推排序算法.
插入排序顶尖进化 -> Hill排序, O(∩_∩)O哈哈~.

学生阶段面试吹一波感觉是足以了~ 扯一点, 年轻时候多吹一点NB,
以往也就只赏心悦目着外人~

0, 1, 2 三个二叉树, 1, 3, 4 二个二叉树, 2, 5, 6一个二叉树, 3, 7, 8
多少个树枝.  直接看代码, 感悟在此之前神的毅力

struct node {
    FILE * txi;    // 当前是那个文件的索引
    int val;    // 读取的值
};

// true表示读取完毕, false可以继续读取
static bool _node_read(struct node * n) {
    assert(n && n->txi);
    return 1 != fscanf(n->txi, "%d\n", &n->val);
}

// 建立小顶堆
static void _node_minheap(struct node a[], int len, int p) {
    struct node node = a[p];
    int c = 2 * p + 1; // 先得到左子树索引
    while (c < len) {
        // 如果有右孩子结点, 并且右孩子结点值小, 选择右孩子
        if (c + 1 < len && a[c].val > a[c + 1].val)
            c = c + 1;

        // 父亲结点就是最小的, 那么这个小顶堆已经建立好了
        if (node.val < a[c].val)
            break;

        // 树分支走下一个结点分支上面
        a[p] = a[c];
        p = c;
        c = 2 * c + 1;
    }
    a[p] = node;
}

struct output {
    FILE * out;    // 输出数据内容
    int cnt;    // 存在具体多少文件内容
    struct node a[];
};

// 数据销毁和构建初始化
void output_delete(struct output * put);
struct output * output_create(int cnt, const char * path);
// 开始排序构建
void output_sort(struct output * put);

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

#define _INT_TXTCNT        (8)
#define _STR_DATA        "data.txt"
#define _STR_OUTDATA    "output.txt"

//
// 对最终生成数据进行一种外排序尝试
//
int main(int argc, char * argv[]) {
    // 构建操作内容
    struct output * put = output_create(_INT_TXTCNT, _STR_OUTDATA);

    output_sort(put);

    // 数据销毁
    output_delete(put);
    return EXIT_SUCCESS;
}

  很久很久从前, 只怕都曾学过那么些常用的排序算法.
那时候以为电脑算法依然有一点像数学.

图片 5

相关文章