文字列結合が遅い

pythonだと文字がイミュータブル(作成後に変更できない)ので、変更のたびにオブジェクトが再作成される。
そのため、文字列結合をループとかで繰り返し行う場合、ループごとに変更を行うと遅い。

s = ""
for i in range(10)
    s = s + str(i)

print(s)

そのため、

s = []
for i in range(10)
    s.append(str(i))

s= ''.join(s)
print(s)

リスト操作の注意点

内容的には同じだが、参照する回数を減らすために

for i in range(n)
    list[i] = list[i] +1

これで実行時間が一割くらい変わった

for i in range(n)
    list[i] +=1

    for i in range(1, n):
        for j in range(i+1, n+1):
                list[minCost] +=1

dictがhashテーブルのためinとか使う際の速度が大きく違う。