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

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

ただいまの
回答率

90.63%

  • Python 3.x

    5866questions

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

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

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 354

Gargantua

score 9

前提・実現したいこと

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

発生している問題・エラーメッセージ

制限時間は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は使えました。
しかし、このアルゴリズムではやはりタイムオーバーとなってしまいました。

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

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

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • miyahan

    2017/09/30 21:07

    NumPy は使えますよ?

    キャンセル

  • CHERRY

    2017/09/30 22:21

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

    キャンセル

回答 1

checkベストアンサー

+2

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

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

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

頑張ってください。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

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

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

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/10/01 11:05

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

    キャンセル

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

  • ただいまの回答率 90.63%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 解決済

    Python入力

    Python3での入力についての質問です。 もっとスマートな書き方を教えてほしいです。 a = int(input()) b = int(input()) c = int(in

  • 受付中

    ターミナルで実行するのに時間がかかりすぎる

    ターミナルで実行するのに時間がかかりすぎます。 画像圧縮のアルゴリズムを書いています。 N × N ピクセルのグレースケール画像があり各ピクセルの画素値は 0 から 255

  • 解決済

    Pythonで得られたデータがint型でない時のみ処理をスキップしたいです

    現状以下のようなコードを書いています while True: rssi = [] dist = [] val = [] for k in ra

  • 解決済

    最後に改行する方法python3

    前提・実現したいこと ここに質問したいことを詳細に書いてください (例)PHP(CakePHP)で●●なシステムを作っています。 ■■な機能を実装中に以下のエラーメッセージが発生し

  • 解決済

    複数行のinput入力

    前提・実現したいこと 複数行のinput()入力がしたい。 【やりたいこと】 >>n = input() 1 2  3  >>print(n) 1 2 3 2を入れようとし

  • 受付中

    プログラムを見やすく改良したい

    正常に動くプルグラムを見やすく改良したい。 具体的に教えていただければありがたいです。セグメンテーションフォルトでベスト7まで表示して停止します。173行あたりだと思うのですが、よ

  • 解決済

    int(input())から得た正の整数から1までの数を求めたい

    標準入力から得た正の整数から1までの値を出力したいです。 よろしくお願いいたします。 ▼例1 入力:3 →出力:1,2,3 ▼例2 入力:10 →出力:1,2,3,4,5

  • 解決済

    pythonで連続出力

    ループ処理でリストから一つずつ取り出して、それを変換したものを、 一行に2個、半角スペースで区切って表示したいのですが、どうしたら良いでしょうか。 入力サンプル 3 2 46 

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

  • Python 3.x

    5866questions

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