python 辞書 値 ○個単位で最小値を求める

Question

num = [i for i in map(int,input().split(" "))] #入力データの一行目取り出し [7, 3]

date=[]
uryo=[]
for i in range(num[0]): #7回繰り返し


    dater=[i for i in map(int,input().split(" "))] #入力データをリストとして取り出し
    date.append(dater[0])
    uryo.append(dater[1])
    player_ans = {}
    for h, p in zip(date, uryo): #取り出した入力データをリストに格納
        player_ans[h] = p 

#上記6行に渡って、「入力データ取り出し　⇒　リスト　⇒辞書」としています。
#下記の1行でできると思ったのですが、上手く動かなかったので、やむを得ず上記のコードとしています。
#player_ans = {date:uryo for date,uryo in input().split(" ")} 動かない

print(player_ans) #{1: 0, 2: 20, 3: 10, 4: 80, 5: 10, 6: 0, 7: 10}

#入力データ
7 3 #7は下記入力データの数を表している。 3は連続する回数を表している。 ※詳しくは下記に。
1 0
2 20
3 10
4 80
5 10
6 0
7 10
#希望する出力 5

『やりたいこと』
・入力データの2行目（1,0)からを対象に、右の数字（今回の場合は3個単位 ※最初の入力データの3をみる）を合計。
最も低い合計の行を出力したい。

　今回の入力データの場合、まず
1 0
2 20
3 10
これらの右の数を合計（30）

　次に
2 20
3 10
4 80
これらの右の数を合計（110）

　3 10
4 80
5 10
これらの右の数を合計（100）

　と、最後までみていき、
合計が最も低い行を出力したい。
今回の入力データでは、
5 10
6 0
7 10
が、合計20となるため、この合計値の先頭（5）を出力

・3個単位で合計を見る必要があるため、例えば先頭の（1,0）が最小（値0）ということで出力するのはNG
最後の（6,0　7,10）が最小（値10）ということで出力するのもNG(2行しかみていないため）

『考えたこと』
・辞書型にして、行をkeyに、値をvalueに、値を3個単位で合計して最小値を求めるのが楽かと思ったんですが、
どのようなコードで計算すればいいかつまづいてしまいました。
※載せているコードは、入力データを辞書化しただけです。

『ご質問』
・辞書型で解く方法、もしくは別なやり方がありましたら、ご教授いただきたいです。
・今回、入力データをリスト化して、辞書型としていますが、
もっと楽に辞書型にできるようでしたら、こちらもご教授いただきたいです。　

ここまで長くなってごめんなさい。
よろしくお願いします。

Answer 1

回答の前にひとつアドバイスしますと、

    player_ans = {}
    for h, p in zip(date, uryo): #取り出した入力データをリストに格納
        player_ans[h] = p 

これをforの中に入れるのはやめましょうか（無駄だから）。

---

どうせ辞書に入れるなら、もうすこし旨味のある入れ方をした方が良いでしょう。

# めんどいので入力周り省略
num = [7, 3]
date = [1,2,3,4,5,6,7]
uryo = [0,20,10,80,10,0,10]

dn, span = num  # 扱いづらいのでunpack
player_ans = {}
for i in range(dn - span + 1):  # このforループの意味は頭をひねって考えること
    player_ans[date[i]] = uryo[i:i+span]

# 以下3つは確認用のprint
print(player_ans)  # => {1: [0, 20, 10], 2: [20, 10, 80], 3: [10, 80, 10], 4: [80, 10, 0], 5: [10, 0, 10]}
print(player_ans.items())  # => dict_items([(1, [0, 20, 10]), (2, [20, 10, 80]), (3, [10, 80, 10]), (4, [80, 10, 0]), (5, [10, 0, 10])])
print(min(player_ans.items(), key=lambda x:sum(x[1])))  # => (5, [10, 0, 10])

# 最終的にほしいもの
print(min(player_ans.items(), key=lambda x:sum(x[1]))[0])  # => 5

# こっちでもいいかなぁ
print(min(player_ans, key=lambda x:sum(player_ans[x])))  # => 5

あるいは、

for i in range(dn - span + 1):  # このforループの意味は頭をひねって考えること
    player_ans[date[i]] = sum(uryo[i:i+span])

で後ろのminのkeyが単純になります。後からリストを使わないのならこの方が良いかも。

Comments

[zeitaku_fire]

いつもありがとうございます。
下記のように理解しました。誤ってましたらご指摘お願いします。
ただ、疑問が2点あります。

>>dn, span = num # 扱いづらいのでunpack
⇒numの値をdn=7 span=3へ　解釈。

>>for i in range(dn - span + 1): # このforループの意味は頭をひねって考えること
>> player_ans[date[i]] = uryo[i:i+span]
⇒まず、繰り返し条件の「dn - span + 1」
　これは、数値にすると5になる
　なぜ5かというと、7個の数値を3個単位で合計する場合、必要なリストの数は合計5となることから、この計算式としている。

次に「player_ans[date[i]] = uryo[i:i+span]」
左の部分「player_ans[date[i]]」、date[i]としていることから、keyを指定されていると想定。
右の部分「uryo[i:i+span]」、uryoはリスト化されていて、[i:i+span]というのは、リストの○番目から○番目を抽出して、keyにリストとして値をもたせている。

『疑問』
2点あります。
■for i in range(dn - span + 1)
上記の場合、iは0からはじまります。現に、iをprintしてみたら、0,1,2･･･となっていました。
しかし、下記コードのdate[i]は1,2,3･･･となっています。
player_ans[date[i]] = uryo[i:i+span]　
i+1という表記はどこにもないはずなのに、なぜ、1がはいるのでしょうか？

■print(min(player_ans.items(), key=lambda x:sum(x[1]))[0]) # => 5
前半部分「min(player_ans.items()」ここの意味は、player_ansは辞書化されていて、値には3個ずつにまとめたリストが入っている。minを指定しているから、最小値のkeyとvalueがitemsにより選択されると解釈。
その先のlambda「key=lambda x:sum(x[1]))[0])」について、
xに前半部分のminで指定したkeyとvalueが引数と渡されて、:の後の処理を行っているのだと想定したのですが、
key=とsum(x[1]))[0])これは何をやっているのでしょうか。。？

[hayataka2049]

疑問1：date = [1,2,3,4,5,6,7]だから。date[0]は1
疑問2：:sum(x[1]))[0])という処理はしていません。3つめの確認用printで出ている結果から、キーだけ取り出してるのが後ろの[0]で、これはminの外にあります
あとはすべてminの中で完結しています。minのkeyについては理解しづらかったら調べると解説記事があると思います

[hayataka2049]

maxだけど、こんな記事があった
http://cointoss.hatenablog.com/entry/2013/10/16/123129

[hayataka2049]

あとこんなのもわかりやすいかも
http://doc.code161.com/python/list-key-usage/

[zeitaku_fire]

ご教授ありがとうございます。
keyについて、理解が深まりました。
記事も目を通しました。
今後ともよろしくお願いします。

Answer 2

個人的には、辞書を使わない方が書きやすい気がします。

解法の方針
0. 3個ずつ組にしたタプルのリストを作る
0. 最も合計値が小さいタプルのインデックスを調べる

n, span = map(int, input().split())

nums = [
    int(input().split()[-1]) for _ in range(n)
]

groups = zip(*[nums[s:] for s in range(span)])
indice = [
    index 
    for index, group in sorted(
        enumerate(groups, start=1),
        key=lambda ig: sum(ig[-1])   # (index, num_group)
    )
]

print(indice[0])

Wandbox

---

hayataka2049さんのご指摘を受けて修正したバージョン。

n, span = map(int, input().split())

nums = [
    int(input().split()[-1]) for _ in range(n)
]

groups = zip(*[nums[s:] for s in range(span)])
index, _ = min(
    enumerate(groups, start=1),
    key=lambda ig: sum(ig[-1])   # (index, num_group)
)

print(index)

Wandbox

せっかくなので

辞書を使った方法も書いてみた。

n, span = map(int, input().split())

nums = [
    int(input().split()[-1]) for _ in range(n)
]

sum_dict = {
    i: 0 for i in range(n-span+1)
}
for key in sum_dict:
    for i in range(span):
        sum_dict[key] += nums[key+i]
        
index = sorted(sum_dict.items(), key=lambda item: item[-1])[0][0]
print(index+1)

Wandbox

コメントを受けて

enumerateなんですが、for文の際に使うもので、リストのインデックスをとるときに使用するものだと認識しておりますが、for文がありません。

ここでのenumerateは何をしているのでしょうか。。？

また、groupsは上記でタプルにされているデータをさしているのはわかるのですが、stard=1は何なのでしょうか？

for文で良く用いられるのは確かですが、その実態はジェネレータを返しているだけなのです。
また、キーワード引数startは、どの数値から順に付与するかを示します。

>>> abc = list('abcdefg')
>>> abc
['a', 'b', 'c', 'd', 'e', 'f', 'g']
>>>
>>> enumerate(abc)
<enumerate object at 0x00000270D21ED438>
>>>
>>> list(enumerate(abc))
[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd'), (4, 'e'), (5, 'f'), (6, 'g')]
>>>
>>> list(enumerate(abc, start=5))
[(5, 'a'), (6, 'b'), (7, 'c'), (8, 'd'), (9, 'e'), (10, 'f'), (11, 'g')]

---

key=lambda ig: sum(ig[-1])

lambdaは、引数、:の後に処理を記述すると認識しております。
min(enumerate(groups, start=1)この処理結果がigにはいって、sumして、keyに入って、それをindexと_に戻り値として渡される？という認識でよろしいでしょうか？

enumerate(groups, start=1)が返した各要素がigに入ります。
例えば一回目は(1, (0, 20, 10))が、二回目は(2, (20, 10, 80))がigに与えられるわけです。

keyは関数が『何をもって要素を比べるか』指定するために使います。
今回はsum(ig[-1])、つまり件の三個組の要素の合計を指標にしています。

minした結果をラムダで処理しているのではなく、minを求めるのにラムダを用いています。
minがどんな処理をしているか覗いてみたら、少しイメージが湧くかもしれません。

def my_min(it, key=None):
    print('-' * 42)
    if key is None:
        key = lambda x: x   # 恒等関数
    
    ret = next(it)
    ret_score = key(ret)
    
    for e in it:
        e_score = key(e)
        print(f'{ret}[score={ret_score}] vs {e}[score={e_score}]', end='\t')
        
        if ret_score > e_score:
            print('latter wins')
            ret, ret_score = e, e_score
        else:
            print('former wins')
    
    print(f'smallest element is {ret}')
    print('-' * 42)
    return ret

実行結果 (minの代わりにmy_minを使用) Wandbox

------------------------------------------
(1, (0, 20, 10))[score=30] vs (2, (20, 10, 80))[score=110]	former wins
(1, (0, 20, 10))[score=30] vs (3, (10, 80, 10))[score=100]	former wins
(1, (0, 20, 10))[score=30] vs (4, (80, 10, 0))[score=90]	former wins
(1, (0, 20, 10))[score=30] vs (5, (10, 0, 10))[score=20]	latter wins
smallest element is (5, (10, 0, 10))
------------------------------------------
5

註： 説明のために書いたコードであり、実際のminの実装を踏襲したものではありません。

---

前半部分「sorted(sum_dict.items()」は、辞書をソートされている。ここまではわかるのですが、

やはり、lambdaの処理が完璧に理解できません。（ソートした辞書をitemに渡す？）

辞書の各要素をタプルにしたシーケンスを作り、そいつをソートしています。
ソートした結果をラムダで処理しているのではなく、ソートするのにラムダを用いています。

>>> tmp_dict = {i: i**2 for i in range(10)}
>>> tmp_dict
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}
>>>
>>> tmp_dict.items()
dict_items([(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49), (8, 64), (9, 81)])

---

回答いただいたのに、それに対しての質問ばかりでごめんなさい。

いえいえ、お気遣いなく。

Comments

[hayataka2049]

この手のコードを見るたびに思いますが、sortせずに済ませるとO(nlogn)がO(n)になってお得です（どうでも良いけど）

[LouiS0616]

拡張性をある程度担保しようという考えが根底にはあります。
が、ただの手癖になってしまっているのが正直なところで、今回も特に意識しないでminを避けsortedを使ってしまいました。
ご指摘ありがとうございます。

[zeitaku_fire]

いつもご教授いただきありがとうございます。
下記の理解で誤りがありましたらご指摘お願いします。

ただ、疑問があります。（全部で4個）

まず、2番目に作成いただいたコードなのですが、

>>nums = [int(input().split()[-1]) for _ in range(n)]
　⇒これで入力データの右側をリスト。(1でも右側を取り出せる）
　　※-1を0にすると、左側だけ取り出せる。
　　for _ in range
　　_(アンダーバー)というのは、変数を使わないということ
　　※for i in rangeとしても同じ動きをする、はず

>>groups = zip(*[nums[s:] for s in range(span)])
　⇒リストを3個単位でタプルにしている。
　　3個というのは、spanの3である。
>>index, _ = min(enumerate(groups, start=1),key=lambda ig: sum(ig[-1]) # (index, >>num_group)
>>)
　index, _は、戻り値がふたつあるから、受け皿を二つ用意。
　必要なのはindexに入る値のみ。_は使用しない？

『疑問』
>>index, _ = min(enumerate(groups, start=1),key=lambda ig: sum(ig[-1]) # (index, >>num_group)
>>)
　minの意味はわかります。※最小値をとる
①　enumerateなんですが、for文の際に使うもので、リストのインデックスをとるときに使用するものだと認識しておりますが、for文がありません。
ここでのenumerateは何をしているのでしょうか。。？
②また、groupsは上記でタプルにされているデータをさしているのはわかるのですが、stard=1は何なのでしょうか？

③key=lambda ig: sum(ig[-1])
lambdaは、引数、:の後に処理を記述すると認識しております。
min(enumerate(groups, start=1)この処理結果がigにはいって、sumして、keyに入って、それをindexと_に戻り値として渡される？という認識でよろしいでしょうか？

====2番目のコードについてはここまで====

3番目の辞書でやって頂いたコードなのですが、
下記のコード以外は、何をやっているのか理解しました。
>>index = sorted(sum_dict.items(), key=lambda item: item[-1])[0][0]
④ 前半部分「sorted(sum_dict.items()」は、辞書をソートされている。ここまではわかるのですが、
やはり、lambdaの処理が完璧に理解できません。（ソートした辞書をitemに渡す？）

回答いただいたのに、それに対しての質問ばかりでごめんなさい。

[LouiS0616]

@zeitaku_fire さん
ご質問の点について追記しましたので、ご確認ください。

[zeitaku_fire]

ありがとうございます。追記頂いた分確認しました。
ご丁寧にコードも作成頂き、イメージを昨日より持つことができました。

完全に理解するにはまだ時間がかかりますが、今後ともご教授のほどよろしくお願いします。

ありがとうございました。

Answer 3

愚直だけど、こんな感じでもできるかもです。
積算値をキュー的に扱い（前の値を引き現在の値を足す）、計算量はO(n)でいけてると思います。

import random
random.seed(110)
cnt = 10
l = [random.randrange(cnt*2) for i in range(cnt)] # rangeも個数に合わせる。（0が連続しないように）
#print(l)
span = 3

# 0番目からspan個を足す。とりあえずこれを最小値とする。
cur_sum = 0
for i in range(span):
    cur_sum += l[i]
#print(cur_sum)
cur_sub = l[0]
min_sum = cur_sum
min_pos = 0

# 1番目から末尾を足すまで
for i in range(1,cnt-span+1):
    # 前の値を引いて、現在の値を足す＝現在の積算値
    cur_sum -= cur_sub
    cur_add = l[i+span-1]
    cur_sum += cur_add
    #print('cur pos={} sub={} add={} sum={}'.format(i,cur_sub,cur_add, cur_sum)) #
    cur_sub = l[i]
    if cur_sum <= min_sum:
        min_sum = cur_sum
        min_pos = i
        #print('min pos={} cur_min={}'.format(min_pos,min_sum))

print( 'total_min pos={} sum={}'.format(min_pos, min_sum))

境界値をちゃんと考慮できていないかも。

Comments

[zeitaku_fire]

ありがとうございます。
ほかのアプローチを思いつかなかったので、ご教授いただいたコード、参考にさせて頂きます。
今後ともよろしくお願いします。