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

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

ただいまの
回答率

90.38%

  • Python 3.x

    10746questions

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

AOJ:Python3 Doubly Linked Listのアルゴリズムについて

受付中

回答 1

投稿

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

_nakamura_

score 2

前提・実現したいこと

AOJの
Dubly Linked List(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp)
をPython3で解いているのですが
どうしても実行時間が規定を超えてしまいます。
下記のコードでどこか計算量を削れるところはあるでしょうか

該当のソースコード

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp
#双方向連結リスト

NEXT = 2
DATA = 1
PREV = 0
def dll_processor(operations):

    front = None
    end = None

    for o in operations:
        if o[0] == "insert":
            front, end = insert(front, end, o[1])
        elif o[0] == "delete":
            front, end = delete(front, end, o[1])
        elif o[0] == "deleteFirst":
            front, end = delete_first(front, end)
        elif o[0] == "deleteLast":
            front, end = delete_last(front, end)
        #print(get_list(front))

    return get_list(front)

def get_list(front):
    if not front:
        return []

    l = []
    target = front
    while True:
        l.append(target[DATA])
        if not target[NEXT]:
            break
        target = target[NEXT]
    return l

def insert(front, end, target):
    node = [None, target, None]
    if front:
        front[PREV] = node
        node[NEXT] = front
        return node, end
    else:
        return node, node

def delete(front, end,target):

    delete_node = front
    while not delete_node[DATA] == target:
        delete_node = delete_node[NEXT]
        if delete_node == None:
            return front, end

    if delete_node[PREV] == None:
        delete_node[NEXT][PREV] = None
        return delete_node[NEXT], end
    elif delete_node[NEXT] == None:
        delete_node[PREV][NEXT] = None
        return front, delete_node[PREV]
    else:
        delete_node[NEXT][PREV] = delete_node[PREV]
        delete_node[PREV][NEXT] = delete_node[NEXT]
        return front, end

def delete_last(front, end):

    if not end[PREV]:
        return None, None
    else:
        end[PREV][NEXT] = None
        return front, end[PREV]

def delete_first(front, end):

    if not front[NEXT]:
        return None, None
    else:
        front[NEXT][PREV] = None
        return front[NEXT], end

def main():
    n_list = int(input())
    target_list = [input().split() for i in range(n_list)]
    print(*dll_processor(target_list))

if __name__ == "__main__":
    main()
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 1

0

回答になりませんが、強いて言えば、両方向リストをわざわざ連想配列など使って実装しているところは削れます。

両方向リストとは、「各々の節点に2つのリンクを保持して、1つで前を指しもう1つで次を指すようにする」(セジウィック『アルゴリズム』) ものです。この性質を持っていれば、そのデータ構造は両方向リストとみなせます。たとえばPythonのリストはインデクスのついた要素の列ですから、自然数の公理により、各要素は前の要素と後の要素を持ちます (最初と最後の要素を除く)。つまり各要素が前と後の要素を指すので、Pythonのリストは両方向リストとみなせます。

あとは自分で考えて下さい。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

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

  • Python 3.x

    10746questions

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