大規模演算に対応できるようなプログラミングの作り方(python3)

Question

###前提・実現したいこと
ネット上の練習問題(本の整理)を解いているのいるのですが、実行時間が長すぎて不合格となってしまいます。どのようにプログラムを書けば省メモリ・高速になりますか？

###発生している問題・エラーメッセージ
制限時間は16秒なのですがこれをオーバーしてしまいます。
メモリは512MBらしいです。

###該当のソースコード

number_of_books=int(input())
booksarray=list(map(int,input().rstrip().split()))
count=0
for i in range(number_of_books):
    if booksarray[i]==i+1:
        pass
    else:
        temporal=booksarray[i]
        booksarray[booksarray.index(i+1)]=temporal
        booksarray[i]=i+1
        count+=1
print(count)

num=int(input())
books=' '+input().rstrip()+' '
count=0
offset=1
for i in range(num):
    idnumber=books[offset]
    j=1
    while True:
        if books[offset+j]!=' ':
            idnumber+=books[offset+j]
            j+=1
        else:
            break
    offset+=len(str(i+1))+1
    if idnumber==str(i+1):
        pass
    else:
        temporal=idnumber
        books=books.replace(' '+str(i+1)+' ',' '+str(temporal)+' ')
        books=books.replace(' '+str(temporal)+' ',' '+str(i+1)+' ',1)
        count+=1
print(count)

###試したこと
リストではメモリを食いすぎると思い、文字列で同じことをやってみましたがやはりタイムオーバーとなってしまいました。

###補足情報(言語/FW/ツール等のバージョンなど)
（自分側に実行環境があるわけではないので、サードパーティ製のモジュール等は使えないです。）
お仰せの通りNumpyは使えました。
しかし、このアルゴリズムではやはりタイムオーバーとなってしまいました。

Comments

[miyahan]

NumPy は使えますよ？

[CHERRY]

paiza は、利用規約の禁止事項に「各種媒体で、paizaで出題した問題の内容、当該問題に対する解答、解答へのヒント等の示唆およびカンニング等の不正を助長する内容等を掲載する行為」とありますので、この質問はカンニングになりますよ。

Answer 1

興味深かったので、自分でも時間がかかりましたがやってみました。最終的にはPython3と標準ライブラリという組み合わせで、大規模データを全て0.14〜0.16秒でパスすることが出来ました。(sortやsortedはもちろん使用していません)

ただなんか直接的なヒントを書くのはご法度のようなので、一般論をアドバイスします。

1. 最後の出力と後続の処理に不要な事は一切しない。
2. なるべくCに近い低級なデータの取り扱い方に絞る。
3. CPU時間(検索オーダー)の節約のためにメモリはふんだんに使う、節約なんてしない。
4. Pythonに備わっている高級な検索やフィルタ機能は使用しない、使用したら負け。

頑張ってください。

Comments

[Gargantua]

今までスピードやメモリを意識したプログラムを書いたことがなかったので、この方針はとてもこれから役に立ちます。ありがとうございました。なおこの問題は練習問題であり、スキル認定とは関係がない問題なので、実際的にインターネット上で質問することに問題はないと思われます。

Answer 2

間違って回答してしまいました
すいません

Answer 3

ふふっふあははははは