external_sort

external-sort

English Version

external-sort是使用Go.lang编写的外排序库; 支持对用户自定义文件的内容进行排序.

使用 (Get Started)

external-sort算法的定义如下:

func ExtSort(r ds.FileReader, cvt ds.Convertable, destination string, N int) error

描述

ExtSort共接收4个参数: r用于读取文件, cvt用于将文件的字符(或二进制)内容转化为文件记录类型的数据, destination为排好序的数据最终存储到的磁盘文件路径, N为对可用内存所能容纳下的文件记录数量的估计.

其中, 文件读取, 转化相关的接口定义如下, 用户必须自行实现这些接口:

1. FileReader

Read() (string, error)
ChangeSource(source *os.File)
Copy() DiskReader

其中, 文件读取接口声明了三个方法: Read()方法从待排序文件中, 读取可以转化为一个文件记录类型变量的字符(或二进制)内容, 并将文件指针移动到下一次读取的位置; ChangeSource()方法将待排序文件修改为source; Copy()方法将当前FileReader类型的变量复制一份并返回;

1. Convertable

Convert(s string) (FileRecord, error)

Convert()方法负责将存放了字符(或二进制)数据的string类型字符串转化为文件记录(FileRecord)类型的变量;

1. FileRecord

type Sortable interface {
	CompareTo(s Sortable) int
}

Sortable
String() string

CompareTo()将当前FileRecord类型变量与另一变量fr进行比较, 如当前变量大于/等于/小于fr时, 返回值分别小于/等于/大于0; String()将当前变量再次变回字符(或二进制)数据;

注意: destination如果表示的是一个已有的文件, 那么ExtSort()会将该文件清空, 如该文件不存在, 则创建该文件. Convert()和String()互为逆操作, 也就是说, string类型的变量s在不进行其他操作的情况下, 经过fr, _ := Convert(s); t := fr.String(), 得到变量t, 则s等于t

案例 (Case)

已有文件numbers.txt:

10
300
34
89
...

下述代码可将numbers.txt进行排序

import (
	"bufio"
	"os"
	"strconv"

	esort "github.com/frealcone/external-sort"
	eds "github.com/frealcone/external-sort/data_structure"
)

type Integer int

func (i Integer) CompareTo(s eds.Sortable) int {
	return int(i) - int(s.(Integer))
}

func (i Integer) String() string {
	return strconv.Itoa(int(i)) + "\n"
}

type IntegerConv struct{}

func (ic IntegerConv) Convert(s string) (eds.FileRecord, error) {
	i, e := strconv.Atoi(s)
	if e != nil {
		return nil, e
	}
	return Integer(i), e
}

type LocalFileReader struct {
	Source *bufio.Reader
}

func (fr LocalFileReader) Read() (string, error) {
	line, _, err := fr.Source.ReadLine()
	return string(line), err
}

func (fr *LocalFileReader) ChangeSource(source *os.File) {
	fr.Source = bufio.NewReader(source)
}

func (fr LocalFileReader) Copy() eds.FileReader {
	return &LocalFileReader{fr.Source}
}

func main() {
	file, _ := os.Open("./numbers.txt")
	source := bufio.NewReader(file)

	reader := &LocalFileReader{Source: source}

	convertor := new(IntegerConv)

	esort.ExtSort(reader, convertor, "./result", 100)
}