Sponsored
Sponsored
In this approach, we can utilize a dictionary (or map) to cache the results of the function calls. The keys in this dictionary will be the string representation of the input arguments, and the values will be the corresponding function output. We will also maintain a count of how many unique calls have been made with new inputs.
The time complexity for each call is O(1) due to dictionary lookups. The space complexity is O(n) in the worst case, where n is the number of unique calls made, due to storage in the cache.
1function memoize(fn) {
The memoize function accepts a function and returns a memoized version of it. The cache is an object and each set of arguments is serialized as a string key. The function updates and checks the cache before invoking the original function. There is also a static method to retrieve the call count.
Preserving the order and distinction of each argument set is crucial and can be achieved using tuples for arguments. With languages like Python, tuples can directly represent immutable and hashable keys for our cache. Similar adaptations exist for other languages, respecting each language's constraints around tuple-like structures and hashable types.
O(1) lookup time in the cache; Space complexity is O(n), dependent on the number of distinct calls stored.
1using System;
2using System.Collections.Generic;
3
4public class Memoize<TArgs, TResult>
5{
6 private readonly Func<TArgs, TResult> _func;
7 private readonly Dictionary<TArgs, TResult> _cache;
8 private int _callCount;
9
10 public Memoize(Func<TArgs, TResult> func)
11 {
12 _func = func;
13 _cache = new Dictionary<TArgs, TResult>();
14 _callCount = 0;
15 }
16
17 public TResult Call(TArgs args)
18 {
19 if (_cache.TryGetValue(args, out TResult result))
20 {
21 return result;
22 }
23
24 result = _func(args);
25 _cache[args] = result;
26 _callCount++;
27 return result;
28 }
29
30 public int GetCallCount() => _callCount;
31}
32
33public static class Program
34{
35 public static int Sum((int, int) args) => args.Item1 + args.Item2;
36 public static int Fib(int n) => n <= 1 ? 1 : Fib(n - 1) + Fib(n - 2);
37 public static int Factorial(int n) => n <= 1 ? 1 : n * Factorial(n - 1);
38}C# utilizes the tuple struct for caching keys, a feature built-in to the language that permits hashing and equality. Tuple provides the flexibility to uniquely store distinct argument sets without unnecessary complexity.