题目

Problem 593. Fleeting Medians

We define two sequences and :

where pk is the kth prime number.

where denotes the floor function.

Then let M(i,j) be the median of elements S2(i) through S2(j), inclusive. For example, M(1,10) = 2021.5 and M(102,103) = 4715.0.

Let . For example, F(100,10) = 463628.5 and F(105,104) = 675348207.5.

Find F(107,105). If the sum is not an integer, use .5 to denote a half. Otherwise, use .0 instead.

分析

我们使用滑动窗口法来求中位数。由于 0 ≤ S2 ≤ 20012,而 k = 105,所以平均每个元素会出现 5 次,相当密集。因此我们使用数组来表示滑动窗口,而不使用 SortedDictionary<int, int>

解答

我们使用以下 C# 程序来解答此题:

 1: using System;
 2: using Skyiv.Utils;
 3: 
 4: static class E593
 5: {
 6:   static int[] GetS2(int n, int m)
 7:   { // nthPrime < n ln(n ln n) for n > 5
 8:     var primes = Primes.GetPrimes(0, (int)(n*Math.Log(n*Math.Log(n))));
 9:     int[] s1 = new int[n], s2 = new int[n];
10:     for (var i = 0; i < n; i++) {
11:       s1[i] = primes[i].ModPow(i+1, m);
12:       s2[i] = s1[i] + s1[(i+1) / 10000];
13:     }
14:     return s2;
15:   }
16: 
17:   static void Main()
18:   { // k must be even
19:     int m = 10007, n = (int)1e7, k = (int)1e5;
20:     Console.WriteLine("n = {0}, k = {1}", n, k);
21:     var s2 = GetS2(n, m);
22:     Console.WriteLine("s2: {0}", s2.Length);
23:     int[] a = new int[m+m-1], b = new int[m+m-1];
24:     var t = new int[k]; Array.Copy(s2, t, k); Array.Sort(t);
25:     int k2 = k / 2, c = t[k2 - 1], d = t[k2];
26:     for (var i = 0; i < k; i++) ((i < k2) ? a : b)[t[i]]++;
27:     var z = (c + d) / 2.0;
28:     for (int p, q, i = k; i < n; i++, z += (c + d) / 2.0)
29:       if ((p = s2[i - k]) <= c) {
30:         a[p]--;
31:         if ((q = s2[i]) <= c) { a[q]++; while (a[c] == 0) c--; }
32:         else if (q <= d) a[c = q]++;
33:         else { a[c = d]++; b[d]--; b[q]++; while (b[d] == 0) d++; }
34:       } else { // p >= d
35:         b[p]--;
36:         if ((q = s2[i]) >= d) { b[q]++; while (b[d] == 0) d++; }
37:         else if (q >= c) b[d = q]++;
38:         else { b[d = c]++; a[c]--; a[q]++; while (a[c] == 0) c--; }
39:       }
40:     Console.WriteLine("F(n, k) = {0:F1}", z);
41:   }
42: }

简要说明:

  • 第 6 行至第 15 行的 GetS2 方法生成 S2 序列。
  • 第 7 行的估计第 n 个素数的不等式请参阅参考资料[2]。
  • 第 8 行的 GetPrimes 方法请参阅参考资料[3]。
  • 第 11 行的 ModPow 方法请参阅参考资料[4]。
  • 第 19 行的 k 必须是偶数,这样,中位数是两个整数的算术平均值。
  • 第 23 行的数组 a 和 b 分别保存低于和高于中位数的部分。
  • 第 24 行的数组 t 保存的 S2 序列的前 k 个元素,然后排序。
  • 第 25 行的整数 c 和 d 是最靠近中间的元素,中位数就是它们的算术平均值。
  • 第 26 行初始化数组 a 和 b,下标是序列 S2 的元素值,数组的值是该元素出现的次数。
  • 第 27 行的浮点数 z 用于累加中位数,初始化为第 1 个中位数的值。
  • 第 28 行开始的主循环使用滑动窗口法求中位数的值。
  • 整数 p = s2[i - k] 是滑动时丢弃的值。
  • 整数 q = s2[i] 是滑动时增加的值。
  • 第 29 行至第 33 行处理 p 位于低半部时的情况。
  • 第 34 行至第 38 行处理 p 位于高半部时的情况。

这个程序的运行时间是 9 秒。实际上,98% 的时间都用于生成 S2 序列,只有 2% 的时间用于计算中位数,如下所示:

$ mcs 593.cs Primes.cs ModPow.cs && mono 593.exe | gnomon -i
   9.2630s | n = 10000000, k = 100000
   0.1973s | s2: 10000000
   0.0158s | F(n, k) = 96?32?20?42.0
           |
     Total | 9.4765s

参考资料

  1. Wikipedia: Median
  2. Wikipedia: Prime-counting function
  3. 图灵社区:编码:使用筛法生成素数
  4. 图灵社区:编码:幂的计算(C#)

评论

推荐 1
Fleeting Medians
应该如何翻译为中文?

推荐 1
前两天刚好也把中位数、众数等用Python捋了一遍。

推荐 1
c#的3元操作符? :还能((i < k2) ? a : b)[t[i]]++;这么用,也是神了
C 和 C++ 的也能够这么用。 –  黄志斌 03-07 08:00
在 C/C++ 中,如果 a 是一个数组,那么 a[2] 也可以写成 2[a] –  黄志斌 03-07 08:03
a[i] 也可以写成 i[a] –  黄志斌 03-07 08:03
a[i] 实际上是 *(a+i),由于加法满足交换律,所以可以对调 a 和 i –  黄志斌 03-07 08:08

推荐 1
我把你的z改为long,最后输出/2.0,几乎没影响,看来浮点除法也还好
计算中位数总共才用 0.1973 秒的时间,占 2%,既便把这个时间减少到 0 秒也影响不大。 –  黄志斌 03-07 08:07
c#的bool是bit还是char? –  lt 03-07 08:18
C# 的 bool 占用 1 个字节,char 占用 2 个字节 –  黄志斌 03-07 08:23
sizeof(bool) == 1 –  黄志斌 03-07 08:23
sizeof(byte) == 1 –  黄志斌 03-07 08:23
sizeof(char) == 2 –  黄志斌 03-07 08:23
所以说,C# 的 bool 类似于 byte –  黄志斌 03-07 08:24
谢谢,学习了 –  lt 03-07 09:02
我测试了一下,算p 3秒,算s 5秒,算s2 0.5秒 –  lt 03-07 09:05
嗯,用筛法生成素数需要 3 秒,计算 ModPow 需要 5 秒,简单的除法和加法只需要 0.5 秒。 –  黄志斌 03-07 09:13

推荐 1
我似乎看懂了,你维护的是一个hash表,记录每个键出现次数,累加后就可以找到中位数
不是 Hash 表,是两个整数数组,分别是低于和高于中位数的部分。 –  黄志斌 03-06 20:33
在滑动窗口时更新这两个数组的值,同时更新整数 c 和 d 的值,而中位数 = (c + d) / 2.0 –  黄志斌 03-06 20:34

推荐 1
上述代码还需要把GetPrimes ModPow等函数放进去

是的。这些函数在参考资料[3]和[4]中。 –  黄志斌 03-06 20:32
同时编译 3 个 C# 源文件:593.cs Primes.cs ModPow.cs –  黄志斌 03-06 20:36

推荐 0
中位数 = (c + d) / 2.0,
在求 F(100, 10) 的时候,
共计算了 90 个中位数,
其中 d - c 的分布如下:
51: 2
166: 1
167: 3
265: 1
...
3117: 1
3425: 1
3687: 1
4843: 2
4935: 2

推荐 0
中位数 = (c + d) / 2.0,
在求 F(10^5, 10^4) 的时候,
共计算了 90,000 个中位数,
其中 d - c 的分布如下:
0: 3,5621
1: 3,3080
2: 1,1698
3: 5,649
4: 2,578
5: 947
6: 300
7: 61
8: 54
9: 9
10: 1
11: 2

推荐 0
中位数 = (c + d) / 2.0,
在求 F(10^7, 10^5) 的时候,
共计算了 9,900,000 个中位数,
其中 d - c 的分布如下:
0: 8,862,064
1: 1,037,558
2: 378
k越大,滑动中位数越接近 –  lt 03-07 07:59

我要评论

需要登录后才能发言
登录未成功,请修改提交。