Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

replace_color 関数の高速化の提案 #5

Closed
koyumeishi opened this issue Jun 3, 2024 · 0 comments
Closed

replace_color 関数の高速化の提案 #5

koyumeishi opened this issue Jun 3, 2024 · 0 comments

Comments

@koyumeishi
Copy link
Contributor

starline.pyreplace_color 関数の高速化の提案です:
https://github.com/mattyamonaca/starline/blob/main/starline.py#L30-L75

現在のアルゴリズムは以下のような流れになっています:

  1. color_1 で塗られているピクセルを列挙する
  2. (1) のピクセルの 4-近傍に color_1color_2 ではない色で塗られているピクセルがあるなら、その色で上書きする
  3. 新たに上書きされたピクセルがなければ終了
  4. (1) に戻る

このアルゴリズムは color_1 の外側の領域から徐々に浸食していくイメージです。ただ、この方法だと全ピクセルの走査が何度も行われるので、時間がかかってしまいます。

そこで、幅優先探索を使って color_1 の境界付近のセルを順に上書きしていく方法を提案します。これにより、一回の走査で対象のピクセルを上書きできるようになります。

手元の環境では、元のアルゴリズムで replace_color に約 60 秒かかっていた入力が、この新しい方法では 0.6 秒ほどに短縮されました。

以下が提案するコードです。一部高速化のためのトリッキーなコードがありますが、根幹は基本的な幅優先探索です (これがないと 4 秒ほどになりました)
https://github.com/koyumeishi/starline/blob/main/starline.py#L30-L99

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants