![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
YAYAで連想配列が使えないと聞いたので簡単なのを実装してみた。 どれが速いかわからないので数種類やってみた。 #contents - バグがあったら報告してください。 - ライセンスは一応CC0とかで。 * ハッシュ:1つの連想配列メモリを使ってIDで区別する実装(微妙そう) [#b4c50df2] EVALと巨大な引数渡しを回避する方法 ** 利点 [#qe980da8] - EVAL等の遅そうな処理がない ** 欠点 [#g703bee3] - 実行時全体のハッシュが一堂に会するので、要素数が多くなった場合微妙かも - EVAL等がない代わりにロジックは煩雑 - YAYAが変数を自動保存するので終了時に内部変数を削除しなければならない - 操作関数の返り値を返さないのが面倒 ** 使用例 [#m0cff258] // map__hash_size = 65536 // 確保するハッシュ領域のサイズ 実行中一度決めたら変更しない _m = map_new() // 初期化してIDを取得 _junk = map_set(_m, 'key', 'value') _k = map_get(_m, 'key') _ks = map_keys(_m) _junk = map_delete(_m, 'key') _junk = map_destroy(_m) // 削除して使えるハッシュ領域を確保 _junk = map_destroy_all() // ハッシュ領域のグローバル変数開放 ** 実装 [#ua34a828] /* _map_id = map_new() 連想配列初期化 cf. map = {} */ map_new{ if ! ISVAR('map__hash_size') { map__hash_size = 65536 } if ! ISVAR('map__id_num') { map__id_num = 0 } if ! ISVAR('map__key_lists') { map__key_lists = IARRAY } if ! ISVAR('map__keys') { map__keys = IARRAY } if ! ISVAR('map__values') { map__values = IARRAY } map__id_num map__id_num++ } /* _value = map_set(_map_id, _key, _value) 連想配列_map_idの_keyに_valueをセット cf. map{key} = value */ map_set{ _id = _argv[0] _key = _argv[1] _value = _argv[2] _hash = map__get_only_index(_id, _key) // キーが事前に存在しないならmap__key_listsにキー情報を追加 if map__keys[_hash] == IVOID { map__key_lists = (map__key_lists, _id, _key) } map__keys[_hash] = _key map__values[_hash] = _value _value } /* _value = map_get(_map_id, _key) 連想配列_map_idの_keyを参照 cf. value = map{key} */ map_get{ _id = _argv[0] _key = _argv[1] _hash = map__get_only_index(_id, _key) map__values[_hash] } /* _junk = map_delete(_map_id, _key) 連想配列_map_idの_keyを削除 cf. delete(map{key}) */ map_delete{ _id = _argv[0] _key = _argv[1] _hash = map__get_only_index(_id, _key) map__keys[_hash] = IVOID map__values[_hash] = IVOID } /* _keys = map_keys(_map_id, _key) 連想配列_map_idの_keyを列挙 cf. keys = keys(map{key}) */ map_keys{ _id = _argv[0] _size = ARRAYSIZE(map__key_lists) / 2 _keys = IARRAY for _i = 0; _i < _size; _i++ { if map__key_lists[_i * 2] == _id { _key = map__key_lists[_i * 2 + 1] _hash = map__get_only_index(_id, _key) if map__values[_hash] != IVOID { _keys = (_keys, _key) } } } _keys } /* _junk = map_destroy(_map_id) 連想配列_map_idを削除 */ map_destroy{ // keysによりmap__keys, map__values当該を消してからmap__key_lists当該を消す _id = _argv[0] _keys = map_keys(_id) foreach _keys; _key { _hash = map__get_only_index(_id, _key) map__keys[_hash] = IVOID map__values[_hash] = IVOID } _size = ARRAYSIZE(map__key_lists) / 2 _to_delete = IARRAY for _i = 0; _i < _size; _i++ { if map__key_lists[_i * 2] == _id { _to_delete = (_to_delete, _i) } } _to_delete = ASORT('int,descending', _to_delete) foreach _to_delete; _i { map__key_lists[_i * 2, _i * 2 + 1] = IARRAY } } /* _junk = map_destroy_all() 連想配列が使用する変数を削除 */ map_destroy_all{ ERASEVAR('map__hash_size', 'map__id_num', 'map__key_lists', 'map__keys', 'map__values') } map__get_only_index{ // 重複しないようインデックスをずらす _id = _argv[0] _key = _argv[1] _hash_key = _id + TOSTR(_key) _hash = map__hash(_hash_key) while (map__keys[_hash] != IVOID) && (map__keys[_hash] != _key) { if _hash >= (map__hash_size - 1){ _hash = 0 } else { _hash++ } } _hash } map__hash{ // ハッシュ関数 _key = _argv[0] _key_len = STRLEN(_key) _hash = 0 for _i = 1; _i < _key_len; _i++ { _hash = (_hash * 137 + CHRCODE(_key, _i)) % map__hash_size } _hash } * ハッシュ:EVALによる実装(あり？) [#y4e0d20d] EVALを使う代わりにより自然なロジックで実装できる。 ** 利点 [#bfa2dc6f] - 自然なロジックで実装できる ** 欠点 [#r10a7b82] - EVALが遅そう(実用上そう気になるレベルではない気がする) - 変数の削除はやはり必要。 - 操作関数の返り値を返さないのが面倒 ** 使用例 [#weff16ed] // map__hash_size = 2048 // 一連想配列に確保するハッシュ領域のサイズ 実行中一度決めたら変更しない _m = map_new() // 初期化してIDを取得 _junk = map_set(_m, 'key', 'value') _k = map_get(_m, 'key') _ks = map_keys(_m) _junk = map_delete(_m, 'key') _junk = map_destroy(_m) // 変数開放 ** 実装 [#s09bacb2] /* _map_id = map_new() 連想配列初期化 cf. map = {} */ map_new{ if ! ISVAR('map__hash_size') { map__hash_size = 2048 } if ! ISVAR('map__id_num') { map__id_num = 0 } LETTONAME('map__keys_' + map__id_num, IARRAY) LETTONAME('map__values_' + map__id_num, IARRAY) map__id_num map__id_num++ } /* _value = map_set(_map_id, _key, _value) 連想配列_map_idの_keyに_valueをセット cf. map{key} = value */ map_set{ _id = _argv[0] _key = _argv[1] _value = _argv[2] _hash = map__get_only_index(_id, _key) _junk = EVAL('map__keys_' + map__id_num + '[_hash] = _key') _junk = EVAL('map__values_' + map__id_num + '[_hash] = _value') _value } /* _value = map_get(_map_id, _key) 連想配列_map_idの_keyを参照 cf. value = map{key} */ map_get{ _id = _argv[0] _key = _argv[1] _hash = map__get_only_index(_id, _key) EVAL('map__values_' + map__id_num + '[_hash]') } /* _junk = map_delete(_map_id, _key) 連想配列_map_idの_keyを削除 cf. delete(map{key}) */ map_delete{ _id = _argv[0] _key = _argv[1] _hash = map__get_only_index(_id, _key) _junk = EVAL('map__keys_' + map__id_num + '[_hash] = IVOID') _junk = EVAL('map__values_' + map__id_num + '[_hash] = IVOID') } /* _keys = map_keys(_map_id, _key) 連想配列_map_idの_keyを列挙 cf. keys = keys(map{key}) */ map_keys{ _id = _argv[0] _keys = IARRAY _size = EVAL('ARRAYSIZE(map__keys_' + map__id_num + ')') for _i = 0; _i < _size; _i ++ { _key = EVAL('map__keys_' + map__id_num + '[_i]') if _key != IVOID { _keys = (_keys, _key) } } _keys } /* _junk = map_destroy(_map_id) 連想配列_map_idを削除 */ map_destroy{ _id = _argv[0] ERASEVAR('map__keys_' + map__id_num) ERASEVAR('map__values_' + map__id_num) } map__get_only_index{ // 重複しないようインデックスをずらす _id = _argv[0] _key = _argv[1] _hash = map__hash(_key) while (EVAL('map__keys_' + _id + '[_hash]') != IVOID) && (EVAL('map__keys_' + _id + '[_hash]') != _key) { if _hash >= (map__hash_size - 1){ _hash = 0 } else { _hash++ } } _hash } map__hash{ // ハッシュ関数 _key = _argv[0] _key_len = STRLEN(_key) _hash = 0 for _i = 1; _i < _key_len; _i++ { _hash = (_hash * 137 + CHRCODE(_key, _i)) % map__hash_size } _hash } * ハッシュ:引数渡しによる実装(おすすめ？) [#i2dc66e4] 巨大な引数渡しをする代わりに、自然なロジックと自然な変数のスコープを実現できる。 ** 利点 [#acf05691] - 自然なロジックで実装できる - ちゃんと連想配列がローカル変数である ** 欠点 [#o90d8cf7] - 巨大な引数渡しが遅そう(実用上そう気になるレベルではない気がする) - 操作が返り値を使うなどやや奇妙 ** 使用例 [#p9cef621] // map__hash_size = 2048 // 一連想配列に確保するハッシュ領域のサイズ 実行中一度決めたら変更しない _m = map_new() // 初期化して実体的な連想配列を取得 _m = map_set(_m, 'key', 'value') // 操作後の連想配列は返り値 _k = map_get(_m, 'key') _ks = map_keys(_m) _m = map_delete(_m, 'key') // 変数の開放は特に必要ない ** 実装 [#wb4a1f18] /* _map = map_new() 連想配列初期化 cf. map = {} */ map_new{ if ! ISVAR('map__hash_size') { map__hash_size = 2048 } IARRAY } /* _map = map_set(_map, _key, _value) 連想配列_mapの_keyに_valueをセットした連想配列を返す cf. map{key} = value */ map_set{ _key = _argv[_argc - 2] _value = _argv[_argc - 1] _argv[_argc - 2, _argc - 1] = IARRAY _hash = map__get_only_index(_argv, _key) _argv[_hash * 2] = _key _argv[_hash * 2 + 1] = _value _argv } /* _value = map_get(_map, _key) 連想配列_mapの_keyを参照 cf. value = map{key} */ map_get{ _key = _argv[_argc - 1] _argv[_argc - 1] = IARRAY _hash = map__get_only_index(_argv, _key) _argv[_hash * 2 + 1] } /* _map = map_delete(_map, _key) 連想配列_mapの_keyを削除した連想配列を返す cf. delete(map{key}) */ map_delete{ _key = _argv[_argc - 1] _argv[_argc - 1] = IARRAY _hash = map__get_only_index(_argv, _key) _argv[_hash * 2] = IVOID _argv[_hash * 2 + 1] = _IVOID _argv } /* _keys = map_keys(_map, _key) 連想配列_mapの_keyを列挙 cf. keys = keys(map{key}) */ map_keys{ _keys = IARRAY for _i = 0; _i < _argc / 2; _i ++ { _key = _argv[_i * 2] if _key != IVOID { _keys = (_keys, _key) } } _keys } map__get_only_index{ // 重複しないようインデックスをずらす _key = _argv[_argc - 1] _argv[_argc - 1] = IARRAY _hash = map__hash(_key) while (_argv[_hash * 2] != IVOID) && (_argv[_hash * 2] != _key) { if _hash >= (map__hash_size - 1){ _hash = 0 } else { _hash++ } } _hash } map__hash{ // ハッシュ関数 _key = _argv[0] _key_len = STRLEN(_key) _hash = 0 for _i = 1; _i < _key_len; _i++ { _hash = (_hash * 137 + CHRCODE(_key, _i)) % map__hash_size } _hash }
