多线程任务

随着互联网的快速发展和大规模数据处理需求的增加，多线程编程可以显著提高系统的性能和响应能力。通过并发执行多个任务，多线程编程可以使程序能够同时处理多个网络请求、并发下载多个文件或同时处理多个客户端连接。这样可以减少用户等待时间，提高系统的吞吐量和并发性能，从而增强用户体验和系统的可扩展性。

多线程排序

实现一个多线程排序算法，能够对给定的整数数组进行排序。可以选择任何排序算法（如快速排序、归并排序等），并使用 线程/协程（下统称线程）对其进行并发化优化。具体要求如下：

• 编写随机数生成器。
  • 生成包含 100,000 条数据的数据集。
• 选择合适的排序算法，实现真正的并发加速
• 将待排序数组分割成多个（逻辑）子数组。
  • 可以根据 CPU 核心数或其他特定参数来确定分割的数量，也可以根据数据大小动态调整分割的数量。将分割后的子数组存储在一个数组或切片中，以便进行并发排序。
• 使用 线程 并发地对各个（逻辑）子数组进行排序。
  • 可以将每个子数组排序的任务分配给不同的 线程，以便并发处理。在并发执行时，需要避免竞态条件和数据冲突等问题，可以使用互斥锁或其他同步机制来保证数据的正确性。
• 使用 IPC、锁+条件变量或其他手段（channels）进行通信，将排序好的子数组传递给其他线程。
  • 在排序完成后，需要将排序好的子数组传递给其他 线程 进行合并操作。可以使用 线程间通信 来传递子数组，以便实现并发通信。
• 合并已排序的子数组，得到最终排序结果。
  • 在所有的子数组都排序完成并传递回来后，可以将这些子数组合并成一个有序的数组，得到最终的排序结果。

• 比单线程排序和多线程排序的性能差异，分析并发优化的效果。(可选)

  • 可以通过测试数据集来对比单线程排序和多线程排序的性能差异，并分析并发优化的效果。在测试时，需要考虑多线程排序的开销和并发通信的开销等因素。

• 此任务可以使用任何语言实现

• 此任务也可使用 多进程 实现

补充问题： 在不同数据量的情况下，多线程的排序会劣于单线程排序吗

C / C++ 选手

线程池

频繁的进行进程的创建与销毁将带来很多开销。不但如此，进程间频繁的切换也将减低 CPU 的利用率。 如果能复用之前创建的进程，而不是为每个并发任务创建一个进程，能有效降低进程创建与销毁的开销并减少进程间切换，从而减少对 CPU 资源的浪费。 虽然线程创建与销毁的代价小于进程创建与销毁，隶属同一进程的线程间切换的代价也小于进程间切换，但复用之前创建的线程，也能有效降低线程创建与销毁的开销并减少线程间切换，从而减少对 CPU 资源的浪费。

总而言之，为每个并发任务分别创建一个进程或线程这种做法，追求编写高性能程序的你可能难以接受这种做法。既然这样，不如来使用线程池来复用线程吧！

线程池就是让线程完成当前任务后继续等待分配给它的新任务！！！

是不是很简单？？？快来试试吧！！！

• Simple thread pool challenge

多线程文件搜索

你的任务是编写一个多线程的文件搜索程序，该程序能够在指定的目录下递归地搜索指定类型的文件并输出结果。具体要求如下：

• 创建一个结构体表示文件搜索的配置，包括搜索的根目录、搜索的文件类型、最大并发数等。
• 使用多线程并发地递归搜索目录下的文件，找到指定类型的文件并输出文件路径。
• 控制并发数，避免过多的线程占用系统资源。
• 设置最大搜索深度，避免无限制地搜索。
• 可以选择是否跳过指定目录或文件的搜索。 以下是任务要求的详细说明：

结构体定义:

struct SearchConfig {
    std::string root_path;    // 要搜索的根目录
    std::string file_type;    // 要搜索的文件类型，如 ".txt"、".cpp" 等
    int max_concurrency;      // 最大并发数
    int max_depth;            // 最大搜索深度
    bool skip_hidden;         // 是否跳过隐藏文件或目录
    std::vector<std::string> skip_paths;   // 要跳过的目录或文件的路径
};

more:
- 可以使用 C++11 中的 std::thread 和 std::mutex 等多线程库，也可以使用 Boost 等第三方库。 - 可以使用 C++17 中的 std::filesystem 库来处理文件和目录，也可以使用 Boost.Filesystem 等第三方库。 - 需要注意线程安全和资源占用问题，避免死锁、竞争条件等问题。 - 可以为搜索结果添加排序、去重等功能。(可选)

提高任务（选做）

还记得上面所说的吗？进程的创建与销毁比线程的创建与销毁的开销更大，那么能否使用进程池来复用进程呢？ 快来试试吧！！！

Golanger

需要一定的网络编程知识 :)

多线程爬虫

Golang 是一种并发友好的语言，使用 goroutines 和 channels 可以轻松地实现多线程爬虫。你的任务是编写一个多线程爬虫，该爬虫能够在指定的网站中获取链接并提取相关信息。具体要求如下：

• 创建一个结构体表示爬虫的配置，包括初始 URL、最大深度、最大并发数等。
• 使用 goroutines 并发地发起 HTTP 请求，获取网页内容。
• 解析网页内容，提取链接以及所需信息。
• 使用 channels 进行通信，将获取到的链接及信息传递给其他 goroutines。
• 控制并发数，避免过多的 goroutines 耗尽资源。
• 设置爬取深度，避免无限制地爬取。

推荐的练习网站

• 在选取练习爬虫的网站前一定要注意:
  • 确定目标网站愿意被爬取(至少不排斥)
  • 确定已经规避了可能的_~法律~风险
  • 确定目标网站没有严格的反爬措施
• 爬虫练习网站:
  • Scrape Center
  • 豆瓣
    • 爬取豆瓣图书 Top250
    • 爬取豆瓣电影 Top250
    • 爬取豆瓣音乐 Top250

多线程下载器

编写一个多线程下载器，能够从给定的 URL 下载文件。具体要求如下：

• 分析下载文件的大小，并将其分割成多个分片。
• 使用 goroutines 并发地下载各个分片。
• 使用 channels 进行通信，传递下载进度及状态。
• 提供下载进度展示，包括已下载大小、总大小、下载速度等信息。(可选)
• 支持断点续传，即在程序意外中断后，能够从上次中断的地方继续下载。(可选)
• 推荐的练习下载的 URL
  • https://speed.hetzner.de/100MB.bin
  • http://mirrors.aliyun.com/archlinux/iso/2023.04.01/archlinux-2023.04.01-x86_64.iso?spm=a2c6h.25603864.0.0.65433ebd8SjcW9
• 引入 P2P 下载的思想(可选)
  • 将文件合理地分为多块,处理好偏移量,从多个头部同时下载
  • 可参考 的下载器
    • IDM
    • aria2

      Q: 什么是 P2P 下载?
      
      A:
      (generate by ChatGPT-3.5-Turbo)
      
      P2P（Peer-to-Peer）下载是一种分布式文件传输协议，它可以让多个计算机（也称为节点）互相连接并分享文件。与传统的客户端-服务器模式不同，P2P 下载中，每个节点都可以充当客户端和服务器，从其他节点下载文件，同时也可以向其他节点分享自己的文件。
      
      在 P2P 下载中，文件被分成多个小块，每个小块都可以从不同的节点下载。这些小块可以同时从多个节点下载，从而提高下载速度和可靠性。当一个节点下载了一个小块后，它也可以充当服务器，向其他节点分享这个小块。这样，其他节点就可以从多个源下载同一个文件，从而减轻单个节点的负担，提高下载效率。
      
      P2P 下载的优点在于，它可以利用多个节点的带宽和存储资源，提高下载速度和可靠性。同时，P2P 下载也具有良好的扩展性，因为节点的数量可以随时增加或减少，从而适应不同的网络环境和下载需求。
      
      不过，P2P 下载也存在一些缺点。由于每个节点都可以充当服务器，因此文件可能会被恶意节点篡改或感染病毒。此外，P2P 下载中，节点之间的连接可能会不稳定，导致下载速度不稳定或下载失败。
      
      总体来说，P2P 下载是一种高效、`分布式`的文件传输协议，可以为用户提供更快、更可靠的下载体验。但在使用时需要注意安全问题，以及网络连接的稳定性和质量。
      

---

性能测试

C++

• Google Benchmark
  • C++ 性能测试框架
• Google Test
  • C++ 单元测试框架，包括性能测试功能
• Valgrind
  • 内存泄漏、越界访问等问题检测工具集
• perf
  • Linux 内核自带的性能追踪工具

Golang

• testing.Benchmark
  • Golang 内置的性能测试框架
  • 可以用来测试代码的性能并输出测试结果
• pprof
  • Golang 内置的性能分析工具
  • 分析代码的 CPU 和内存使用情况
• go-torch
  • 生成火焰图的工具
• race
  • Golang 中的数据竞争检测工具
  • 避免并发程序中的潜在错误

CLI

• hyperfile
  • A command-line benchmarking tool

---

以上任务对你掌握 Golang 的并发概念非常有用, 希望你在这个过程中可以深入理解 goroutines 和 channels,编写出高效的多线程程序。

Good luck!