后端系统开发之面试和工作中的map

xiaoxiao2021-03-01  27

map是C++ STL中的关联容器,存储的是键值对(Key-Value),可以通过key快速索引到value。map容器中的数据是自动排序的,其排序方式是严格的弱排序(stick weak ordering),即在判断Key1和Key2的大小时,使用“<”而不是“<=”。map 使用二叉搜索树实现,STL map的底层实现是红黑树。

map有几个值得注意的地方:map的赋值运算是深拷贝,即调用map_a = map_b后,map_a中的元素拥有独立的内存空间。map[]运算比较有意思,当元素不存在的时候会插入新的元素;在map中查找key是否存在时可以用find或count方法,find查找成功返回的是迭代器,查找失败则返回mymap.end(),说明该key不存在;map中的key不允许重复,其count方法只能返回0或1。

map可以做什么?来看一个非常经典的算法面试题:有一个包含100万个整数的大文件,文件的每一行都是一个int型数字,那么如何找到其中出现次数最多的10个数?

从数据存储方面分析,通常一个int是4个字节,100万个int约为4MB字节。在处理这个问题时,需要记录每个整数出现的次数,次数也用一个int来存储,因此总共需要约8MB字节的内存。从数据处理方面分析,可以用一个Key和Value都为int的map容器来存储数据,通过逐行扫描文件,将文件中的整数作为key保存到map中,对应的value为其在文件中出现次数,这样就完成了数据输入。

对于求N个数中的最大K个数问题,是典型的top K问题,其解决方案是利用一个大小为K的数组构建小顶堆,然后依次对N个数中的元素和堆顶元素做比较,如果满足条件则替换堆顶元素,并重新构建小顶堆,否则处理下一个数据。待所有数据都处理完毕后,小顶堆中的数据集合即为最大的K个数,最后通过堆排序输出即可。

Talk is cheap,show me the code。

#include <string> #include <vector> #include <map> #include <algorithm> // make_heap算法 #include <cstdio> #include <string.h> #include <sys/time.h> // 从文件中读取ID值,保存到map中 int ReadDataFile(const std::string &file_name, std::map<int, int> &map_result) { FILE *fp = fopen(file_name.c_str(), "r"); if (fp == NULL) { perror("Open file fail"); return -1; } map_result.clear(); char buf[100]; int id; while (true) { memset(buf, 0, sizeof(buf)); if (fgets(buf, sizeof(buf), fp) == NULL) { break; } id = atoi(buf); ++map_result[id]; // 记录ID出现次数 } fclose(fp); return 0; } // 最终结果 typedef struct Result { int id; // ID值 int times; // 该ID值出现的次数 Result() { id = 0; times = 0; } // 根据ID出现次数比较大小 bool operator>(const Result &other) const { return times > other.times; } }Result; // 从map中获取top k的值,并保存到存储Result对象的vector容器中 void GetTopK(std::map<int, int> &map_result, std::vector<Result> *final_result, int k) { // k值可能比map_result中的元素个数要多 size_t min_k = std::min((int)map_result.size(), k); std::vector<Result> heap; heap.resize(min_k); // 创建一个小顶堆,即出现次数最少的ID在堆顶位置 // make_heap默认创建的是大顶堆,第三个参数是less std::make_heap(heap.begin(), heap.end(), std::greater<Result>()); Result tmp; for (auto &it : map_result) { tmp.times = it.second; // 只需要处理ID出现次数大于堆顶位置元素的情况 if (tmp.times < heap[0].times) { continue; } tmp.id = it.first; heap[0] = tmp; std::make_heap(heap.begin(), heap.end(), std::greater<Result>()); } std::sort_heap(heap.begin(), heap.end(), std::greater<Result>()); final_result->clear(); final_result->swap(heap); } // 直接排序 void DirectSort(std::map<int, int> &map_result, std::vector<Result> *final_result, int k) { std::vector<Result> result; Result tmp; for (auto &it : map_result) { tmp.id = it.first; tmp.times = it.second; result.push_back(tmp); } std::sort(result.begin(), result.end(), std::greater<Result>()); final_result->clear(); final_result->swap(result); // k值可能比map_result中的元素个数要多 size_t min_k = std::min((int)map_result.size(), k); final_result->resize(min_k); } // 获取微秒时间 long GetUsTime() { struct timeval tv; gettimeofday(&tv, NULL); return tv.tv_sec * 1000000 + tv.tv_usec; } int main(int argc, char **argv) { // 读取文件数据并保存到map const std::string file_name = "test.data"; std::map<int, int> map_result; int ret = ReadDataFile(file_name, map_result); if (ret < 0) { printf("ERROR: ReadDataFile fail\n"); return -1; } printf("map_result size:%lu\n", map_result.size()); // 获取出现次数最多的10个ID值 std::vector<Result> final_result; long start = GetUsTime(); GetTopK(map_result, &final_result, 10); long end = GetUsTime(); printf("GetTopK used time: %ldms\n", (end - start)/1000); for (auto &it : final_result) { printf("id: m, times: %d\n", it.id, it.times); } // 直接排序 final_result.clear(); start = GetUsTime(); DirectSort(map_result, &final_result, 10); end = GetUsTime(); printf("DirectSort used time: %ldms\n", (end - start)/1000); for (auto &it : final_result) { printf("id: m, times: %d\n", it.id, it.times); } return 0; } #include <iostream> #include <cstdio> #include <unistd.h> int WriteDataFile() { const int MAX_ID = 999999; const int MAX_LINES = 2000000; FILE *fp = fopen("test.data", "w"); if (fp == NULL) { perror("fopen test.data"); return -1; } srand(time(NULL)); for (int i = 0; i < MAX_LINES; ++i) { fprintf(fp, "%ld\n", random() * random() % MAX_ID); } fclose(fp); return 0; } int main(int argc, char **argv) { WriteDataFile(); return 0; }

map中的元素是按key排序的,这个题目中其实不需要对key进行排序,C++11提供了基于哈希实现的map容器unordered_map,其访问元素的效率比map要高一些,来看一下将map替换为unordered_map后的性能比较。

另外,这个面试题目有非常多的玩法和变种,例如将数字总数100万改成20个亿,同时限制内存使用不超过2GB,大家可以思考一下解决思路。

map功能强大,它的作用当然不只在于解决面试题目,在一个大型后端系统中,几乎到处都能看到map的身影。例如,面试题中的出现次数最多的数字可以想象为频繁非法访问的黑名单ID,可以用一个map来保存黑名单ID和其访问次数,那么如何使用这个map呢?假如有一个保存了很多ID的vector,里面可能有黑名单ID,在处理数据的时候需要将黑名单ID剔除,代码可以这么写:

void FilterBlackID(const std::map<int, int> &black_list, std::vector<int> *ids) { if (black_list.empty()) { return; } auto it = ids->begin(); while (it != ids->end()) { if (black_list.find(*it) != black_list.end()) { ids->erase(it); } else { ++it; } } }

想要掌握更多的map原理和使用技巧,推荐大家阅读《C++ Primer》或者网上搜索“C++ map”相关的博客文章,然后主动练习,不断丰富自己的开发武器库。

转载请注明原文地址: https://www.6miu.com/read-4050114.html

最新回复(0)