MapReduce

Description

MapReduce是Google提出的一个软件架构，用于大规模数据集（大于1TB）的并行运算。概念“Map（映射）”和“Reduce（归纳）”，及他们的主要思想，都是从函数式编程语言借来的，还有从矢量编程语言借来的特性。

下面我们要实现一个词频统计的MapReduce Worker，通俗来说就是统计一段文本中各个单词出现的次数。

MapReduce包括两部分：Map任务和Reduce任务。

Map任务：给定一段文本，对于其每一个单词逐一映射为key为该单词，value为字符串"1"的键值对，并按出现顺序逐个输出键值对

Reduce任务：给定一个键值对序列，将相同的key的value值相加，并将其按key从小到大输出键值对

Note: 单词的分割标准为空格分隔

Input 第一行包括字符串task—— 代表任务类型，有Map和Reduce两种。

若为Map任务，第二行包括一行字符串text(0 < |text| <= 1e7) ——一段需要处理的文本。

若为Reduce，第二行包括整数n (0 < n <= 1e5)—— 键值对序列长度，第3到n+3行输入键值对key和value(0 <=

|key| <= 1e5, 0<=value<=1000) —— 要处理的键值对序列。有多组样例，请处理到文件结尾。

键值对格式为key value。

保证正常运算过程中int类型不溢出。

Output 对于Map任务，输出文本后中每个单词映射的键值对的key和value。

对于Reduce任务，输出排序后的键值对的key和value。键值对格式为key value。

每个样例间用空行分割。

Sample Input 1

Map

This is a MapReduce problem inspired by MapReduce

Reduce

8

This 1

is 1

a 1

MapReduce 1

problem 1

inspired 1

by 1

MapReduce 1

Sample Output 1

This 1

is 1

a 1

MapReduce 1

problem 1

inspired 1

by 1

MapReduce 1

MapReduce 2

This 1

a 1

by 1

inspired 1

is 1

problem 1

思路

用STL中的map 模拟这个过程

题解

#include<iostream>

#include<cstdio>

#include<cmath>

#include<map>

#include<algorithm>

#include<queue>

#include<string>

using namespace std;

#define ll long long

const int Len = 1e6 + 5;

int n,m;

string s[Len];

map<string, int> mp;

string st;

int main()

{

    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("T.txt","r",stdin);

    while(cin >> st)

    {

        if(st == "Map")

        {

            int k = 0;

            while(cin >> s[k])

            {

                if(s[k] == "Reduce")

                {

                    cout << endl;

                    goto lab;

                }

                cout << s[k] << " " << 1 <<endl;

            }

            cout << endl;

        }

        else

        {

            mp.clear();

            lab:;

            int n;

            cin >> n;

            int val;

            for(int i = 1; i <= n; i ++)

                cin >> st >> val, mp[st] += val;

            for(auto x : mp)

            {

                cout << x.first << " " << x.second <<endl;

            }

            cout << endl;

            mp.clear();

        }

    }

    return 0;

}

巴特西

MapReduce（ map的使用）

MapReduce

思路

题解

最新文章

热门文章