JavaScript の Map でタプルをキーにしたい
- カテゴリ:
- JavaScript
- コメント数:
- Comments: 0
◆ 「値⇨文字列」変換するハッシュ関数を作って 実際は 1 つの文字列をキーに保存する
◆ イメージ: fn(1, 2)
◆ Map をネストさせて順番に取り出す
◆ イメージ: fn(1)(2)
◆ イメージ: fn(1, 2)
◆ Map をネストさせて順番に取り出す
◆ イメージ: fn(1)(2)
JavaScript で Map を使うときにタプルをキーにしたいってことありますよね
文字列しかキーにできないオブジェクトとは違って Map はキーに配列やオブジェクトも使えます
しかし JavaScript には正確にタプルというものはありません
のように配列をタプル風に使えるのですがあくまで配列です
なので
のように中身が一緒でも別物です
a と b に 2 つのデータを入れてその 2 値のタプルをキーとして map にランダム値をデータとして入れます
すでにそのタプルに対するデータがある場合はあるものを返して 同じ値になってほしいです
しかし 上記のように配列では別の参照なので
と (1, 2) のときに値が異なり map には 3 種類の値が入っています
配列を渡すとシンボルが返ってくるというのが理想ですが 「配列⇨シンボル」 の変換をハッシュのように瞬時に変換するのが難しいです
これができるなら その機能を Map 代わりにしてしまえば済みますし
総当たりで一致したものを返すような作りにはできますが 数が増えてくると重いですしあまりやりたい方法ではないです
なので ひとつひとつの値を文字列のハッシュ値に変換するというものを作ります
プリミティブ型はそのまま JSON.stringify を通して オブジェクト型はランダムな文字列にします
オブジェクト型の場合の作った文字列は Map に保存しておき同じオブジェクトなら保存してあるものを返します
今回作ろうとしてるものと同じですね
それぞれのデータを文字列化できるようになったので 次はタプルの扱い方です
実際はただの配列なので 半角スペース区切りで結合します
オブジェクト型のランダムな文字には半角スペースを含まず 文字列型はダブルクオートで囲まれるので 半角スペースでつなげても異なるものが一致することはないはずです
あとはキーをこの方法で作ったものに置き換えるだけです
もう少しいくつかキーのパターンを試します
この方法だとキーが文字列になるので Map でなくオブジェクトにすることも可能です
Map 自体をタプル対応にしたものです
イメージはこれに近いです
[1, 2] というタプルをキーにしたい場合は Map からまず 1 で値を取り出し 返ってくる Map から 2 を取り出します
ネストした Map ということです
ただ 単純にその構造するだけだと 操作が面倒なので 単純に使えるように Map の代わりにする TupleMap というのを作ってみました
ちょっと長いですが 後ろの方で使い方を書いているので具体的な中身に興味がなければ飛ばしておっけいです
使うときはこうなります
fn は最初のやりたいことのところに書いたコードと一緒です
タプルの 1 つめだけを指定した 関数の部分適用っぽいことができるので こんなこともできます
部分 Map を取得するには get の 2 つめの引数に true を指定する必要があります
キーが配列でなければ自動で配列するのでタプルでない ただの値なら [] の省略が可能です
ただし 見分けがつかないので配列単体をキーにしたい場合は [] が必要です
こっちの TupleMap のほうが高機能ですごそうな気もしますけど 内部でなんども Map を取得/作成するのでパフォーマンスは悪いと思います
それにネストしてて走査が手間だったので forEach 等は未実装です
get/set/has のみでほとんど WeakMap 程度の機能です
文字列しかキーにできないオブジェクトとは違って Map はキーに配列やオブジェクトも使えます
しかし JavaScript には正確にタプルというものはありません
const [x, y] = [1, 2]
console.log(x, y)
// 1 2
のように配列をタプル風に使えるのですがあくまで配列です
なので
;[1, 2] === [1, 2]
// false
のように中身が一緒でも別物です
やりたいこと
やりたいことはこういうことですconst map = new Map()
function fn(a, b) {
const key = [a, b]
if (map.has(key)) {
return map.get(key)
} else {
const value = Math.random()
map.set(key, value)
return value
}
}
a と b に 2 つのデータを入れてその 2 値のタプルをキーとして map にランダム値をデータとして入れます
すでにそのタプルに対するデータがある場合はあるものを返して 同じ値になってほしいです
しかし 上記のように配列では別の参照なので
fn(1, 2)
// 0.6594388366526296
fn(2, 3)
// 0.3087648937774141
fn(1, 2)
// 0.9877452630565369
// Map(3)
// 0: {Array(2) => 0.6594388366526296}
// 1: {Array(2) => 0.3087648937774141}
// 2: {Array(2) => 0.9877452630565369}
と (1, 2) のときに値が異なり map には 3 種類の値が入っています
方法 1 : オブジェクトハッシュ
タプルのような複数のデータをまとめたもので値が同じとみなす機能がないので 同じデータなら同じ値になる物を作ります配列を渡すとシンボルが返ってくるというのが理想ですが 「配列⇨シンボル」 の変換をハッシュのように瞬時に変換するのが難しいです
これができるなら その機能を Map 代わりにしてしまえば済みますし
総当たりで一致したものを返すような作りにはできますが 数が増えてくると重いですしあまりやりたい方法ではないです
なので ひとつひとつの値を文字列のハッシュ値に変換するというものを作ります
プリミティブ型はそのまま JSON.stringify を通して オブジェクト型はランダムな文字列にします
オブジェクト型の場合の作った文字列は Map に保存しておき同じオブジェクトなら保存してあるものを返します
今回作ろうとしてるものと同じですね
const object_hash = new WeakMap()
function toHash(value) {
if (value instanceof Object) {
if (object_hash.has(value)) {
return object_hash.get(value)
}
const hash = "H" + Date.now() + Math.random().toString(16)
object_hash.set(value, hash)
return hash
} else {
return JSON.stringify(value)
}
}
それぞれのデータを文字列化できるようになったので 次はタプルの扱い方です
実際はただの配列なので 半角スペース区切りで結合します
オブジェクト型のランダムな文字には半角スペースを含まず 文字列型はダブルクオートで囲まれるので 半角スペースでつなげても異なるものが一致することはないはずです
あとはキーをこの方法で作ったものに置き換えるだけです
const map = new Map()
function fn(a, b) {
const key = [a, b].map(toHash).join(" ")
if (map.has(key)) {
return map.get(key)
} else {
const value = Math.random()
map.set(key, value)
return value
}
}
fn(1, 2)
// 0.05375427963967594
fn(2, 3)
// 0.830083259217193
fn(1, 2)
// 0.05375427963967594
map
// Map(2) {"1 2" => 0.05375427963967594, "2 3" => 0.830083259217193}
もう少しいくつかキーのパターンを試します
fn("a", { a: 1 })
// 0.10295979815104284
fn("b", { b: 1 })
// 0.05500963580446072
fn("b", { a: 1 })
// 0.9048060198879411
fn("a", { b: 1 })
// 0.4493650098454389
const t = {}
fn("a", t)
// 0.013185157169169459
fn("a", t)
// 0.013185157169169459
map
// Map(7)
// 0: {"1 2" => 0.05375427963967594}
// 1: {"2 3" => 0.830083259217193}
// 2: {""a" H15236738499370.47358cff196c6" => 0.10295979815104284}
// 3: {""b" H15236738556320.d39e03f88f4d1" => 0.05500963580446072}
// 4: {""b" H15236738602010.f2d93a4edec94" => 0.9048060198879411}
// 5: {""a" H15236738636320.6eec26fee5f07" => 0.4493650098454389}
// 6: {""a" H15236738840360.58e0d15d6aeec" => 0.013185157169169459}
この方法だとキーが文字列になるので Map でなくオブジェクトにすることも可能です
方法 2 : TupleMap
別の方法も考えてみましたMap 自体をタプル対応にしたものです
イメージはこれに近いです
const x = a => b => a + b
x(1)(2)
[1, 2] というタプルをキーにしたい場合は Map からまず 1 で値を取り出し 返ってくる Map から 2 を取り出します
ネストした Map ということです
ただ 単純にその構造するだけだと 操作が面倒なので 単純に使えるように Map の代わりにする TupleMap というのを作ってみました
ちょっと長いですが 後ろの方で使い方を書いているので具体的な中身に興味がなければ飛ばしておっけいです
function TupleMap() {
this.map = new Map()
}
TupleMap.no_value = Symbol("novalue")
Object.assign(TupleMap.prototype, {
_fixTuple(tuple_arr) {
if (arguments.length === 0 || (Array.isArray(tuple_arr) && tuple_arr.length === 0)) {
throw new Error("Invalid arguments.")
}
return Array.isArray(tuple_arr) ? tuple_arr : [tuple_arr]
},
_initKey(key) {
this.map.set(key, { value: TupleMap.no_value, sub_tuple_map: new TupleMap() })
},
set(tuple_arr, value) {
const arr = this._fixTuple.apply(this, arguments)
if (!this.map.has(arr[0])) {
this._initKey(arr[0])
}
const data = this.map.get(arr[0])
if (arr.length === 1) {
data.value = value
} else {
data.sub_tuple_map.set(arr.slice(1), value)
}
},
get(tuple_arr, return_sub_tuple_map) {
const arr = this._fixTuple.apply(this, arguments)
if (!this.map.has(arr[0])) {
if (return_sub_tuple_map) {
this._initKey(arr[0])
} else {
return
}
}
const data = this.map.get(arr[0])
if (arr.length === 1) {
return data.value === TupleMap.no_value ? (return_sub_tuple_map ? data.sub_tuple_map : undefined) : data.value
} else {
return data.sub_tuple_map.get(arr.slice(1), return_sub_tuple_map)
}
},
has(tuple_arr) {
const arr = this._fixTuple.apply(this, arguments)
if (!this.map.has(arr[0])) {
return false
}
const data = this.map.get(arr[0])
if (arr.length === 1) {
return data.value !== TupleMap.no_value
} else {
return data.sub_tuple_map.has(arr.slice(1))
}
},
})
使うときはこうなります
fn は最初のやりたいことのところに書いたコードと一緒です
const map = new TupleMap()
function fn(a, b) {
const key = [a, b]
if (map.has(key)) {
return map.get(key)
} else {
const value = Math.random()
map.set(key, value)
return value
}
}
fn(1, 2)
// 0.32935602073723746
fn(2, 3)
// 0.9025675052861724
fn(1, 2)
// 0.32935602073723746
map
// Map(2)
// 0: {1 => Object}
// key: 1
// value: {value: Symbol(novalue), sub_tuple_map: TupleMap}
// value: Symbol(novalue)
// sub_tuple_map: TupleMap
// map: Map(1)
// 0: {2 => Object}
// key: 2
// value: {value: 0.32935602073723746, sub_tuple_map: TupleMap}
// value: 0.32935602073723746
// sub_tuple_map: TupleMap
// map: Map(0)
// 1: {2 => Object}
// key: 2
// value: {value: Symbol(novalue), sub_tuple_map: TupleMap}
// value: Symbol(novalue)
// sub_tuple_map: TupleMap
// map: Map(1)
// 0: {3 => Object}
// key: 3
// value: {value: 0.9025675052861724, sub_tuple_map: TupleMap}
// value: 0.9025675052861724
// sub_tuple_map: TupleMap
// map: Map(0)
タプルの 1 つめだけを指定した 関数の部分適用っぽいことができるので こんなこともできます
const tmap = new TupleMap()
const t = {}
tmap.set([1, t, "a"], 100)
tmap.set([1, t, "b"], 200)
tmap.set([1, t, true, false], 300)
const subtmap = tmap.get([1, t], true)
subtmap.get(["a"])
// 100
subtmap.get(["b"])
// 200
subtmap.get([true, false])
// 300
subtmap.set(["x", "y"], 500)
tmap.get([1, t, "x", "y"])
// 500
subtmap.get([10], true).get(20, true).get(30, true).set(40, 600)
tmap.get([1, t, 10, 20, 30, 40])
// 600
部分 Map を取得するには get の 2 つめの引数に true を指定する必要があります
キーが配列でなければ自動で配列するのでタプルでない ただの値なら [] の省略が可能です
ただし 見分けがつかないので配列単体をキーにしたい場合は [] が必要です
こっちの TupleMap のほうが高機能ですごそうな気もしますけど 内部でなんども Map を取得/作成するのでパフォーマンスは悪いと思います
それにネストしてて走査が手間だったので forEach 等は未実装です
get/set/has のみでほとんど WeakMap 程度の機能です