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.
1class Memoize:
2
The Memoize class is defined to wrap the target function. It maintains a cache dictionary and a call count integer. If the input arguments are already present in the cache, the cached result is returned. Otherwise, the function is called, the result is cached, and the call count is incremented.
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.