记一次编程比赛

编程题目如下：

实现如下功能：
步骤1、提供一个函数，实现生成指定长度范围的字符串，长度为随机的10-60字节（含10和60），每个字符串的内容为小写的'a'-'z'中随机选择。
步骤2、初始化一个有1000万个单元的数组，每个数组单元指向一个步骤1中随机生成的字符串。
步骤3、开始计时1
将步骤2中的1000万个随机字符串（作为key，value是8字节的整数，存放字符串的CRC32哈希值）插入到自己实现的哈希表中（不得用指针指向步骤2中的字符串，哈希表中需要自己存储字符串副本），
结束计时1，记录插入完成所有1000万个单元所需的时间T1。
步骤4、开始计时2
查询数组中1000万个单元对应的字符串在哈希表中的VALUE（不得直接基于CRC32来获取，必须通过哈希表来查找到），
结束计时2，记录完成1000万次查询所需的时间T2。

所有开发人员参加，其他人员可自主决定是否参加，编程语言不限。结果需保证正确，
取T1+T2总和最小的前6名，进入最终排名，性能占比60%，内存资源占用40%，如假定最快10秒完成得60分，则20秒得30分，内存最小占用100M，得40分，则200M得20分，以此类推。
不得使用数据压缩来降低内存消耗。

乔阳准备一台LINUX X86作为对比平台，支持C/C++、JAVA、GO等编译运行环境。

// hashtablepro.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <time.h>
#include <random>
#include <string.h>
#include <thread>
#include <atomic>
#ifdef WIN32
#include "windows.h"
#else
#include <time.h>
#include <sys/time.h>
#endif

#define CRC32_POLYNOMIAL            0xEDB88320

#define N_THREAD         80

#ifdef WIN32
typedef __int64          sint64;
typedef unsigned __int64 uint64;
#else
typedef long long int          sint64;
typedef unsigned long long int uint64;
#endif

typedef struct hashnode hnode;
typedef struct hashtable htable;
typedef struct task itask;

struct hashnode
{
    char* key;
    unsigned int crc;

    hnode* next;
};

struct hashtable
{
    void** array;
    int cap, size;
};

struct task
{
    int type;
    int index;
    int batch;
};

using namespace std;

int    g_asize = 10000000;
char** g_array = NULL;
void** g_hnode = NULL;

hashtable*        g_ht[1000] = { 0 };
itask*            g_tsk[1000] = { 0 };
std::atomic<int>  counter(0);
int               exit_flag = 0;

/////////////////////////////crc32 module////////////////////////////////////////

unsigned int get_crc32(const char *msg)
{
    int crc = 0xFFFFFFFF;
    int i, j, len = strlen(msg);

    for (i = 0; i < len; i++) {
        crc ^= msg[i];
        for (j = 0; j < 8; j++) {
            if (crc & 0x01)
                crc = (crc >> 1) ^ CRC32_POLYNOMIAL;
            else
                crc = crc >> 1;
        }
    }

    return (unsigned int)(crc ^ 0x7FFFFFFF);
}

/////////////////////////////hashtable module////////////////////////////////////////

hashtable* hashtable_init(int size)
{
    hashtable* ht;
    int cap = (int)(size * 1.19);

    ht = (hashtable*)malloc(sizeof(hashtable) + sizeof(void*) * cap);
    ht->array = (void**)(ht + 1);
    ht->size = 0;
    ht->cap = cap;
    for (int i = 0; i < cap; i++)
    {
        ht->array[i] = NULL;
    }

    return ht;
}

void hashtable_deinit(hashtable* ht)
{
    int i;
    hashnode* node;
    hashnode* next = NULL;

    // to release each bucket
    for (i = 0; i < ht->cap; i++)
    {
        node = (hashnode*)ht->array[i];
        while (node)
        {
            next = node->next;
            free(node);
            node = next;
        }
    }

    free(ht);
}

hashnode* hashnode_get(const char* key)
{
    hashnode* hn;

again:
    hn = (hashnode*)malloc(sizeof(hashnode) + strlen(key) + 1);
    if (!hn) goto again;

    hn->crc = get_crc32(key);
    hn->next = NULL;
    hn->key = (char*)(hn + 1);

    strcpy(hn->key, key);

    return hn;
}

int hashtable_insert(hashtable* ht, int i, const char* key)
{
    int index;
    hashnode* cell = NULL;
    //hashnode* hn = hashnode_get(key);
    hashnode* hn = (hashnode*)g_hnode[i];

    index = hn->crc % ht->cap;
    cell = (hashnode*)ht->array[index];
    if (!cell)
    {
        ht->array[index] = hn;
    }
    else
    {
        hn->next = cell;
        ht->array[index] = hn;
    }
    
    ht->size++;
    return 0;
}

int hashtable_get(hashtable* ht, const char* key)
{
    hashnode* cell = NULL;
    int crc = -1;
    int index = get_crc32(key) % ht->cap;

    cell = (hashnode*)ht->array[index];

    while (cell)
    {
        if (strcmp(key, cell->key) == 0)
        {
            crc = cell->crc;
            break;
        }

        cell = cell->next;
    }
    
    return crc;
}

/////////////////////////////phase module////////////////////////////////////////

char* phase_i_gen_string()
{
    int len = rand() % 51 + 10;
    int i;
    char* str = (char*)malloc(len + 1);
    str[len] = '\0';

    for (i = 0; i < len; i++)
    {
        str[i] = rand() % 26 + 'a';
    }

    return str;
}

int phase_ii_gen_array()
{
    int i, count = g_asize;
    hashnode* hn;
    if (!g_array)
    {
        g_array = (char**)malloc(sizeof(char*) * count);
        g_hnode = (void**)malloc(sizeof(void*) * count);
    }
    for (i = 0; i < count; i++)
    {
        g_array[i] = phase_i_gen_string();
        g_hnode[i] = (void*)malloc(sizeof(hashnode) + strlen(g_array[i]) + 1);
        hn = (hashnode*)g_hnode[i];
        {
            hn->crc = get_crc32(g_array[i]);
            hn->next = NULL;
            hn->key = (char*)(hn + 1);
            strcpy(hn->key, g_array[i]);
        }
        // std::cout << g_array[i] << std::endl;
    }

    return 0;
}

int phase_iii_hashtable_put(hashtable* ht)
{
    int i;

    for (i = 0; i < g_asize; i++)
    {
        hashtable_insert(ht, i, g_array[i]);
    }
    
    std::cout << "input " << ht->size << " entry.\n";
    return ht->size;
}

void hashtable_put_run(int ithread, int index, int size)
{
    hashtable* ht;
    int        last = index + size;
    
    if (ithread == N_THREAD - 1)
    {
        size = g_asize - index;
        last = index + size;
    }

    ht = hashtable_init(size);

    for (int i = index; i < last; i++)
    {
        hashtable_insert(ht, i, g_array[i]);
    }

    g_ht[ithread] = ht;
    return ;
}

int phase_iii_hashtable_put_ex()
{
    int i;
    int batch = g_asize / N_THREAD;
    if (g_asize % N_THREAD)
    {
        batch += batch / N_THREAD;
    }

    std::vector<std::thread> vec_thrd;

    for (i = 0; i < N_THREAD; i ++)
    {
        vec_thrd.push_back(std::thread(hashtable_put_run, i, i * batch, batch));
    }

    for (std::thread& t : vec_thrd)
    {
        t.join();
    }

    return 0;
}

int phase_iii_hashtable_put_max()
{
    itask task[N_THREAD];
    int batch = g_asize / N_THREAD;
    int count = N_THREAD;
    
    if (g_asize % N_THREAD)
    {
        batch += batch / N_THREAD;
    }

    for (int i = 0; i < N_THREAD; i++)
    {
        task[i].type  = 0;
        task[i].index = i * batch;
        task[i].batch = batch;

        g_tsk[i] = &task[i];
        counter.fetch_add(1);
    }

    std::this_thread::sleep_for(std::chrono::milliseconds(100));

    while (counter.fetch_add(0))
    {
        std::this_thread::sleep_for(std::chrono::microseconds(100));
    }

    return 0;
}

int phase_iv_hashtable_get(hashtable* ht, char** array, int size, int** crc_arr)
{
    int* hc_arr;
    int i;

    hc_arr = (int*)malloc(sizeof(int) * size);
    for (i = 0; i < size; i++)
    {
        hc_arr[i] = hashtable_get(ht, array[i]);
    }
    *crc_arr = hc_arr;
    return 0;
}

int hashtable_get_run(int ithread, int index, int batch)
{
    int last = index + batch;
    int crc;

    if (ithread == N_THREAD - 1)
    {
        last = g_asize - index;
    }

    for (int i = index; i < last; i++)
    {
        crc = hashtable_get(g_ht[ithread], g_array[i]);
//             if (crc_arr[i] != get_crc32(g_array[i]))
//             {
//                 printf("error.\n");
//             }
    }
    return 0;
}

int phase_iv_hashtable_get_max()
{
    itask task[N_THREAD];
    int batch = g_asize / N_THREAD;

    if (g_asize % N_THREAD)
    {
        batch += batch / N_THREAD;
    }

    for (int i = 0; i < N_THREAD; i++)
    {
        task[i].type = 1;
        task[i].index = i * batch;
        task[i].batch = batch;

        g_tsk[i] = &task[i];
        counter.fetch_add(1);
    }

    std::this_thread::sleep_for(std::chrono::milliseconds(100));

    while (counter.fetch_add(0))
    {
        std::this_thread::sleep_for(std::chrono::microseconds(100));
    }

    return 0;
}

int phase_iv_hashtable_get_ex(int* crc_arr)
{
    std::vector<std::thread> vec_thrd;
    int batch = g_asize / N_THREAD;
    if (g_asize % N_THREAD)
    {
        batch += batch / N_THREAD;
    }

    for (int i = 0; i < N_THREAD; i++)
    {
        vec_thrd.push_back(std::thread(hashtable_get_run, i, i * batch, batch));
    }

    for (std::thread& t : vec_thrd)
    {
        t.join();
    }

    return 0;
}


void hashtable_run(int ithread)
{
    itask*  task;

    while (1)
    {
        if (exit_flag)
            break;

        task    = g_tsk[ithread];
        if (!task)
        {
            std::this_thread::sleep_for(chrono::microseconds(200));
            continue;
        }

        if (!task->type)
        {
            hashtable_put_run(ithread, task->index, task->batch);
        }
        else
        {
            hashtable_get_run(ithread, task->index, task->batch);
        }

        g_tsk[ithread] = NULL;
        counter.fetch_sub(1);
    }

    return;
}


uint64 get_tick()
{
#ifdef WIN32
    return GetTickCount();
#else
    struct timeval tm;
    gettimeofday(&tm, NULL);
    return tm.tv_sec * 1000 + tm.tv_usec / 1000;
#endif
}

int main()
{
    hashtable* htable;
    int*    crc_vec;
    uint64  t1, t2, t3;
    char    mode;
    std::vector<std::thread> vec_thrd;

    std::cout << "Ready Go...\n";

    std::cout << "run mode, s, m, x.\n";
    mode = getchar();

    srand((unsigned int)time(NULL));

    htable = hashtable_init(g_asize);

    crc_vec = (int*)malloc(sizeof(int) * g_asize);

    std::cout << "phase ii start.\n";
    phase_ii_gen_array();

    for (int i= 0; i < N_THREAD; i++)
    {
        vec_thrd.push_back(std::thread(hashtable_run, i));
    }

    t1 = get_tick();
    std::cout << "phase iii start at " << t1 << ".\n";

    if (mode == 'm')
        phase_iii_hashtable_put_ex();
    else if (mode == 'x')
        phase_iii_hashtable_put_max();
    else
        phase_iii_hashtable_put(htable);

    t2 = get_tick();
    std::cout << "phase iv start at " << t2 << ".\n";

    if (mode == 'm')
        phase_iv_hashtable_get_ex(crc_vec);
    else if (mode = 'x')
        phase_iv_hashtable_get_max();
    else
        phase_iv_hashtable_get(htable, g_array, g_asize, &crc_vec);

    t3 = get_tick();
    std::cout << "phase iv finish at " << t3 << ".\n";

    std::cout << "put spent " << t2 - t1 << "ms\n";
    std::cout << "get spent " << t3 - t2 << "ms.\n";

    while (1)
    {
        char c = getchar();
        if (c == 'e')
        {
            exit_flag = 1;

            for (std::thread& t : vec_thrd)
            {
                t.join();
            }

            std::cout << "Game Over!\n";
            break;
        }

        continue;
    }

    return 0;
}

获得第三名，还算过得去。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,634评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,951评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 161,427评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,770评论 1赞 290
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,835评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,799评论 1赞 294
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,768评论 3赞 416
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,544评论 0赞 271
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,979评论 1赞 308
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,271评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,427评论 1赞 345
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,121评论 5赞 340
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,756评论 3赞 324
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,375评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,579评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,410评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,315评论 2赞 352