2023-2024-2-编程作业3¶

2021级，Flink，不计入分数

最大公约数(GCD)¶

难易程度: ** 中¶

待完成:¶

请在 DSPPCode.flink.gcd.impl 中创建GCDImpl, 继承 GCD, 实现抽象方法

题目描述:¶

给定两个非负整数，求两者的最大公约数（GCD）。通常，两个数的最大公约数可用辗转相除法求解，其原理是：两个数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。例如：存在a和b两个数，并且a大于b，则a和b的最大公约数等于b与两数相除余数 a mod b 的最大公约数，记作gcd(a, b) = gcd(b, a mod b)。假定r = a mod b，若r依然为正整数，为了求解a和b的最大公约数，需进一步求解b和r的最大公约数，即gcd(b, r) = gcd(r, b mod r)。显然，计算最大公约数的过程是一个迭代计算过程，初始迭代时需对两个正整数做除法运算求得余数，然后每轮迭代都需对上一轮迭代的除数和余数做相同的除法运算。直到上一轮迭代的除数和余数可以整除，迭代计算方会终止。此时，上一轮迭代的除数即为最大公约数。现要求求解两个整数的最大公约数，并且在求解过程中输出每轮迭代的除数和余数。
输入格式: 每行由一个字母标识符以及两个非负整数a和b组成，三者之间使用空格分隔。字母标识符逐行递增，用于标识不同的最大公约数计算请求。例如：A 5 2表示这是第一个计算请求，要求求解5和2的最大公约数。

A 5 2 B 18 6

输出格式: 对于每个计算请求，要求依次输出每轮迭代的除数和余数。其输出格式为(计算请求对应的字母标识符,除数,余数)。例如：(A,2,1)表示第一个计算请求在第一轮迭代计算中的除数和余数分别为2和1。

(A,2,1) (B,6,0) (A,1,0)

GCDImpl 参考实现¶

package DSPPCode.flink.gcd.impl;

import DSPPCode.flink.gcd.question.GCD;
import org.apache.flink.api.common.functions.MapFunction;
import org.apache.flink.api.java.tuple.Tuple3;
import org.apache.flink.streaming.api.datastream.DataStreamSource;
import org.apache.flink.api.common.functions.FilterFunction;
import org.apache.flink.api.common.functions.FlatMapFunction;
import org.apache.flink.streaming.api.datastream.DataStream;
import org.apache.flink.streaming.api.datastream.IterativeStream;
import org.apache.flink.streaming.api.environment.StreamExecutionEnvironment;
import org.apache.flink.util.Collector;

public class GCDImpl extends GCD{
  public DataStream<Tuple3<String, Integer, Integer>> calGCD(IterativeStream<Tuple3<String, Integer, Integer>> iteration){
        // |创建反馈流|
        // |选择第三位置不为0的元组，例如(A, 2, 1)|
        DataStream<Tuple3<String, Integer, Integer>> feedback =
            iteration.filter(
                new FilterFunction<Tuple3<String, Integer, Integer>>() {
                  @Override
                  public boolean filter(Tuple3<String, Integer, Integer> value) throws Exception {
                    return value.f2 != 0;
                  }
                });
        // |实现迭代步逻辑，计算下一个GCD|
        DataStream<Tuple3<String, Integer, Integer>> iteratedStream =
          feedback.flatMap(
              new FlatMapFunction<Tuple3<String, Integer, Integer>, Tuple3<String, Integer, Integer>>() {
                @Override
                public void flatMap(
                    Tuple3<String, Integer, Integer> value, Collector<Tuple3<String, Integer, Integer>> out)
                    throws Exception {
                  // |例如迭代算子的输入输入为(A, 2, 1)，此处转换将(A, 2, 1)转换为(A, 1, 0)|
                  Tuple3<String, Integer, Integer> feedbackValue =
                      new Tuple3(value.f0, value.f2, value.f1 % value.f2);
                  out.collect(feedbackValue);
                }
              });
        iteration.closeWith(iteratedStream);
        return iteratedStream;
  }
}

Twitter Hot Topics¶

难易程度: ** 中¶

待完成:¶

请在DSPPCode.flink.twitter_hot_topics中创建TwitterHotTopicsImpl, 继承TwitterHotTopics, 实现抽象方法
请在DSPPCode.flink.twitter_hot_topics中创建TwitterTextHandlerImpl, 继承TwitterTextHandler, 实现抽象方法

题目描述:¶

来自世界各地的Twitter用户们每时每刻都在发布着新的推文。这些推文所讨论的话题是各不相同的，并且在讨论热度上也是有所差异的。一般来说，弄清哪些话题是热门话题有利于为用户做内容推荐。假设存在一个程序正在源源不断地采集着Twitter的推文数据，现在希望你能对这些数据进行处理，以找出纯英文推文中的热门话题。每条推文的数据格式均为JSON，纯英文推文的"lang"字段所对应的值为en。也就是说，如果某一推文含有英文和其它语种的文字，该推文不是纯英文推文，"lang"字段所对应的值不等于en。为了简单起见，推文中的每个英文单词被视作一个话题。当话题数大于等于4时，该话题称之为热门话题。此外，对于每个话题而言，只有其对应的英文单词具备一定的意义才会纳入热门话题。例如，对于the话题，由于the无意义，则不应纳入热门话题。另外在处理过程中，需要将大写单词均转换为小写形式。最后，为了方便判定话题是否具备一定的意义，本题提供了一份包含所有无意义单词的停词表，可通过StopWordsOperation.getStopWords方法获取。
输入格式：每条输入数据的格式为JSON。在每条JSON数据中，"text"字段表示用户发布的推文，而"lang"字段表示用户发布的推文所使用的语言。假设，某一Twitter用户发布了五条相同的纯英文推文，其内容均为how to use flink? i love it，则推文对应的数据格式如下所示。其中，"text"字段所对应的值为how to use flink? i love it，而"lang"字段所对应的值为en。

json { "created_at": "Mon Jan 1 00:00:00 +0000 1901", "id": 0, "id_str": "000000000000000000", "text": "how to use flink? i love it", "source": null, "truncated": false, "in_reply_to_status_id": null, "in_reply_to_status_id_str": null, "in_reply_to_user_id": null, "in_reply_to_user_id_str": null, "in_reply_to_screen_name": null, "user": { "id": 0, "id_str": "0000000000", "name": "test1", "screen_name": "iphone", "location": "Shanghai", "protected": false, "verified": false, "followers_count": 999999, "friends_count": 99999, "listed_count": 999, "favourites_count": 9999, "statuses_count": 999, "created_at": "Mon Jan 1 00:00:00 +0000 1901", "utc_offset": 7200, "time_zone": "Amsterdam", "geo_enabled": false, "lang": "en", "entities": { "hashtags": [ { "text": "example1", "indices": [ 0, 0 ] }, { "text": "tweet1", "indices": [ 0, 0 ] } ] }, "contributors_enabled": false, "is_translator": false, "profile_background_color": "C6E2EE", "profile_background_tile": false, "profile_link_color": "1F98C7", "profile_sidebar_border_color": "FFFFFF", "profile_sidebar_fill_color": "252429", "profile_text_color": "666666", "profile_use_background_image": true, "default_profile": false, "default_profile_image": false, "following": null, "follow_request_sent": null, "notifications": null }, "geo": null, "coordinates": null, "place": null, "contributors": null }

输出格式：每行以元组形式输出热门话题（全部小写）以及热门话题出现的次数，并且当话题数大于等于4时即开始输出。以上述的五条推文数据为例，love这一热门话题总共出现了5次，因此会产生两次输出。

(love,4) (love,5) (flink,4) (flink,5)