このページでは、batファイルを利用して並列処理を実装する方法と、それを活用したクイックソート(もどき)を紹介します。
要素の条件は、最大値が1以上の整数で、1から最大値まで欠番・重複のない整数列です。
処理時間は1～320までで10秒ほど、1～1600までで40～50秒ほどとなります。
batファイルでも楽に実装できるバブルソートなどに比べればかなり高速かと思います。
ただし、著しく少ない要素数でこのソートを実行するとバブルソートよりもかなり遅くなります。
表：処理時間目安。ただしこのbatファイルは動作時間にばらつきが多いためあくまで目安。
| 要素数(個) | 処理時間(sec) |
|---|---|
| 2 | 5 |
| 8 | 5.2 |
| 16 | 5~6 |
| 32 | 6 |
| 64 | 6~6.5 |
| 100 | 6~7 |
| 200 | 7~8 |
| 300 | 9~10 |
| 500 | 12~14 |
| 1000 | 19~22 |
| 1600 | 40~46 |
| 2400 | 約100 |
今回のプログラムは3つに分割されています。使用する時は以下の3つのbatファイルを同じディレクトリに保存し、QuickSort.batのみを起動してください。
@echo off
cd %~dp0
setlocal enabledelayedexpansion
:Main
call :GetNoe
call :Reset
echo シャッフル中。
call :Shuffle1
call :Shuffle2
cls
echo シャッフル完了。何かキーを押すとソートを開始します。
pause >NUL
call :GetStartTime
call :QuickSort
call :fPutResult
echo 出力完了！
call :GetEndTime
call :PutTime
echo 何かキーを押すと終了します。
pause >NUL
exit
:GetNoe
echo 要素数を1以上の整数(半角)で入力。3000以上にしないことををお勧めします。0以下または入力なしで終了。
set /p noe=
if "%noe%" == "" exit
if %noe% lss 1 exit
echo 要素を並び替えるための入れ替え回数を指定。要素数の1.3倍以上が適切です。
set /p count=
exit /b 0
:Reset
rmdir /s /q %cd%\Flag1
rmdir /s /q %cd%\Flag2
rmdir /s /q %cd%\SortTemp
mkdir %cd%\SortTemp
del /q %cd%\sorted.txt
cls
echo %random% >nul
(echo 1)>%cd%\SortTemp\tmprd.txt
(echo %noe%)>>%cd%\SortTemp\tmprd.txt
set n=-2
exit /b 0
:shuffle1
for /l %%i in (1,1,%noe%) do set yama%%i=%%i
exit /b 0
:shuffle2
for /l %%i in (1,1,%count%) do (
set /a sel1=!random!*%noe%/32768+1
set /a sel2=!random!*%noe%/32768+1
set /a yamatmp=yama!sel1!,yama!sel1!=yama!sel2!,yama!sel2!=yamatmp
)
for /l %%i in (1,1,%noe%) do echo !yama%%i!>>%cd%\SortTemp\tmprd.txt
ren %cd%\SortTemp\tmprd.txt QS1.txt
exit /b 0
:QuickSort
call :SetpNum
cls
echo %pNum%分割中…
mkdir %cd%\Flag1
call :Partition
set adjust=0
call :wait 1
rmdir /s /q %cd%\Flag1
cls
echo %pNum%分割完了！
mkdir %cd%\Flag2
call :Sorting
set adjust=0
call :wait 2
rmdir /s /q %cd%\Flag2
echo ソート完了！
exit /b 0
:SetpNum
if %noe% geq 2500 (
set pNum=256
set l2=65
set hi=129
set hi2=193
exit /b 0
)
if %noe% geq 1400 (
set pNum=128
set l2=33
set hi=65
set hi2=97
exit /b 0
)
if %noe% geq 700 (
set pNum=64
set l2=17
set hi=33
set hi2=49
exit /b 0
)
if %noe% geq 400 (
set pNum=32
set l2=9
set hi=17
set hi2=25
exit /b 0
)
set pNum=16
set l2=5
set hi=9
set hi2=13
exit /b 0
:Partition
for /f %%i in (%cd%\SortTemp\QS1.txt) do (
set /a n+=1
set element[!n!]=%%i
)
del /q %cd%\SortTemp\QS1.txt
set min=!element[-1]!
set max=!element[0]!
set /a piv=max/2
set /a hpiv=piv+1
(echo %min%)>%cd%\SortTemp\QS1.txt
(echo %piv%)>>%cd%\SortTemp\QS1.txt
(echo %hpiv%)>%cd%\SortTemp\QS%hi%.txt
(echo %max%)>>%cd%\SortTemp\QS%hi%.txt
for /l %%i in (1,1,%noe%) do (
if !element[%%i]! leq %piv% (
echo !element[%%i]!>>%cd%\SortTemp\QS1.txt
) else echo !element[%%i]!>>%cd%\SortTemp\QS%hi%.txt
)
start /min "" %cd%\QS.bat 1 %l2%
start /min "" %cd%\QS.bat %hi% %hi2%
(echo 1)>>%cd%\Flag1\complete1.txt
(echo 1)>>%cd%\Flag1\complete%hi%.txt
exit /b 0
:Sorting
for /l %%a in (1,1,%wNum%) do (
start /min "" %cd%\Sorting.bat %%a
)
exit /b 0
:fPutResult
for /l %%a in (1,1,%wNum%) do (
for /f %%b in (%cd%\SortTemp\QS%%a.txt) do (
(echo %%b)>>sorted.txt)
)
)
rmdir /s /q %cd%\SortTemp
exit /b 0
:wait
set wNum=%pNum%
set n1=%1
for /l %%i in (1,1,%wNum%) do (
if not exist %cd%\Flag%n1%\complete%%i.txt goto wait
)
exit /b 0
:GetStartTime
set T=%TIME: =0%
set H=%T:~0,2%
set M=%T:~3,2%
set S=%T:~6,2%
set C=%T:~9,2%
rem --8進対策
set /a H=1%H%-100,M=1%M%-100,S=1%S%-100,C=1%C%-100
exit /b 0
:GetEndTime
set T1=%TIME: =0%
set H1=%T1:~0,2%
set M1=%T1:~3,2%
set S1=%T1:~6,2%
set C1=%T1:~9,2%
rem --8進対策
set /a H1=1%H1%-100,M1=1%M1%-100,S1=1%S1%-100,C1=1%C1%-100
rem --終了時間の計算
set /a H2=H1-H,M2=M1-M
if %M2% LSS 0 set /a H2=H2-1,M2=M2+60
set /a S2=S1-S
if %S2% LSS 0 set /a M2=M2-1,S2=S2+60
set /a C2=C1-C
if %C2% LSS 0 set /a S2=S2-1,C2=C2+100
if %C2% LSS 10 set C2=0%C2%
exit /b 0
:PutTime
echo.
echo 開始時間：%T%
echo 終了時間：%T1%
echo 経過時間：%H2%h %M2%m %S2%.%C2%sec
exit /b 0
このファイルを起動し、他の2ファイルをここから呼び出す構造になっています。
残りの2ファイルは以下の通り
@echo off
setlocal enabledelayedexpansion
:Main
call :Reset %1 %2
call :Partition
(echo 1)>>%cd%\complete.txt
call :WhereNext
if %errorlevel% == 1 exit
rem 分割を繰り返すためにこのbatファイルを再帰的に呼び出す。
rem このstartコマンドが取る引数については下に記載。
start /min "" %cd%\QS.bat %l% %l2%
start /min "" %cd%\QS.bat %h% %h2%
exit
:Reset
cd %~dp0
set n=-2
set l=%1
set h=%2
exit /b 0
:Partition
rem 指定されたtxtファイル内の要素を1つずつ読み込み。
for /f %%i in (%cd%\QS%l%.txt) do (
set /a n+=1
set element[!n!]=%%i
)
rem 読みこんだら削除。
del /q %cd%\QS%l%.txt
rem ヘッダにある最小値最大値を登録
set min=!element[-1]!
set max=!element[0]!
remファイル内の値域の真ん中あたりの値をピボットに指定。
set /a piv=(min+max-1)/2
set /a hpiv=piv+1
rem 分割で生成される新しいtxtファイルのヘッダ(最小値と最大値)書き込み
(echo %min%)>%cd%\QS%l%.txt
(echo %piv%)>>%cd%\QS%l%.txt
(echo %hpiv%)>%cd%\QS%h%.txt
(echo %max%)>>%cd%\QS%h%.txt
rem ピボット以下なら元のファイルへ、ピボットより大きければ新しい%h%番ファイルへ
for /l %%i in (1,1,%n%) do (
if !element[%%i]! leq %piv% (
echo !element[%%i]!>>%cd%\QS%l%.txt
) else echo !element[%%i]!>>%cd%\QS%h%.txt
)
exit /b 0
:WhereNext
rem ファイル番号の差を取り、分割が何回目か判定。
rem 差が8ならこの分割は2回目。次の分割では、l番ファイルをl番とl+4番に、h番ファイルをh番とh+4番に分割するため、引数を用意。
rem 4なら3回目、2なら4回目。
rem 差が1ならこの時点で分割完了。
set /a diff=h-l
if %diff% == 8 (
set /a l2=l+4,h2=h+4
exit /b 0
)
if %diff% == 4 (
set /a l2=l+2,h2=h+2
exit /b 0
)
if %diff% == 2 (
set /a l2=l+1,h2=h+1
exit /b 0
)
if %diff% == 1 (
exit
)
exit /b 1
これが分割を行うbatファイルです。再帰呼び出しを使用しており、1つにつき2つ自分を呼び出すため、かなり多くのプロセスを実行します。ただstartコマンドに/minオプションをつけているので、コンソールウィンドウは出現しません。
次はソート実行ファイルです。
@echo off
setlocal enabledelayedexpansion
:Main
call :Reset %1
call :InsertionSort
rem ソートが完了したらソートを行ったファイル番号に対応した番号のcompleteファイルを作成(1を書き込む)。
(echo 1)>>%cd%\complete%l%.txt
exit
:Reset
cd %~dp0
set n=-2
set l=%1
set tmp=0
exit /b 0
:InsertionSort
rem 引数で与えられた番号のファイルを読み込み。
for /f %%i in (%cd%\QS%l%.txt) do (
set /a n+=1
set element[!n!]=%%i
)
rem 読みこんだら削除。
del /q %cd%\QS%l%.txt
rem ヘッダにある最小値最大値を登録
set min=!element[-1]!
set max=!element[0]!
rem ここのソートは挿入ソートです。最後まで分割を繰り返すよりも、
rem ある程度要素が少なくなるまで分割したら別の方法に切り替えるのがよいという判断。
set /a num=max-min+1
for /l %%i in (2,1,%num%) do (
set /a k=%%i-1
for /l %%j in (1,1,!k!) do (
if !element[%%j]! gtr !element[%%i]! (
set tmp=!element[%%i]!
set /a m=%%j+1
for /l %%o in (%%i,-1,!m!) do (
set /a n=%%o-1
set /a element[%%o]=element[!n!]
)
set element[%%j]=!tmp!
)
)
)
rem ソート結果を元のファイルに書き出し。
rem この時、今までヘッダとして書き加えられていた最小値と最大値は書きこまれないので、
rem 32ファイルでソートが完了したらそれを1番から順番に1つのファイルに書き出せばソート完了。
for /l %%i in (1,1,%num%) do (
(echo !element[%%i]!)>>%cd%\QS%l%.txt
)
exit /b 0
これがソートを行うファイルです。クイックソート(もどき)と言っていたのはここのせいです。ここでは分割されたファイル内の数値を読み出し、挿入ソートを実行した後、元の番号のファイルに書き出すという処理を行います。プログラム内のコメントにも書きましたが、最後まで分割を繰り返すよりも、ある程度要素が少なくなるまで分割したら別の方法に切り替えるのがよいと判断しました。
このファイルは親batファイルからfor文内のstartコマンドで32個起動します。これも/minオプションがついているのでバックグラウンドで実行になります。
ソート実行結果はsorted.txtに保存されます。また、実行中にtxtファイルが30～65個ほど生成・消滅を繰り返しますが、(正常に動作すれば)最後にはすべて削除されているのでご安心ください。(念のために3つのbatファイルはデスクトップやダウンロードなどに直接保存ではなく、新しいフォルダを作成してその中に保存されることをお勧めします。)
startコマンドの難しい点は、startで呼んだbatの処理がすべて終わったかどうかの判定がとても難しいということです。startコマンドには戻り値を返す機能がないため、今回のようにtxtファイルを終了フラグとして利用しました。また、戻り値の機能があるcallコマンドは、呼び出したラベルやbatファイルの処理が終わりexit /bが実行されるまで、呼び出し元の処理は止まってしまうので、並列処理を実装するためにはstartコマンドを使わざるを得ません。
startコマンドで子処理の終了フラグとして使えるもの
1.timeout /t 5 /nobreak >NULなどで親の処理を止めてしまう
この方法は子処理の処理時間が(ほぼ)一定である場合にのみ使用できます。
今回は、分割時は要素数が不明、ソート時は挿入ソートで動作時間が不明 であるため使用を断念。
2.フラグ用にtxtファイルを1つ用意し、子処理が1つ終わるたびにそのファイルに1を追加で書き込む
この方法は、子処理の実行数が固定されている場合に使用可。
しかし、同時に大量の子処理が実行完了するような場合、同じファイルに一斉に書き込もうとして競合し、処理はすべて完了しているのに「1」の数が足りないなんて事態が起こったりします。
3.子処理が1つ終わるたびにフラグ用のtxtファイルを新規作成する
この方法も、子処理の実行数が固定されている場合に使用可。
2番の方法による競合はほぼ回避できますが、50個100個クラスで子処理を実行する場合は(一時的ではあるが)大量のtxtファイルがディレクトリ内に溢れかえります。(forループで削除するのも割と手間になります。)また、ファイル名の重複を防ぐために、親処理で呼び出す時点で個別に引数を与えるなどして番号を区別してやる必要があります。
4.最後の子処理が完了したときに、フラグ用ファイルに1を書きこむ
この方法は、子処理の中だけでこの子処理群の終了条件が判定できる場合に使用可。
子処理の実行数が不明でも、子処理の中で「これで最後」と判定ができるならこれが安定か。
並列処理で最後の処理よりも時間が長くかかる処理がある場合は、最後と判定した後にtimeoutコマンドなどで数秒待ってから1を書き込むなどの対処が必要。
startコマンドを用いて大量のbatファイルを開き、並列処理を実現しようとする方法は、現時点ではどれも動作は不安定になります。
今後の課題は、並列処理のさらなる安定化と、ソートの高速化です。
ソートについて具体的には、今回、要素数が1000を超えたあたりから速度がものすごく低下していたため、それを改善したいと思います。これは、32分割で分割を打ち止めて挿入ソートに切り替えており、要素数が大きくなると挿入ソートの非効率性が浮き彫りになったためだと考えられます。(クイックソートの平均計算時間は$O(nlogn)$だが、挿入ソートの平均計算時間は$O(n^2)$)
よって、要素数によって分割数を動的に変更できるような仕組みを取り入れれば、大きな要素数にも効率よく対応できると思われます。
何か新発見がありましたら更新します。
何かご指摘・ご意見・batでの並列処理に関する新情報などございましたら、コメントでお願いいたします。