アルゴリズムとデータ構造 -No.2-

アルゴリズムとデータ構造の学習

この記事は以下の本で学んだ内容を自分なりにまとめたものです。 bookclub.kodansha.co.jp

前回に引き続き、今回は全探索・再帰・分割統治法についてまとめていきたいと思います。

全探索

全探索とは、解きたい問題に対して、考えられる可能性を全て調べ上げることによって解決する手法です。

線形探索法

線形探索法とは全探索の一種で、一つひとつの要素を順に調べていく手法です。例として、ある数列の中から特定の要素が含まれているかを判定する問題に対して、全ての要素を順番に確認していくプログラム等が挙げられます。このように1重のfor文によるアルゴリズムの計算量はO(N)となります。

ペアの全探索

与えられたデータの中から最適なペアを探索する問題では、2重のfor文によって解くことができ、このようなアルゴリズムの場合の計算量はO(N2)となります。

組み合わせの探索

さて、上記二つに加えてより実用的かつ応用的な組み合わせの探索では、より複雑な対象を探索するため、より高度な探索技法が必要となります。具体的には、再帰・グラフ等が挙げられます。以下で再帰について詳しくまとめていきます。

再帰

さて、複雑な問題にも対応できるより汎用的な全探索手法であり、全てのアルゴリズムの基礎として重要である再帰関数を用いる手法をまとめていきます。

再帰の重要なルール

再帰を用いる際には以下のルールを守らないといけません。

  • 再帰法は、再帰終了条件を持たなければならない。
  • 再帰法は、状態を変えながら再帰終了条件に進んでいかなければならない。
  • 再帰法は、再帰的に関数自身を呼び出さなければならない。

ベースケース

ベースケースとは、再帰関数の中で再帰呼び出しを行わずにreturnするケースのことです。この、ベースケースに対する処理はとても大事で、なぜならこの処理が行われないと再帰呼び出しを無限に繰り返してしまいます。また、実装上のポイントとして、再帰呼び出しを行った時の引数がベースケースに近づくようにするべきです。これも、ベースケースに対する処理を記述してもベースケース自体に近づくことができなければ再帰呼び出しを無限に繰り返してしまうことになるからです。

pythonによるサンプルコード

正しくベースケース処理を行えている例

本の中ではC++でサンプルコードが記載されていましたが、pythonで簡単な再帰関数を実装してみました。

def func(n):
    if n <= 0:
        return n
    return n + func(n-1)

この例は、1からnまでの自然数の和を返す再帰関数であり、nが0以下の場合には再帰呼び出しを行わずにreturnしています。これが先ほど説明したベースケースです。 例えばnが10である場合、func(10) = 10 + func(9)であり、func(9)は 9 + func(8) を戻り値として返します。このような処理をベースケース、つまりnが0まで繰り返すことで最終的に1から10までの和を返してくれます。

再帰呼び出しを無限に繰り返してしまう例

def func(n):
    if n <= 0:
        return n
    return n + func(n+1)

さて、この例ではどうでしょう? この例では、ベースケースに対する処理を記述しているにも関わらず、再帰呼び出しを無限に繰り返してしまいます。「再帰呼び出しを行った時の引数がベースケースに近づくようにする」というポイントをしっかりと頭に入れて実装するようにしましょう。

分割統治法

さて、再帰に関する説明が一通り終わりましたが、分割統治法とは何でしょう?名前は非常に難しそうですが、この分割統治法とはこれまで学んだ再帰を用いた手法と考えられます。 本の中では、与えられた問題をいくつかの部分問題に分解し、各部分問題を再帰的に解き、それらの解を組み合わせて元の問題の解を構成するアルゴリズム技法、と説明されていました。 簡単に説明すると、再帰のテクニックを用いて、問題を分割し、それを再帰的に解き、それを統合することで解く技法です。

この分割統治法は、すでに多項式時間アルゴリズムが得られている問題に対して、より高速なアルゴリズムを設計する際に役立ちます。

さて、今回は全探索・再帰・分割統治法と第4章まで一気に進めました。再帰という概念はプログラム初学時には非常に理解しづらく、厄介なものでしたが、辛抱強く学習することにします。やはり概念だけ学習しても100%身に付く訳ではないので、どんどん実装して慣れていきたいと思います!!

アルゴリズムとデータ構造 -No.1-

アルゴリズムとデータ構造の学習

就活が終わり、今後1年「TOEIC 800」・「アルゴリズム」・「Django & React」を大きな学習目標として立てました!!

 

と言うことで、アルゴリズムを学ぶ上でオススメされた

bookclub.kodansha.co.jp

で学んだ内容を本ブログにまとめていこうと思います。

アルゴリズムとは

アルゴリズムとは、問題を処理するための操作手順です。

この本で紹介されていた、「問題に対する具体的な解を書き下すことができなくても、解を得るための「手順」を与えることができれば良い」と言う言葉が非常に印象的であり、これまでなんとなくプログラミングをしていましたがアルゴリズムを学ぶ事は非常に重要であると気づきました。

計算量とオーダー記法

計算量:アルゴリズムの良し悪しを測る重要な指標

この計算量により、コンピューター上での実行に要する時間を、大雑把に見積もることができるらしいです。これまで講義などで計算量について学ぶ機会はありましたが、いつも難しそうなイメージがへばりついており、なかなか積極的に触れてこなかったですがこの機会にしっかり学ぼうと思います。

オーダー記法(ランダウのO記法)

アルゴリズムAの計算時間T(N)が概ねP(N)に比例する」ということを、T(N)=O(P(N))であると表し、アルゴリズムAの計算量はO(P(N))であるといいます。

 

 代表的な計算ステップ回数の比較は以下の通りです。logなどが出てくるとどうも苦手意識が出てしまうのですが、ひとまずはこちらを覚えつつ理解しようと思います。

logN > N > N^2 > N^3 > 2^N > N!

 

Nの増加に伴い計算時間が急速に大きくなる

定数 d>0 が存在して計算量がN^dの定数倍によって上から抑えられる

N>=10^5 まで行くと膨大な時間がかかる

問題の大きさに依存しない定数時間以内に処理が終わる

*データを雑に扱ってしまうとO(N)となってしまう場合がある

 

ちなみに、大体1秒間で処理できる計算ステップ回数は 10^9 回程度だそうです。

 

ランダウのO記法の詳細

  • O記法:計算時間を上から抑えて評価
  • Ω記法:計算時間を下から抑えて評価
  • θ記法:計算時間を上からも下からも抑えるという評価

主には、O記法が用いられるそうです。

 

今日は第1章、第2章を学習しました。計算量については、外枠だけを学んだような感じなので実際にプログラムを組みながらつかんでいきたいと思います。

 

カスタムユーザモデルに変更した際にハマった大穴

カスタムユーザモデルに変えたら大変なことに、、、

実装を進めていく上でデフォルトのユーザモデルでは物足りなくなって今更カスタムユーザモデルに変更しました。

さて、そこでたくさんのエラーに見舞われて大穴にハマりました。

migrationエラー

さて、細かなエラーはたくさんあったのですが一番ハマったエラーについてメモ程度に残しておきます。

モデルを変更したあと、migrationデータを削除しました。するとmakemigrationsとmigrateを実行したときにこのようなエラーで永遠に進めなくなりました。

django.db.migrations.exceptions.InconsistentMigrationHistory: Migration account.0001_initial is applied before its dependency myapp.0001_initial on database 'default'.

 

たくさんサイトを見て探したのですが、最終的には

migrateフォルダ内のinit.py以外のファイルとルート直下のdb.sqlite3を完全削除しました。

 

$ python3 manage.py makemigrations

$ python3 manage.py migrate

で解決。。しかしデータベースは初期化されてしまった、、

 

次からはカスタムユーザは初めから作ろう!!と強く思いました。

Djangoのmigrate実行時のエラーについて

 実行環境

さて、Djangoを用いたアプリケーションを作成していますが、モデルをいろいろ追記した際のmigrate実行時のエラーにハマったのでメモ程度に解決法を記しておきます。

実行環境は、python 3.7.3 、Django 3.1.2 です。

 

エラー概要

モデルをいくつか追記し、

$ python3 manage.py makemigrations

$ python3 manage.py migrate

 

を実行する際に、以下のエラーがずらずらと出ました。

TypeError: int() argument must be a string, a bytes-like object or a number, not 'datetime.datetime'

あれ、どこにもdatetime形式で設定したつもりはないぞ、、と思いながら

変更したモデルをコメントアウトしても直らず、数日苦戦しました。

助けてくれたのはこちらの記事です。

qiita.com

stackpython.medium.com

 

migrationsというファイル内にマイグレーションファイルが保存されており、そちらを確認することで解決しました。

どこまでマイグレーションファイルが適用されているか、

python3 manage.py showmigrations

で確認し、エラーに対応するマイグレーションファイルを直す、といった手順です。

初めてのGit(Mac)

#Mac #Git

 

さて、Djangoを用いたプロジェクトを進めています。

一度インターンでBitBucketは使用したことがあるのですが、個人的なプロジェクトでGitを使ったことがなく、いくつかつまづいた点があるのでメモ書き程度にブログを書きます。

 

Gitコマンドのエラー

そもそもGitコマンドが何かしらのエラーで使えない!!

エラー↓

xcrun: error: invalid active developer path (/Library/Developer/CommandLineTools), missing xcrun at: /Library/Developer/CommandLineTools/usr/bin/xcrun

そういえば、最近Macのキーボードエラーで無料修理プログラム(MacBook Pro 2017)に出したので、MacOSをアップデートしました。この年代のMacBook Proに限り設計不良でキーボードの修理が後を耐えないとか。。

 

そこで、以下の記事を参考にcommand line toolsを手動でインストールし、解決しました¡¡

qiita.com

 

Gitの使い方(初期設定)

さて、ここからが本題です。

$ git --version でGitバージョンを確認し、

git version 2.24.3 (Apple Git-128) でした。

ここでpushしたいファイルがあるディレクトリに移動し、

$ git init を行います。

 

そして最初なので全てのファイルをadd、コミットします。

$ git add .

$ git commit -m "first commit"

 

するとたくさんのメッセージが出てきておそらくエラーが出ました。

Gitの初期設定としてユーザ登録ができていないようです。

$ git config --global user.name 'Hoge Hoge'

$ git config --global user.email 'hoge@hoge'

この記事を参考に色々設定しました。

blog.katsubemakito.net

 

Gitの使い方(コミット)

予め作成しておいたGithubリポジトリのURLをコピペして、以下のコマンドを打っていきました。

$ gitremote add origin [URL]

$ git push origin master

 

これで完成です!!

Djangoにチャレンジしてみよう(4)

フォームの作成

Django/mysite/myapp

にforms.pyを作成しました.

from django import forms
from .models import Post

class PostCreateForm(forms.ModelForm):
  class Meta:
   model = Post
   fields = (
    'content',
   )
   widgets = {
    'content': forms.Textarea(
     attrs={'rows': 10, 'cols': 30, 'placeholder': 'ここに入力'}
   ),
 }

 

フォームを見えるようにするためにmysite/myapp/views.pyを以下のようにしました.

from django.shortcuts import render, redirect
from .models import Post
from .forms import PostCreateForm

def myapp_list(request):
   context = {
    'myapp_list': Post.objects.all(),
   }
  return render(request, 'myapp/myapp_list.html', context)

 

def post_create(request):
  if request.method == "POST":
   form = PostCreateForm(request.POST)
   if form.is_valid():
    form.save()
    return redirect('myapp:myapp_list')
  else:
   form = PostCreateForm()
 return render(request, 'myapp/post_create.html', {'form': form})

 

mysite/myapp/urls.pyに

path('post_create/', views.post_create, name='post_create'),

を追記します.

 

これによりユーザからの入力情報をデータベースに追記し,画面に一覧表示させることができました.

 

このように,入力した文字列をデータベースに保存し,画面に出力させるところまでできました^^

f:id:kachuno:20200729003547p:plain

投稿画面

f:id:kachuno:20200729003447p:plain

表示画面


ここからはオリジナルで色々機能を作っていきたいと思います.

Djangoにチャレンジしてみよう(3)

view関数とurlルーティング

view関数はリクエストを受け取り,レスポンスを返します.

試しに,以下のように記述しました.

/mysite/myapp/view.py

from django.shortcuts import render

  def myapp_list(request):
    context = {}
    return render(request, 'myapp/myapp_list.html', context)

 

続いて,URLを設定してブラウザに表示できるようにします.

アプリケーションを作成した時点ではデフォルトで内側のmysite内にしかurls.pyは存在しないので,myapp内にもurls.pyというファイルを作成します.

 

/mysite/myapp/urls.py

from django.urls import path
from . import views

app_name = 'myapp'

urlpatterns = [
  path('', views.myapp_list, name='myapp_list'),
]

 

mysite/mysite/urls.py

from django.contrib import admin
from django.urls import path, include

urlpatterns = [
  path('admin/', admin.site.urls),
  path('', include('myapp.urls')),
]

 

また,mysite/mysite/settingsを以下のように編集しました.

TEMPLATES = [
{
  'BACKEND': 'django.template.backends.django.DjangoTemplates',
  'DIRS': [os.path.join(BASE_DIR, 'templates')],

  以下省略

 

これによりtemplateディレクトリを置く場所を設定し,プロジェクト直下にtemplate/myapp各ディレクトリを作成します.

template/myapp/myapp_list.htmlに

<h1>Hello Django!</h1>と書き込みます.

 

 

するとブラウザ上にHello Django!と表示されました^^

 

今回urlの設定やらにかなり時間がかかりました..