【プログラミング問題解答例】エラトステネスの篩(Python編)
↓問題はこちら↓
【プログラミング問題】エラトステネスの篩 - shiroの備忘録的メモ
解答例1
問題文のアルゴリズムに沿って、そのまま書いたものです。
初心者の方の練習用に使ってもらえたら嬉しいので、コメント付きです。
直観的なプログラムにはなっていると思います。が、激烈に遅いです。
# エラトステネスの篩 def sieve_of_eratosthenes(x): import math prime_list = [] # 1. 探索リストに2から指定した値maxまでの整数を昇順で入れる。 search_list = [i for i in range(2, x + 1)] # 3. 2の操作を探索リストの先頭値がmaxの平方根に達するまで行う。 search_end_num = math.sqrt(x) while search_list[0] < search_end_num: # 2. 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから削除する。 check_num = search_list[0] prime_list.append(check_num) for i in search_list: if i % check_num == 0: search_list.remove(i) # 4. 探索リストに残った数を素数リストに移動する。 prime_list += search_list return prime_list # 素数リストを取得して表示する prime_list = sieve_of_eratosthenes(10000) for prime in prime_list: print(prime)
解答例2
解答例1が遅いのはリストのremoveとか使って何度も無駄な探索してるせいでしょ、、、
ということで速度重視で書き直してみたものです。
10万までの素数で実行時間を調べてみたところ、だいぶ改善されました。
解答例1:約23.9[sec]
解答例2:約0.6[sec]
まだ明らかに遅い箇所があればぜひ教えてください。
# エラトステネスの篩(高速版) def sieve_of_eratosthenes_fast(x): import math judge_list = [True] * (x - 1) search_end_num = math.sqrt(x) check_num = 2 while check_num < search_end_num: for n in range(check_num + 1, x + 1): if n % check_num == 0: judge_list[n - 2] = False for n in range(check_num + 1, x + 1): if judge_list[n - 2]: check_num = n break prime_list = [] for i in range(2, len(judge_list)): if judge_list[i - 2]: prime_list += [i] return prime_list # 素数リストを取得して表示する prime_list = sieve_of_eratosthenes_fast(100000) for prime in prime_list: print(prime)
Twitterのアカウントが凍結されてしまった件
フリーとして活動していくうえであった方がいいかなーと思い立ち、
今更ながらTwitterアカウントを作成いたしました。
よろしくお願いします。
作成したのですが…
なんと半日ほどで凍結されてしまいました。
電話番号を登録すればOKみたいですが、
そんなことはしたくない。
その前提でロック解除してもらおうと奮闘したので、やりとりを残しておきます。
結論から言うと、連絡してすぐに解除してもらうことができました。
目次
経緯
アカウント凍結まで
Twitterアカウントを作成したのは3/18の夜。
フォローとプロフィール作成した時点で眠くなったのでその日は寝ました。
フォローした方は、興味あるものに「プログラミング」と入れた自動フォローの結果を少し精査した程度です。
で、起きて気づいたらロックされてしまっていたわけです。
サポートへの連絡を決意
慌てて復旧を試みると、「電話番号を登録せよ」とのこと。
これは困った。
最近、どこかで電話番号を書くたびに迷惑なショートメールが来るので、できるだけ不要なところには登録したくないんです。
だから、電話番号を聞かれるTwitterも登録していなかったのです。
が、アカウント作成時に「メールアドレスでも可」となっていたので登録したのです。
ここで電話番号を登録してしまっては本末転倒。
そこで、サポートに問い合わせて異議申し立てを行いました。
念のためTwitterルールには目を通して、違反していないことは確認したうえでです。
これが3/19の21:00過ぎです。
アカウント凍結の異議申し立て
異議申し立てページは入力フォームがあって、それを埋めていく形式でした。
問題の詳細には、
「突然アカウントが凍結されてしまっていましたが、心当たりがありません。電話番号を登録せずにロックを解除していただけないでしょうか?よろしくお願いいたします。」
のような感じで記載しました。
また、氏名は入力しましたが、電話番号は任意とのことでしたので未記入で送信しました。
メールで連絡
すると速攻で登録したメールアドレスに連絡が。
どうやら自動化動作に違反していたらしい。
そのほかの内容はTwitterルールとほぼ同じでした。
このメールはおそらく自動送信で、かつ
認証後も問題が発生する場合は、
発生している問題を詳細に記載してこのメッセージに返信してくだ さい。
と記載がありました。
「これはこっち待ち?」という印象を受けたので、仕方なくメールでお願いすることにしました。
記載通りこのメールに返信して、上で記載したような内容をメールしました。
この時点で3/19の21:35です。
アカウント凍結解除
すると数分後(3/19の21:43)にTwitterのサポートから連絡が。
どうやらもう解除して頂けたようです。
ということで、わたわたブログを書いている途中で解決してしまいました。
ちょっとIT系をかじっている者としての考察
ロックした技術の設計方針について
アカウントロック解除のメールに、下記の記載がありました。
Twitterは大量に自動生成されるスパムアカウントに対処す
るため、 これらを機械的に検出して一括削除するシステムを採用しています 。今回、 こちらのアカウントはシステムによりスパムグループとして誤検出 された可能性があります。このような誤検出は、 Twitterルール(https://twitter. com/rules) に違反する自動化動作が見られるアカウントに対して起こることが あります。
つまり、AI的なシステムの過剰な検出が原因ではないかと述べられています。
これは「False Positive」と呼ばれます。
日本語では「過検出」とか「誤検知」とか訳されるようです。
(医学関係の方は「偽陽性」と訳されます。そっちの方が歴史が長いです。)
要は「正しいものを間違っているものと判断してしまった」ということです。
反対に「False Negative」と呼ばれるものもあります。
日本語では「検出漏れ」と訳すとしっくりきます。
(医学関係の方は「偽陰性」と訳されます。)
要は「間違っているものなのに正しいものと判断してしまった」ということです。
一般的に、こういったチェック機構は
- False Negativeは可能な限り0に近づける
- そのうえで、False Positiveをできる範囲で少なくする
という方針で設計されます。
つまりTwitterは上記2.の技術がまだ発展途上、ということになります。
というより、「間違っているもの」側がなんとか検出を掻い潜ろうと工夫してくるので、日々その対策に追われていると考えたほうが自然な気がします。
技術の進歩も双方に影響するので、結局イタチごっこになります。
つまり、ちょっと待てば過検出率が改善される、ということでもないのです。
結局、ロックされた原因は?
結論から言うと、「よく分からない」です。
おそらくTwitter側の方々も明確には分からないのではないでしょうか。
判断の理由付けはAIの苦手なところですし。
Twitterがこういう対策をしていることは人に聞いて知っていたので、
「プロフィールをちゃんと作っとけばとりあえず大丈夫だろ」
とか
「一応なんかつぶやいておくか…」
とか考えて両方真っ先にやりましたが、関係なかったようです。
ということで、この検出は
- フォローしたアカウントが少ない
- 誰からもフォローされていない
あたりが要因でしょうか。
とはいえ、そんなに簡単な話ではないと思います。
おそらくはツイート数も含め、多次元で総合的に判断しているはずです。
なので一概に「こうしたら大丈夫!」とは言えないというのが結論です。
というかそれが分かってしまうと、スパムアカウントも作り放題になってしまうので困ります。
結論
上述の通り、 自動チェックがなされている以上、過検出はどうしても避けられません。
なので我々のような善良な一般ユーザーは、
アカウントロックされたら解除をお願いする
という対策で乗り切りましょう。
たまたまかもしれませんが、私はすぐに対応していただけました。
ぜひ参考にしてください。
ごあいさつ
はじめまして!shiroと申します。
自身で気づいたことや気になることなどを書き留めておこうと、技術ブログを設立しました。
ついでに趣味のつぶやきも書くかもしれません。
よろしくお願いいたします。
以下、簡単に自己紹介をいたします。
プロフィール
名前:shiro
年齢:31歳(2017年12月現在)
性別:♂
趣味:ゲーム
好きなアーティスト:ポルノグラフィティ、GARNET CROW
経歴
某国立大学の情報系学科に入り、そこで修士号まで取得しました。
2017年まで某大手メーカーでソフトウェア技術者として働いておりまして、
そこからはプログラミング等の講師をしております。
得意な分野
- AI (2010年ごろ大学で研究していた。)
- 組み込み (仕事で覚えた。エンベデッドシステムスペシャリスト持ってます。)
使える言語
- C言語:仕事で使って製品つくってた。メモリ操作系は人よりは得意だと思う。
- Java:ほぼ自分用のGUIツールをつくるために使ってた。
- Python:流行ってるから最近覚えた。現在のマイブーム言語だけどまだまだ未熟。
- C++:一応仕事で使ってたけど、C++っぽいコードはしばらく書いてないから忘れ気味。
- VBA:業務を楽にしたくて簡単なエクセルマクロを書いてた程度。