data_structure

package

v0.0.0-...-34c64f0 Latest Latest Go to latest Published: Feb 25, 2024 License: MIT Imports: 3 Imported by: 0

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

github.com/frealcone/external-sort

Links

Open Source Insights

Documentation ¶

Index ¶

type Convertable
type FRecordSpace
- func NewFRecordSpace(options ...FRecordSpaceOption) *FRecordSpace
- func (s *FRecordSpace) Flush() map[string]int
- func (s *FRecordSpace) Insert(record FileRecord) error
type FRecordSpaceOption
- func WithMaxRecordNum(N int) FRecordSpaceOption
- func WithTempPath(path string) FRecordSpaceOption
type FileReader
type FileRecord
type FileRecordHeap
type MergeTree
- func (mt *MergeTree) Insert(node MergeTreeNode)
- func (mt *MergeTree) Merge(nodeName string, k int) ([]string, int)
type MergeTreeNode
type RaceTree
- func NewEmptyRaceTree(N int) RaceTree
- func NewRaceTree(records []FileRecord) RaceTree
type Sortable

Constants ¶

This section is empty.

Variables ¶

This section is empty.

Functions ¶

This section is empty.

Types ¶

type Convertable ¶

type Convertable interface {
	Convert(s string) (FileRecord, error)
}

Convertable 是将文本转化为一条数据记录的工具

type FRecordSpace ¶

type FRecordSpace struct {
	N int // 最大记录数量
	// contains filtered or unexported fields
}

选择置换排序所用空间

func NewFRecordSpace ¶

func NewFRecordSpace(options ...FRecordSpaceOption) *FRecordSpace

func (*FRecordSpace) Flush ¶

func (s *FRecordSpace) Flush() map[string]int

将记录立刻全部保存到磁盘上

func (*FRecordSpace) Insert ¶

func (s *FRecordSpace) Insert(record FileRecord) error

将记录有序插入到游程文件中

type FRecordSpaceOption ¶

type FRecordSpaceOption func(*FRecordSpace)

func WithMaxRecordNum ¶

func WithMaxRecordNum(N int) FRecordSpaceOption

func WithTempPath ¶

func WithTempPath(path string) FRecordSpaceOption

type FileReader ¶

type FileReader interface {
	Read() (string, error)
	ChangeSource(source *os.File)
	Copy() FileReader
}

FileReader 定义了从文件中读取文本, 且一次读取相当于一条记录的文本的方法

type FileRecord ¶

type FileRecord interface {
	Sortable
	String() string
}

FileRecord 是从文件中读取到的文本转化为的数据记录, 一条记录必须满足: 1. 可排序(即, 可以与另一条记录比较大小) 2. 可转化为文本, 从而输出到结果文件中

type FileRecordHeap ¶

type FileRecordHeap []FileRecord

文件类型的小根堆

func (FileRecordHeap) Len ¶

func (frh FileRecordHeap) Len() int

func (FileRecordHeap) Less ¶

func (frh FileRecordHeap) Less(i, j int) bool

func (*FileRecordHeap) Pop ¶

func (frh *FileRecordHeap) Pop() interface{}

func (*FileRecordHeap) Push ¶

func (frh *FileRecordHeap) Push(x interface{})

func (FileRecordHeap) Swap ¶

func (frh FileRecordHeap) Swap(i, j int)

type MergeTree ¶

type MergeTree []MergeTreeNode

MergeTree 合并树数据结构 (Huffman Tree)

func (*MergeTree) Insert ¶

func (mt *MergeTree) Insert(node MergeTreeNode)

Insert 将合并树节点插入合并树

func (*MergeTree) Merge ¶

func (mt *MergeTree) Merge(nodeName string, k int) ([]string, int)

Merge 将合并树中权重最小的K个节点合并, 合并后新的节点名称为nodeName 返回被合并的节点名称和实际合并的节点数量

type MergeTreeNode ¶

type MergeTreeNode struct {
	FileName string // 待合并文件名称
	Weight   int    // 待合并文件在合并树中的权重
}

MergeTreeNode 合并树节点

type RaceTree ¶

type RaceTree []FileRecord

func NewEmptyRaceTree ¶

func NewEmptyRaceTree(N int) RaceTree

func NewRaceTree ¶

func NewRaceTree(records []FileRecord) RaceTree

初始化PK树, 用于初始化的记录数组必须长度为偶数

func (RaceTree) Adjust ¶

func (tree RaceTree) Adjust(i int)

func (RaceTree) Peak ¶

func (tree RaceTree) Peak() (FileRecord, int)

func (RaceTree) Put ¶

func (tree RaceTree) Put(record FileRecord, idx int)

type Sortable ¶

type Sortable interface {
	CompareTo(s Sortable) int
}

Sortable 定义了CompareTo方法, 该方法将本Sortable数据与s比较返回值>0或=0或<0分别代表本数据大于/等于/小于s

Source Files ¶

View all Source files

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL