乙Py先生のプログラミング教室

乙Py先生のプログラミング教室
初学者のためのプログラミング学習サイト

今回はPython言語で
様々なソートプログラムを実装して
色々比較してみました。


解説動画はこちら





今回は
ソートプログラムを比較してみる検証です。

用意したソートプログラムは
こんなのです。

1.バブルソート(Bubble Sort)
2.選択ソート(Selection Sort)
3.挿入ソート(Insertion Sort)
4.マージソート(Merge Sort)
5.クイックソート(Quick Sort)
6.ヒープソート(Heap Sort)
7.シェルソート(Shell Sort)



さてひとつづつ見ていきましょう。

バブルソート(Bubble Sort)


隣接する要素を比較して順番が逆であれば交換を行う
比較的単純なソートアルゴリズムで
効率はあまりよくなく、実装が容易です。
# バブルソート
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr



選択ソート(Selection Sort)

配列を走査し、最小値を見つけて
先頭の要素と交換することを繰り返すことで
ソートを行うアルゴリズム

バブルソートよりも効率的です。
# 選択ソート
def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


挿入ソート(Insertion Sort)

要素を1つずつ取り出して
適切な位置に挿入していくことで
ソートを行うアルゴリズム

データの量が少ない場合や
すでにほぼソートされている場合には
高速に動作するようです。
# 挿入ソート
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr


マージソート(Merge Sort)

分割統治法を用いた再帰的なアルゴリズムで
データを分割してソートし、それをマージすることで
ソートを行うアルゴリズム

安定かつ効率的なアルゴリズムであり
大きなデータセットに対しても
高速に動作するそうです。
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr


クイックソート(Quick Sort)

分割統治法を用いた再帰的なアルゴリズムで
ピボットを選択し、それを基準にデータを分割して
ソートするアルゴリズム

一般的に高速でメモリ効率も良いですが
最悪の場合には効率が落ちることがあるそうです。

再帰を用いたものと
再帰無しバージョンがあり
検証は無しバージョンを使用してます。

# クイックソート(再帰あり)
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = [x for x in arr[1:] if x < pivot]
        right = [x for x in arr[1:] if x >= pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)

再帰無し
# 再帰なし
def quick_sort(arr):
    size = len(arr)
    stack = [(0, size - 1)]
    while stack:
        start, end = stack.pop()
        if start >= end:
            continue

        pivot = arr[end]
        low = start
        high = end - 1

        while low <= high:
            if arr[low] > pivot and arr[high] < pivot:
                arr[low], arr[high] = arr[high], arr[low]
                low += 1
                high -= 1
            if arr[low] <= pivot:
                low += 1
            if arr[high] >= pivot:
                high -= 1

        arr[low], arr[end] = arr[end], arr[low]

        if low - start < end - low:
            stack.append((start, low - 1))
            stack.append((low + 1, end))
        else:
            stack.append((low + 1, end))
            stack.append((start, low - 1))
    return arr




ヒープソート(Heap Sort)

ヒープと呼ばれる特殊なデータ構造を使用して
ソートを行うアルゴリズム

安定でありながらも効率的なソートが可能ですが
実装がやや複雑です。
def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[i] < arr[left]:
        largest = left

    if right < n and arr[largest] < arr[right]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

# ヒープソート
def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr


シェルソート(Shell Sort)

挿入ソートの改良版であり
データを一定の間隔で分割して
ソートを行うアルゴリズム

間隔を縮めながら繰り返し処理を行うことで
最終的にソートされた配列が得られます。
# シェルソート
def shell_sort(arr):
    n = len(arr)
    gap = n // 2

    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr


速度比較

これら7つのソートプログラムを用いて
速度を比較してみましょう。

こちらのコードで比較検証を行いました。
import numpy as np
import time
import sys
sys.setrecursionlimit(20000)

# 関数実行時間チェック
def time_check(name,func,n):
    start_time = time.time()
    val = func(n);
    end_time = time.time()
    print(name, end_time - start_time)

# ソート比較
def compare_sort(n):
    # ソート対象のリスト生成
    arr = [1 for _ in range(n)]
    np.random.shuffle(arr)
    
    # 各ソートアルゴリズムの実行時間計測
    #time_check("バブルソート" , bubble_sort, arr.copy())
    #time_check("選択ソート" , selection_sort, arr.copy())
    time_check("挿入ソート" , insertion_sort, arr.copy())
    #time_check("マージソート" , merge_sort, arr.copy())
    time_check("クイックソート" , quick_sort, arr.copy())
    time_check("ヒープソート" , heap_sort, arr.copy())
    time_check("シェルソート" , shell_sort, arr.copy())

compare_sort(1000)




最後に


とまあ、ソートプログラムを書くのは
プログラミングのお勉強には良いですが
業務上の実益はほぼほぼ無いですねー

そもそもPythonの組み込みソートは
圧倒的に性能が良く

数10万件程度だと
誤差の範囲で終わってしまうので
ソートを業務で実装することは
余り無いですね。

超大規模なデータを用いるような
大掛かりなプロジェクトでなければ
ソートに手を入れて高速化をはかるような
案件に出会えないですかね。

興味がある方は
突き詰めてみるのも面白いかもです。

今回はこれまでです
それでは。

先日放送されていた
水曜日のダウンタウンの企画で使われていた
清春さんの新曲にAIは
どこまで正しく文字起こしできるのか
検証してみることとしました。

解説動画はこちら




はじめに


元ネタは「水曜日のダウンタウン」の企画
「清春の新曲、歌詞を全て書き起こせるまで脱出できない生活」
です。

ここでは、清春さんの新曲「霧」の歌詞を
芸人「きしたかの」が二人合わせて聞き取っていましたが
AI文字起こしでどこまで正しく文字起こしできるのか
試してみる事としました。


手順としては
1.spleeterでボーカル音声を抽出する
2.ボーカル音声をWhisperで文字起こしする
となります。



1.Spleeter でボーカルを抽出する

楽曲の音声ファイルから
声だけを抜き取るには
「Spleeter」を使うと出来ます。

詳しい使い方は
音楽データからボーカル・伴奏の音を抽出できるspleeterを使ってみた


インストール
# インストール
!pip uninstall tensorflow -y
!pip install yt-dlp
!pip install pydub
!pip install spleeter==2.4.0

ライブラリの読み込み
# モジュール読み込み
import warnings
warnings.simplefilter('ignore')
from IPython.display import Audio,display,clear_output,update_display
import glob
import os
import subprocess
import re
import ipywidgets as widgets
import shutil
from pydub import AudioSegment
from spleeter.separator import Separator

音声ファイルをディレクトリ に起きます。
配置したmp3からボーカルだけを抽出します。
#@title mp3からボーカル抽出
from spleeter.separator import Separator
file_name = "霧.mp3"#@param {type:"string"}
MP3_BITRATE = "192k"#@param {type:"string"}

# 2stemsモデルを使用してボーカルと伴奏に分離
separator = Separator('spleeter:2stems')

# 音楽ファイルを読み込み、分離を実行
separator.separate_to_file(file_name, '/content')

# wavをmp3に変換する
dir_path = file_name.replace(".mp3","")
vol_file_name = "vocals.wav"
audio_file_path = f"/content/{dir_path}/{vol_file_name}"
AudioSegment.from_wav(audio_file_path).export(audio_file_path.replace(".wav",".mp3"),format="mp3",bitrate=MP3_BITRATE)

抽出した音声を聴く場合は
#@title ボーカル抽出を聞いてみる
from IPython.display import Audio

# 音声ファイルのパス
audio_file_path = '/content/霧/vocals.mp3'#@param {type:"string"}

# 音声の再生
Audio(audio_file_path)

2.Whisperで文字起こしをする

whisperはopen AI が開発した
音声文字起こしです。

詳しくはこちら
音声認識ライブラリWhisperを使って文字起こししてみる


OpenAI Whisperのインストール
!pip install git+https://github.com/openai/whisper.git

文字起こしの実行はこちら
#@title OpenAI Whisperで文字起こし
import whisper

vocal_file_path = "/content/霧/vocals.wav"#@param {type:"string"}

model = whisper.load_model("base")
result = model.transcribe(vocal_file_path)

answer = result["text"]
print(answer)

うまく文字起こしできたら
テキストが表示されると思います。


さーて
うまくいったのでしょうか!!?!

結果は動画をお楽しみ下さい
それでは。



今回はR1ファイナリスト
ルシファー吉岡さんのネタを
検証してみることとしました。

解説動画はこちら





はじめに

R1ファイナリスト
ルシファー吉岡大先生のネタに
東京中のデリ全部呼んでみた

というネタがあります。

このネタの中では
大体の店舗数と
平均在籍人数がうたわれていましたが
今、このネタを実践すると
おおよそ幾ら掛かるのか

大雑把なフェルミ推定してみたいと思います



計算方法

店舗数 x 在籍人数 x 平均金額
金額はネタと同じく
60分あたりの金額とします。



1.東京都のデリバリー店舗数

こういうのは警視庁の許可がいりますね。

無店舗型性風俗特殊営業1号 の許可数が
店舗数になると思います。


こんな資料をみつけました

こちらに
令和4年12月末時点の
許可数が出ていました。



2.在籍人数を推測する

全ての店舗のHPが
WEB上に存在する訳では
無さそうだったので

「シティー天国」というサイトがあったので
そこのデータを引っ張ってくる事にしました。


うまく取れなかったのを除いて
在籍数の分布は
ninzuu

こんな感じになります。
これの平均在籍人数を求めました。



3.料金はどうなっているのか

そのお店の紹介に載っている
コースの料金を元に
60分あたりのコース料金を計算しました。


kakaku

分布はこんな感じになります。
この平均値を一人当たりの料金とします。


実際にかかる金額はいくらになるか

1.店舗数 : X件
2.平均在籍人数 : Y人
3.60分平均料金 : Z円

X * Y * Z = ・・・・・

金額は動画を見てみて下さいね。


最後に

いやーこんな素敵なネタを思いついて下さるなんて
素晴らしいですね

発想が神の領域侵犯です。

2024年のR1ファイナリストらしいので
是非優勝していただきたいと思います。

それでは。

このページのトップヘ