ARST打卡第190周[190/521]

2022-12-25 2633 words 6 minutes

Contents

Algorithm

lc1739_放置盒子

找规律，看下面的代码和题解

二分法和找规律法其实是类似的，不过多了一个求和公式，使得效率更好了一些，方法三则是更近一步，直接把方程给解出来了，然后效率就更高。有兴趣的看题解：作者：力扣官方题解链接：https://leetcode.cn/problems/building-boxes/solutions/2030450/fang-zhi-he-zi-by-leetcode-solution-7ah2/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


/* 
2022年12月25日14:33:41 感觉像是一个找规律的题目
思路:
尽量少的地面，也就是优先靠着墙角，然后能堆高就必须堆高。
因为高度最高为n，而只有n个立方体，按照上面的规律肯定不用考虑放不下的问题。
然后就是找规律
1-3 --> n
4 --> 3
5 --> 4
6 --> 5
7 --> 5
8-10 --> 6

所以是这样:
1. 下层1-2-3-4-5地慢慢累加，也就是1-3-6-10
2. 每次累加后，上面堆叠量可以承载前面一个前缀和的值，也即是3时上面承载1,6时上面承载3+1(二次累加和)

2022年12月25日14:49:20 感觉找规律不方便把中间态公式化，还是尝试dp模拟放置过程吧，
但是n为1e9,不能遍历到1e9..学习下题解怎么找到的规律吧

看了一下，题解通过数学列式得出规律，其实和我前面思路一样，但是我没有持续想下去...
*/
func minimumBoxes(n int) int {
    cur, i, j := 1, 1, 1
    for n > cur {
        n -= cur
        i++
        // 累加值，相当于一开始减去顶层，然后减去第二层
        cur += i
    }
    cur = 1
    for n > cur {
        n -= cur
        j++
        // 这里一个个添加边缘的时候的规律，前头加一个，后头加2个成为一个堆，再后头又加两个，但上层又有一个，
        // 所以1,2,3,4---想象成楼梯一开始只有一级，复制一个切面有2级，再一个切面就是3级
        cur++
    }
    return (i-1)*i/2 + j
}

Review

You Don’t Actually Know What Your Future Self Wants | Shankar Vedantam | TED

许多年后，你可能不再是当下的你，但是你却可以塑造未来的自己，就像你活着的意义可以自己赋予一样。

因此可以做如下三件事情去塑造未来的自己:

花时间做自己的业余兴趣，职业梦想相关的探索，去看对应领域的专家怎么做，而不是把所有的时间花在家人身上。保持对外界的好奇心。
当我们自信表达现在的观点的时候，可能未来的自己都会是觉得反对观点的，所以请保持谦逊。
对于生活中的挑战性的机会，今天没办法做到，也许明天有办法做到，所以勇敢一点。

Tips

由浅入深聊聊Golang的sync.Map

结论

amended: 意思是被修改过的，为true就是表明dirty和readOnly中的map的数据不相同了 readOnly中的map数据为nil: 就是正常的Delete()操作会让readOnly中的map数据值为nil，key还在 readOnly中的map数据被标记为expunged(擦去；删掉): 就是只有在readOnly生成dirty数据时，如果遇到readOnly中标记为nil的值，则标记为expunged，并且不放在dirty中，没有对应key和值

因为一个readOnly数据被抹去分为2种情况:

情况一（dirty提升为readOnly的map）：
1. 在readOnly中标记key对应的值为nil，dirty中数据的key直接被删除
2. 在readOnly中的miss命中率太低了，然后dirty_map提升为readOnly中的map，readOnly中的nil值key被抹去(之前之前的dirty的key已经被删除掉了)
情况二（readOnly先生成dirty，之后再被dirty替换）：
1. 在readOnly中标记key对应的值为nil，dirty中数据的key直接被删除
2. 插入过程引发的readOnly刷新未删除的数据到dirty（此时会将已经删除标记为nil的数据标记为expunged）（expunged状态可以在Store存储的时候恢复为nil）
3. 等到后面miss命中率太低，然后dirty_map提升为readOnly的map，去除掉相对应的key值

从上面可以看出，nil状态下，dirty中可能有对应的key值。而expunged状态下，dirty绝对没有对应的key值，除非在增(改)的时候添加对应的key到dirty中，此时也会相对应地把expunged状态转化为nil状态

sync.Map介绍与参考文章

由浅入深聊聊Golang的sync.Map

理解的hack过程

`Delete()`为什么没有更改amended的状态

感觉这两个状态的理解要理解全部实现，发现删除Delete()是没有更改amended的状态的！！！这样的话，~~就会造成dirty和readOnly数据不一致(先暂时如此假设，后面会证实为错误，其实是对先前的一些定义没有深入理解)~~，但是可能amended还是false

那么两次删除同一个数据，第一次readOlny标记为nil删除掉数据，第二次，!ok 而且还amended为false，那就导致dirty中存在数据

之后再反复读这个数据，一直miss..然后再dirty同步到readOnly，那岂不是没删除掉？？？

一定是哪里理解有偏差

理解了，因为readOnly和dirty中的entry指向同一片地址，所以第一次删除一个数据后，不用修改掉amended，还是完全一致的

所以得出结论是，amended在删，查的时候都不会发生变化，只有在增(改)的时候发生变化

但是同样还有这个问题就是，如果增加一个值后，连续删除这个值两次，那么就会第一次dirty中有值，第二次dirty中没有值，当然这时候readOnly是nil，但是其实是科学的，得出的结论就是nil状态下，dirty中可能有对应的key值

看了go1.18的源码就更加清晰了，源码中确定了无论dirty中是否有对应的值，也即是证明了有可能有值，有可能没有值，然后都让miss增加，因为走的是先readOnly再dirty的最长查找路径，所以需要尽快把dirty提升到readOnly上面

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


// LoadAndDelete deletes the value for a key, returning the previous value if any.
// The loaded result reports whether the key was present.
func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended {
        m.mu.Lock()
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            e, ok = m.dirty[key]
            delete(m.dirty, key)
            // Regardless of whether the entry was present, record a miss: this key
            // will take the slow path until the dirty map is promoted to the read
            // map.
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if ok {
        return e.delete()
    }
    return nil, false
}

// Delete deletes the value for a key.
func (m *Map) Delete(key any) {
    m.LoadAndDelete(key)
}