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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

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

Q&A

1回答

2258閲覧

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

_nakamura_

総合スコア8

Python 3.x

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

0グッド

0クリップ

投稿2016/12/01 12:40

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

###該当のソースコード

Python

1#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp 2#双方向連結リスト 3 4NEXT = 2 5DATA = 1 6PREV = 0 7def dll_processor(operations): 8 9 front = None 10 end = None 11 12 for o in operations: 13 if o[0] == "insert": 14 front, end = insert(front, end, o[1]) 15 elif o[0] == "delete": 16 front, end = delete(front, end, o[1]) 17 elif o[0] == "deleteFirst": 18 front, end = delete_first(front, end) 19 elif o[0] == "deleteLast": 20 front, end = delete_last(front, end) 21 #print(get_list(front)) 22 23 return get_list(front) 24 25def get_list(front): 26 if not front: 27 return [] 28 29 l = [] 30 target = front 31 while True: 32 l.append(target[DATA]) 33 if not target[NEXT]: 34 break 35 target = target[NEXT] 36 return l 37 38def insert(front, end, target): 39 node = [None, target, None] 40 if front: 41 front[PREV] = node 42 node[NEXT] = front 43 return node, end 44 else: 45 return node, node 46 47def delete(front, end,target): 48 49 delete_node = front 50 while not delete_node[DATA] == target: 51 delete_node = delete_node[NEXT] 52 if delete_node == None: 53 return front, end 54 55 if delete_node[PREV] == None: 56 delete_node[NEXT][PREV] = None 57 return delete_node[NEXT], end 58 elif delete_node[NEXT] == None: 59 delete_node[PREV][NEXT] = None 60 return front, delete_node[PREV] 61 else: 62 delete_node[NEXT][PREV] = delete_node[PREV] 63 delete_node[PREV][NEXT] = delete_node[NEXT] 64 return front, end 65 66def delete_last(front, end): 67 68 if not end[PREV]: 69 return None, None 70 else: 71 end[PREV][NEXT] = None 72 return front, end[PREV] 73 74def delete_first(front, end): 75 76 if not front[NEXT]: 77 return None, None 78 else: 79 front[NEXT][PREV] = None 80 return front[NEXT], end 81 82def main(): 83 n_list = int(input()) 84 target_list = [input().split() for i in range(n_list)] 85 print(*dll_processor(target_list)) 86 87if __name__ == "__main__": 88 main()

気になる質問をクリップする

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

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

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

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

投稿2016/12/04 05:40

編集2016/12/04 05:52
ikedas

総合スコア4227

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問