四月 24, 2024

经典并发编程问题之哲学家进餐

施工中…

原题：https://leetcode.cn/problems/the-dining-philosophers/description/

题解参考：https://leetcode.cn/problems/the-dining-philosophers/solutions/2130703/li-shun-xian-cheng-zheng-qiang-xin-hao-l-gzb1/

5 个沉默寡言的哲学家围坐在圆桌前，每人面前一盘意面。叉子放在哲学家之间的桌面上。（5 个哲学家，5 根叉子）

所有的哲学家都只会在思考和进餐两种行为间交替。哲学家只有同时拿到左边和右边的叉子才能吃到面，而同一根叉子在同一时间只能被一个哲学家使用。每个哲学家吃完面后都需要把叉子放回桌面以供其他哲学家吃面。只要条件允许，哲学家可以拿起左边或者右边的叉子，但在没有同时拿到左右叉子时不能进食。

假设面的数量没有限制，哲学家也能随便吃，不需要考虑吃不吃得下。

设计一个进餐规则（并行算法）使得每个哲学家都不会挨饿；也就是说，在没有人知道别人什么时候想吃东西或思考的情况下，每个哲学家都可以在吃饭和思考之间一直交替下去。

哲学家从 0 到 4 按 顺时针 编号。请实现函数 void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)：

philosopher 哲学家的编号。
pickLeftFork 和 pickRightFork 表示拿起左边或右边的叉子。
eat 表示吃面。
putLeftFork 和 putRightFork 表示放下左边或右边的叉子。
由于哲学家不是在吃面就是在想着啥时候吃面，所以思考这个方法没有对应的回调。

给你 5 个线程，每个都代表一个哲学家，请你使用类的同一个对象来模拟这个过程。在最后一次调用结束之前，可能会为同一个哲学家多次调用该函数。

解法

前置知识

该问题本质上是线程同步中的死锁问题，常用线程同步方式有互斥锁、条件变量、信号量法；这里使用信号量的方法

P-V信号量

经典的死锁问题解决方案，对于信号量m，P(m)检查m是否为0，为0阻塞，否则将其减1，表示占用资源；V(m)将m加1，表示释放资源

C++方法

sem_init, sem_wait, sem_post 是与信号量（semaphore）相关的函数，常用于进程或线程间的同步。信号量是一种高级的同步机制，用于控制对共享资源的访问数量。

这些函数属于 POSIX 线程库（Pthreads），在多种编程环境中可用，尤其是在 UNIX、Linux 系统中。下面是这些函数的基本用途和如何使用它们的简要说明：

sem_init

用途：初始化一个未命名的信号量。
原型
```
int sem_init(sem_t *sem, int pshared, unsigned int value);
```
- sem：指向信号量结构的指针。
- pshared：如果这个值非零，信号量在进程间共享；如果为零，信号量只在创建它的进程的所有线程之间共享。
- value：信号量的初始值。

sem_wait

用途：减少信号量的值（P 操作）。如果信号量的值为零，则调用线程将被阻塞，直到信号量值大于零。

继续阅读

四月 22, 2024

长度为n的字符串权重之和

4.21阿里笔试压轴题，状压dp->快速幂，可惜快速幂写错了，三分之一的测试用例因为超时没通过，复盘一下

题目：一个字符串由小写字母组成，其权重定义为不相邻的元音字母（即aeiou）对的个数，例如“aba”的权重为1，请设计程序，计算长度为n的所有字符串的权重之和，答案取模1000000009。

如n=3时，有权重为1的字符串“aaa”“abe”等，这些字符串的权重和为650。

很容易想到dp，而且想求某一特定字符串的权重并不难，但这并不是本题的重点。

经过比较长时间的思考+动笔计算，确定dp方法：dp[i]表示长为i的所有字符串的权重之和，dp[i]=dp[i-1]*26+(i-2)*25*26^(i-2)；大概的含义为，i-1字符串的权重和，加上第i个字母结尾的元音对所加入的新权重

#include <bits/stdc++.h>

#define MOD 1000000009
using namespace std;

long solve(int n);

int main() {
    int n;
    cin>>n;
    cout<<solve(n)<<endl;
}

long solve(int n) {
    vector<long> dp(n+1, 0);
    long pow=1;
    for(int i=3; i<=n; ++i) {
        pow = pow*26%MOD;
        dp[i] = (dp[i-1]*26%MOD + (i-2)*25*pow%MOD*26%MOD)%26;
    }
    return dp[n];
}

提交，通过66.7%的用例，提示内存过大，于是很容易想到状态压缩：

#include <bits/stdc++.h>

#define MOD 1000000009
using namespace std;

long solve(int n);

int main() {
    int n;
    cin>>n;
    cout<<solve(n)<<endl;
}

long solve(int n) {
    long pre=0, cur;
    long pow=1;
    for(int i=3; i<=n; ++i) {
        pow = pow*26%MOD;
        cur = (pre * 26 % MOD + ((i-2) * 25 % MOD) * pow % MOD) % MOD;
        pre = cur;
    }
    return cur;;
}

提交，还是只通过66.7%用例，提示超时。

继续阅读

四月 17, 2024

Hive中SQL转化为MapReduce的原理

JOIN操作实现原理

在MapReduce中实现join主要有以下几种方式：Reduce-side join、Map-side join、和Repartition join。下面详细介绍这些方法及其原理。

Reduce-side Join

Reduce-side join是MapReduce中最通用的join类型，适用于大规模数据集的连接，特别是当两个数据集都很大且没有任何特殊排序或分区时。

工作原理：

Map阶段：
- Mapper读取两个数据集的所有输入数据（可能来自HDFS的不同文件或目录）。
- 对每个输入记录，Mapper输出key-value对，其中key是join操作的键，value是包含数据集标识（如标记来自哪个数据集）和数据记录的值。
Shuffle阶段：
- MapReduce框架将所有Mapper输出的key-value对根据key进行分组和排序，然后分发给Reducers。
Reduce阶段：
- 每个Reducer接收到特定key的所有记录，这些记录来源于所有的Mapper。Reducer通过检查每条记录的来源数据集标识，将来自不同数据集的记录进行组合。
- 对于每个key，Reducer执行实际的join逻辑（如inner join, left join等），输出最终的结果。

Map-side Join

Map-side join通常在其中一个数据集很小（足够小到可以被加载到内存中）时使用，这种方法效率更高，因为它避免了在Reduce阶段进行大量的数据排序和分组。

工作原理：

预处理阶段：
- 小的数据集被分发到所有的Mapper节点上，通常通过将其存储在HDFS上并通过DistributedCache机制让每个Mapper节点访问。
Map阶段：
- 每个Mapper读取大的数据集，并同时加载小的数据集到内存。
- Mapper对大数据集的每条记录进行处理，使用内存中的小数据集进行即时join操作。
- 输出join后的结果。

Repartition Join

Repartition join是另一种Reduce-side join的形式，适用于需要特殊排序或分区的场景。

工作原理：

类似于普通的Reduce-side join，但在map阶段会对数据进行额外的分区和排序处理，以优化join的效率。

应用场景

当两个大数据集需要被连接时，使用Reduce-side join。
当一个小数据集可以全局广播到所有Mapper时，使用Map-side join。
当数据需要特殊处理或优化分区时，考虑使用Repartition join。

例如一个Reduce-side Join：

select u.name, o.orderid from order o join user u on o.uid = u.uid;

在map的输出value中为不同表的数据打上tag标记，在reduce阶段根据tag判断数据来源。

Group By操作实现原理

Map阶段

任务：读取输入数据，处理记录，并输出键值对。
输出：键是GROUP BY字段，值是需要聚合的数据。

Shuffle阶段

处理：框架自动对Mapper的输出进行排序和分组，确保相同的键被送到同一个Reducer。

Reduce阶段

聚合：Reducer接收到键和对应的值集合，进行数据聚合（如计数、求和）。
结果：输出每个组基于GROUP BY字段的聚合结果。

将GroupBy的字段组合为map的输出key值，利用MapReduce的排序，在reduce阶段保存LastKey区分不同的key。MapReduce的过程如下

继续阅读