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

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

ただいまの
回答率

89.52%

リストを使わずyieldを使って数列を生成したい

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 180

naomi3

score 1066

ある画像処理用のアルゴリズムのPythonによる実装です。目的の数列は得られるのですが、リストを使っているためにメモリ効率が悪いです。Pythonにはジェネレータがあることを知り、リストを使わずyieldを使ってスマートにメモリ効率の良いコードが書けるのではないかと思ったのですが、Pythonを学んで日が浅く、わからずにいます。

import sys


def create(depth, left, right):
    if left > right:
        return None
    else:
        return bin_node(depth + 1, left, right)


def bin_node(depth, left, right):
    center = (left + right) // 2
    return {
            'depth': depth,
            'center': center,
            'leftNode': create(depth, left, center - 1),
            'rightNode': create(depth, center + 1, right)
            }


def get_max_depth(node):
    if node is None:
        return 0
    else:
        return max([node['depth'], get_max_depth(node['leftNode']), get_max_depth(node['rightNode'])])


def traverse_in_depth(node, depth):
    list = []
    if node is not None and node['depth'] == depth:
        list.append(node['center'])
    elif node is not None and node['depth'] < depth:
        list.extend(traverse_in_depth(node['leftNode'], depth))
        list.extend(traverse_in_depth(node['rightNode'], depth))
    return list


def bin_node_iterator(left, right):
    root_node = create(0, left, right)

    max_depth = get_max_depth(root_node)

    list = []
    for depth in range(1, max_depth + 1):
        list.extend(traverse_in_depth(root_node, depth))

    return list


left = int(sys.argv[1])
right = int(sys.argv[2])
print(left, right)
for n in bin_node_iterator(left, right):
    print(n, end=" ")

試したこと
(traverse_in_depth関数、bin_node_iterator関数以外は同じ)

def traverse_in_depth(node, depth):
    if node is not None and node['depth'] == depth:
        yield node['center']
    elif node is not None and node['depth'] < depth:
        yield traverse_in_depth(node['leftNode'], depth)
        yield traverse_in_depth(node['rightNode'], depth)


def bin_node_iterator(left, right):
    root_node = create(0, left, right)

    max_depth = get_max_depth(root_node)

    for depth in range(1, max_depth + 1):
        yield traverse_in_depth(root_node, depth)
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 1

checkベストアンサー

+1

◯ 提案

全体のコードを読めていないので、直るかはわからないのですが
traverse_in_depth 関数を呼び出す際に yield  from を使ってみると、どうでしょうか?

# 修正前
def traverse_in_depth(node, depth):
    if node is not None and node['depth'] == depth:
        yield node['center']
    elif node is not None and node['depth'] < depth:
        yield traverse_in_depth(node['leftNode'], depth)
        yield traverse_in_depth(node['rightNode'], depth)


def bin_node_iterator(left, right):
    root_node = create(0, left, right)

    max_depth = get_max_depth(root_node)

    for depth in range(1, max_depth + 1):
        yield traverse_in_depth(root_node, depth)
# 修正後
def traverse_in_depth(node, depth):
    if node is not None and node['depth'] == depth:
        yield node['center']
    elif node is not None and node['depth'] < depth:
        yield from traverse_in_depth(node['leftNode'], depth)  # <--- yield from を使います。
        yield from traverse_in_depth(node['rightNode'], depth)  # <--- yield from を使います。


def bin_node_iterator(left, right):
    root_node = create(0, left, right)

    max_depth = get_max_depth(root_node)

    for depth in range(1, max_depth + 1):
        yield from traverse_in_depth(root_node, depth)  # <--- yield from を使います。

◯ 補足

yield を使った関数を「ジェネレータ関数」と言います。
「ジェネレータ関数」は「ジェネレータイテレータ」というオブジェクトを返します。

traverse_in_depth 関数は「ジェネレータイテレータ」を返しています。
修正前の bin_node_iterator 関数は traverse_in_depth 関数が返した
「ジェネレータイテレータ」を1つずつ返してしまっています。

# コピペで動きます。
def f():
    yield g1()
    yield g2()

def g1():
    yield 0
    yield 1

def g2():
    yield 2
    yield 3

[i for i in f()]
# [<generator object g1 at 0x100e9db48>, <generator object g2 at 0x100e9dba0>]

今回は「ジェネレータイテレータ」の 中身 が欲しいので、
yield from を使います。

# コピペで動きます。
def f():
    yield from g1()
    yield from g2()

def g1():
    yield 0
    yield 1

def g2():
    yield 2
    yield 3

[i recursive.pyfor i in f()]
# [0, 1, 2, 3]

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2019/10/20 15:36

    ご回答ありがとうございます。ですが、動作しません。よろしくお願いいたします。

    キャンセル

  • 2019/10/20 15:45

    既に試されているかもしれないのですが、
    traverse_in_depth が再帰呼び出し担っているのを見落としていました。
    2 箇所 yield from を追記いたしました。
    これでも動くかはわからないのですが、いかがでしょうか。

    キャンセル

  • 2019/10/20 15:52

    ありがとうございます。
    うまく動きました。

    キャンセル

  • 2019/10/20 16:05

    よかったです :)

    キャンセル

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

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