2016年6月29日水曜日

WebWorkerでナンプレを解くサンプルを作成しました

WebWorkerの利用例として適切なテーマを模索中。
そこそこの計算コストが必要でマルチスレッドにも向いている……と思いナンプレを選んでみましたが、作ってみたら25x25でもサブスレッド1つで2秒で解けちゃいました。
捨てるのも勿体ないので公開します。




サンプルソースは以下。
<html>
<head>
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<title>web worker ナンプレ</title>
<style type="text/css">
.inp99{font-size:0.6em;width:1.4em;height:1.4em;text-align:center;}
</style>
</head>
<body>
<table id=tbl border=1 style="border-collapse:collapse;">
<tr><td style="padding:0px;"><input class=inp99></td></tr>
</table>
<div id=div></div>
<button id=btn>処理開始</button>
<button id=btnテキスト出力>テキスト化</button>
<button id=btnテキスト読込>テキストから読み込み</button><br>
<textarea id=ta style="width:500px;height:500px;"></textarea>
</body>
<script type="text/jscript">
平方根 = 5
resizeTo(570, 850)
onload=function(){
一辺の長さ = Math.pow(平方根, 2)
初期化()
}
btn.onclick=function(){
処理開始()
}
btnテキスト出力.onclick=function(){
var arr=各セル値から二次元配列作成()
for(var i=0,L=arr.length;i<L;i++){ arr[i] = arr[i].join('\t') }
ta.value = arr.join('\r\n')
}
btnテキスト読込.onclick=function(){
var arr=ta.value.replace(/\r/g,'').split('\n')
for(var i=0,L=arr.length;i<L;i++){
arr[i] = arr[i].split('\t')
}
二次元配列を各セルに代入(arr)
}
function 処理開始(){
開始時刻 = (new Date()).getTime()
btn.disabled = true
全セルに(function(inp){ inp.disabled=true })
worker.postMessage({
msg : '開始',
二次元配列 : 各セル値から二次元配列作成()
})
}
function 全セルに(func){
for(var row=0; row<一辺の長さ ;row++){
for(var col=0; col<一辺の長さ ;col++){
func(gets(getCell(row, col), 'input')[0], row, col)
}
}
}
function 初期化(){
tblを9x9にする()
}
function tblを9x9にする(){
var tbo=gets(tbl, 'tbody')[0], tr=gets(tbl, 'tr')[0], td=gets(tbl, 'td')[0]
// とりあえず9列にする
for(var i=1; i<一辺の長さ ;i++){ tr.insertBefore(td.cloneNode(true)) }
// 次に9行にする
for(var i=1; i<一辺の長さ ;i++){ tbo.insertBefore(tr.cloneNode(true)) }
}
function getCell(row, col){
var tr=gets(tbl, 'tr')[row], td=gets(tr, 'td')[col]
return td
}
function 二次元配列を各セルに代入(二次元配列){
全セルに(function(inp, row, col){ inp.value=二次元配列[row] ? 二次元配列[row][col] : '' })
}
function 各セル値から二次元配列作成(){
var 二次元配列=[]
for(var i=0;i<一辺の長さ;i++){二次元配列[i] = []}
全セルに(function(inp, row, col){ 二次元配列[row][col]=inp.value })
return 二次元配列
}
worker = fun2Worker(function(){
// ワーカー側スコープ
onmessage = function(e){
switch(e.data.msg){
case '開始':
二次元配列 = e.data.二次元配列
一辺の長さ = 二次元配列.length
平方根 = Math.sqrt(一辺の長さ)
検査No = 1
sw空きマス0 = false
sw値無しマス = false
sw進展なし = true
postMessage({
msg :'confirm',
value:[
'一辺の長さ : '+一辺の長さ,
'平方根 : '+平方根,
'二次元配列 : ',
'　['+二次元配列.join(']\n　[')+']',
'WebWorker:メイン()'
].join('\n')
})
メイン()
break
}
}
function メイン(){
マスキング()
空きマスobj作成()
if(sw空きマス0){
// 空きマスが1つもない場合(マスキングによって"空き"じゃないマスもあり得る)
// 値無しのマスが1つも無いなら、完成したことを報告して処理終了する。
if(!sw値無しマス){ return postMessage({msg:'完成'}) }
}else{
穴埋め()
}
検査No++
if(検査No > 一辺の長さ){
if(sw進展なし){
// すべての検査Noを試しても進展なしの場合、それ以上継続しても無駄なので終了する。
return postMessage({msg :'進展なし'})
}
検査No = 1
sw進展なし = true
}
setTimeout(arguments.callee, 1)
}
function マスキング(){
// 値が確定済みのセルや、検査Noが入る箇所が確定している列・行のセルは
// 処理対象外として判別するためのマスクデータを作成する。
マスク = []
for(var row=0; row<一辺の長さ ;row++){ マスク[row] = [] }
for(var i=0;i<一辺の長さ;i++){
マスキング_横(i)
マスキング_縦(i)
マスキング_ブロック(i)
}
var str=''
for(var row=0;row<一辺の長さ;row++){
str += '　'
for(var col=0;col<一辺の長さ;col++){
str += マスク[row][col] ? '■' : '□'
}
str += '\n'
}
postMessage({
msg :'confirm',
value:[
'マスク後',
'検査No : '+検査No,
'マスク : ',
str,
'WebWorker:マスク()'
].join('\n')
})
}
function マスキング_横(row){
var sw検査No有り
横に (row, function(row, col, val){ if(val==検査No ){return sw検査No有り=true } }, 二次元配列)
横に (row, function(row, col, val){ if(sw検査No有り || val){ マスク[row][col] = true } }, 二次元配列)
}
function マスキング_縦(col){
var sw検査No有り
縦に (col, function(row, col, val){ if(val==検査No ){return sw検査No有り=true } }, 二次元配列)
縦に (col, function(row, col, val){ if(sw検査No有り || val){ マスク[row][col] = true } }, 二次元配列)
}
function マスキング_ブロック(num){
var sw検査No有り
ブロックに(num, function(row, col, val){ if(val==検査No ){return sw検査No有り=true } }, 二次元配列)
ブロックに(num, function(row, col, val){ if(sw検査No有り || val){ マスク[row][col] = true } }, 二次元配列)
}
function 空きマスobj作成(){
// マスキングでターゲットになったセルに処理を集中させるために
// どの行・列のセルが空き（ターゲット）なのかを示すオブジェクトを作成する。
obj空きマス = {行:{}, 列:{}, ブロック:{}}
sw空きマス0 = true
sw値無しマス = false
全セルに(function(row, col){
var val=二次元配列[row][col]
// 全セルに値が入力済み、でなければtrueを入れる
if(!val){ sw値無しマス = true }
// 値があるセルと、マスクtrueのセルは無視
if(val || マスク[row][col]){return true}
// 一つでも空きがある場合はsw空きマス0はfalseとする
sw空きマス0 = false
/*
if(row==0 && col==8){
postMessage({
msg :'confirm',
value:[
'空きマスobj作成',
'検査No : '+検査No,
'row : '+row,
'col : '+col,
'WebWorker:穴埋め()'
].join('\n')
})
}
*/
if(!obj空きマス.行[row]){ obj空きマス.行[row]={} }
if(!obj空きマス.列[col]){ obj空きマス.列[col]={} }
obj空きマス.行[row][col] = true
obj空きマス.列[col][row] = true
})
var num, func=function(row, col, val){
var i=arguments.callee.i++
// 値があるセルと、マスクtrueのセルは無視
if(val || マスク[row][col]){return true}
/*
postMessage({
msg :'confirm',
value:[
'空きマスobj作成_ブロック',
'検査No : '+検査No,
'row : '+row,
'col : '+col,
'val : '+val,
'num : '+num,
'i : '+i,
'WebWorker:空きマスobj作成()'
].join('\n')
})
*/
if(!obj空きマス.ブロック[num]){ obj空きマス.ブロック[num]={} }
obj空きマス.ブロック[num][i] = true
}
for(num=0;num<一辺の長さ;num++){
func.i = 0
ブロックに(num, func, 二次元配列)
}
}
function 穴埋め(){
// 各列・行・ブロックで、空きマスが一つしかない領域がある場合
// そのマスには検査Noの値を入れれば良い。
var row, col, num, i
for(row in obj空きマス.行){
// 空きマス：1以外は無視する
if(カウントforIn(obj空きマス.行[row]) != 1){ continue }
for(col in obj空きマス.行[row]){}
for(col in obj空きマス.行[row]){
postMessage({
msg :'confirm',
value:[
'特定_行',
'検査No : '+検査No,
'row : '+row,
'col : '+col,
'WebWorker:穴埋め()'
].join('\n')
})
特定(row, col)
}
}
for(col in obj空きマス.列){
// 空きマス：1以外は無視する
if(カウントforIn(obj空きマス.列[col]) != 1){ continue }
for(row in obj空きマス.列[col]){
postMessage({
msg :'confirm',
value:[
'特定_列',
'検査No : '+検査No,
'row : '+row,
'col : '+col,
'WebWorker:穴埋め()'
].join('\n')
})
特定(row, col)
}
}
for(num in obj空きマス.ブロック){
// 空きマス：1以外は無視する
if(カウントforIn(obj空きマス.ブロック[num]) != 1){ continue }
for(i in obj空きマス.ブロック[num]){
var 余り=num%平方根, offsetRow=num-余り, offsetCol=余り*平方根
row = offsetRow + (i - i % 平方根) / 平方根
col = offsetCol + i % 平方根
postMessage({
msg :'confirm',
value:[
'特定_ブロック',
'検査No : '+検査No,
'num : '+num,
'i : '+i,
'row : '+row,
'col : '+col,
'WebWorker:穴埋め()'
].join('\n')
})
特定(row, col)
}
}
}
function カウントforIn(obj){
var i=0,name
for(name in obj){i++}
return i
}
function 横に(row,func,arr){
for(var col=0;col<一辺の長さ;col++){
if(func(row, col, arr?arr[row][col]:arr)){return}
}
}
function 縦に(col,func,arr){
for(var row=0;row<一辺の長さ;row++){
if(func(row, col, arr?arr[row][col]:arr)){return}
}
}
function ブロックに(num, func, arr){
var 余り=num%平方根, offsetRow=num-余り, offsetCol=余り*平方根, row, col
for(var i=0;i<一辺の長さ;i++){
row = offsetRow + (i - i % 平方根) / 平方根
col = offsetCol + i % 平方根
func(row, col, arr?arr[row][col]:arr)
}
}
function 全セルに(func){
for(var row=0; row<一辺の長さ ;row++){
for(var col=0; col<一辺の長さ ;col++){
func(row, col)
}
}
}
function 特定(row, col){
二次元配列[row][col] = 検査No
postMessage({
msg : '特定',
row : row,
col : col,
num : 検査No
})
sw進展なし = false
// 特定によるマスク
横に(row, function(row, col){マスク[row][col] = true})
縦に(col, function(row, col){マスク[row][col] = true})
var ブロックnum=getブロックnum(row, col)
ブロックに(ブロックnum, function(row, col){マスク[row][col] = true})
// 特定した空きマスをobj空きマスから削除（行ごと、列ごと、ブロックごと削除する）
delete obj空きマス.行[row]
delete obj空きマス.列[col]
delete obj空きマス.ブロック[ブロックnum] // [(row%平方根)*平方根+(col%平方根)]
}
function getブロックnum(row, col){
return row - (row % 平方根) + ((col - (col % 平方根)) / 平方根)
}
})
worker.onmessage = function(e){
var obj=e.data
switch(obj.msg){
case '特定':
gets(getCell(obj.row, obj.col), 'input')[0].value = obj.num
break
case '完成':
終了時刻 = (new Date()).getTime()
btn.disabled = false
全セルに(function(inp){ inp.disabled=false })
div[iT] = (終了時刻 - 開始時刻) + ' ミリ秒'
break
case '進展なし':
終了時刻 = (new Date()).getTime()
btn.disabled = false
全セルに(function(inp){ inp.disabled=false })
div[iT] = (終了時刻 - 開始時刻) + ' ミリ秒'
break
case 'confirm':
// confirm(obj.value)
break
}
}
サンプルデータ = [
' 3 13 6 10 18 17 11 14 20 9 24 22',
'4 17 13 8 21 12 23 20 10 2 1 3 15 16 19 ',
' 5 11 7 6 15 16 3 2 12 22 9 25 18',
' 8 18 16 14 23 1 24 19 17 21 11',
'14 23 3 25 2 8 4 7 13 17',
'2 1 10 16 19 6 22 18 25 17 21 13 14 ',
'3 24 5 14 15 11 4 23 7 25 16 ',
' 15 1 18 13 9 10 22 24 7 21 20 8',
' 19 12 20 9 25 24 14 6 5 16 11 4 15 18 13',
' 13 18 23 24 21 2 7 5 22 16 12 17 9 ',
' 22 5 17 25 21 11 1 20 10 23 4',
'24 6 18 4 7 14 19 8 23 16 13 5',
'10 16 15 2 7 8 22 17 5 9 18 19 1 3 ',
'20 23 12 21 9 14 2 22 13 3 11 6 7 ',
'11 21 25 19 10 23 20 24 17 15 8 2 6',
'8 9 22 11 19 15 24 20 17 16 13 18 10 21 4 ',
' 12 1 20 25 18 10 23 7 3 5 9 14 4 ',
' 17 25 5 1 8 4 12 7 13 16 11 24',
'16 21 13 15 22 6 3 19 25 23 5 7 8 2',
' 6 10 22 3 25 2 15 21 19 12 ',
'9 16 13 14 1 25 12 8 15 7 2 22 17 3 19',
' 1 10 9 16 7 19 24 14 20 15 17 5 ',
'17 22 7 2 20 4 12 19 21 25 14 6 1 8 23 ',
'23 5 15 11 21 25 4 24 14 22 6 10 ',
' 3 25 5 13 17 23 19 12 7 18 1'
].join('\n')
ta.value = サンプルデータ
// 以下、定型文
FI='firstChild', CN='childNodes', iT='innerText'
function getFunctionBody(fun){
return fun.toString().trim().match(/^function[\s\w]*\([\w\s,]*\)\s*{([\w\W]*?)}$/)[1]
}
function fun2Worker(fun){
var str=getFunctionBody(fun), blob=new Blob([str], {type:'text/javascript'}), url=URL.createObjectURL(blob), worker
try{worker = new Worker(url)}
catch(e){
// Workerに渡すアドレスは同一生成元ポリシーを守らなければいけない。
// 変数urlの中身は「brob:XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX」のﾗﾝﾀﾞﾑな文字列
// 呼び出し元ファイルのアドレスがローカルのものなら、ローカルPathしか渡せない。
var fs=new ActiveXObject('Scripting.FileSystemObject'), path=fs.getSpecialFolder(2)+'/'+fs.getTempName()+'.js', ws=fs.CreateTextFile(path,true,true)
ws.Write(str)
ws.Close()
worker = new Worker(path)
}
return worker
}
function gets(elem, name){return elem.getElementsByTagName(name)}
</script>
</html>
view raw WebWorker_ナンプレ.hta hosted with ❤ by GitHub


画面



マス目に数字を入力して「処理開始」ボタンを押すとWorkerスレッドが作成されて、各空欄に入る数字が特定できたらその欄に数字が入力されていきます。

マス目に数字を入力するのが大変な場合は「テキストから読み込み」ボタンをクリックすると、画面下部のテキストエリア内にある情報がマス目に展開されます。



実行結果



軽く見渡してみると、なんとなく正解になっているように見えますが一応Excelでも検証してみました。
※下図では表示されていませんが縦・横・ブロックごとに数字の重複がないかcountifで確認しています。

正解のようです。


当初の目的はWebWorkerの有効活用でしたが、いきなりマルチスレッドな仕組みにするとデバッグが大変そうだったので、とりあえず（マルチスレッドを見据えつつ）サブスレッド１つで作りました。
結果的に１つのサブスレッドでしか計算していないのでWebWorkerを使わずとも2秒程度で解けるようです。


シングルスレッドでは長時間かかる処理がマルチスレッドだと短縮できる、というのを実用的な用途で実測したいのですが・・・なかなか見つかりません。
投稿者 時刻:
ラベル: , ,

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)