Javascript 记忆查找数组
Javascript memoize find array
我正在努力提高我在 javascript 中关于记忆的知识。我创建了一个记忆功能（我认为..）
我对项目进行了一系列更改（更改日志）。数组中的每个项目都包含一个对其进行编辑的引用 ID(employeeId)。看起来像这样。
const changeLog = [
{
id: 1,
employeeId: 1,
field: 'someField',
oldValue: '0',
newValue: '100',
},
{
id: 2,
employeeId: 2,
field: 'anotherField',
oldValue: '20',
newValue: '100',
},
...
]
我还有一个包含每个员工的数组，看起来像这样：
const employees = [
{
name: 'Joel Abero',
id: 1
},
{
name: 'John Doe',
id: 2
},
{
name: 'Dear John',
id: 3
}
]
为了找到做出更改的员工，我映射了 changeLog 中的每个项目，并在 employees-array 中找到 employeeId 等于 id 的位置。
这两个数组都包含 500 多个项目，我只是粘贴了片段。
下面我粘贴了我的 memoize 助手。
1) 我如何进行测试以查看这两个 运行 中哪一个最快？
2) 这是使用记忆的正确方法吗？
3) 何时使用记忆有经验法则吗？还是我应该尽可能多地使用它？
const employees = [
{
name: 'Joel Abero',
id: 1
},
{
name: 'John Doe',
id: 2
},
{
name: 'Dear John',
id: 3
}
]
const changeLog = [
{
id: 1,
employeeId: 1,
field: 'someField',
oldValue: '0',
newValue: '100',
},
{
id: 2,
employeeId: 2,
field: 'anotherField',
oldValue: '0',
newValue: '100',
},
{
id: 3,
employeeId: 3,
field: 'someField',
oldValue: '0',
newValue: '100',
},
{
id: 4,
employeeId: 3,
field: 'someField',
oldValue: '0',
newValue: '100',
},
{
id: 5,
employeeId: 3,
field: 'someField',
oldValue: '0',
newValue: '100',
}
]
function findEditedByEmployee (employeeId) {
return employees.find(({ id }) => id === employeeId)
}
function editedByWithMemoize () {
let employeesSavedInMemory = {}
return function(employeeId) {
if(employeeId in employeesSavedInMemory) {
console.log("from memory")
return employeesSavedInMemory[employeeId]
}
console.log("not from memory")
const findEditedBy = findEditedByEmployee(employeeId)
employeesSavedInMemory[findEditedBy.id] = {name: findEditedBy.name }
return findEditedBy
}
}
const memoizedEmployee = editedByWithMemoize();
// with memoization
const changeLogWithEmployeesMemoized = changeLog.map( log => {
const employeeName = memoizedEmployee(log.employeeId);
return {
...log,
employeeName: employeeName.name
}
})
// without memoization
const changeLogWithEmployees = changeLog.map( log => {
const editedBy = findEditedByEmployee(log.employeeId);
return {
...log,
employeeName: editedBy.name
}
})
console.log('memoized', changeLogWithEmployeesMemoized)
console.log('not memoized', changeLogWithEmployees)
我会提前创建一个 Map 并从地图中获取对象进行更新。
如果 map 不包含想要的 id，创建一个新对象并将其添加到 employees 和 map.
const
employees = [{ name: 'Joel Abero', id: 1 }, { name: 'John Doe', id: 2 }, { name: 'Dear John', id: 3 }],
changeLog = [{ id: 1, employeeId: 1, field: 'someField', oldValue: '0', newValue: '100' }, { id: 2, employeeId: 2, field: 'anotherField', oldValue: '20', newValue: '100' }],
map = employees.reduce((map, o) => map.set(o.id, o), new Map);
for (const { id, field, newValue } of changeLog) {
let object = map.get(id);
if (object) {
object[field] = newValue;
} else {
let temp = { id, [field]: newValue };
employees.push(temp)
map.set(id, temp);
}
}
console.log(employees);
.as-console-wrapper { max-height: 100% !important; top: 0; }
我会尽量回答你的每一个问题：
1) How can I perform a test to see which of these two run the fastest?
最好的方法就是一个简单的 for 循环。以一个假的 API 请求为例：
const fakeAPIRequest = id => new Promise(r => setTimeout(r, 100, {id}))
根据要求，这需要 100 毫秒才能完成。使用记忆化，我们可以通过检查之前是否发出过此请求来避免发出此 100 毫秒的请求：
const cache = {}
const memoizedRequest = async (id) => {
if (id in cache) return Promise.resolve(cache[id])
return cache[id] = await fakeAPIRequest(id)
}
这是一个工作示例：
const fakeAPIRequest = id => new Promise(r => setTimeout(r, 100, {id}))
const cache = {}
const memoizedRequest = async (id) => {
if (id in cache) return Promise.resolve(cache[id])
return cache[id] = await fakeAPIRequest(id)
}
const request = async (id) => await fakeAPIRequest(id)
const test = async (name, cb) => {
console.time(name)
for (let i = 50; i--;) {
await cb()
}
console.timeEnd(name)
}
test('memoized', async () => await memoizedRequest('test'))
test('normal', async () => await request('test'))
2) Is this a proper way to use memoization?
我不完全确定您的意思，但可以将其视为短期缓存。
如果你的 memo 调用包含一个 API 请求，这对于不变的数据可能很好，节省了大量时间，但另一方面，如果数据在短时间内可能发生变化，那么 memoization可能是个坏主意，这意味着它很快就会过时。
如果您多次调用此函数，它可能会占用内存，具体取决于 return 数据的大小，但这个因素取决于实现，而不是 "a proper way".
3) Is there a rule of thumb when to use memoization? Or should I use it as often as I can?
通常情况下，记忆是矫枉过正的——因为计算机速度非常快，它通常可以归结为只节省几毫秒——如果你只调用函数几次，记忆几乎没有什么好处。但我一直在强调 API 请求，这可能需要很长时间。如果你开始使用记忆函数，你应该尽可能在任何地方使用它。但是，如前所述，它可以根据 return 数据快速耗尽内存。
关于记忆的最后一点是，如果数据已经在客户端，使用像 建议的地图绝对是一种更好、更有效的方法。它不是每次都循环查找对象，而是循环一次将数组转换为对象（或映射），从而允许您在 O(1) 时间内访问数据。举个例子，这次用find代替我之前做的fakeAPI函数：
const data = [{"id":0},{"id":1},{"id":2},{"id":3},{"id":4},{"id":5},{"id":6},{"id":7},{"id":8},{"id":9},{"id":10},{"id":11},{"id":12},{"id":13},{"id":14},{"id":15},{"id":16},{"id":17},{"id":18},{"id":19},{"id":20},{"id":21},{"id":22},{"id":23},{"id":24},{"id":25},{"id":26},{"id":27},{"id":28},{"id":29},{"id":30},{"id":31},{"id":32},{"id":33},{"id":34},{"id":35},{"id":36},{"id":37},{"id":38},{"id":39},{"id":40},{"id":41},{"id":42},{"id":43},{"id":44},{"id":45},{"id":46},{"id":47},{"id":48},{"id":49},{"id":50},{"id":51},{"id":52},{"id":53},{"id":54},{"id":55},{"id":56},{"id":57},{"id":58},{"id":59},{"id":60},{"id":61},{"id":62},{"id":63},{"id":64},{"id":65},{"id":66},{"id":67},{"id":68},{"id":69},{"id":70},{"id":71},{"id":72},{"id":73},{"id":74},{"id":75},{"id":76},{"id":77},{"id":78},{"id":79},{"id":80},{"id":81},{"id":82},{"id":83},{"id":84},{"id":85},{"id":86},{"id":87},{"id":88},{"id":89},{"id":90},{"id":91},{"id":92},{"id":93},{"id":94},{"id":95},{"id":96},{"id":97},{"id":98},{"id":99}]
const cache = {}
const findObject = id => data.find(o => o.id === id)
const memoizedFindObject = id => id in cache ? cache[id] : cache[id] = findObject(id)
const map = new Map(data.map(o => [o.id, o]))
const findObjectByMap = id => map.get(id)
const list = Array(50000).fill(0).map(() => Math.floor(Math.random() * 100))
const test = (name, cb) => {
console.time(name)
for (let i = 50000; i--;) {
cb(list[i])
}
console.timeEnd(name)
}
test('memoized', memoizedFindObject)
test('normal', findObject)
test('map', findObjectByMap)
总而言之，memoization 是一个很棒的工具，与缓存非常相似。它在繁重的计算或长时间的网络请求时提供了很大的加速，但如果不经常使用它可能会证明无效。
你的记忆过程有问题！
你没有 return 个形状相同的对象
当您没有在缓存中找到员工时，您会查找它并return整个对象，但是，你只记住了对象的一部分：
employeesSavedInMemory[findEditedBy.id] = {name: findEditedBy.name }
因此，当您在缓存中找到员工时，您 return 数据的简化版本：
const employees = [ { name: 'Joel Abero', id: 1 }, { name: 'John Doe', id: 2 }, { name: 'Dear John', id: 3 } ]
function findEditedByEmployee (employeeId) {
return employees.find(({ id }) => id === employeeId)
}
function editedByWithMemoize () {
let employeesSavedInMemory = {}
return function(employeeId) {
if(employeeId in employeesSavedInMemory) {
console.log("from memory")
return employeesSavedInMemory[employeeId]
}
console.log("not from memory")
const findEditedBy = findEditedByEmployee(employeeId)
employeesSavedInMemory[findEditedBy.id] = {name: findEditedBy.name }
return findEditedBy
}
}
const memoizedEmployee = editedByWithMemoize();
const found = memoizedEmployee(1);
const fromCache = memoizedEmployee(1);
console.log("found:", found); //id + name
console.log("fromCache:", fromCache);//name
当使用相同的参数调用相同的函数时，您得到 不同的数据。
你没有return相同的对象
另一个大问题是你创建了一个新对象——即使你改变得到一个complete副本，memoization 也不是t运行sparent:
const employees = [ { name: 'Joel Abero', id: 1 }, { name: 'John Doe', id: 2 }, { name: 'Dear John', id: 3 } ]
function findEditedByEmployee (employeeId) {
return employees.find(({ id }) => id === employeeId)
}
function editedByWithMemoize () {
let employeesSavedInMemory = {}
return function(employeeId) {
if(employeeId in employeesSavedInMemory) {
console.log("from memory")
return employeesSavedInMemory[employeeId]
}
console.log("not from memory")
const findEditedBy = findEditedByEmployee(employeeId)
employeesSavedInMemory[findEditedBy.id] = { ...findEditedBy } //make a copy of all object properties
return findEditedBy
}
}
const memoizedEmployee = editedByWithMemoize();
memoizedEmployee(1)
const found = memoizedEmployee(1);
const fromCache = memoizedEmployee(1);
console.log("found:", found); //id + name
console.log("fromCache:", fromCache); //id + name
console.log("found === fromCache :", found === fromCache); // false
结果与您获得的 "different" 数据基本相同，因为对象不同。因此，例如，如果您这样做：
const employees = [ { name: 'Joel Abero', id: 1 }, { name: 'John Doe', id: 2 }, { name: 'Dear John', id: 3 } ]
function findEditedByEmployee (employeeId) {
return employees.find(({ id }) => id === employeeId)
}
function editedByWithMemoize () {
let employeesSavedInMemory = {}
return function(employeeId) {
if(employeeId in employeesSavedInMemory) {
console.log("from memory")
return employeesSavedInMemory[employeeId]
}
console.log("not from memory")
const findEditedBy = findEditedByEmployee(employeeId)
employeesSavedInMemory[findEditedBy.id] = { ...findEditedBy } //make a copy of all object properties
return findEditedBy
}
}
const memoizedEmployee = editedByWithMemoize();
const original = employees[0];
const found = memoizedEmployee(1);
found.foo = "hello";
console.log("found:", found); //id + name + foo
const fromCache = memoizedEmployee(1);
console.log("fromCache 1:", fromCache); //id + name
fromCache.bar = "world";
console.log("fromCache 2:", fromCache); //id + name + bar
console.log("original:", original); //id + name + foo
与正常实施比较
我会用memoize from Lodash，但还有很多其他的通用实现，它们仍然以相同的方式工作，所以这仅供参考：
const { memoize } = _;
const employees = [ { name: 'Joel Abero', id: 1 }, { name: 'John Doe', id: 2 }, { name: 'Dear John', id: 3 } ]
function findEditedByEmployee (employeeId) {
return employees.find(({ id }) => id === employeeId)
}
const memoizedEmployee = memoize(findEditedByEmployee);
const original = employees[0];
const found = memoizedEmployee(1);
console.log("found 1:", found); //id + name
found.foo = "hello";
console.log("found 2:", found); //id + name + foo
const fromCache = memoizedEmployee(1);
console.log("fromCache 1:", fromCache); //id + name + foo
fromCache.bar = "world";
console.log("fromCache 2:", fromCache); //id + name + foo + bar
console.log("original:", original); //id + name + foo + bar
console.log("found === fromCache :", found === fromCache); //true
<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.15/lodash.min.js"></script>
只是证明记忆是完全透明的 运行 并且不会产生任何奇怪或不寻常的行为。使用memoized函数完全和普通函数在效果上是一样的。唯一的区别是缓存，但对函数的行为没有影响。
进入实际问题：
How can I perform a test to see which of these two run the fastest?
老实说，就个人而言 - 你不应该。记忆化的正确实现具有已知属性。线性搜索也有已知的属性。因此，速度测试就是测试两种算法的两个已知属性。
让我们在这里深入探讨纯逻辑 - 我们需要考虑两件事：
- 实现是正确的（让我们称之为P）
- 实现的属性是正确的（我们称之为 Q）
我们可以肯定地说 "If the implementation is correct, then properties of implementation are correct"，运行 可以变成 "if P, then Q" 或正式地 P -> Q。如果我们朝相反的方向 Q -> P 并尝试测试已知属性以确认实现是否正确，那么我们就犯了 affirming the consequent.
的谬误
我们确实可以观察到测试速度甚至没有测试解决方案的正确性。您可以 不正确 实现记忆化，但它会表现出与 O(n) 一次查找和 O(1) 重复读取相同的速度 属性 作为正确的记忆化。因此，测试 Q -> P 将失败。
相反，您应该测试 实现 的正确性，如果您能证明这一点，那么您可以推断出重复读取的速度是恒定的。 O(1) 访问将比 O(n) 查找更快（在大多数情况下，尤其是这个）。
因此，如果您不需要证明正确性，那么您可以把剩下的留给g运行ted。如果您使用已知的记忆实现，则无需测试您的库。
综上所述，是您可能仍需要注意的事项。记忆期间的缓存依赖于为缓存项创建正确的 key。根据密钥的派生方式，这可能会产生很大的（即使是恒定的）开销成本。因此，例如，查找数组开头附近的内容可能需要 10ms，但为缓存创建密钥可能需要 15ms，这意味着 O(1) 将是 [=136] =]慢。比 一些 案例慢。
验证速度的正确测试通常是检查（平均）查找数组中的第一项、数组中的最后一项、数组中间的某项所花费的时间，然后检查从缓存中获取内容需要多少时间。每一个都必须 运行 多次，以确保您不会获得 运行dom 速度峰值，无论是上升还是下降。
不过我以后还有话要说*
2) Is this a proper way to use memoization?
是的。同样，假设正确实施，这就是您的做法 - 记忆一个函数，然后您会从缓存中获得很多好处。
话虽如此，您可以从 Lodash 实现中看出，您可以将记忆化实现概括化并将其应用于 any 函数，而不是编写每个函数的记忆化版本。这是一个很大的好处，因为您只需要测试一个记忆功能。相反，如果您有类似 findEmployee()、findDepartment() 和 findAddress() 的函数，您想要缓存其结果，那么您需要测试 each 记忆化实施。
3) Is there a rule of thumb when to use memoization? Or should I use it as often as I can?
是的，您应该尽可能多地使用它*（有一个巨大的星号）
*（大星号）
这是我知道如何使用 markdown 制作的最大星号（除了嵌入图像之外）。我可以买稍微大一点的，可惜。
您必须确定何时可以使用它，以便在可以使用的时候使用它。我并不是说这会让人感到困惑——你不应该到处乱用记忆函数。在 种情况下您无法使用它们。这就是我在回答第一个问题的最后提到的 - 我想在一个地方谈论这个：
您必须非常小心地验证您的实际用法。如果数组中有 100 万个项目，并且只有前 10 个项目的查找速度比从缓存中获取的速度快，那么有 0.001% 的项目不会从缓存中受益。在那种情况下 - 你会从缓存中获益......或者你呢？如果您只对每个项目进行几次读取，并且您只查找不到四分之一的项目，那么缓存可能不会给您带来长期的好处。如果您恰好将每个项目查找两次，那么您的内存消耗就会 加倍 老实说，整体速度的提高非常微不足道。然而，如果您不是从数组中进行内存中查找，而是进行网络请求（例如，数据库读取）之类的操作，该怎么办？在那种情况下，即使是单次使用的缓存也可能非常有价值。
您可以看到一个细节是如何摇摆不定的，无论您是否应该使用记忆。很多时候，当您最初编写应用程序时甚至都不是那么清楚，因为您甚至不知道最终调用函数的频率、为它提供的值以及调用它的频率一遍又一遍地使用相同的值。即使您知道典型用法可能是什么，您仍然需要一个真实的环境来进行测试，而不是仅仅单独调用函数的非记忆化和记忆化版本。
Eric Lippert has an an amazing piece on performance testing 这主要归结为 - 当性能很重要时，尝试使用真实数据和真实使用情况测试真实应用程序。否则你的基准可能会因为各种原因而关闭。
即使 memoization 显然是 "faster" 你也必须考虑内存使用情况。这是一个有点愚蠢的例子来说明 memoization 消耗了比必要更多的内存：
const { memoize } = _;
//stupid recursive function that removes 1 from `b` and
//adds 1 to `a` until it finds the total sum of the two
function sum (a, b) {
if(b)
return sum(a + 1, b - 1)
//only log once to avoid spamming the logs but show if it's called or not
console.log("sum() finished");
return a;
}
//memoize the function
sum = memoize(sum);
const result = sum(1, 999);
console.log("result:", result);
const resultFromCache1 = sum(1, 999); //no logs as it's cached
console.log("resultFromCache1:", resultFromCache1);
const resultFromCache2 = sum(999, 1); //no logs as it's cached
console.log("resultFromCache2:", resultFromCache2);
const resultFromCache3 = sum(450, 550); //no logs as it's cached
console.log("resultFromCache3:", resultFromCache3);
const resultFromCache4 = sum(42, 958); //no logs as it's cached
console.log("resultFromCache4:", resultFromCache4);
<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.15/lodash.min.js"></script>
这会将一千个缓存结果放入内存。是的，memoized 函数很傻，做了很多不必要的调用，这意味着有很多内存开销。但与此同时，如果我们用 总和为 1000 的任何参数重新调用它，那么我们会立即得到结果，而无需进行任何递归。
即使不涉及递归，您也可以轻松拥有相似的真实代码 - 您最终可能会使用大量不同的输入多次调用某个函数。这将用所有结果填充缓存，但它是否有用仍然悬而未决。
因此，如果您可以，您应该使用记忆。最大的问题是找出 如果 可以。
我正在努力提高我在 javascript 中关于记忆的知识。我创建了一个记忆功能（我认为..）
我对项目进行了一系列更改（更改日志）。数组中的每个项目都包含一个对其进行编辑的引用 ID(employeeId)。看起来像这样。
const changeLog = [
{
id: 1,
employeeId: 1,
field: 'someField',
oldValue: '0',
newValue: '100',
},
{
id: 2,
employeeId: 2,
field: 'anotherField',
oldValue: '20',
newValue: '100',
},
...
]
我还有一个包含每个员工的数组，看起来像这样：
const employees = [
{
name: 'Joel Abero',
id: 1
},
{
name: 'John Doe',
id: 2
},
{
name: 'Dear John',
id: 3
}
]
为了找到做出更改的员工，我映射了 changeLog 中的每个项目，并在 employees-array 中找到 employeeId 等于 id 的位置。 这两个数组都包含 500 多个项目，我只是粘贴了片段。 下面我粘贴了我的 memoize 助手。
1) 我如何进行测试以查看这两个 运行 中哪一个最快？
2) 这是使用记忆的正确方法吗？
3) 何时使用记忆有经验法则吗？还是我应该尽可能多地使用它？
const employees = [
{
name: 'Joel Abero',
id: 1
},
{
name: 'John Doe',
id: 2
},
{
name: 'Dear John',
id: 3
}
]
const changeLog = [
{
id: 1,
employeeId: 1,
field: 'someField',
oldValue: '0',
newValue: '100',
},
{
id: 2,
employeeId: 2,
field: 'anotherField',
oldValue: '0',
newValue: '100',
},
{
id: 3,
employeeId: 3,
field: 'someField',
oldValue: '0',
newValue: '100',
},
{
id: 4,
employeeId: 3,
field: 'someField',
oldValue: '0',
newValue: '100',
},
{
id: 5,
employeeId: 3,
field: 'someField',
oldValue: '0',
newValue: '100',
}
]
function findEditedByEmployee (employeeId) {
return employees.find(({ id }) => id === employeeId)
}
function editedByWithMemoize () {
let employeesSavedInMemory = {}
return function(employeeId) {
if(employeeId in employeesSavedInMemory) {
console.log("from memory")
return employeesSavedInMemory[employeeId]
}
console.log("not from memory")
const findEditedBy = findEditedByEmployee(employeeId)
employeesSavedInMemory[findEditedBy.id] = {name: findEditedBy.name }
return findEditedBy
}
}
const memoizedEmployee = editedByWithMemoize();
// with memoization
const changeLogWithEmployeesMemoized = changeLog.map( log => {
const employeeName = memoizedEmployee(log.employeeId);
return {
...log,
employeeName: employeeName.name
}
})
// without memoization
const changeLogWithEmployees = changeLog.map( log => {
const editedBy = findEditedByEmployee(log.employeeId);
return {
...log,
employeeName: editedBy.name
}
})
console.log('memoized', changeLogWithEmployeesMemoized)
console.log('not memoized', changeLogWithEmployees)
我会提前创建一个 Map 并从地图中获取对象进行更新。
如果 map 不包含想要的 id，创建一个新对象并将其添加到 employees 和 map.
const
employees = [{ name: 'Joel Abero', id: 1 }, { name: 'John Doe', id: 2 }, { name: 'Dear John', id: 3 }],
changeLog = [{ id: 1, employeeId: 1, field: 'someField', oldValue: '0', newValue: '100' }, { id: 2, employeeId: 2, field: 'anotherField', oldValue: '20', newValue: '100' }],
map = employees.reduce((map, o) => map.set(o.id, o), new Map);
for (const { id, field, newValue } of changeLog) {
let object = map.get(id);
if (object) {
object[field] = newValue;
} else {
let temp = { id, [field]: newValue };
employees.push(temp)
map.set(id, temp);
}
}
console.log(employees);
.as-console-wrapper { max-height: 100% !important; top: 0; }
我会尽量回答你的每一个问题：
1) How can I perform a test to see which of these two run the fastest?
最好的方法就是一个简单的 for 循环。以一个假的 API 请求为例：
const fakeAPIRequest = id => new Promise(r => setTimeout(r, 100, {id}))
根据要求，这需要 100 毫秒才能完成。使用记忆化，我们可以通过检查之前是否发出过此请求来避免发出此 100 毫秒的请求：
const cache = {}
const memoizedRequest = async (id) => {
if (id in cache) return Promise.resolve(cache[id])
return cache[id] = await fakeAPIRequest(id)
}
这是一个工作示例：
const fakeAPIRequest = id => new Promise(r => setTimeout(r, 100, {id}))
const cache = {}
const memoizedRequest = async (id) => {
if (id in cache) return Promise.resolve(cache[id])
return cache[id] = await fakeAPIRequest(id)
}
const request = async (id) => await fakeAPIRequest(id)
const test = async (name, cb) => {
console.time(name)
for (let i = 50; i--;) {
await cb()
}
console.timeEnd(name)
}
test('memoized', async () => await memoizedRequest('test'))
test('normal', async () => await request('test'))
2) Is this a proper way to use memoization?
我不完全确定您的意思，但可以将其视为短期缓存。 如果你的 memo 调用包含一个 API 请求，这对于不变的数据可能很好，节省了大量时间，但另一方面，如果数据在短时间内可能发生变化，那么 memoization可能是个坏主意，这意味着它很快就会过时。
如果您多次调用此函数，它可能会占用内存，具体取决于 return 数据的大小，但这个因素取决于实现，而不是 "a proper way".
3) Is there a rule of thumb when to use memoization? Or should I use it as often as I can?
通常情况下，记忆是矫枉过正的——因为计算机速度非常快，它通常可以归结为只节省几毫秒——如果你只调用函数几次，记忆几乎没有什么好处。但我一直在强调 API 请求，这可能需要很长时间。如果你开始使用记忆函数，你应该尽可能在任何地方使用它。但是，如前所述，它可以根据 return 数据快速耗尽内存。
关于记忆的最后一点是，如果数据已经在客户端，使用像 find代替我之前做的fakeAPI函数：
const data = [{"id":0},{"id":1},{"id":2},{"id":3},{"id":4},{"id":5},{"id":6},{"id":7},{"id":8},{"id":9},{"id":10},{"id":11},{"id":12},{"id":13},{"id":14},{"id":15},{"id":16},{"id":17},{"id":18},{"id":19},{"id":20},{"id":21},{"id":22},{"id":23},{"id":24},{"id":25},{"id":26},{"id":27},{"id":28},{"id":29},{"id":30},{"id":31},{"id":32},{"id":33},{"id":34},{"id":35},{"id":36},{"id":37},{"id":38},{"id":39},{"id":40},{"id":41},{"id":42},{"id":43},{"id":44},{"id":45},{"id":46},{"id":47},{"id":48},{"id":49},{"id":50},{"id":51},{"id":52},{"id":53},{"id":54},{"id":55},{"id":56},{"id":57},{"id":58},{"id":59},{"id":60},{"id":61},{"id":62},{"id":63},{"id":64},{"id":65},{"id":66},{"id":67},{"id":68},{"id":69},{"id":70},{"id":71},{"id":72},{"id":73},{"id":74},{"id":75},{"id":76},{"id":77},{"id":78},{"id":79},{"id":80},{"id":81},{"id":82},{"id":83},{"id":84},{"id":85},{"id":86},{"id":87},{"id":88},{"id":89},{"id":90},{"id":91},{"id":92},{"id":93},{"id":94},{"id":95},{"id":96},{"id":97},{"id":98},{"id":99}]
const cache = {}
const findObject = id => data.find(o => o.id === id)
const memoizedFindObject = id => id in cache ? cache[id] : cache[id] = findObject(id)
const map = new Map(data.map(o => [o.id, o]))
const findObjectByMap = id => map.get(id)
const list = Array(50000).fill(0).map(() => Math.floor(Math.random() * 100))
const test = (name, cb) => {
console.time(name)
for (let i = 50000; i--;) {
cb(list[i])
}
console.timeEnd(name)
}
test('memoized', memoizedFindObject)
test('normal', findObject)
test('map', findObjectByMap)
总而言之，memoization 是一个很棒的工具，与缓存非常相似。它在繁重的计算或长时间的网络请求时提供了很大的加速，但如果不经常使用它可能会证明无效。
你的记忆过程有问题！
你没有 return 个形状相同的对象
当您没有在缓存中找到员工时，您会查找它并return整个对象，但是，你只记住了对象的一部分：
employeesSavedInMemory[findEditedBy.id] = {name: findEditedBy.name }
因此，当您在缓存中找到员工时，您 return 数据的简化版本：
const employees = [ { name: 'Joel Abero', id: 1 }, { name: 'John Doe', id: 2 }, { name: 'Dear John', id: 3 } ]
function findEditedByEmployee (employeeId) {
return employees.find(({ id }) => id === employeeId)
}
function editedByWithMemoize () {
let employeesSavedInMemory = {}
return function(employeeId) {
if(employeeId in employeesSavedInMemory) {
console.log("from memory")
return employeesSavedInMemory[employeeId]
}
console.log("not from memory")
const findEditedBy = findEditedByEmployee(employeeId)
employeesSavedInMemory[findEditedBy.id] = {name: findEditedBy.name }
return findEditedBy
}
}
const memoizedEmployee = editedByWithMemoize();
const found = memoizedEmployee(1);
const fromCache = memoizedEmployee(1);
console.log("found:", found); //id + name
console.log("fromCache:", fromCache);//name
当使用相同的参数调用相同的函数时，您得到 不同的数据。
你没有return相同的对象
另一个大问题是你创建了一个新对象——即使你改变得到一个complete副本，memoization 也不是t运行sparent:
const employees = [ { name: 'Joel Abero', id: 1 }, { name: 'John Doe', id: 2 }, { name: 'Dear John', id: 3 } ]
function findEditedByEmployee (employeeId) {
return employees.find(({ id }) => id === employeeId)
}
function editedByWithMemoize () {
let employeesSavedInMemory = {}
return function(employeeId) {
if(employeeId in employeesSavedInMemory) {
console.log("from memory")
return employeesSavedInMemory[employeeId]
}
console.log("not from memory")
const findEditedBy = findEditedByEmployee(employeeId)
employeesSavedInMemory[findEditedBy.id] = { ...findEditedBy } //make a copy of all object properties
return findEditedBy
}
}
const memoizedEmployee = editedByWithMemoize();
memoizedEmployee(1)
const found = memoizedEmployee(1);
const fromCache = memoizedEmployee(1);
console.log("found:", found); //id + name
console.log("fromCache:", fromCache); //id + name
console.log("found === fromCache :", found === fromCache); // false
结果与您获得的 "different" 数据基本相同，因为对象不同。因此，例如，如果您这样做：
const employees = [ { name: 'Joel Abero', id: 1 }, { name: 'John Doe', id: 2 }, { name: 'Dear John', id: 3 } ]
function findEditedByEmployee (employeeId) {
return employees.find(({ id }) => id === employeeId)
}
function editedByWithMemoize () {
let employeesSavedInMemory = {}
return function(employeeId) {
if(employeeId in employeesSavedInMemory) {
console.log("from memory")
return employeesSavedInMemory[employeeId]
}
console.log("not from memory")
const findEditedBy = findEditedByEmployee(employeeId)
employeesSavedInMemory[findEditedBy.id] = { ...findEditedBy } //make a copy of all object properties
return findEditedBy
}
}
const memoizedEmployee = editedByWithMemoize();
const original = employees[0];
const found = memoizedEmployee(1);
found.foo = "hello";
console.log("found:", found); //id + name + foo
const fromCache = memoizedEmployee(1);
console.log("fromCache 1:", fromCache); //id + name
fromCache.bar = "world";
console.log("fromCache 2:", fromCache); //id + name + bar
console.log("original:", original); //id + name + foo
与正常实施比较
我会用memoize from Lodash，但还有很多其他的通用实现，它们仍然以相同的方式工作，所以这仅供参考：
const { memoize } = _;
const employees = [ { name: 'Joel Abero', id: 1 }, { name: 'John Doe', id: 2 }, { name: 'Dear John', id: 3 } ]
function findEditedByEmployee (employeeId) {
return employees.find(({ id }) => id === employeeId)
}
const memoizedEmployee = memoize(findEditedByEmployee);
const original = employees[0];
const found = memoizedEmployee(1);
console.log("found 1:", found); //id + name
found.foo = "hello";
console.log("found 2:", found); //id + name + foo
const fromCache = memoizedEmployee(1);
console.log("fromCache 1:", fromCache); //id + name + foo
fromCache.bar = "world";
console.log("fromCache 2:", fromCache); //id + name + foo + bar
console.log("original:", original); //id + name + foo + bar
console.log("found === fromCache :", found === fromCache); //true
<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.15/lodash.min.js"></script>
只是证明记忆是完全透明的 运行 并且不会产生任何奇怪或不寻常的行为。使用memoized函数完全和普通函数在效果上是一样的。唯一的区别是缓存，但对函数的行为没有影响。
进入实际问题：
How can I perform a test to see which of these two run the fastest?
老实说，就个人而言 - 你不应该。记忆化的正确实现具有已知属性。线性搜索也有已知的属性。因此，速度测试就是测试两种算法的两个已知属性。
让我们在这里深入探讨纯逻辑 - 我们需要考虑两件事：
- 实现是正确的（让我们称之为P）
- 实现的属性是正确的（我们称之为 Q）
我们可以肯定地说 "If the implementation is correct, then properties of implementation are correct"，运行 可以变成 "if P, then Q" 或正式地 P -> Q。如果我们朝相反的方向 Q -> P 并尝试测试已知属性以确认实现是否正确，那么我们就犯了 affirming the consequent.
我们确实可以观察到测试速度甚至没有测试解决方案的正确性。您可以 不正确 实现记忆化，但它会表现出与 O(n) 一次查找和 O(1) 重复读取相同的速度 属性 作为正确的记忆化。因此，测试 Q -> P 将失败。
相反，您应该测试 实现 的正确性，如果您能证明这一点，那么您可以推断出重复读取的速度是恒定的。 O(1) 访问将比 O(n) 查找更快（在大多数情况下，尤其是这个）。
因此，如果您不需要证明正确性，那么您可以把剩下的留给g运行ted。如果您使用已知的记忆实现，则无需测试您的库。
综上所述，是您可能仍需要注意的事项。记忆期间的缓存依赖于为缓存项创建正确的 key。根据密钥的派生方式，这可能会产生很大的（即使是恒定的）开销成本。因此，例如，查找数组开头附近的内容可能需要 10ms，但为缓存创建密钥可能需要 15ms，这意味着 O(1) 将是 [=136] =]慢。比 一些 案例慢。
验证速度的正确测试通常是检查（平均）查找数组中的第一项、数组中的最后一项、数组中间的某项所花费的时间，然后检查从缓存中获取内容需要多少时间。每一个都必须 运行 多次，以确保您不会获得 运行dom 速度峰值，无论是上升还是下降。
不过我以后还有话要说*
2) Is this a proper way to use memoization?
是的。同样，假设正确实施，这就是您的做法 - 记忆一个函数，然后您会从缓存中获得很多好处。
话虽如此，您可以从 Lodash 实现中看出，您可以将记忆化实现概括化并将其应用于 any 函数，而不是编写每个函数的记忆化版本。这是一个很大的好处，因为您只需要测试一个记忆功能。相反，如果您有类似 findEmployee()、findDepartment() 和 findAddress() 的函数，您想要缓存其结果，那么您需要测试 each 记忆化实施。
3) Is there a rule of thumb when to use memoization? Or should I use it as often as I can?
是的，您应该尽可能多地使用它*（有一个巨大的星号）
*（大星号）
这是我知道如何使用 markdown 制作的最大星号（除了嵌入图像之外）。我可以买稍微大一点的，可惜。
您必须确定何时可以使用它，以便在可以使用的时候使用它。我并不是说这会让人感到困惑——你不应该到处乱用记忆函数。在 种情况下您无法使用它们。这就是我在回答第一个问题的最后提到的 - 我想在一个地方谈论这个：
您必须非常小心地验证您的实际用法。如果数组中有 100 万个项目，并且只有前 10 个项目的查找速度比从缓存中获取的速度快，那么有 0.001% 的项目不会从缓存中受益。在那种情况下 - 你会从缓存中获益......或者你呢？如果您只对每个项目进行几次读取，并且您只查找不到四分之一的项目，那么缓存可能不会给您带来长期的好处。如果您恰好将每个项目查找两次，那么您的内存消耗就会 加倍 老实说，整体速度的提高非常微不足道。然而，如果您不是从数组中进行内存中查找，而是进行网络请求（例如，数据库读取）之类的操作，该怎么办？在那种情况下，即使是单次使用的缓存也可能非常有价值。
您可以看到一个细节是如何摇摆不定的，无论您是否应该使用记忆。很多时候，当您最初编写应用程序时甚至都不是那么清楚，因为您甚至不知道最终调用函数的频率、为它提供的值以及调用它的频率一遍又一遍地使用相同的值。即使您知道典型用法可能是什么，您仍然需要一个真实的环境来进行测试，而不是仅仅单独调用函数的非记忆化和记忆化版本。
Eric Lippert has an an amazing piece on performance testing 这主要归结为 - 当性能很重要时，尝试使用真实数据和真实使用情况测试真实应用程序。否则你的基准可能会因为各种原因而关闭。
即使 memoization 显然是 "faster" 你也必须考虑内存使用情况。这是一个有点愚蠢的例子来说明 memoization 消耗了比必要更多的内存：
const { memoize } = _;
//stupid recursive function that removes 1 from `b` and
//adds 1 to `a` until it finds the total sum of the two
function sum (a, b) {
if(b)
return sum(a + 1, b - 1)
//only log once to avoid spamming the logs but show if it's called or not
console.log("sum() finished");
return a;
}
//memoize the function
sum = memoize(sum);
const result = sum(1, 999);
console.log("result:", result);
const resultFromCache1 = sum(1, 999); //no logs as it's cached
console.log("resultFromCache1:", resultFromCache1);
const resultFromCache2 = sum(999, 1); //no logs as it's cached
console.log("resultFromCache2:", resultFromCache2);
const resultFromCache3 = sum(450, 550); //no logs as it's cached
console.log("resultFromCache3:", resultFromCache3);
const resultFromCache4 = sum(42, 958); //no logs as it's cached
console.log("resultFromCache4:", resultFromCache4);
<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.15/lodash.min.js"></script>
这会将一千个缓存结果放入内存。是的，memoized 函数很傻，做了很多不必要的调用，这意味着有很多内存开销。但与此同时，如果我们用 总和为 1000 的任何参数重新调用它，那么我们会立即得到结果，而无需进行任何递归。
即使不涉及递归，您也可以轻松拥有相似的真实代码 - 您最终可能会使用大量不同的输入多次调用某个函数。这将用所有结果填充缓存，但它是否有用仍然悬而未决。
因此，如果您可以，您应该使用记忆。最大的问题是找出 如果 可以。