On the example of leetcode task, we'll see how instead of a naive solution, we can utilize more elegant lazy evaluation.
I’m usually skeptical about leetcode tasks since this is not something you’ll encounter in your daily line-of-business code. But the idea behind this particular task has fascinated me. So I’ll break it down here.
I’ll provide a slightly simplified version of the task so you could capture the gist of it more easily.
Quote:
Write an API that generates fancy sequences using the append, addAll, and multAll operations.
Implement the Fancy class:
Fancy() Initializes the object with an empty sequence.
void append(val) Appends an integer val to the end of the sequence.
void addAll(inc) Increments all existing values in the sequence by an integer inc.
void multAll(m) Multiplies all existing values in the sequence by an integer m.
int getIndex(idx) Gets the current value at index idx (0-indexed). If the index is greater or equal than the length of the sequence, return -1.
Example 1:
Input
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
Output
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]
Explanation
Fancy fancy = new Fancy();
fancy.append(2); // fancy sequence: [2]
fancy.addAll(3); // fancy sequence: [2+3] -> [5]
fancy.append(7); // fancy sequence: [5, 7]
fancy.multAll(2); // fancy sequence: [5*2, 7*2] -> [10, 14]
fancy.getIndex(0); // return 10
fancy.addAll(3); // fancy sequence: [10+3, 14+3] -> [13, 17]
fancy.append(10); // fancy sequence: [13, 17, 10]
fancy.multAll(2); // fancy sequence: [13*2, 17*2, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // return 26
fancy.getIndex(1); // return 34
fancy.getIndex(2); // return 20
Constraints:
1 <= val, inc, m <= 100
0 <= idx <= 105
At most 105 calls total will be made to append, addAll, multAll, and getIndex.
Number of read operation surpasses number of mutations
The naive solution would be to perform each operation on all elements of an array and then get element at desired index. However, this solution is suboptimal since we may need only a couple of items from the collection so there’s clearly no need to calculate each item for such a case.
Alternatively, we might want to compute each item of the array on-demand leveraging some sort of lazy evaluation. In such a case, we need to ensure that we don’t calculate the same item twice. For such an occasion, we need to store the result of the calculation in an intermediary data structure. map would be the best fit for such structure since it allows us to get the desired element at O(1) time. The element index will serve as a key while the value of the map is the result of the calculation.
So the types are declared as follows:
type Operation struct {
operationCode int8
operand int
valuesLastIndex int32
}
type Fancy struct {
values []int8
operations []Operation
cache map[int]int
}
When appending values, we’re just increasing array of values:
func (this *Fancy) Append(val int) {
this.values = append(this.values, int8(val))
}
When adding or multiplying, we’re increasing array of operations. No evaluation happens at this point in time.
func (this *Fancy) AddAll(inc int) {
this.operations = append(this.operations,
Operation{-2, inc, int32(len(this.values))})
this.cache = make(map[int]int)
}
func (this *Fancy) MultAll(m int) {
this.operations = append(this.operations,
Operation{-1, m, int32(len(this.values))})
this.cache = make(map[int]int)
}
Evaluation occurs on-demand. We either try to hit a cache or calculate it if we miss a cache:
func (this *Fancy) GetIndex(idx int) int {
if idx < 0 || idx >= len(this.values) {
return -1
}
if val, ok := this.cache[idx]; ok {
return val
}
var vv uint64
vv = uint64(this.values[idx])
for _, v := range this.operations {
if idx >= int(v.valuesLastIndex) {
continue
}
switch os := v.operationCode; os {
case -2:
vv += uint64(v.operand)
case -1:
vv *= uint64(v.operand)
}
}
if this.cache == nil {
this.cache = make(map[int]int)
}
this.cache[idx] = int(vv)
return int(vv)
}
As some of you might have noticed each mutation operation leads to clearing the cache. So this method might be ineffective when the number of mutations surpasses the number of reads. So (as with every other solution in software engineering) it is advisable to evaluate your constraints before applying methods from your toolbox.
Evaluating cache
One thing that is worth noting is that cache we construct occupies space in memory. That means that we should evaluate using it so it won’t turn into a huge memory leak. For the same reason, you should have cache expiration strategy for most of your projects.
Since we know that the maximum number of operations is 10^5 we can deduce that cache size will reach its peak we won’t perform any additions or multiplications thus clearing the cache but instead half of the operations will be appending items and the other one will be evaluating them thus calculating new item each time.
func BenchmarkMemoryConsumption() {
var m1, m2 runtime.MemStats
runtime.GC()
runtime.ReadMemStats(&m1)
const MaxOperations int = 100000
fancy := Constructor()
for i := 0; i < MaxOperations/2; i++ {
fancy.Append(100)
}
for i := 0; i < MaxOperations/2; i++ {
fancy.GetIndex(i)
}
runtime.ReadMemStats(&m2)
fmt.Println("total:", m2.TotalAlloc-m1.TotalAlloc)
fmt.Println("mallocs:", m2.Mallocs-m1.Mallocs)
}
I’ve found built-in benchmarking functionality providing allocs per second metric irrelevant for this case so instead I’ve came up with the benchmark as above. The output is
<code>total: 3082976
mallocs: 1986
</code>
3MBs for the cache of maximum size? Easy for most of the line-of-business applications.
Conclusion
In case we’re presented with the perspective of doing a lot of wasteful computations, we can omit that by restoring to computing values when necessary using lazy evaluation.
History
- 30th May, 2022 - Published initial version
- 10th August, 2022 - Added paragraph about possible drawbacks
