「38」上亿数据的快速排序

发表于 本文字数： 8.2k 阅读时长 ≈ 7 分钟

前序

前面说到了快速排序的自定义通用方案:

「37」Quick Sort快速排序

但是又有一个新想法: 1亿条数据,100M内存,怎么搞?

分析

问题

  • 内存不足以放1亿条数据
  • 即使够用,一次把1亿条数据放入内存,如果说高并发下,每次都是1亿,消耗过大!

解决思路:

大化小,小归大「归并算法的思想」,利用磁盘文件形式进行存储,比较,再存储…

代码部分「其它语言类似」:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302

type User struct {
	Name  string
	Age   int
	Count int
}

const Counter = 100000000

var SplitNum = Counter / 10000000

func QuickSortAll(a []interface{}, left, right int, By func(a, b interface{}) bool) []interface{} {
	if left < right {
		mid := partitionAll(a, left, right, By)
		QuickSortAll(a, left, mid-1, By)
		QuickSortAll(a, mid+1, right, By)
	}
	return a

}

func partitionAll(a []interface{}, left int, right int, By func(a, b interface{}) bool) int {
	pivot := a[left]
	for ; left < right; {
		//for ; left < right && a[right] >= pivot; {
		for ; left < right && By(a[right], pivot); {
			right--
		}
		a[left] = a[right]
		//for ; left < right && a[left] <= pivot; {
		for ; left < right && By(pivot, a[left]); {
			left++

		}
		a[right] = a[left]
	}
	a[left] = pivot
	return left
}

func StartSort(dirName string) string {
	var lock sync.Mutex
	resultPaths := make([]string, 0)
	group, _ := errgroup.WithContext(context.TODO())
	for ia := 0; ia < Counter; ia += SplitNum * 2 {
		i := ia
		//group.Go(func() error {
		Mem("compareTwoFileObject")
		filePath, _ := compareTwoFileObject(dirName+"/"+strconv.Itoa(i)+"_split_quicksort.txt",
			dirName+"/"+strconv.Itoa(i+SplitNum)+"_split_quicksort.txt", dirName, SortBy)
		lock.Lock()

		resultPaths = append(resultPaths, filePath)
		lock.Unlock()
		//return nil
		//})
	}
	group.Wait()

	return recursionDeal(resultPaths, dirName, lock)
}
func recursionDeal(paths []string, dirName string, lock sync.Mutex) string {
	tmpPaths := make([]string, 0)
	if len(paths) == 1 {
		return paths[0]
	}

	group, _ := errgroup.WithContext(context.TODO())
	for ia := 0; ia < len(paths); ia += 2 {
		i := ia
		if len(paths)%2 != 0 && i == len(paths)-1 {
			lock.Lock()
			tmpPaths = append(tmpPaths, paths[i])
			lock.Unlock()
			break
		}

		//group.Go(func() error {
		filePath, _ := compareTwoFileObjectForRecursion(dirName+"/"+paths[i], dirName+"/"+paths[i+1], dirName, SortBy)
		lock.Lock()
		tmpPaths = append(tmpPaths, filePath)
		lock.Unlock()
		Mem("recursionDeal：" + filePath)
		//return nil
		//})
	}
	_ = group.Wait()
	return recursionDeal(tmpPaths, dirName, lock)
}

func compareTwoFileObject(filePathBefore, filePathAfter, dirName string, By func(a, b interface{}) bool) (resultFilePath string, errRet error) {
	defer func() {
		os.Remove(filePathBefore)
		os.Remove(filePathAfter)
	}()
	fileBefore, _ := readObjectFromFile(filePathBefore)
	fileAfter, _ := readObjectFromFile(filePathAfter)
	resultFilePath = sha1s(strconv.Itoa(int(time.Now().UnixNano()))) + "_split_quicksort.txt"
	f, _ := os.OpenFile(dirName+"/"+resultFilePath, os.O_CREATE|os.O_RDWR|os.O_APPEND, os.ModeAppend|os.ModePerm)

	flag := 0
	flagResultAfter := 0
	for i := 0; i < len(fileBefore); i++ {
		tmp := fileBefore[i]

		for ai := flag; ai < len(fileAfter); ai++ {
			if flag+1 == len(fileAfter) {
				// fileAfter遍历完了
				break
			}
			if len(fileAfter) == ai+1 {
				// 最后赋值
				flag = ai
			}

			if By(tmp, fileAfter[ai]) {
				tmpJson, _ := json.Marshal(fileAfter[ai])
				f.WriteString(string(tmpJson) + "\n")
				flagResultAfter = ai
				continue
			}

			flag = ai
			break
		}

		tmpJson, _ := json.Marshal(tmp)
		f.WriteString(string(tmpJson) + "\n")
	}

	if fileAfter == nil {
		f.Close()
		return
	}

	if flagResultAfter < len(fileAfter) {
		flagResultAfter++
	}

	fileAfter = fileAfter[flagResultAfter:]
	for _, v := range fileAfter {
		tmpJson, _ := json.Marshal(v)
		f.WriteString(string(tmpJson) + "\n")
	}

	f.Close()
	return
}

// 读取文件中的数据,用于排序
func readObjectFromFile(filePath string) (users []interface{}, errRet error) {
	fileBefore, err := os.Open(filePath)
	defer fileBefore.Close()
	if err != nil {
		errRet = err
		return
	}

	brBefore := bufio.NewReader(fileBefore)
	for {
		a, _, c := brBefore.ReadLine()
		if c == io.EOF {
			break
		}
		if len(a) == 0 {
			continue
		}
		users = append(users, resolveObject(a))
	}

	if len(users) == 0 {
		return
	}

	QuickSortAll(users, 0, len(users)-1, SortBy)
	return
}

func Mem(msg string) {
	var m runtime.MemStats
	runtime.ReadMemStats(&m)
	fmt.Println(msg, "系统内存：", m.Sys, "   常驻内存：", m.HeapInuse, "    堆上分配的，gc后会归还： ", m.HeapAlloc)
}


// 对于两个排序好的文件,进行比较并存储
func compareTwoFileObjectForRecursion(filePathBefore, filePathAfter, dirName string, By func(a, b interface{}) bool) (resultFilePath string, errRet error) {

	resultFilePath = sha1s(strconv.Itoa(int(time.Now().UnixNano()))) + "_split_quicksort.txt"
	f, _ := os.OpenFile(dirName+"/"+resultFilePath, os.O_CREATE|os.O_RDWR|os.O_APPEND, os.ModeAppend|os.ModePerm)

	defer func() {
		os.Remove(filePathBefore)
		os.Remove(filePathAfter)
	}()
	fileBefore, err := os.Open(filePathBefore)
	defer fileBefore.Close()
	if err != nil {
		errRet = err
		return
	}
	brBefore := bufio.NewReader(fileBefore)

	fileAfter, err := os.Open(filePathAfter)
	defer fileAfter.Close()
	if err != nil {
		errRet = err
		return
	}
	brAfter := bufio.NewReader(fileAfter)

	fa := true
	fb := true
	var va, vb []byte

	for {
		var ca, cb error
		if fa {
			a, _, cae := brBefore.ReadLine()
			va = a
			ca = cae
		}

		if fb {
			b, _, cbe := brAfter.ReadLine()
			vb = b
			cb = cbe
		}

		if ca == io.EOF || cb == io.EOF {
			break
		}

		if len(va) == 0 {
			continue
		}

		if len(vb) == 0 {
			continue
		}

		bUser := User{}
		_ = json.Unmarshal(vb, &bUser)

		if By(resolveObject(va), resolveObject(vb)) {

			f.WriteString(string(vb) + "\n")
			fb = true
			fa = false
			continue
		} else {

			f.WriteString(string(va) + "\n")
			fa = true
			fb = false
			continue
		}
	}

	for {
		a, _, ca := brBefore.ReadLine()
		if ca == io.EOF {
			break
		}

		f.WriteString(string(a) + "\n")
		continue
	}

	for {
		b, _, ca := brBefore.ReadLine()
		if ca == io.EOF {
			break
		}

		f.WriteString(string(b) + "\n")
		continue
	}

	Mem(filePathBefore + "=====>" + filePathAfter)

	f.Close()
	return
}

// 自定义序列化对象
func resolveObject(a []byte) User {
	user := User{}
	_ = json.Unmarshal(a, &user)
	return user
}

// 自定义排序
func SortBy(a, b interface{}) bool {
	return a.(User).Age <= b.(User).Age //按照count排序
}

func sha1s(s string) string {
	r := sha1.Sum([]byte(s))
	return hex.EncodeToString(r[:])
}

注意事项:

主函数,这次的数据都是自己造的,实景就按照某某某来源来操作把.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func main() {
	dirName := "tmp_quick_sort" + time.Now().Format("2006_01_02_15_04_05")
	err2 := os.Mkdir(dirName, os.ModeAppend|os.ModePerm)
	if err2 != nil {
		return
	}
	f, err := os.OpenFile(dirName+"/0_split_quicksort.txt", os.O_CREATE|os.O_RDWR|os.O_APPEND, os.ModeAppend|os.ModePerm)
	if err != nil {
		fmt.Println(f)
	}
	t := time.Now().Unix()
	Mem("before write file")
	for i := 0; i < quicksort.Counter; i++ {
		auser := quicksort.User{
			Name:  strconv.Itoa(i),
			Age:   i,
			Count: rand.Intn(quicksort.Counter),
		}
		marshal, _ := json.Marshal(auser)

		f.Write(marshal)
		f.Write([]byte("\n"))
		if i%quicksort.SplitNum == 0 {
			f.Close()
			Mem(strconv.Itoa(i) + "after write file")
			f, err = os.OpenFile(dirName+"/"+strconv.Itoa(i)+"_split_quicksort.txt", os.O_CREATE|os.O_RDWR|os.O_APPEND, os.ModeAppend|os.ModePerm)
		}
	}
	f.Close()
	runtime.GC()
	Mem("after write file")

	fmt.Println("filename: ", quicksort.StartSort(dirName))

	fmt.Println(time.Now().Unix() - t)
	Mem("last msg")

	fmt.Println(unsafe.Sizeof([100000]quicksort.User{}))
}

结果到底是否如设计的那样可行呢?

内存打印的实际情况

后续改进

痛点:

  • 单个服务器,速度太慢
  • 单线程,有点慢「磁盘读写速度不快的,建议就使用单线程」
  • 没有断点「电」继续的机制.

改进方法:

  • 多服务器计算
  • 改进排序,单服务器可以分左右两部分
  • 增加任务记录机制,用于断点继续任务.

End