지연 평가 활용

저는 일반적으로 leetcode 작업에 대해 회의적입니다. 이는 일상 업무 코드에서 마주하게 될 것이 아니기 때문입니다. 하지만 이 특정 작업 뒤에 있는 아이디어가 저를 매료시켰습니다. 그래서 여기서 분해하겠습니다.

작업의 요지를 보다 쉽게 ​​캡처할 수 있도록 작업의 약간 단순화된 버전을 제공하겠습니다.

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

순진한 솔루션은 배열의 모든 요소에 대해 각 작업을 수행한 다음 원하는 인덱스에서 요소를 가져오는 것입니다. 그러나 이 솔루션은 컬렉션에서 몇 개의 항목만 필요할 수 있으므로 이러한 경우 각 항목을 계산할 필요가 없기 때문에 차선책입니다.

또는 일종의 지연 평가를 활용하여 온디맨드 배열의 각 항목을 계산할 수도 있습니다. 이 경우 동일한 항목을 두 번 계산하지 않도록 해야 합니다. 이러한 경우를 위해 중간 데이터 구조에 계산 결과를 저장해야 합니다. map는 O(1) 시간에 원하는 요소를 얻을 수 있기 때문에 이러한 구조에 가장 적합합니다. 요소 인덱스는 키 역할을 하며 맵의 값은 계산 결과입니다.

따라서 유형은 다음과 같이 선언됩니다.

type Operation struct {
    operationCode   int8
    operand         int
    valuesLastIndex int32
}

type Fancy struct {
    values     []int8
    operations []Operation
    cache      map[int]int
}

값을 추가할 때 값 배열을 늘리는 것입니다.

func (this *Fancy) Append(val int) {
    this.values = append(this.values, int8(val))
}

더하거나 곱할 때 연산 배열을 늘립니다. 이 시점에서는 평가가 수행되지 않습니다.

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)
}

평가는 온디맨드 방식으로 이루어집니다. 우리는 캐시에 적중하려고 시도하거나 캐시를 놓친 경우 계산합니다.

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)
}

여러분 중 일부는 각 변형 작업이 캐시를 지우는 것을 알아차렸을 것입니다. 따라서 이 방법은 돌연변이 수가 읽기 수를 초과할 때 비효율적일 수 있습니다. 따라서 (소프트웨어 엔지니어링의 다른 모든 솔루션과 마찬가지로) 도구 상자에서 방법을 적용하기 전에 제약 조건을 평가하는 것이 좋습니다.

캐시 평가 중

주목할 가치가 있는 한 가지는 우리가 구성하는 캐시가 메모리 공간을 차지한다는 것입니다. 즉, 엄청난 메모리 누수로 바뀌지 않도록 사용을 평가해야 합니다. 같은 이유로 대부분의 프로젝트에 대해 캐시 만료 전략이 있어야 합니다.

최대 작업 수가 10^5임을 알고 있기 때문에 캐시 크기가 최대치에 도달할 것이라고 추론할 수 있으므로 더하기 또는 곱하기를 수행하지 않고 캐시를 지우는 대신 작업의 절반은 항목을 추가하고 다른 하나는 평가하여 매번 새 항목을 계산합니다.

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)
}

이 경우와 관련이 없는 초당 할당량 메트릭을 제공하는 것을 발견built-in benchmarking functionality했기 때문에 대신 위와 같이 벤치마크를 생각해 냈습니다.
출력은

total: 3082976
mallocs: 1986

최대 크기의 캐시에 3MB? 대부분의 LOB(기간 업무) 응용 프로그램에 사용하기 쉽습니다.

결론

읽기 집약적인 시나리오에서 많은 낭비적인 계산을 수행하는 관점이 제시되는 경우 지연 평가 및 캐싱을 사용하여 필요할 때 컴퓨팅 값으로 복원함으로써 이를 생략할 수 있습니다. 그러나 캐시를 사용할 때는 크기와 만료 전략을 고려해야 합니다.