I'm trying to solve LeetCode's longest palindromic subsequence problem using Javascript by applying memoization to a recursive solution. Here is the recursive solution, 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;
Here are some Jest test cases for it, 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);
});
});
This works, but is rather slow due to the exponential increase in the number of recursive calls. For example, for a string of length ~50 it takes 9 seconds:
$ 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.
To improve this performance, I tried using _.memoize in an updated module longestPalindromicSubsequence2.js:
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;
However, when I try to run the tests with this module, I get a "Javascript heap out of memory" error:
$ 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
As I understand from Node.js heap out of memory, the standard memory usage for Node is 1.7GB, which I reckon should be sufficient. Any ideas why the memoized version is not working, and on how to fix it?
I managed to fix the problem by changing the resolver function from (string, start, end) => [string, start, end] to (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;
Now the 'long string' test takes only 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.
It would appear that using a string as a key into the cache is much more memory-efficient than using an array - perhaps because strings are immutable in Javascript? Any explanations of this improvement would be welcome.