WebWorker用asearch

実装

interfaceを少し変える

code:script.d.ts

declare function fuzzySearch<T>(Props: {

query: string;

source: T[];

callback: (item: T) => string;

limit?: number;

ambig?: number;

timeout?: number;

}): T[][];

引数

配列で渡す

時間内に計算が終わらなかかったら、その時点までに検索できたもののみ返す

0以下だと例外を投げる

0から3までのいずれかを指定できる

戻り値

実装したいこと

マイナス曖昧検索

組み合わせたくさんある

AND: 曖昧度1 / NOT: 曖昧度0

AND: 曖昧度2 / NOT: 曖昧度0

AND: 曖昧度0 / NOT: 曖昧度1

...

マイナス検索は完全一致のみを考慮するだけで良さそう

code:script.js

function fuzzySearch({query, source, callback = w => w, limit, ambig, timeout} = {}) {

// 検索keyword及び検索候補が空のときは何もしない

if (query.trim() === '' || source.length === 0) return [];

// 値のcheck

if (typeof query !== 'string') throw Error('query is not a string.');

if (typeof callback !== 'function') throw Error('callback is not a function');

if (typeof limit !== 'number' && limit !== undefined) throw Error('limit is not a number');

if (limit <= 0) throw Error('limit is not more than 0.');

if (typeof ambig !== 'number' && ambig !== undefined) throw Error('ambig is not a number');

if (typeof timeout !== 'number') throw Error('timeout is not a number.');

if (timeout <= 0) throw Error('timeout is not more than 0.');

let cancel = false;

const execCancel = () => cancel = true; // 計算を中断する関数

/*

// この時点ではまだPromiseを開始しない

const execPromise = () => new Promise((resolve) => {*/

// 空白文字で区切った文字列を並び替え、曖昧検索objectを作る

const asearches = getPermutation(query.split(/\s/))

//console.log('created asearches.');

// ambigの最大値を計算する

maxAmbig = maxAmbig > 4 ? 4 : maxAmbig;

すべての計算が終了してから実行されている

ただ、このコードはWebWorkerから分離してある。

中断処理をWebWorkerからcallbackとして指定できるようにすればいいのか？

対策

cancel処理を外部に委譲する

戻り値に、cancelするための関数を返す

また計算処理をpromiseで包む

22:08:11 これでもだめだ

promiseの計算に時間がかかっていて、ずっとそっちの処理にかかりっきりになる

code:script.js

// 検索する

const results = [];

const totalResults = new Set();

const searchList = source.map(object => {return {object, text: callback(object)};});

const start = (new Date()).getTime();

3重ループを一気に抜けるために、無名関数でfor loop全体を包んでいる

code:script.js

for (const ambig of range(maxAmbig)) {

const matches = [];

for (const asearch of asearches) {

// 検索したものを重複を取り除いて追加する

for (const {object, text} of searchList) {

if (limit && totalResults.size >= limit) execCancel();

if (cancel) {

// 計算を中断する

results.push(matches);

//resolve(results);

return results;

}

if (totalResults.has(text)) continue;

if (!asearch.match(text, ambig)) continue;

matches.push(object);

totalResults.add(text);

}

if (start + timeout < (new Date()).getTime()) {

console.info('time out');

execCancel();

}

}

results.push(matches);

}

//resolve(results);

/*});*/

//console.log('created promise.');

//return {execute: execPromise, cancel: execCancel};

return results;

}

Utilities

code:script.js

class Asearch {

get INITPAT() {return 0x80000000;} // 0100,0000,0000,0000,0000,0000,0000,0000

get MAXCHAR() {return 0x100;} // 256文字が上限

constructor(source) {

this.shiftpat = Array(this.MAXCHAR).map(_ => 0);

this.epsilon = 0;

let mask = this.INITPAT;

for (const item of this.unpack(source)) {

// 0x20 is a space

if (item === 0x20) {

this.epsilon |= mask;

} else {

mask >>>= 1;

}

}

this.acceptpat = mask;

}

tolower(c) {

return this.isupper(c) ? c + 0x20 : c;

}

toupper(c) {

return this.islower(c) ? c - 0x20 : c;

}

isupper(c) {

// 0x41 = A, 0x5a = Z

return (c >= 0x41) && (c <= 0x5a);

}

islower(c) {

// 0x61 = a, 0x7a = z

return (c >= 0x61) && (c <= 0x7a);

}

state(str = '') {

for (const item of this.unpack(str)) {

i3 = (i3 & this.epsilon) | ((i3 & mask) >>> 1) | (i2 >>> 1) | i2;

i2 = (i2 & this.epsilon) | ((i2 & mask) >>> 1) | (i1 >>> 1) | i1;

i1 = (i1 & this.epsilon) | ((i1 & mask) >>> 1) | (i0 >>> 1) | i0;

i0 = (i0 & this.epsilon) | ((i0 & mask) >>> 1);

i1 |= i0 >>> 1;

i2 |= i1 >>> 1;

i3 |= i2 >>> 1;

}

}

match(str, ambig = 0) {

ambig = ambig < this.INITSTATE.length ? ambig : this.INITSTATE.length - 1;

const s = this.state(str);

}

// UTF-16 code pointを上8bitと下8bitとに分割する

unpack(str) {

return str.split('')

.flatMap(char => {

const code = char.charCodeAt(0);

if (code > 0xFF) {

}

});

}

}

リストの順列を返す

code:script.js

// 重複は考慮していない

function getPermutation(list) {

if (list.length == 0) return list;

return list.flatMap(first => {

const restList = list.filter(item => item !== first);

});

}

test code

code:js

(() => {

const worker = new Worker('/api/code/programming-notes/WebWorker用asearch/test1_worker.js');

worker.postMessage({type: 'fetch', projects: [

'hub',

'shokai',

'nishio',

'masui',

'rakusai',

'yuiseki',

'june29',

'ucdktr2016',

'villagepump',

'rashitamemo',

'thinkandcreateteck',

'customize',

'scrapboxlab',

'scrasobox',

'foldrr',

'scrapbox-drinkup',

'motoso',

'public-mrsekut',

'mrsekut-p',

'marshmallow-rm',

'wkpmm',

'sushitecture',

'nwtgck',

'dojineko',

'kadoyau',

'inteltank',

'sta',

'kn1cht',

'miyamonz',

'rmaruon',

'MISONLN41',

'yuta0801',

'choiyakiBox',

'choiyaki-hondana',

'spud-oimo',

'keroxp',

'aioilight',

]});

window.search = (word, {limit = 30, timeout = 10000,} = {}) => worker.postMessage({type: 'search', word, limit, timeout});

})();

code:test1_worker.js

self.importScripts('/api/code/programming-notes/WebWorker用asearch/script.js');

// 検索候補

const list = [];

self.addEventListener('message', message => {

switch (message.data.type) {

case 'search':

search(message.data);

break;

case 'fetch':

fetch_(message.data.projects);

break;

}

});

async function search({word, limit, timeout}) {

const result = fuzzySearch({

query: word.split('/').join(' '),

source: list,

limit, timeout,

});

_log('finished: %o', result);

self.postMessage({links: result,});

/* const {execute, cancel} = fuzzySearch({

query: word.split('/').join(' '),

source: list,

limit,

});

let promise = undefined;

let timer = null;

const post = async () => {

clearTimeout(timer);

const result = await promise;

_log('finished: %o', result);

self.postMessage({links: result,});

}

_log('start timer.', timeout);

promise = execute();

timer = setTimeout(async () => {

cancel();

_log('abort searching.', timeout);

clearTimeout(timer);

const result = await promise;

_log('finished: %o', result);

self.postMessage({links: result,});

}, timeout);

await post();*/

}

async function fetch_(projects) {

_log('Loading links from %o', projects);

const result = await Promise.all(projects

.map(project => fetchExternalLinks(project))

);

_log('Finish loading links from %o', projects);

list.push(...result.flat());

}

async function fetchExternalLinks(project) {

let followingId = null;

let temp = [];

do {

const json = await (!followingId ?

).then(res => {

followingId = res.headers.get('X-Following-Id');

return res.json();

});

} while(followingId);

return links;

}

// debug用

function _log(msg, ...objects) {

}

JavaScript.icon