"Javascript heap out of memory" 使用 Lodash memoize

Question

我正在尝试通过将记忆应用于递归解决方案来使用 Javascript 解决 LeetCode 的 longest palindromic subsequence 问题。这是递归解决方案，longestPalindromicSubsequence.js:

function longestPalindromicSubsequence(string, start = 0, end = string.length) {
  if (end < start) { return 0; }
  if (start === end) { return 1; }
  if (string[start] === string[end]) {
    return 2 + longestPalindromicSubsequence(string, start + 1, end - 1);
  }
  return Math.max(
    longestPalindromicSubsequence(string, start + 1, end),
    longestPalindromicSubsequence(string, start, end - 1),
  );
}

module.exports = longestPalindromicSubsequence;

这里有一些 Jest 测试用例，longestPalindromicSubsequence.test.js:

const longestPalindromicSubsequence = require('./longestPalindromicSubsequence');

describe('longest palindromic subsequence', () => {
  test('works for aab', () => {
    expect(longestPalindromicSubsequence('aab')).toBe(2);
  });

  test('works for long string', () => {
    expect(longestPalindromicSubsequence(`${'a'.repeat(50)}bcdef`)).toBe(50);
  });
});

这可行，但由于递归调用数量呈指数增长，速度相当慢。例如，对于长度为 ~50 的字符串，需要 9 秒：

$ jest longestPalindromicSubsequence.test.js
 PASS  ./longestPalindromicSubsequence.test.js (9.6s)
  longest palindromic subsequence
    ✓ works for aab (3ms)
    ✓ works for long string (9315ms)

Test Suites: 1 passed, 1 total
Tests:       2 passed, 2 total
Snapshots:   0 total
Time:        10.039s
Ran all test suites matching /longestPalindromicSubsequence.test.js/i.

为了提高性能，我尝试在更新的模块 longestPalindromicSubsequence2.js:

中使用 _.memoize

const _ = require('lodash');

const longestPalindromicSubsequence = _.memoize(
  (string, start = 0, end = string.length) => {
    if (end < start) { return 0; }
    if (start === end) { return 1; }
    if (string[start] === string[end]) {
      return 2 + longestPalindromicSubsequence(string, start + 1, end - 1);
    }
    return Math.max(
      longestPalindromicSubsequence(string, start + 1, end),
      longestPalindromicSubsequence(string, start, end - 1),
    );
  },
  (string, start, end) => [string, start, end], // resolver function
);

module.exports = longestPalindromicSubsequence;

但是，当我尝试运行使用此模块进行测试时，出现 "Javascript heap out of memory" 错误：

$ jest longestPalindromicSubsequence.test.js

 RUNS  ./longestPalindromicSubsequence.test.js

<--- Last few GCs --->
at[89308:0x104801e00]    15800 ms: Mark-sweep 1379.2 (1401.3) -> 1379.2 (1401.3) MB, 1720.4 / 0.0 ms  (+ 0.0 ms in 5 steps since start of marking, biggest step 0.0 ms, walltime since start of marking 1735 ms) (average mu = 0.128, current mu = 0.057) allocat[89308:0x104801e00]    17606 ms: Mark-sweep 1390.0 (1412.3) -> 1390.0 (1412.3) MB, 1711.7 / 0.0 ms  (+ 0.0 ms in 4 steps since start of marking, biggest step 0.0 ms, walltime since start of marking 1764 ms) (average mu = 0.091, current mu = 0.052) allocat

<--- JS stacktrace --->

==== JS stack trace =========================================

    0: ExitFrame [pc: 0x20b000bdc01d]
Security context: 0x1c189571e549 <JSObject>
    1: /* anonymous */ [0x1c18f7682201] [/Users/kurtpeek/GoogleDrive/LeetCode/longestPalindromicSubsequence2.js:~14] [pc=0x20b0015cd091](this=0x1c18d38893a1 <JSGlobal Object>,string=0x1c18f7682271 <String[55]: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcdef>,start=45,end=45)
    2: memoized [0x1c18f7682309] [/Users/kurtpeek/GoogleDrive/LeetCode/node_...

FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memory
 1: 0x100037733 node::Abort() [/usr/local/bin/node]
 2: 0x1000378d6 node::FatalTryCatch::~FatalTryCatch() [/usr/local/bin/node]
 3: 0x10018e57b v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [/usr/local/bin/node]
 4: 0x10018e51c v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, bool) [/usr/local/bin/node]
 5: 0x1004682ee v8::internal::Heap::UpdateSurvivalStatistics(int) [/usr/local/bin/node]
 6: 0x100469ed7 v8::internal::Heap::CheckIneffectiveMarkCompact(unsigned long, double) [/usr/local/bin/node]
 7: 0x1004675cb v8::internal::Heap::PerformGarbageCollection(v8::internal::GarbageCollector, v8::GCCallbackFlags) [/usr/local/bin/node]
 8: 0x1004663e6 v8::internal::Heap::CollectGarbage(v8::internal::AllocationSpace, v8::internal::GarbageCollectionReason, v8::GCCallbackFlags) [/usr/local/bin/node]
 9: 0x10046eafc v8::internal::Heap::AllocateRawWithLigthRetry(int, v8::internal::AllocationSpace, v8::internal::AllocationAlignment) [/usr/local/bin/node]
10: 0x10046eb48 v8::internal::Heap::AllocateRawWithRetryOrFail(int, v8::internal::AllocationSpace, v8::internal::AllocationAlignment) [/usr/local/bin/node]
11: 0x10044eb7a v8::internal::Factory::NewFillerObject(int, bool, v8::internal::AllocationSpace) [/usr/local/bin/node]
12: 0x100634916 v8::internal::Runtime_AllocateInTargetSpace(int, v8::internal::Object**, v8::internal::Isolate*) [/usr/local/bin/node]
13: 0x20b000bdc01d 
Abort trap: 6

据我了解，Node 的标准内存使用量是1.7GB，我认为应该足够了。记忆版本无法正常工作的任何想法，以及如何修复它？

Answer 1

我设法通过将解析器函数从 (string, start, end) => [string, start, end] 更改为 (string, start, end) => string + start + end:

来解决问题

const _ = require('lodash');

const longestPalindromicSubsequence = _.memoize(
  (string, start = 0, end = string.length) => {
    if (end < start) { return 0; }
    if (start === end) { return 1; }
    if (string[start] === string[end]) {
      return 2 + longestPalindromicSubsequence(string, start + 1, end - 1);
    }
    return Math.max(
      longestPalindromicSubsequence(string, start + 1, end),
      longestPalindromicSubsequence(string, start, end - 1),
    );
  },
  (string, start, end) => string + start + end, // resolver function
);

module.exports = longestPalindromicSubsequence;

现在 'long string' 测试只需要 3ms:

$ jest longestPalindromicSubsequence.test.js
 PASS  ./longestPalindromicSubsequence.test.js
  longest palindromic subsequence
    ✓ works for aab (3ms)
    ✓ works for long string (3ms)

Test Suites: 1 passed, 1 total
Tests:       2 passed, 2 total
Snapshots:   0 total
Time:        1.004s, estimated 10s
Ran all test suites matching /longestPalindromicSubsequence.test.js/i.

使用字符串作为缓存中的键似乎比使用数组更节省内存 - 也许是因为字符串在 Javascript 中是不可变的？欢迎对此改进的任何解释。

Answer 2

我知道您发布了最佳答案，但我想补充说明。根本问题是使用数组是造成瓶颈的原因。在幕后，lodash 有自己的 MapCache 他们定义似乎假设字符串将被传递。

但是重新查看 documentation 和评论，他们确实公开了 Cache 对象供您覆盖，假设它具有与他们的 Map 相同的接口。

Creates a function that memoizes the result of func. If resolver is provided, it determines the cache key for storing the result based on the arguments provided to the memoized function. By default, the first argument provided to the memoized function is used as the map cache key. The func is invoked with the this binding of the memoized function.

Note: The cache is exposed as the cache property on the memoized function. Its creation may be customized by replacing the _.memoize.Cache constructor with one whose instances implement the Map method interface of clear, delete, get, has, and set.

我进去测试了你的代码，因为如果你想将键引用为 objects/non-strings，你应该使用的实际 Map 是 WeakMap。这是我测试的

const _ = require('lodash');

// override Cache and use WeakMap
_.memoize.Cache = WeakMap;

const longestPalindromicSubsequence = _.memoize(
  (string, start = 0, end = string.length) => {
    if (end < start) { return 0; }
    if (start === end) { return 1; }
    if (string[start] === string[end]) {
      return 2 + longestPalindromicSubsequence(string, start + 1, end - 1);
    }
    return Math.max(
      longestPalindromicSubsequence(string, start + 1, end),
      longestPalindromicSubsequence(string, start, end - 1),
    );
  },
  (string, start, end) => [string, start, end], // resolver function
);

module.exports = longestPalindromicSubsequence;

虽然它仍然需要很长时间，但它最终会通过而不会遇到 JavaScript 堆内存不足问题。

正如您所确定的那样，最好的解决方案是简单地对密钥进行字符串化:)以碰撞告终）

"Javascript heap out of memory" 使用 Lodash memoize

"Javascript heap out of memory" using Lodash memoize

javascript

algorithm

recursion

memoization

lodash