MyCaffe.trainers.common.SegmentTree Class Reference

Segment tree data structure More...

Inheritance diagram for MyCaffe.trainers.common.SegmentTree:

Public Types
enum	OPERATION { SUM , MIN }
	Specifies the operations used during the reduction. More...

Public Member Functions
	SegmentTree (int nCapacity, OPERATION oper, float fNeutralElement)
	The constructor. More...
double	reduce (int nStart, int? nEnd=null)
	Returns result of applying self.operation to a contiguous subsequence of the array. operation(arr[start], operation(ar[start+1], operation(..., arr[end]))) More...

Protected Attributes
int	m_nCapacity
	Specifies the capacity of the segment tree. More...
OPERATION	m_op
	Specifies the operation to perform when reducing the tree. More...
double[]	m_rgfValues
	Specifies the data of the tree. More...

Properties
double	this[int nIdx] [getset]
	Element accessor to get and set items. More...

Detailed Description

Segment tree data structure

The segment tree can be used as a regular array, but with two important differences:

a.) Setting an item's value is slightly slower: O(lg capacity) instead of O(1). b.) User has access to an efficient 'reduce' operation which reduces the 'operation' over a contiguous subsequence of items in the array.

See also

Wikipedia: Segment tree

GitHub: openai/baselines 2018

GitHub: higgsfield/RL-Adventure 2018

Definition at line 24 of file SegmentTree.cs.

Member Enumeration Documentation

OPERATION

enum MyCaffe.trainers.common.SegmentTree.OPERATION

Specifies the operations used during the reduction.

Enumerator
SUM	Sum the two elements together.
MIN	Return the minimum of the two elements.

Definition at line 42 of file SegmentTree.cs.

Constructor & Destructor Documentation

SegmentTree()

MyCaffe.trainers.common.SegmentTree.SegmentTree	(	int	nCapacity,
		OPERATION	oper,
		float	fNeutralElement
	)

The constructor.

Parameters

nCapacity	Specifies the total size of the array - must be a power of two.
oper	Specifies the operation for combining elements (e.g. sum, min)
fNeutralElement	Specifies the nautral element for the operation above (e.g. float.MaxValue for min and 0 for sum).

Definition at line 60 of file SegmentTree.cs.

Member Function Documentation

reduce()

double MyCaffe.trainers.common.SegmentTree.reduce	(	int	nStart,
		int?	nEnd = null
	)

Returns result of applying self.operation to a contiguous subsequence of the array. operation(arr[start], operation(ar[start+1], operation(..., arr[end])))

Parameters

nStart	Beginning of the subsequence.
nEnd	End of the subsequence

Returns

Definition at line 129 of file SegmentTree.cs.

Member Data Documentation

m_nCapacity

int MyCaffe.trainers.common.SegmentTree.m_nCapacity

protected

Specifies the capacity of the segment tree.

Definition at line 29 of file SegmentTree.cs.

m_op

OPERATION MyCaffe.trainers.common.SegmentTree.m_op

protected

Specifies the operation to perform when reducing the tree.

Definition at line 33 of file SegmentTree.cs.

m_rgfValues

double [] MyCaffe.trainers.common.SegmentTree.m_rgfValues

protected

Specifies the data of the tree.

Definition at line 37 of file SegmentTree.cs.

Property Documentation

this[int nIdx]

double MyCaffe.trainers.common.SegmentTree.this[int nIdx]

getset

Element accessor to get and set items.

Parameters

nIdx	Specifies the index of the item to access.

Returns

The item at the specified index is returned.

Definition at line 147 of file SegmentTree.cs.

---

The documentation for this class was generated from the following file:

• C:/Data/Data/SS_Projects/Intelligence/GitHub/MyCaffe/MyCaffe.trainers/common/SegmentTree.cs