pow_mod, inverse の速度

ベンチマークコード

適当．g++ -O2．標準入力は適当に10とか入れてる．

const ll MOD = 1000000009;

const int N = 2000000;

int main() {
  int a;
  scanf("%d", &a);

  ll t = a;
  for (int k = 1; k <= N; ++k) {
    t = inverse(t, MOD) * k % MOD;
  }
  printf("%lld\n", t);

  return 0;
}

今までのやつ

駆け出しだった頃の僕が，適当に bmerry か誰かのやつを参考にして書いた．中で再帰している上にいちいち丁寧に正にするために % を 2 回もとってて遅そう．（でもマイナスが帰るとそれが原因のバグをつくりそうで恐ろしいからなあ）

inline ll mod(ll a, ll m) { return (a % m + m) % m; }

ll inverse(ll a, ll m) {
  if ((a = mod(a, m)) == 1) return 1;
  return mod((1 - m * inverse(m % a, a)) / a, m);
}

~/contests/tmp% time ./a.out <<< 10 [14:10:35]
249011238
./a.out <<< 10 2.84s user 0.01s system 99% cpu 2.870 total
~/contests/tmp% time ./a.out <<< 10 [14:10:39]
249011238
./a.out <<< 10 2.85s user 0.00s system 99% cpu 2.870 total
~/contests/tmp% time ./a.out <<< 10 [14:10:43]
249011238
./a.out <<< 10 2.83s user 0.02s system 99% cpu 2.868 total

inline

再帰関数だからあんま意味分からんと思うが一応 inverse に inline つけてみた．

~/contests/tmp% g++ -O2 inverse.cpp [14:11:39]
~/contests/tmp% time ./a.out <<< 10 [14:11:41]
249011238
./a.out <<< 10 2.75s user 0.00s system 99% cpu 2.763 total
~/contests/tmp% time ./a.out <<< 10 [14:11:44]
249011238
./a.out <<< 10 2.75s user 0.00s system 99% cpu 2.762 total
~/contests/tmp% time ./a.out <<< 10 [14:11:49]
249011238
./a.out <<< 10 2.75s user 0.00s system 100% cpu 2.748 total

ちょっぴりはやくなったｗ


pow_mod １

今まで使っていた pow_mod を使う．これも再帰していて丁寧に mod を呼んでいて見るからに遅そうである．

inline ll mod(ll a, ll m) { return (a % m + m) % m; }

ll pow_mod(ll a, ll k, ll m) {
  if (k == 0) return 1;
  ll t = pow_mod(a, k / 2, m);
  return mod(mod(t * t, m) * (k % 2 ? a : 1), m);
}

inline ll inverse(ll a, ll m) {
  return pow_mod(a, m - 2, m);
}

~/contests/tmp% time ./a.out <<< 10 [14:13:19]
249011238
./a.out <<< 10 3.39s user 0.00s system 99% cpu 3.407 total
~/contests/tmp% time ./a.out <<< 10 [14:13:23]
249011238
./a.out <<< 10 3.39s user 0.00s system 99% cpu 3.407 total
~/contests/tmp% time ./a.out <<< 10 [14:13:28]
249011238
./a.out <<< 10 3.37s user 0.02s system 99% cpu 3.411 total

遅くなったｗ


pow_mod ２

pow_mod を高速そうな実装にしてみる．

inline ll pow_mod(ll a, ll k, ll m) {
  ll r = 1;
  for (; k > 0; k >>= 1) {
    if (k & 1) (r *= a) %= m;
    (a *= a) %= m;
  }
  return r;
}

~/contests/tmp% time ./a.out <<< 10 [14:16:27]
249011238
./a.out <<< 10 0.45s user 0.01s system 99% cpu 0.463 total
~/contests/tmp% time ./a.out <<< 10 [14:16:28]
249011238
./a.out <<< 10 0.47s user 0.00s system 100% cpu 0.468 total
~/contests/tmp% time ./a.out <<< 10 [14:16:31]
249011238
./a.out <<< 10 0.45s user 0.01s system 99% cpu 0.463 total

むっちゃはやくなったｗ

少し予想はしていたが，今までのはやはり爆遅だった

Compact routing in power-law graphs

Wei Chen, Christian Sommer, Shang-Hua Teng, and Yajun Wang. 2009. Compact routing in power-law graphs. In Proceedings of the 23rd international conference on Distributed computing (DISC'09), Idit Keidar (Ed.). Springer-Verlag, Berlin, Heidelberg, 379-391.

実際にはTALGに出しているらしき原稿の方を読んだ． こっちだと数式がレンダリングされます http://iwi.tc/wiki/index.php?%E8%AB%96%E6%96%87%2F%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96%E7%B3%BB%2FA%20Compact%20Routing%20Scheme%20and%20Approximate%20Distance%20Oracle%20for%20Power-law%20Graphs

続きを読む

A model-based approach to attributed graph clustering

Zhiqiang Xu, Yiping Ke, Yi Wang, Hong Cheng, and James Cheng. 2012. A model-based approach to attributed graph clustering. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD '12). ACM, New York, NY, USA, 505-516. DOI=10.1145/2213836.2213894 http://doi.acm.org/10.1145/2213836.2213894

続きを読む

ネットワークの成長

辺が追加されることのみが考慮されるモデル・アルゴリズムが横行している．なんでなんだろう？とずっと思っていた．

辺が一方的に追加されていくネットワークの成長のデータセットを公開している Alan Mislove の博論を見た．

6.2 Growth dominates network evolution

In all of the networks we examined, we found that link addition was significantly more frequent than link removal. In particular, we found that in Flickr, link additions exceeded link removals in our data sets at a rate of 2.43:1. Similar characteristics were observed in the other networks we studied: in YouTube-U, the ratio of link additions to removals was 3.71:1, and in the Internet, we found that the ratio was 2.06:1.

うーん……一番大きくても 3.71:1 って辺の削除も結構大きいと思うが……