データ構造

土 17 8月 2019

データ構造の勉強

背景

  • 目的

    • データ構造を改めて勉強する。
    • Pythonでコーディングして知識整理を行い、再コーディング時に自走出来るようにする。

  • 参考

    • 参考書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」

データ構造

  1. Stack
buffer = []#init
buffer.append(x)#append（末尾）
y = buffer.pop()#pop（末尾）
  1. Queue
    • 専用のqueueモジュールが存在するが、
      • listのみで実装が可能。
      • アルゴリズム上位というか、概要確認が目的のため今回は使わない。
      • マルチスレッド処理などが良いようだ（？）
buffer = []#init
buffer.append(x)#append（末尾）
y = buffer.pop(0)#pop（先頭）

  1. 双方向連結リスト

    • Pythonで書くのは重いということが起きそうな気がしているがPythonでやってみた。

      • ALDS1_3_Cの処理時間制限でアウトの状態。

      • ポインタのつなぎ方、Gurdianなどが復習できた。

      • 性能問題ありだが、動作はする状態。

        • 無限ループ whileよりもforが良いという情報あり、やってみたが、課題クリアに至らず。
        • データコンテナに独自クラスを利用していることが最大の問題ではないかと推測。

    • 高速化について考察

      • TOPのソースを見ると、from collections import dequeを使っている。
        • コードも超シンプル・・。これが競技プログラミングの世界か。
        • 何か悔しいが、使えるものが見えたので、ここまで。

Python Tips

  1. 取り出した値（str型）が数字かどうかの判定
    • 逆ポーランド記法をStackで解く場合に必要になった。
y.isdecimal()# return True/False
  1. StackやQueueで実装していると、不要なところもStack/Queueで実装してしまっていることがある。適切に必要な実装を心がける。

まとめ

学習したこと

  • stack, queue, 双方向連結リストのロジックを再確認した。
  • 双方向連結リストに関して、pythonではcollections.dequeを使えば良い。

残課題

  • pythonのlistによる、双方向連結リストの独自実装の改良。
    • ただ、collections.dequeがあるので現状はそれを知るに留めておく。
  • pythonのlist型の各メソッドの計算量の確認とか、最適なロジックの検討。

以上

social