質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
87.20%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

PyPy

PyPy(パイパイ)は、RPythonで記述されたPythonの実装のひとつです。CPythonとの互換性に重点を置いて開発されており、コードを必要に応じて機械語にコンパイルする「JITコンパイル機能」を備えています。

解決済

pythonとPyPyの計算時間の違いに関して

Algeot
Algeot

総合スコア19

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

PyPy

PyPy(パイパイ)は、RPythonで記述されたPythonの実装のひとつです。CPythonとの互換性に重点を置いて開発されており、コードを必要に応じて機械語にコンパイルする「JITコンパイル機能」を備えています。

2回答

0リアクション

0クリップ

279閲覧

投稿2022/07/29 08:12

計算時間に関する質問になります.
Pop count (2進数表記におけるbitが1であるものの個数) を求める関数popcountと, 同様のことが可能な組み込み関数count('1')の実行時間をそれぞれ出力し, さらにその結果をpythonとPyPyで比較します.

Python

def popcount(n): c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555) c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333) c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f) c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff) c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff) c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff) return c

検証方法としては, 恣意的に選んだ64bit以下の大きな数Nのpopcountを 30 ** 2 回計算し, 全体の時間を求めるということを行っております.

Python

import time N = 2 ** 63 + 5 ** 15 s = time.perf_counter() for _ in range(3000): for _ in range(3000): a = popcount(N) t = time.perf_counter() print(t - s) s = time.perf_counter() for _ in range(3000): for _ in range(3000): a = bin(N).count('1') t = time.perf_counter() print(t - s)

これをpython3.9で実行すると

popcount関数→ 6.4915954秒
組み込み関数→ 3.3203775秒

という結果になり, またPyPy3.11で行ったときには

popcount関数→ 0.0214806秒
組み込み関数→ 1.3355724秒

という結果が得られました.

ここでご教授いただきたい質問とは, PyPy において popcount 関数が高速であることは分かったが, pythonでそれを行った場合に組み込み関数より遅くなってしまうのはどうしてか, ということです.

このpopcount関数はそれを求めるのに高速なアルゴリズムとして紹介されていた関数です.
一般に速いということは理解しております.
そうであるのにpythonで動作させると非常に遅くなってしまうのはなぜなのでしょうか.
count('1')の構造や, pythonとpypyの違い等について, 何かご存知の方がいらっしゃれば, この原因を推測していただきたいです.
拙い知識と説明になりますが, 何卒宜しくお願い致します.

以下のような質問にはリアクションをつけましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

リアクションが多い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

まだ回答がついていません

会員登録して回答してみよう

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

PyPy

PyPy(パイパイ)は、RPythonで記述されたPythonの実装のひとつです。CPythonとの互換性に重点を置いて開発されており、コードを必要に応じて機械語にコンパイルする「JITコンパイル機能」を備えています。