asearch-engine

用途

interface

code:js

import {create} from 'xxx';

const emojiEngine = create({

source: emojis,

});

const resultPromises = emojiEngine.search('searchParam'); // 検索

わかりやすくするために、型付きで説明しておこう

code:ts

const create: <T>(props: CreateProps<T>) => SearchEngine<T>;

type CreateProps = <T>{

converter: (item: T) => string;

source?: T[];

limit?: number;

timeout?: number;

};

declare class SearchEngine<T> {

constructor(converter: (item: T) => string, limit: number, timeout: number);

search(query: string) => Promise<{

result: T[];

state: 'fullfilled' | 'timedout';

} | {

state: 'skipped';

}>[];

update(source: T[]) => Promise<void>;

};

検索に使うクラス

非同期関数

検索に使用したWeb Workerと同じ数だけPromiseが返ってくる

dependencies

code:script.js

import {asyncSingleton} from '/api/code/takker/async-singleton/script.js';

変数をカプセル化するために、classのstatic変数ではなくmodule内部のglobal変数として定義している

code:script.js

const workers = range(navigator.hardwareConcurrency)

.map(_ => new Worker(workerSource));

let idCounter = 0; // 実行しているengineの識別子

code:script.js

export async function create({converter, source = [], limit = 30, timeout = 10000, ambig = undefined} = {}) {

const engine = new SearchEngine(converter, limit, timeout, ambig, idCounter);

idCounter++;

if (source.length > 0) await engine.update(source);

return engine;

}

class SearchEngine {

constructor(converter, limit, timeout, ambig, id) {

this.id = id;

this.converter = converter;

this.searchObjects = [];

this.skips = [];

this._searchCallbacks = workers.map(worker => asyncSingleton(async query => {

const {indicesList} = await postToWorker(worker, {

type: 'search', id, query, limit, timeout, ambig

});

return indicesList;

}));

}

search(query) {

return this._searchCallbacks.map(async (callback, workerIndex) => {

const {result: indicesList, state} = await callback(query);

if (state === 'canceled') return {state};

return {

result: indicesList

.map(indices => indices

),

state,

};

});

}

async update(sourceObjects) {

// 元のobjectを保存する

this.searchObjects = sourceObjects;

// 検索用文字列リストを作る

const source = this.searchObjects.map(object => this.converter(object));

// 検索用文字列リストをworkersに分割して渡す

const chunkLength = Math.floor(source.length/workers.length) + 1;

const promises = workers.map((worker, i) =>{

const chunk = source.slice(i * chunkLength, (i + 1) * chunkLength);

this.skips.push(i * chunkLength);

return postToWorker(worker, {type: 'update', id: this.id, source: chunk});

});

return await Promise.all(promises);

}

}

複数の入力補完scriptが同じworkerに処理を送るので、どのscriptから来た命令なのかを区別できるようにする

code:script.js

function postToWorker(worker, message) {

worker.postMessage(message);

return new Promise(resolve => {

const callback = ({data}) => {

if (data.type !== message.type || data.id !== message.id) return;

resolve(data);

worker.removeEventListener('message', callback);

}

worker.addEventListener('message', callback);

});

}

worker code

code:worker.js

self.importScripts('/api/code/takker/asearch/worker.js');

let sourceList = []; // 検索用文字列を格納するリスト

self.addEventListener('message', ({data: {id, type, source, ...rest}}) => {

switch(type) {

case 'search':

self.postMessage({indicesList: search({id, ...rest}), id, type,});

break;

case 'update':

update({id, source});

self.postMessage({id, type,}); // 処理の終了を通知する

break;

}

});

function search({id, query, ambig, limit, timeout}) {

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

if (!source || source.length === 0) return [];

// 値のcheck

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

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

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 timeout !== 'number') throw Error('timeout is not a number.');

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

// 検索語句が空のときは、検索候補の先頭limit個の番号を取得する

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

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

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

maxAmbig = maxAmbig > 4 ? 4 : maxAmbig;

// 検索する

const indicesList = [];

const totalResults = new Set();

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

let matches = [];

let cancel = false; // 計算を中断するflag

for (let ambig = 0; ambig < maxAmbig; ambig++) {

matches = [];

for (const asearch of asearches) {

// 検索した文字列の要素番号を重複を取り除いて追加する

for (let i = 0; i < source.length; i++) {

if (limit && totalResults.size >= limit) {

cancel = true;

break;

}

if (totalResults.has(i)

matches.push(i);

totalResults.add(i);

}

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

console.info('time out');

cancel = true;

}

if (cancel) break;

}

indicesList.push(matches);

if (cancel) break;

}

return indicesList;

}

function update({id, source}) {

}

code:worker.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

(async () => {

const {execute} = await import('/api/code/takker/asearch-engine/test1.js');

await execute();

// 一つづつ検索

await externalSearch('scrapbox');

await emojiSearch('いい');

// 同時検索

await Promise.all([

externalSearch('scrapbox'),

emojiSearch('いい'),

]);

// 連続してPOSTされたら、途中の計算を省く

await Promise.all([

externalSearch('理想 問題'),

externalSearch('理想 問題'),

externalSearch('理想 問題'),

emojiSearch('goo'),

emojiSearch('goo'),

emojiSearch('goo'),

emojiSearch('goo'),

externalSearch('理想 問題'),

externalSearch('理想 問題'),

externalSearch('理想 問題'),

emojiSearch('goo'),

emojiSearch('goo'),

emojiSearch('goo'),

externalSearch('理想 問題'),

externalSearch('理想 問題'),

externalSearch('理想 問題'),

externalSearch('理想 問題'),

]);

})();

code:test1.js

import {create} from '/api/code/takker/asearch-engine/script.js';

import {projects as projectList} from '/api/code/takker/asearch-engine/test1-project-list.js';

export async function execute() {

createTestData(projectList),

createEmojiData(),

]);

create({

source: externalSource,

limit: 100,

ambig: 4,

}),

create({

source: emojiSource,

limit: 10,

}),

]);

let counter = 0;

const search = async (engine, query) => {

const promises = engine.search(query);

const counter_ = counter;

counter++;

promises.forEach(async (promise, index) => {

const {result, state} = await promise;

if (state === 'canceled') {

return;

}

});

await Promise.all(promises);

};

window.emojiSearch = (query) => search(emojiEngine, query);

window.externalSearch = (query) => search(externalEngine, query);

}

async function createTestData(projects) {

return shuffle((await Promise.all(projects.map(project => fetchPagess(project)))).flat());

}

async function createEmojiData() {

.map(project => fetchPagess(project)))

).flat();

}

function shuffle(array) {

let result = array;

for (let i = result.length; 1 < i; i--) {

const k = Math.floor(Math.random() * i);

}

return result;

}

async function fetchPagess(project) {

// projectの空でない全てのページ数を取得する

const {count} = await res.json();

const maxIndex = Math.floor(parseInt(count) / 1000) + 1;

const {pages} = await response.json();

return pages.map(({title}) => {return {project, title};});

});

const emojis = (await Promise.all(promises)).flat();

return emojis;

}

async function fetchEmojis(project) {

// projectの全ページ数を取得する

const {count} = await res.json();

const maxIndex = Math.floor(parseInt(count) / 1000) + 1;

const {pages} = await response.json();

});

const emojis = (await Promise.all(promises)).flat();

return emojis;

}

function _log(msg, ...objects) {

if (typeof msg !== 'object') {

} else {

}

}

code:test1-project-list.js

export const 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',

];