Javascript memoize 查找数组

Question

我正在尝试提高我对 javascript 中内存的知识。我创建了一个内存功能(我认为..)

我对项目进行了一系列更改(更改日志)。数组中的每个项目都包含一个对其进行编辑的 reference-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) 何时使用 memoization 是否有经验法则？或者我应该尽可能多地使用它？

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)

Answer 1

我将尝试回答您的每个问题:

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 毫秒才能完成。使用 memoization，我们可以通过检查我们之前是否发出过这个请求来避免发出这个 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?

我不完全确定您的意思，但可以将其视为短期缓存。
如果您的备忘录调用包含 API 请求，它可能非常适合不更改的数据，从而节省大量时间，但另一方面，如果数据在短时间内发生变化，那么备忘录可能会很糟糕想法，这意味着它很快就会过时。

如果您对该函数进行多次调用，它可能会根据返回数据的大小消耗内存，但这个因素取决于实现，而不是“正确的方法”。

3) Is there a rule of thumb when to use memoization? Or should I use it as often as I can?

通常情况下，memoization 是多余的——因为计算机速度非常快，它通常可以归结为只节省几毫秒——如果你只是调用这个函数，即使只是几次，memoization 几乎没有好处。但我确实一直强调 API 请求，这可能需要很长时间。如果你开始使用内存函数，你应该尽可能在任何地方使用它。但是，如前所述，它可能会根据返回数据迅速耗尽内存。

关于记忆化的最后一点是，如果数据已经在客户端，则使用建议的 Nina 之类的 map 绝对是一种更好、更有效的方法。它不是每次循环查找对象，而是循环一次将数组转换为对象(或映射)，从而允许您在 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 是一个很棒的工具，与缓存非常相似。它为繁重的计算或长的网络请求提供了很大的加速，但如果不经常使用，可能会证明是无效的。