14193549836

Committed 01 Apr 2025 10:40AM UTC coverage: 69.046% (+0.007%) from 69.039%

Build # 14193549836

Build Type

Pull #9665

github

Committed by

web-flow

Commit Message

Merge e8825f209 into b01f4e514

Pull Request Pull Request #9665: kvdb: bump etcd libs to v3.5.12

Run Details

133439 of 193262 relevant lines covered (69.05%)

22119.45 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,507,941✔
16	// Calculate the sum of weights.	10,507,941✔
17	var sum float64	10,507,941✔
18	for _, v := range w {	761,706,900✔
19	sum += v	751,198,959✔
20	}	751,198,959✔
21
22	if sum <= 0 {	10,507,992✔
23	return 0, ErrNoPositive	51✔
24	}	51✔
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,507,890✔
39	for i := range w {	387,714,838✔
40	r -= w[i]	377,206,948✔
41	if r <= 0 {	387,714,838✔
42	return i, nil	10,507,890✔
43	}	10,507,890✔
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,073✔
61	scores[i] = v.Score	68,512,858✔
62	nodeIDs[i] = k	68,512,858✔
63	i++	68,512,858✔
64	}	68,512,858✔
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 {	645,055✔
70	choice, err := weightedChoice(scores)	507,840✔
71	if err == ErrNoPositive {	507,890✔
72	return chosen, nil	50✔
73	} else if err != nil {	507,840✔
74	return nil, err	×
75	}	×
76
77	nID := nodeIDs[choice]	507,790✔
78		507,790✔
79	chosen[nID] = s[nID]	507,790✔
80		507,790✔
81	// We set the score of the chosen node to 0, so it won't be	507,790✔
82	// picked the next iteration.	507,790✔
83	scores[choice] = 0	507,790✔
84	}
85
86	return chosen, nil	137,165✔
87	}

lightningnetwork / lnd / 14193549836

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