技術メモ

役に立てる技術的な何か、時々自分用の覚書。幅広く色々なことに興味があります。

ダイクストラ法がやっと理解できた

ダイクストラ法というアルゴリズム
重み付きの経路の最短経路を求めるアルゴリズムとして有名である。
そのダイクストラ法というアルゴリズム、存在自体は知っていたが何度か自分で実装しようとしてはなぜそれが最短経路を求めるアルゴリズムになるのか腹落ちしないまま諦めかけていた。
だが恥ずかしながらようやくわかったので、わかった過程と実装を紹介する。

直感的に理解するには身近な問題に置き換えれば良い。
最短経路を求める問題は紐付きのビー玉を持ち上げる問題と同じなのだ。
そう考えればようやくわかってきた。
問題はこうだ

Q. それぞれが大小様々な紐でつながったビー玉がN個ある。(それぞれのビー玉は必ずしもお互いにつながっている必要はないが、どのビー玉にも繋がっていないものはないとする)
その中の1個を持ち上げることを考える。
この時、最後に持ち上がるビー玉の高さはどれくらいか?

このビー玉持ち上げ問題を考える時はこう考えるのがわかりやすい

ビー玉をそれぞれa0, a1, a2, ....aNとし、aiとajに繋がる紐の長さをLijとする。
最初にa0を持ち上げ始める。
すると次に地面から持ち上がるビー玉はなんだろう。
それは、a0に繋がっている紐のうち最小のものと繋がったビー玉aiになる。

ではさらにその次に地面から持ち上がるビー玉はなんだろう。
a0と紐でつながっているビー玉かaiと紐でつながっているビー玉のうち、L0j もしくは L0i + Lijが最小になるj、ajである。

ではさらににその次は...?
ここで仮にL0j > L0i + Lij だったとしよう。
すると今度は L0sもしくはL0i + LisもしくはL0i + Lij + Ljs が最小になるasになる。

さらにその次は...?

同じようにして考えいくとアルゴリズムの考え方の道筋が見えてくる。
そして最短経路はそれぞれのビー玉に対してどの紐によって持ち上がったかを記憶しておけば最短経路を辿ることができる。
(ここからはグラフの用語にしたがってノードと辺という言葉を使う。)

1. 基準となるノードから最小の辺に繋がるノードを選択し、「探索済み」としておく。探索済みのノードは同時にそれぞれ最小距離を保持しておく。
2. 探索済みのノードから繋がっている全てのノードに対して、最短距離を計算する。この時最短距離の計算は以下の通り。
  最短距離=全ての探索済みノードに対して「探索済みのノードが保持している最短距離+そのノードとの辺の重み」の最小値
3. 2で求めた最短距離が最小になるノードを選択肢「探索済み」としておく。
4. 全てのノードが探索済みになるまで2,3を繰り返す。


これをもう少し効率的に改変してみよう。
2の計算において全ての探索済みノードを毎回取り出してその度に最短距離を計算するのでは効率が悪い。
各ノードに対して「探索済みノードからの最短距離」を持っておいて、ノードが選択される毎にその最短距離を更新すれば良いのではないか。そうすればノードが選択されるたびに全探索済みノードに繋がっている辺を見に行かなくても選択されたノードから繋がっている辺を見るだけで済む。
ということで効率的にしたアルゴリズムはこのようになる

1. 各ノードに対して最短距離を表す配列Dを用意する。0番目を基準のノードとするとD=[0, ∞, ∞, ... ∞]とする。
2. Dの中で最小の値をとるノードiを選択し、iを探索済みとして記録する。
3. iから繋がる全ての辺Lijに対して、以下の規則でDを更新する。
  D[i] + Lij < D[j] ならば D[j] ← D[i] + Lij
4. 全てのノードが探索済みになるまで2,3を繰り返す。


これであれば実装できそうだ。
...ということでPythonで簡単に実装してみる。

# データ
links = {
    (0,1): 1.4,
    (0,2): 3.1,
    (0,3): 4.6,
    (1,2): 2.9,
    (2,3): 1.1,
    (1,3): 3.1,
    (1,4): 2.7,
    (4,1): 2.3,
    (2,4): 2.1,
    (3,4): 1.8,
}
nodes = 5
d = [0] + [1000] * (nodes -1)
prev = [0] * nodes
completed = [False] * nodes

# dの最小値の位置を求める
def argmin(d):
    idx = None
    min_val = 10000
    for i, j in enumerate(d):
        if j < min_val and completed[i] == False:
            min_val = j
            idx = i
    return idx

# 全てが探索済みになるまで繰り返す
while not all(completed):
    selectd = argmin(d)
    completed[selectd] = True
    for i, j in links:
        if i==selectd:
            if d[i] + links[(i,j)] < d[j]:
                d[j] = d[i] + links[(i,j)]
                prev[j] = i
        
print(d)
print(prev)

シェルスクリプトでFOR文でバックグラウンドで起動したの並列処理を待機する方法

# ジョブ ID を格納する配列
job_ids=()

array=(2 5 4 7 2 1)
for i in ${array[@]}; do
    
    # ジョブをバックグラウンドで実行し、ジョブ ID を取得
    (sleep $i && echo $i) &
    
    # 直前にバックグラウンドで起動したプロセスの ID を取得
    job_ids+=($!)
done

# すべてのジョブが終了するまで待機
for job_id in "${job_ids[@]}"; do
    wait "${job_id}" || exit 1
done

# 後続処理を記述
echo "Finish!"

結果

 » sh sample.sh
1
2
2
4
5
7
Finish!

■例
あるフォルダのすべてのファイルに対して並列で時間のかかる処理を実行し、並列処理が完了したら後続処理をしたいという場合

input_dir=$1

# ジョブ ID を格納する配列
job_ids=()

for file in "${input_dir}/*"; do
    
    # first.sh(時間がかかる処理)をバックグラウンドで実行し、ジョブ ID を取得
    (sh first.sh "${file}") &
    
    # 直前にバックグラウンドで起動したプロセスの ID を取得
    job_ids+=($!)
done

# すべてのジョブが終了するまで待機
for job_id in "${job_ids[@]}"; do
    wait "${job_id}" || exit 1
done

# 後続処理を記述
sh second.sh

補足

job_ids=()

この書き方ではbash特有の記法になる。
POSIX準拠の記法は以下のようになる。

# POSIXシェルでは配列を使わず、代わりに一時ファイルを使用
job_ids_file=$(mktemp)

for file in "${input_dir}/*"; do
    # first.sh(時間がかかる処理)をバックグラウンドで実行し、ジョブ ID を一時ファイルに書き込む
    (sh first.sh "${file}") &
    echo $! >> "$job_ids_file"
done

# 生成したジョブIDの一覧を読み込み、それぞれのジョブが終了するのを待つ
while IFS= read -r job_id; do
    wait "${job_id}" || exit 1
done < "$job_ids_file"

# 一時ファイルを削除
rm "$job_ids_file"

# 後続処理を記述
sh second.sh

【DRF】 カスタムユーザーを使ってuserをregisterする時、パスワードを入れているのに「この項目は必須です。」と言われる

Django Rest Frameworkを使ってカスタムユーザーを使ってユーザー登録しようとした時、password1とpassword2を同じにして登録しているはずなのにパスワードが必須だと言われる。

{
    "password1": [
        "This field is required."
    ],
    "password2": [
        "This field is required."
    ]
}

(日本語版)

{
    "password1": [
        "この項目は必須です。"
    ],
    "password2": [
        "この項目は必須です。"
    ]
}


ネットでいくら探しても有力な解決法はなかったけれど、自分なりの解決法が見つかったのでブログに記すことにする。
qiita.com
一応Qiitaでも同様の現象が報告されているが解決策が力技すぎた。
当記事の原因とは違うなどどうしても解決できない場合は参考にしてみてほしい。

前提

認証には dj-rest-auth を使用。
今回作成したカスタムユーザーは以下の通り。

[accounts/models.py]

...
class User(AbstractBaseUser, PermissionsMixin, TimeStampedModel):
    name = models.CharField(max_length=128, verbose_name=_('Name'), null=False, blank=True)
    email = models.EmailField(unique=True, verbose_name=_('Email'))
    icon = models.ImageField(verbose_name=_('Profile picture'), null=True, blank=True)
    birthday = models.DateField(verbose_name=_('Birthday'), null=True, blank=True)
    bio = models.TextField(verbose_name=_('Biography'), null=True, blank=True)

    is_active = models.BooleanField(verbose_name=_('Is active'), default=True)
    is_staff = models.BooleanField(verbose_name=_('Is staff'), default=False)
    is_superuser = models.BooleanField(verbose_name=_('Is superuser'), default=False)

    objects = CustomUserManager()

    USERNAME_FIELD = 'email'

[accounts/serializers.py]

....
class UserRegisterSerializer(RegisterSerializer):
    email = serializers.EmailField()
    name = serializers.CharField(max_length=128)
    birthday = serializers.DateField()
    bio = serializers.CharField(required=False)

    def get_cleaned_data(self):
        return {
            'username': self.validated_data.get('username', ''),
            'password1': self.validated_data.get('password1', ''),
            'email': self.validated_data.get('email', ''),
            'name': self.validated_data.get('name', ''),
            'birthday': self.validated_data.get('birthday', None),
            'bio': self.validated_data.get('bio', None),
        }

    def custom_signup(self, request, user):
        data = self.cleaned_data
        user.name = data.get('name', '')
        user.birthday = data.get('birthday', '')
        user.bio = data.get('bio', '')
        user.save()

modelsとserializersはこのように定義し、settingsでこのserializerをregisterに使うように設定した。

[project_name/settings.py]

...
REST_AUTH = {
    "REGISTER_SERIALIZER": "accounts.serializers.UserRegisterSerializer",
}
...

ここまでの流れはだいたいこの記事の通りにした
Custom users using Django REST framework | Kraken Systems Ltd.

原因

原因は自分の場合、JSONの出力と入力をcamelCaseに対応させるため djangorestframework_camel_case を入れていたことが問題だった。
どうやら "password1" が "password_1" と解釈されるよう。
"password1"って書き方正式にはsnake_caseじゃないんですね。知らなかった…
この原因を突き止めるまで相当苦労した…

解決

暫定対応1

とりあえずcamelCaseを辞めるのを暫定対応とした。
つまり `settings.py` を書き換える。

REST_FRAMEWORK = {
    'DEFAULT_RENDERER_CLASSES': (
        'djangorestframework_camel_case.render.CamelCaseJSONRenderer',
        'djangorestframework_camel_case.render.CamelCaseBrowsableAPIRenderer',
        'rest_framework.renderers.JSONRenderer',
    ),
    'DEFAULT_PARSER_CLASSES': (
        'djangorestframework_camel_case.parser.CamelCaseFormParser',
        'djangorestframework_camel_case.parser.CamelCaseMultiPartParser',
        'djangorestframework_camel_case.parser.CamelCaseJSONParser',
        'rest_framework.parsers.JSONParser',
    ),

こう書いていたのを

REST_FRAMEWORK = {
    'DEFAULT_RENDERER_CLASSES': (
        'rest_framework.renderers.JSONRenderer',
    ),
    'DEFAULT_PARSER_CLASSES': (
        'rest_framework.parsers.JSONParser',
    ),

こうする。

暫定対応2

とはいえフロントとの疎通の仕様上いまさらcamelCaseをsnake_caseに書き換えるのは無謀な話ということだった。
なのでどうにかならないかと思い悩んだ結果Serializerを書き換えることでなんとか対応できた。
具体的にはpassword1とされるところを徹底的にpassword_1に置き換えるという作業をした。

  • 継承元のserializers.Serializerでfieldの変数名を解釈している箇所"fields"
  • RegisterSerializerで"password1", "password2"という変数名を取って来て比較している箇所"validate"
  • RegisterSerializerで"password1"というフィールドを取得する箇所"get_cleaned_data"

を書き換える必要があった。

from django.utils.functional import cached_property

class UserRegisterSerializer(RegisterSerializer):
    email = serializers.EmailField()
    name = serializers.CharField(max_length=128)
    birthday = serializers.DateField()
    bio = serializers.CharField(required=False)

    @cached_property
    def fields(self):
        from rest_framework.utils.serializer_helpers import BindingDict
        fields = BindingDict(self)
        for key, value in self.get_fields().items():
            if key == "password1":
                key = "password_1"
            if key == "password2":
                key = "password_2"
            fields[key] = value
        return fields

    def validate(self, data):
        if data['password_1'] != data['password_2']:
            raise serializers.ValidationError(_("The two password fields didn't match."))
        return data

    def get_cleaned_data(self):
        return {
            'username': self.validated_data.get('username', ''),
            'password1': self.validated_data.get('password_1', ''),
            'email': self.validated_data.get('email', ''),
            'name': self.validated_data.get('name', ''),
            'birthday': self.validated_data.get('birthday', None),
            'bio': self.validated_data.get('bio', None),
        }

    def custom_signup(self, request, user):
        data = self.cleaned_data
        user.name = data.get('name', '')
        user.birthday = data.get('birthday', '')
        user.bio = data.get('bio', '')
        user.save()

継承元のserializers.Serializer の関数をオーバーライドするという魔改造なのでDjangoの仕様が変わるとそれに対応できなくなるという怖さがある。

追記

恒久対応

ついに恒久対応を見つけてしまった。
djangorestframework_camel_caseの仕様で特定の文字をparse対象から省くことができる機能がある。
GitHub - vbabiy/djangorestframework-camel-case: Camel case JSON support for Django REST framework.

[project_name/settings.py]

REST_FRAMEWORK = {
    # ...
    "JSON_UNDERSCOREIZE": {
        "ignore_keys": ("password1", "password2"),
    },
    # ...
}

とするだけ。
accounts/serializers.pyは元に戻す