topk应用问题 模拟热搜数据
需要完整思路和源代码，最好是附带讲解图文和流程文件。在最差情况下可进行远程指导。需要用到Javaweb和数据库。需要完整的项目才能确认答案
帮你把表创建出来 ：搜索词(SearchWord)、搜索记录(SearchRecord)
CREATE TABLE `search_word` (
`id` INT(11) NOT NULL AUTO_INCREMENT,
`content` VARCHAR(50) NOT NULL,
`hot` INT(11) NOT NULL DEFAULT '0',
`last_hot_time` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
PRIMARY KEY (`id`)
) ENGINE=INNODB DEFAULT CHARSET=utf8
CREATE TABLE `search_record` (
`id` INT(11) NOT NULL AUTO_INCREMENT,
`search_word_id` INT(11) NOT NULL,
`count` INT(11) NOT NULL DEFAULT '1',
`date` DATE NOT NULL,
PRIMARY KEY (`id`),
KEY `search_word_id` (`search_word_id`)
)
结构图如下 ：
├─src
│ ├─main
│ │ ├─java
│ │ │ └─com.example.hotsearch
│ │ │ ├─dao
│ │ │ │ SearchRecordDao.java
│ │ │ │ SearchWordDao.java
│ │ │ ├─entity
│ │ │ │ SearchRecord.java
│ │ │ │ SearchWord.java
│ │ │ ├─schedule
│ │ │ │ HotSearchTask.java
│ │ │ └─service
│ │ │ SearchService.java
│ │ └─resources
│ │ ├─mapper
│ │ │ SearchRecordMapper.xml
│ │ │ SearchWordMapper.xml
│ │ └─templates
│ │ index.html
│ └─test
│
├─pom.xml
可以用堆
使用一个最小堆来实现，即堆中的最小值位于堆顶。我们可以维护一个大小为10的最小堆，遍历热搜数据，将数据依次插入堆中，当堆的大小超过10时，将堆顶元素删除，保持堆的大小为10。最后，堆中的元素就是前10个最热门的数据。
可参考
import java.util.*;
public class TopKHotSearch {
public static void main(String[] args) {
// 模拟热搜数据
List<HotSearch> hotSearchList = new ArrayList<>();//存放热搜名和热度
hotSearchList.add(new HotSearch("HotSearch1", 1000));
hotSearchList.add(new HotSearch("HotSearch2", 2000));
hotSearchList.add(new HotSearch("HotSearch3", 3000));
hotSearchList.add(new HotSearch("HotSearch4", 4000));
hotSearchList.add(new HotSearch("HotSearch5", 5000));
hotSearchList.add(new HotSearch("HotSearch6", 6000));
hotSearchList.add(new HotSearch("HotSearch7", 7000));
hotSearchList.add(new HotSearch("HotSearch8", 8000));
hotSearchList.add(new HotSearch("HotSearch9", 9000));
hotSearchList.add(new HotSearch("HotSearch10", 10000));
hotSearchList.add(new HotSearch("HotSearch11", 21000));
hotSearchList.add(new HotSearch("HotSearch12", 22000));
// 构建最小堆 大小为10
PriorityQueue<HotSearch> minHeap = new PriorityQueue<>(10, new Comparator<HotSearch>() {
@Override
public int compare(HotSearch o1, HotSearch o2) {
return o1.getHeat() - o2.getHeat();
}
});
// 遍历热搜数据
for (HotSearch hotSearch : hotSearchList) {
// 插入堆
minHeap.offer(hotSearch);
// 如果堆大小超过10，删除堆顶元素
if (minHeap.size() > 10) {
minHeap.poll();
}
}
// 输出前10个最热门的数据
while (!minHeap.isEmpty()) {
System.out.println(minHeap.poll());
}
}
}
class HotSearch {
private String name;//热搜名字
private int heat;//热度
public HotSearch(String name, int heat) {
this.name = name;
this.heat = heat;
}
public String getName() {
return name;
}
public int getHeat() {
return heat;
}
@Override
public String toString() {
return "HotSearch{" +
"name='" + name + '\'' +
", heat=" + heat +
'}';
}
}
基本思路是:
- 初始化一个大小为K的最小堆,用于存储热度最高的K个搜索词
- 随机产生搜索词及其热度,如果热度高于堆顶,则弹出堆顶元素,将新搜索词入堆
- 堆满K个元素后,堆顶元素即为热度第K高的搜索词,最小堆可以实时得出TopK热搜
public class Test {
public static void main(String[] args) {
TopK topK = new TopK(3, 10);
String[] top3 = topK.getTopK();
System.out.println("Top 3 hot search:");
for (String word : top3) {
System.out.println(word);
}
}
}
class TopK {
private int k; // top k
private int heatMax; // 搜索词热度上限
public TopK(int k, int heatMax) {
this.k = k;
this.heatMax = heatMax;
}
// 获取top k热搜
public String[] getTopK() {
PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> getHeat(b) - getHeat(a));
String[] topK = new String[k];
for (int i = 0; i < k; i++) { // 初始化最小堆
String word = getWord();
int heat = getHeat();
heap.add(word);
topK[i] = word;
}
for (int i = k; i < heatMax; i++) { // 产生新的搜索词
String word = getWord();
int heat = getHeat();
if (heat > getHeat(heap.peek())) { // 如果热度大于堆顶,弹出堆顶
heap.poll();
heap.add(word);
topK[--k] = word; // 替换第k热词
}
}
return topK;
}
// 随机产生搜索词
private String getWord() {
return "word" + (int)(Math.random() * 100);
}
// 随机产生热度
private int getHeat() {
return (int)(Math.random() * heatMax);
}
}
给你个简单例子，参考gpt:
您好！TopK问题是大数据处理中经常遇到的问题之一。在海量数据中找出出现频率最好的前k个数，或者从海量数据中找出最大的前k个数，这类问题通常被称为top K问题。
针对top K类问题，通常比较好的方案是分治+Trie树/hash+小顶堆(就是上面提到的最小堆),即先将数据集按照Hash方法分解成若干个子集，然后对每个子集进行排序，最后取前k个数即可。
下面是一个简单的Python代码实现：
import heapq
def top_k(nums, k):
nums.sort()
return heapq.nlargest(k, nums)
其中，nums为待排序的列表，k为需要取出的前k个数。该函数会返回一个包含前k个数的列表。
希望这个回答能够帮到您！
引用GPT回答：
思路：
使用JavaWeb开发一个简单的网页，用于展示热搜排行榜。
使用数据库来存储热搜数据，其中每个热搜项目包括名称和热度值。
使用TopK算法来维护热搜排行榜，每次有新的热搜项目加入或者热度值发生变化时，使用TopK算法重新计算排行榜。
使用Java的定时任务，定时从网页上爬取热搜数据，并将数据存入数据库中。
在网页上展示热搜排行榜，并且可以进行搜索操作。
源代码及详细说明：
创建一个名为HotSearch的JavaWeb项目，包含以下文件：
pom.xml：项目的依赖文件
src/main/java/com/hotsearch：Java代码的存放位置
src/main/resources：配置文件的存放位置
src/main/webapp：网页文件的存放位置
在src/main/java/com/hotsearch下创建HotSearchController.java文件，用于处理网页请求和响应。
package com.hotsearch;
import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;
@Controller
public class HotSearchController {
@RequestMapping(value = "/index", method = RequestMethod.GET)
public String index() {
// 返回index.jsp页面
return "index";
}
@RequestMapping(value = "/search", method = RequestMethod.POST)
public String search(String keyword) {
// 根据关键字在数据库中搜索热搜项目，并返回搜索结果页面
return "search";
}
}
在src/main/java/com/hotsearch下创建HotSearchService.java文件，用于处理数据相关的操作。
package com.hotsearch;
import java.util.List;
public interface HotSearchService {
/**
* 获取热搜排行榜
* @return 热搜排行榜列表
*/
List<HotSearch> getHotSearchRanking();
/**
* 增加热搜项目
* @param hotSearch 热搜项目
*/
void addHotSearch(HotSearch hotSearch);
/**
* 更新热搜项目的热度值
* @param name 热搜项目名称
* @param increment 热度值增量
*/
void updateHotSearch(String name, int increment);
/**
* 根据关键字搜索热搜项目
* @param keyword 关键字
* @return 热搜项目列表
*/
List<HotSearch> searchHotSearch(String keyword);
}
在src/main/java/com/hotsearch下创建HotSearchServiceImpl.java文件，实现HotSearchService接口。
package com.hotsearch;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class HotSearchServiceImpl implements HotSearchService {
private Map<String, Integer> hotSearchMap = new LinkedHashMap<>();
public HotSearchServiceImpl() {
// 从数据库中加载热搜数据
// ...
}
@Override
public List<HotSearch> getHotSearchRanking() {
// 使用TopK算法计算热搜排行榜
List<HotSearch> hotSearchList = new ArrayList<>();
// ...
return hotSearchList;
}
@Override
public void addHotSearch(HotSearch hotSearch) {
// 将热搜项目添加到数据库中
// ...
}
@Override
public void updateHotSearch(String name, int increment) {
// 更新热搜项目的热度值到数据库中
// ...
}
@Override
public List<HotSearch> searchHotSearch(String keyword) {
// 在数据库中搜索热搜项目
List<HotSearch> hotSearchList = new ArrayList<>();
// ...
return hotSearchList;
}
}
在src/main/java/com/hotsearch下创建HotSearch.java文件，表示热搜项目的数据结构。
package com.hotsearch;
public class HotSearch {
private String name;
private int score;
public HotSearch(String name, int score) {
this.name = name;
this.score = score;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getScore() {
return score;
}
public void setScore(int score) {
this.score = score;
}
}
在src/main/resources下创建application.properties文件，配置数据库相关属性。
数据库驱动
spring.datasource.driver-class-name=com.mysql.jdbc.Driver
数据库URL
spring.datasource.url=jdbc:mysql://localhost:3306/hotsearch?useUnicode=true&characterEncoding=utf8
数据库用户名
spring.datasource.username=root
数据库密码
spring.datasource.password=root
在src/main/resources下创建db.sql文件，用于创建数据库和表。
-- 创建数据库
CREATE DATABASE hotsearch CHARSET utf8mb4 COLLATE utf8mb4_unicode_ci;
-- 使用hotsearch数据库
USE hotsearch;
-- 创建hotsearch表
CREATE TABLE hotsearch (
id INT(11) NOT NULL AUTO_INCREMENT,
name VARCHAR(255) NOT NULL,
score INT(11) NOT NULL,
PRIMARY KEY (id)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci;
在pom.xml中添加依赖，包括Spring Boot、Spring Web、Spring Data JPA、MySQL驱动等。
<dependencies>
<!-- Spring Boot -->
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter</artifactId>
</dependency>
<!-- Spring Web -->
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-web</artifactId>
</dependency>
<!-- Spring Data JPA -->
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-data-jpa</artifactId>
</dependency>
<!-- MySQL驱动 -->
<dependency>
<groupId>mysql</groupId>
<artifactId>mysql-connector-java</artifactId>
<version>8.0.23</version>
``` </dependency>
</dependencies>
在src/main/resources下创建application.yml文件，用于配置服务器端口和定时任务。
```bash
server:
port: 8080
spring:
task.scheduling.pool.size: 1
hotsearch:
url: https://www.baidu.com/s?wd=%E7%83%AD%E6%90%9C
interval: 60
在src/main/java/com/hotsearch下创建HotSearchApplication.java文件，启动整个项目。
package com.hotsearch;
import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import org.springframework.scheduling.annotation.EnableScheduling;
@SpringBootApplication
@EnableScheduling
public class HotSearchApplication {
public static void main(String[] args) {
SpringApplication.run(HotSearchApplication.class, args);
}
}
在src/main/java/com/hotsearch下创建HotSearchTask.java文件，用于定时获取热搜数据并更新到数据库中。
package com.hotsearch;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.scheduling.annotation.Scheduled;
import org.springframework.stereotype.Component;
import java.util.List;
@Component
public class HotSearchTask {
private final HotSearchService hotSearchService;
@Autowired
public HotSearchTask(HotSearchService hotSearchService) {
this.hotSearchService = hotSearchService;
}
@Scheduled(fixedRateString = "${hotsearch.interval}000", initialDelay = 5000)
public void updateHotSearchRanking() {
// 爬取热搜数据，并更新到数据库中
List<HotSearch> hotSearchList = new ArrayList<>();
// ...
for (HotSearch hotSearch : hotSearchList) {
hotSearchService.updateHotSearch(hotSearch.getName(), hotSearch.getScore());
}
}
}
在src/main/webapp下创建index.jsp文件，用于展示热搜排行榜和搜索框。
<%@ page language="java" contentType="text/html; charset=UTF-8"
pageEncoding="UTF-8"%>
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>热搜排行榜</title>
</head>
<body>
<h1>热搜排行榜</h1>
<table>
<thead>
Java实现topK问题
package topKQues;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.HashMap;
import java.io.FileReader;
import java.io.IOException;
import java.io.BufferedReader;
public class TopKwithPriorityQueue<E extends Comparable> {
static String filepath = "/Users/alicelmx/java_workspace/algorithm_java8/src/topKQues/demo.txt";
PriorityQueue<E> queue ;
static int K ;
public TopKwithPriorityQueue(int maxSize) {
if (maxSize <= 0)
throw new IllegalArgumentException();
this.K = maxSize;
this.queue = new PriorityQueue<>(maxSize, new Comparator<E>() {
@Override
public int compare(E o1, E o2) {
// 小根堆使用o1-o2
return (o1.compareTo(o2));
}
});
}
public void add(E e) {
if(queue.size() < K)
queue.add(e);
else {
E peek = queue.peek();
if(e.compareTo(peek) > 0) {
queue.poll();
queue.add(e);
}
}
}
public ArrayList<E> sortedList() {
ArrayList<E> list = new ArrayList<E>(queue);
return list;
}
public static HashMap<String,Integer> readAndConvert() {
HashMap<String,Integer> map = new HashMap<String,Integer>();
try {
FileReader fr = new FileReader(filepath);
BufferedReader bf = new BufferedReader(fr);
String str;
// 按行读取字符串
while ((str = bf.readLine()) != null) {
if(!map.containsKey(str))
map.put(str,1);
else {
int time = map.get(str);
map.put(str,time+1);
}
}
bf.close();
fr.close();
} catch (IOException e) {
e.printStackTrace();
}
return map;
}
public static void main(String[] args) {
HashMap<String,Integer> map = readAndConvert();
TopKwithPriorityQueue pq = new TopKwithPriorityQueue(2);
for(String key: map.keySet())
pq.add(map.get(key));
ArrayList<String> res = new ArrayList<>();
for(int i=0;i<pq.sortedList().size();i++) {
for(String key:map.keySet()) {
if(map.get(key).equals(pq.sortedList().get(i))&&!res.contains(key))
res.add(key);
}
}
System.out.println(res);
}
}
如果数据量比较大，比如现实中的百度微博等热搜，需要使用大数据相关的工具才能做到。如果数据量小，只是写个程序来简单实现下的话，可以考虑建立一个N=M大小的大顶堆，然后输出根节点之后，将根节点删除，然后再将剩余的元素调整成大顶堆；依次重复K次这个过程，最终就找出了K个最大的数。这实质上就是堆排序的过程。
热搜数据是根据用户点击、搜索、分享等行为进行计算的，并且在一段时间内进行排名。因此，可以模拟出一些用户行为，如点击、搜索等，并且设置一段时间，如一天、一小时等，进行统计排名。