13586005509

Committed 28 Feb 2025 10:14AM UTC coverage: 68.629% (+9.9%) from 58.77%

Build # 13586005509

Build Type

Pull #9521

github

Committed by

web-flow

Commit Message

Merge 37d3a70a5 into 8532955b3

Pull Request Pull Request #9521: unit: remove GOACC, use Go 1.20 native coverage functionality

Run Details

129950 of 189351 relevant lines covered (68.63%)

23726.46 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.33

/autopilot/choice.go

package autopilot

import (
        "errors"
        "fmt"
        "math/rand"
)

// ErrNoPositive is returned from weightedChoice when there are no positive
// weights left to choose from.
var ErrNoPositive = errors.New("no positive weights left")

// weightedChoice draws a random index from the slice of weights, with a
// probability proportional to the weight at the given index.
func weightedChoice(w []float64) (int, error) {
        // Calculate the sum of weights.
        var sum float64
        for _, v := range w {
                sum += v
        }

        if sum <= 0 {
                return 0, ErrNoPositive
        }

        // Pick a random number in the range [0.0, 1.0) and multiply it with
        // the sum of weights. Then we'll iterate the weights until the number
        // goes below 0. This means that each index is picked with a probability
        // equal to their normalized score.
        //
        // Example:
        // Items with scores [1, 5, 2, 2]
        // Normalized scores [0.1, 0.5, 0.2, 0.2]
        // Imagine they each occupy a "range" equal to their normalized score
        // in [0, 1.0]:
        // [|-0.1-||-----0.5-----||--0.2--||--0.2--|]
        // The following loop is now equivalent to "hitting" the intervals.
        r := rand.Float64() * sum
        for i := range w {
                r -= w[i]
                if r <= 0 {
                        return i, nil
                }
        }

        return 0, fmt.Errorf("unable to make choice")
}

// chooseN picks at random min[n, len(s)] nodes if from the NodeScore map, with
// a probability weighted by their score.
func chooseN(n uint32, s map[NodeID]*NodeScore) (
        map[NodeID]*NodeScore, error) {

        // Keep track of the number of nodes not yet chosen, in addition to
        // their scores and NodeIDs.
        rem := len(s)
        scores := make([]float64, len(s))
        nodeIDs := make([]NodeID, len(s))
        i := 0
        for k, v := range s {
                scores[i] = v.Score
                nodeIDs[i] = k
                i++
        }

        // Pick a weighted choice from the remaining nodes as long as there are
        // nodes left, and we haven't already picked n.
        chosen := make(map[NodeID]*NodeScore)
        for len(chosen) < int(n) && rem > 0 {
                choice, err := weightedChoice(scores)
                if err == ErrNoPositive {
                        return chosen, nil
                } else if err != nil {
                        return nil, err
                }

                nID := nodeIDs[choice]

                chosen[nID] = s[nID]

                // We set the score of the chosen node to 0, so it won't be
                // picked the next iteration.
                scores[choice] = 0
        }

        return chosen, nil
}

1	package autopilot
2
3	import (
4	"errors"
5	"fmt"
6	"math/rand"
7	)
8
9	// ErrNoPositive is returned from weightedChoice when there are no positive
10	// weights left to choose from.
11	var ErrNoPositive = errors.New("no positive weights left")
12
13	// weightedChoice draws a random index from the slice of weights, with a
14	// probability proportional to the weight at the given index.
15	func weightedChoice(w []float64) (int, error) {	10,509,709✔
16	// Calculate the sum of weights.	10,509,709✔
17	var sum float64	10,509,709✔
18	for _, v := range w {	762,116,138✔
19	sum += v	751,606,429✔
20	}	751,606,429✔
21
22	if sum <= 0 {	10,509,755✔
23	return 0, ErrNoPositive	46✔
24	}	46✔
25
26	// Pick a random number in the range [0.0, 1.0) and multiply it with
27	// the sum of weights. Then we'll iterate the weights until the number
28	// goes below 0. This means that each index is picked with a probability
29	// equal to their normalized score.
30	//
31	// Example:
32	// Items with scores [1, 5, 2, 2]
33	// Normalized scores [0.1, 0.5, 0.2, 0.2]
34	// Imagine they each occupy a "range" equal to their normalized score
35	// in [0, 1.0]:
36	// [\|-0.1-\|\|-----0.5-----\|\|--0.2--\|\|--0.2--\|]
37	// The following loop is now equivalent to "hitting" the intervals.
38	r := rand.Float64() * sum	10,509,663✔
39	for i := range w {	393,091,524✔
40	r -= w[i]	382,581,861✔
41	if r <= 0 {	393,091,524✔
42	return i, nil	10,509,663✔
43	}	10,509,663✔
44	}
45
46	return 0, fmt.Errorf("unable to make choice")	×
47	}
48
49	// chooseN picks at random min[n, len(s)] nodes if from the NodeScore map, with
50	// a probability weighted by their score.
51	func chooseN(n uint32, s map[NodeID]*NodeScore) (
52	map[NodeID]*NodeScore, error) {	137,215✔
53		137,215✔
54	// Keep track of the number of nodes not yet chosen, in addition to	137,215✔
55	// their scores and NodeIDs.	137,215✔
56	rem := len(s)	137,215✔
57	scores := make([]float64, len(s))	137,215✔
58	nodeIDs := make([]NodeID, len(s))	137,215✔
59	i := 0	137,215✔
60	for k, v := range s {	68,650,767✔
61	scores[i] = v.Score	68,513,552✔
62	nodeIDs[i] = k	68,513,552✔
63	i++	68,513,552✔
64	}	68,513,552✔
65
66	// Pick a weighted choice from the remaining nodes as long as there are
67	// nodes left, and we haven't already picked n.
68	chosen := make(map[NodeID]*NodeScore)	137,215✔
69	for len(chosen) < int(n) && rem > 0 {	646,823✔
70	choice, err := weightedChoice(scores)	509,608✔
71	if err == ErrNoPositive {	509,653✔
72	return chosen, nil	45✔
73	} else if err != nil {	509,608✔
74	return nil, err	×
75	}	×
76
77	nID := nodeIDs[choice]	509,563✔
78		509,563✔
79	chosen[nID] = s[nID]	509,563✔
80		509,563✔
81	// We set the score of the chosen node to 0, so it won't be	509,563✔
82	// picked the next iteration.	509,563✔
83	scores[choice] = 0	509,563✔
84	}
85
86	return chosen, nil	137,170✔
87	}

lightningnetwork / lnd / 13586005509

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous