題目描述
給予序列 $A \left\lbrack 1 \cdots n \right]$,請計算前綴和序列 $S \left\lbrack 1 \cdots n \right]$,其中 $$ S \left\lbrack i \right] = \sum_{k=1}^{i} A \left\lbrack k \right]$$
為了檢測方便,移除輸入和輸出時間,序列 $A$ 由一個簡單加密 $\textit{key}$ 得到序列 $$ A \left\lbrack i \right] = \textit{encrypt}(i, \textit{key})$$ 以及輸出部分直接呼叫 $\textit{output}(\textit{S}, n)$。注意 $S\left\lbrack 0 \right] = 0$,儲存答案的範圍為 $S\left\lbrack 1 \cdots n \right]$。
utils.h
可以直接 #include "utils.h"
在你的程式中。
1234567891011 #ifndef _UTILS_H
#define _UTILS_H
#include <stdint.h>
static
inline
uint32_t rotate_left(uint32_t x, uint32_t n) {
return
(x << n) | (x >> (32-n));
}
static
inline
uint32_t encrypt(uint32_t m, uint32_t key) {
return
(rotate_left(m, key&31) + key)^key;
}
void
output(uint32_t presum[],
int
n);
#endif
prefixsum-seq.c
請修改這份程序。
12345678910111213141516171819202122 #include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include "utils.h"
#define MAXN 10000005
#define MAX_THREAD 4
uint32_t prefix_sum[MAXN];
int
main() {
int
n;
uint32_t key;
while
(
scanf
(
"%d %"
PRIu32, &n, &key) == 2) {
uint32_t sum = 0;
for
(
int
i = 1; i <= n; i++) {
sum += encrypt(i, key);
prefix_sum[i] = sum;
}
output(prefix_sum, n);
}
return
0;
}
secret.c (測試用)
實際情況會用助教寫好的平行方式進行計算且雜湊公式不同。
123456789101112 #include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include "utils.h"
void
output(uint32_t presum[],
int
n) {
uint32_t hash = 0;
for
(
int
i = 1; i <= n; i++)
hash += presum[i] * i;
printf
(
"%"
PRIu32
"\n"
, hash);
}
輸入格式
輸入有多組測資,每組測資一行兩個整數 $n$, $\textit{key}$,分別為序列長度 $n$,加密金鑰 $\textit{key}$。
- $1 \le n \le 10^7$
- $0 \le key \lt 2^{32}$
輸出格式
對於每一組測資呼叫 output(uint32_t presum[], int n)
,隨後會輸出一個數值。
範例輸入
3 2
10 5
範例輸出
100
54560
範例解釋
- $(n, \textit{key})=(3, 2)$,得 $A \left\lbrack 1 \cdots 3\right] = \left\lbrack 4, 8, 12 \right]$,$S \left\lbrack 1 \cdots 3\right] = \left\lbrack 4, 12, 24 \right]$,$\text{hash} = 4 + 12 \times 2 + 24 \times 3 = 100$
編譯方式
1 gcc -std=c99 -O2 -pthread prefixsum-
seq
.c secret.c -o prefixsum-
seq
測試主機資訊
推薦使用 6 個執行緒解決此問題,平行效能接近 2 倍改進。若使用過多的執行緒,將因為要排到另一個處理器上運行而變慢。
由於 NUMA 的緣故,在主程式運行前,將其執行緒設定在 CPU0~CPU5 之間運行,其測試結果較為穩定。
#define _GNU_SOURCE
...
int
main() {
{
cpu_set_t cpuset;
CPU_ZERO(&cpuset);
for
(
int
i = 0; i < 6; i++)
CPU_SET(i, &cpuset);
assert
(sched_setaffinity(0,
sizeof
(cpuset), &cpuset) == 0);
}
...
processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 62
model name : Intel(R) Xeon(R) CPU E5-2620 v2 @ 2.10GHz
stepping : 4
microcode : 0x415
cpu MHz : 1200.000
cache size : 15360 KB
physical id : 0
siblings : 12
core id : 0
cpu cores : 6
apicid : 0
initial apicid : 0
fpu : yes
fpu_exception : yes
cpuid level : 13
wp : yes
processor : 1
vendor_id : GenuineIntel
cpu family : 6
model : 62
model name : Intel(R) Xeon(R) CPU E5-2620 v2 @ 2.10GHz
stepping : 4
microcode : 0x415
cpu MHz : 1200.000
cache size : 15360 KB
physical id : 0
siblings : 12
core id : 1
cpu cores : 6
apicid : 2
initial apicid : 2
fpu : yes
fpu_exception : yes
cpuid level : 13
wp : yes