5000個の数字をファイルから読み込んで和を求め、一〇桁だけ取る。

Question

現在、Project Eulerというサイトの問題(問題13)を解いています。問題は、5000個のランダムの整数の和の最初の10桁を求めるというものです。

問題13

##これまでやってみたこと

Pythonを使って一行ずつ文字列として読み込んで、それを整数を要素とするリストに変換して、for文でループを回して和を求めてほしい桁をスライスで取ろうと考えましたが、5000個の和を求めるところで(当然ですが)、スピードが遅くなってしまうようです。

そこでnumpyのsum関数が使えないかと考えたのですが、どうもうまくいきません。それ以外にも手を加えると、文字列から整数への変換等の処理が増えてしまうと考えられ、速度を落とすことができません。

import numpy as np
def sample5000_read():
    number_line = []
    sample_5000 = open('sample5000.txt','rt')
    number_line = sample_5000.read()
    sample_5000.close()
    number_line = number_line.replace('\n','')
    return list(str(number_line))

def number_list():
    number_list=[]
    number_list = [int(sample5000_read()[i]) for i in range(len(sample5000_read()))]
    return np.array(number_list)

if __name__=='__main__':
        print(number_list().sum())

sample5000.txtにはウェブサイトそのままのデータがテキストファイルに入っています。100行x50列

##ほしいアドバイス
Pythonのリスト機能を使わずに、速度を上げたいと考えています。基本的にはnumpyを使って処理したいと考えているので、numpyのライブラリでこうすればいいのではないかというところがあれば教えていただきたいです。また、Python初心者なので、コードの改善点や、その他のライブラリでも役に立ちそうなのがあれば、ぜひ教えていただけると大変光栄です。

以上よろしくお願いします。

Answer 1

まず計算が遅い理由ですが、決してリストのsum() が遅いからではありません。

原因はデータ文字列を数値のリストに変換する内包表記

number_list = [int(sample5000_read()[i]) for i in range(len(sample5000_read()))]

の部分です。

理由は簡単で、上記の記述だとループの回数（5000回）分 sample5000_read() 呼び出してしまうので、結果ファイルのopen()/close() を5000回（正確には5001回）行っています。

これを修正するには

data = sample5000_read()
number_list = [int(data[i]) for i in range(len(data))]

のようにデータを別変数に格納しておくのが良いかと思います。

この変更だけでかなり処理が早くなります。

更に上記の部分は index値ではなくデータそのものでループを回すように修正できます。

data = sample5000_read()
number_list = [int(d) for d in data]

または

number_list = [int(d) for d in sample5000_read()]

と修正できます。

これでまた少し早くなると思います。

ここまで来ると、内包表記をmap()で

number_list = map(int, sample5000_read())

のように簡単に書き換えることができ、これでかなり高速になると思います。

あとは リストをsum() で

print(sum(number_list))

もしくはNumpyを使って

print(np.array(list(number_list)).sum())

Python3 の場合、map() の結果を Numpy.array() に変換する為に、一度 listに変換する必要があります。

とすると合計が求まります。

Comments

[退会済みユーザー]

詳しい回答ありがとうございます。遅い部分の解説がわかりやすく助かりました。
map関数の使用は考えたのですが、mapオブジェクトを返してしまうので、途方にくれていました。
再度調べ直したら(http://swimmingpython.net/ja/?p=565)map関数の値はlistで変換する必要があるようです。

-------------------------------------------------
ご助言通り、以下のように書き換えてみました.
'''
def sample5000_read():
number_line = []
sample_5000 = open('sample5000.txt','rt')
number_line = sample_5000.read()
sample_5000.close()
number_line = number_line.replace('\n','')
return list(str(number_line))

def number_list():
number_list=[]
number_list = map(int, sample5000_read())
return number_list

if __name__=='__main__':
print(sum(number_list()))
'''
このソースコードでは、計算結果が22660とでますが(他の回答者様同様)、正解ではないようです。。。正解は(https://pythonandr.com/2015/09/01/large-sum-project-euler-problem-13/)にある値のようです(10桁)。

[退会済みユーザー]

他の回答者様のご指摘にあったのですが、少し問題の解釈を間違えていたようです。お手数おかけして大変申し訳ありません。

Answer 2

# coding: utf-8

print(str(sum(list(map(int, open("sample5000.txt").read().split("\n")))))[:10])

#encoding: utf-8

print open("sample5000.txt").read.split("\n").map(&:to_i).inject(:+).to_s[0..9]

Pythonは全く分かりませんが考えてみました。
個人的にはlistを使った方が簡単だと思います。

参考にしたページ
問題の内容
Problem 13 「大きな数の足し算」
以下の50桁の数字100個の合計の上から10桁を求めなさい。

答え
Project Euler 13: Sum of 50-digit numbers
PROJECT EULER PROBLEM 13

#追記
5000個の整数を足す

# coding: utf-8

print(sum(list(map(int, sum(list(map(lambda x: list(x), open("sample5000.txt").read().split("\n"))), [])))))

結果

22660

#encoding: utf-8

print open("sample5000.txt").read.split("\n").map{|e| e.split("")}.flatten.map(&:to_i).inject(:+).to_s

結果

22660

この数字が正しいかどうかは分かりません。

Comments

[退会済みユーザー]

回答ありがとうございます。
いろいろ修正しつつやっていますが、どうしても解答は22660になってしまいますね。ただ、ネットの解答を見る限り間違いなようです。どうして間違いかも気になるところです。

(他の回答者の方へ) 現在いろいろ考えて教えていただいた内容を考えているので、お待ちいただけると幸いです。

[退会済みユーザー]

wikiの日本語訳された問題文によると、改行までの50文字で1つの数字みたいです。それを全て足して前から10文字とると「参考にしたページ」の「答え」に書いてある5537376230になります。
私が書いた、追記より上の2つのコードを実行すると5537376230になります。

[退会済みユーザー]

ほんとですか！
これは大変勘違いしていました。解釈間違いで巻き込んでしまい申し訳ありません。とにかく、どういう形であれ、助けてもらえてよかったです。頂いた解答も参考にしつつ、もう少し考えてみます。

[退会済みユーザー]

いえいえ。wikiと答えについては私の回答の「参考にしたページ」にリンクをつけているので、時間があればどうぞ。

Answer 3

ヒントだけ。
numpy使わないほうが簡単にできます。
素直に下の位から足していけばよいです。繰り上がりは桁毎にすればよいです。
だいたい50桁×100行=5000回の足し算だけでできます。

Comments

[退会済みユーザー]

回答ありがとうございます。
私が少し勘違いしていたようです。