量子運動のGolangによる説明

1
2
3
4
5
// Define point structure
type Point struct {
    X float64
    Y float64
}

1
2
3
4
5
// Define line segment structure
type Line struct {
    A Point
    B Point
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Distance uses random time as the sole criterion for measuring the length of an N-dimensional line segment
func (l Line) Distance() time.Duration {
    // Calculate Euclidean distance
    dx := l.A.X - l.B.X
    dy := l.A.Y - l.B.Y
    dist := math.Sqrt(dx*dx + dy*dy)

    // Map the distance to between 1ms~1000ms (logarithmic mapping for smoother growth)
    ms := 1 + int64(999*math.Tanh(dist/10)) // For large distances, approaches 1000ms

    // Add ±10% random jitter
    jitter := rand.Float64()*0.2 - 0.1
    ms = int64(float64(ms) * (1 + jitter))

    if ms < 1 {
        ms = 1
    } else if ms > 1000 {
        ms = 1000
    }
    return time.Duration(ms) * time.Millisecond
}

1
2
3
4
5
 // Beans structure: built-in concurrent dictionary key->Point
type Beans struct {
    mu    sync.RWMutex
    items map[int]model.Point
}

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
type RWLock struct {
}

// GetCost solves the problem using O(n) read-write lock
func (lock RWLock) GetCost() time.Duration {
    start := time.Now()
    end := time.Now()

    m := map[int]model.Point{}
    n := 50
    for i := 0; i < n; i++ {
        p := model.RandonPoint()
        m[i] = p
        // fmt.Println(p)
    }
    beans := NewBeans(m)
    // Simplify the problem by using two random initial points as the starting points for Pac-Man
    a := make([]model.Point, 1)
    a[0] = m[0]
    beans.GetAndRemove(0)
    b := make([]model.Point, 1)
    b[0] = m[1]
    beans.GetAndRemove(1)
    alipay := AlibabaCompany{}
    aliyun := AlibabaCompany{}
    for i := 2; i < n; i++ {
        p, _ := beans.GetAndRemove(i)
        line1 := model.NewLine(a[len(a)-1], p)
        // fmt.Println(line1.Distance())
        line2 := model.NewLine(b[len(b)-1], p)
        // fmt.Println(line2.Distance())
        t1 := line1.Distance()
        t2 := line2.Distance()
        if t1 < t2 {
            // a = append(a, p)
            end = end.Add(t1)
            alipay.Lines = append(alipay.Lines, line1)
        } else {
            // b = append(b, p)
            end = end.Add(t2)
            aliyun.Lines = append(aliyun.Lines, line2)
        }
    }
    // fmt.Println(a)
    // fmt.Println(b)
    alipayBeans := make([]model.Bean, 0)
    for _, item := range alipay.Lines {
        alipayBeans = append(alipayBeans, model.Bean{Line: item})
    }
    beansA := alipay.EatBeans(alipayBeans)
    fmt.Println("支付宝吃豆人：")
    fmt.Println(beansA)

    aliyunBeans := make([]model.Bean, 0)
    for _, item := range aliyun.Lines {
        aliyunBeans = append(aliyunBeans, model.Bean{Line: item})
    }
    beansB := aliyun.EatBeans(aliyunBeans)
    fmt.Println("阿里云吃豆人：")
    fmt.Println(beansB)

    return end.Sub(start)
}

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
type Information struct {
    date    time.Time
    content string
}

type AlibabaGroup struct {
    N    int           // algorithm scale
    Cost time.Duration // total time cost
    model.Alipay
    model.Aliyun
}

func (a *AlibabaGroup) Actor(core string, inbox <-chan Information) {
    for msg := range inbox {
        fmt.Printf("[%v]Actor %s received[%d]: %s\n", msg.date, core, a.N, msg.content)
        a.N++
    }
}

// EatBean If the problem is converted into a whole (Aliyun and Alipay are both assets of Alibaba Group), the problem can be simplified as a simple producer-consumer model
func (ali *AlibabaGroup) EatBean(beans []model.Bean) map[time.Time]model.Point {
    var m map[time.Time]model.Point = make(map[time.Time]model.Point)
    now := time.Now()
    start := now
    // fmt.Println(start)
    n := len(beans)
    var wg sync.WaitGroup
    memory := make(chan Information, 1) // limit to 1, forcibly convert to synchronous queue structure
    wg.Add(1)
    go func() {
        defer wg.Done()
        ali.Actor("1A84", memory)
    }()
    a := model.RandonPoint()
    m[now] = a
    memory <- Information{content: "立ち上がれ、江崎プリン！"}
    memory <- Information{date: start, content: fmt.Sprintf("(%f,%f)", a.X, a.Y)}
    cache := make(map[float64]float64)
    for i := 0; i < n-1; i++ {
        b := model.RandonPoint()
        notIn := true
        for notIn {
            if _, contains := cache[b.X]; contains {
                b = model.RandonPoint()
                continue
            } else {
                cache[b.X] = b.Y
                notIn = false
                break
            }
        }
        line := model.NewLine(a, b)
        now = now.Add(line.Distance())
        m[now] = b
        memory <- Information{date: now, content: fmt.Sprintf("(%f,%f)", b.X, b.Y)}
    }
    // fmt.Println(now)
    // fmt.Printf("cost: %v \n", ali.GetCost())
    ali.Cost = now.Sub(start)
    memory <- Information{date: time.Now(), content: fmt.Sprintf("cost: %v", ali.GetCost())}
    close(memory)
    wg.Wait()
    return m
}

func (ali *AlibabaGroup) GetCost() time.Duration {
    return ali.Cost
}

1
2
3
4
5
6
7
8
9
10
11
// NLine: n-dimensional line segment based on time
type NLine struct {
    t       time.Time
    actorID string
    model.Line
}

type Journey struct {
    Lines  []model.Line             // n-dimensional line segments (for simplicity, time is not introduced) as a 2D line segment array
    NBeans map[model.Bean]time.Time // n-dimensional objects
}

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
// Beans structure: built-in concurrent dictionary key->Point
// To avoid dependencies, directly copy from v1 version, do not use inheritance
type Beans struct {
    Name    string
    mu      sync.RWMutex
    items   map[int]model.Point
    FirstNL NLine
}

func (beans *Beans) Thought(n int, date time.Time) *Journey {
    // Simplify the problem by using a random initial point as the starting point for Pac-Man
    a := make([]model.Point, 1)
    first, _ := beans.GetAndRemove(0)
    journey := NewJourney(n - 1)
    a[0] = first
    // n points can only form n-1 line segments
    for i := 1; i < n; i++ {
        p, contains := beans.GetAndRemove(i)
        if !contains {
            break
        }
        line := model.NewLine(a[len(a)-1], p)
        // fmt.Printf("%d:%s\n", i, line.String())
        date = date.Add(line.Distance())
        journey.AddLine(date, i-1, line)
        if i == 1 {
            line := model.NewLine(a[0], p)
            beans.FirstNL = NLine{t: date, actorID: beans.Name, Line: line}
        }
        // Reset condition for the next round
        a = append(a, p)
    }
    result, err := journey.Validate()
    if !result || err != nil {
        fmt.Println("Journey validation failed:", err)
        return journey
    }
    return journey
}

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
func DoubleThought(n int) []NLine {
    m := make(map[int]model.Point, n)
    for i := 1; i < n; i++ {
        m[i] = model.RandonPoint()
    }
    p1 := model.RandonPoint()
    p2 := model.RandonPoint()
    // Force assignment of different starting points
    for p1.Compare(p2) {
        p2 = model.RandonPoint()
    }
    bean1 := NewBeansWithFirstPoint(p1, m)
    bean1.Name = "aliyun"
    bean2 := NewBeansWithFirstPoint(p2, m)
    bean2.Name = "alipay"

    now := time.Now()
    journey1 := bean1.Thought(n, now)
    journey2 := bean2.Thought(n, now)
    // Normalize and merge, remove redundant points.
    nLines := make(map[time.Time]NLine)
    nMap := NewNLineMap(0)
    for k, t1 := range journey1.NBeans {
        t2, ok := journey2.NBeans[k]
        if !ok {
            continue
        }
        // The one that falls behind gets eliminated
        if t1.After(t2) {
            delete(journey1.NBeans, k)
            line := NLine{t: t2, Line: k.Line, actorID: bean2.Name}
            nLines[t2] = line
            nMap.Add(t2, line)
            continue
        }
        if t2.After(t1) {
            delete(journey2.NBeans, k)
            line := NLine{t: t1, Line: k.Line, actorID: bean1.Name}
            nLines[t1] = line
            nMap = nMap.Add(t1, line)
            continue
        }
        // Since the dictionary automatically deduplicates, collisions can be ignored
        fmt.Printf("%v:%v Two Pac-Man arrive at %v simultaneously, collision occurred\n", t1, t2, k.Line)
    }
    nMap.AddZero(bean1.FirstNL)
    nMap.AddZero(bean2.FirstNL)
    fmt.Printf("%v : total n-dimensional line segments: %d; Pac-Man %v count %v; Pac-Man %v count %v;\n", now,
        len(nMap.items)+2, bean1.Name, len(journey1.NBeans), bean2.Name, len(journey2.NBeans))
    lines := nMap.All(false)
    fmt.Printf("len(lines):%v\n", len(lines))
    for k, v := range lines {
        fmt.Printf("%v:%v\n", k, v.String())
    }
    fmt.Println(journey1.End())
    return lines
}

1
2
3
4
func TestDoubleThought(t *testing.T) {
    lines := DoubleThought(50)
    t.Logf("len(lines): %v", len(lines))
}

1
2
3
4
5
6
p1 := model.RandonPoint()
p2 := model.RandonPoint()
    // Force assignment of different starting points
    for p1.Compare(p2) {
        p2 = model.RandonPoint()
    }