编程知识 cdmana.com

Go programming pattern: Generic Programming

Go Linguistic 1.17 Version released , Generics are officially supported . Although there are some limitations ( such as , You can't put generic functions export), however , You can experience it . I'm in a 《Go Programming model 》 The series finally has real generic programming , There is no need to use reflection or go generation These difficult technologies . On the weekend , I put Go 1.17 download , then , Experienced generic programming , It's pretty good . below , Let's take a look at Go Generic programming for .( notes : however , If you don't understand the importance of generic programming , You can read the previous article first 《Go Programming model :Go Generation》, Then read again 《Go Programming model :MapReduce》)

This article is the second in the series 10 / 10 piece :Go Programming model

On

Let's start with a simple example :

package mainimport "fmt"func print[T any] (arr []T) {  for _, v := range arr {    fmt.Print(v)    fmt.Print(" ")  }  fmt.Println("")}func main() {  strs := []string{"Hello", "World",  "Generics"}  decs := []float64{3.14, 1.14, 1.618, 2.718 }  nums := []int{2,4,6,8}  print(strs)  print(decs)  print(nums)}

In the example above , There is one print() function , This function just wants to output the value of the array , Without generics , This function needs to write int edition ,float edition ,string edition , And our custom types (struct) Version of . Ok now , With the support of generics , We can use [T any] This way to declare a generic type ( It's kind of like C++ Of typename T), Then all the faces use T Just declare variables .

In the example above , We are generic print() Three types of adaptations are supported —— int type ,float64 type , and string type . To make this program run, you need to add... To the compilation line -gcflags=-G=3 Compile parameters ( This compilation parameter will be 1.18 On the version, it becomes the default parameter ), As shown below :

$ go run -gcflags=-G=3 ./main.go

After having an operation , We can write some standard algorithms , such as , A search algorithm

func find[T comparable] (arr []T, elem T) int {  for i, v := range arr {    if  v == elem {      return i    }  }  return -1}

We noticed that , We didn't use [T any] In the form of , But use [T comparable] In the form of ,comparable It's an interface type , It constrains our types to support == The operation of , Otherwise, there will be wrong type compilation errors . This one on top find() The function can also be used for int, float64 or string type .

From the above two small programs ,Go Language generics are basically available , It's just , There are three more questions :

  • One is fmt.Printf() The generic type in is %v Not good enough , Can not be like c++ iostream heavy load >> To get the output customized by the program .
  • The other is ,go Operator overloading is not supported , therefore , It's also hard for you to use in generic algorithms “ Generic operators ” Such as :==  etc.
  • The last one is , above find() The algorithm depends on “ Array ”, about hash-table、tree、graph、link And other data structures have to be rewritten . in other words , There is no one like C++ STL A generic iterator like that ( Part of this work, of course, also needs to be done through overloaded operators ( Such as :++ To achieve )

however , This is already very good , Let's see , What can I do .

data structure

Stack Stack

The biggest advantage of programming support for generics is that it can implement type independent data structures . below , We use it Slices This structure is used to implement a Stack Number structure of .

First , We can define a generic Stack

type stack [T any] []T

It looks simple , still [T any] , then []T It's an array , Next, there are various methods to implement this data structure . The following code implements push() ,pop(),top(),len(),print() Here are a few ways , These methods and C++ Of STL Medium Stack Is very similar .( notes : at present Go Generic functions of do not support export, So you can only use function names whose first character is lowercase )

func (s *stack[T]) push(elem T) {  *s = append(*s, elem)}func (s *stack[T]) pop() {  if len(*s) > 0 {    *s = (*s)[:len(*s)-1]  } }func (s *stack[T]) top() *T{  if len(*s) > 0 {    return &(*s)[len(*s)-1]  }   return nil}func (s *stack[T]) len() int{  return len(*s)}func (s *stack[T]) print() {  for _, elem := range *s {    fmt.Print(elem)    fmt.Print(" ")  }  fmt.Println("")}

The above example is relatively simple , But in the process of implementation , For one, if the stack is empty , that top() Or go back to error Or return a null value , Stuck in this place . because , Before , We return “ empty ” value , Or int Of 0, Or string Of “”, However, in generic T Next , This value is not easy to do . in other words , Except after type generics , There needs to be some more “ Generics of values ”( notes : stay C++ in , If you want to use an empty stack top() operation , You'll get one segmentation fault), therefore , Here we return a pointer , In this way, you can judge whether the pointer is empty .

Here's how to use this stack Code for .

func main() {  ss := stack[string]{}  ss.push("Hello")  ss.push("Hao")  ss.push("Chen")  ss.print()  fmt.Printf("stack top is - %v\n", *(ss.top()))  ss.pop()  ss.pop()  ss.print()    ns := stack[int]{}  ns.push(10)  ns.push(20)  ns.print()  ns.pop()  ns.print()  *ns.top() += 1  ns.print()  ns.pop()  fmt.Printf("stack top is - %v\n", ns.top())}

 

LinkList Double linked list

Let's look at the implementation of a two-way linked list . The following implementation implements Here are a few ways :

  • add() – Insert a data node from scratch
  • push() – Insert a data node from the tail
  • del() – Delete a node ( Because we need to compare , So we used compareable  The generic )
  • print() – Traverse a linked list from scratch , And output the value .
type node[T comparable] struct {  data T  prev *node[T]  next *node[T]}type list[T comparable] struct {  head, tail *node[T]  len int}func (l *list[T]) isEmpty() bool {  return l.head == nil && l.tail == nil}func (l *list[T]) add(data T) {  n := &node[T] {    data : data,    prev : nil,    next : l.head,  }  if l.isEmpty() {    l.head = n    l.tail = n  }  l.head.prev = n  l.head = n}func (l *list[T]) push(data T) {   n := &node[T] {    data : data,    prev : l.tail,    next : nil,  }  if l.isEmpty() {    l.head = n    l.tail = n  }  l.tail.next = n  l.tail = n}func (l *list[T]) del(data T) {   for p := l.head; p != nil; p = p.next {    if data == p.data {            if p == l.head {        l.head = p.next      }      if p == l.tail {        l.tail = p.prev      }      if p.prev != nil {        p.prev.next = p.next      }      if p.next != nil {        p.next.prev = p.prev      }      return     }  } }func (l *list[T]) print() {  if l.isEmpty() {    fmt.Println("the link list is empty.")    return   }  for p := l.head; p != nil; p = p.next {    fmt.Printf("[%v] -> ", p.data)  }  fmt.Println("nil")}

The above code is some more conventional linked list operations , Students who have learned linked list data structure should be familiar with , The code used is not difficult , As shown below , All very simple. , Just look at the code .

func main(){  var l = list[int]{}  l.add(1)  l.add(2)  l.push(3)  l.push(4)  l.add(5)  l.print() //[5] -> [2] -> [1] -> [3] -> [4] -> nil  l.del(5)  l.del(1)  l.del(4)  l.print() //[2] -> [3] -> nil  }

Functional paradigm

Next , Let's take a look at the three major pieces of our functional programming map()reduce() and filter() Prior to 《Go Programming model :Map-Reduce》 In the article , We can see that to implement such generics , Reflection is required , The code is too complex to read . Let's take a look at the real generic version .

Generic Map
func gMap[T1 any, T2 any] (arr []T1, f func(T1) T2) []T2 {  result := make([]T2, len(arr))  for i, elem := range arr {    result[i] = f(elem)  }  return result}

This one above map I used two types in the function – T1 and T2 ,

  • T1 – Is the type of data that needs to be processed
  • T2 – Is the processed data type

T1 and T2 It can be the same , It can be different .

We also have a function parameter –  func(T1) T2 signify , The entry is T1 Type of , Out came T2 Type of .

then , The whole function returns a []T2

well , Let's see how to use this map function :

nums := []int {0,1,2,3,4,5,6,7,8,9}squares := gMap(nums, func (elem int) int {  return elem * elem})print(squares)  //0 1 4 9 16 25 36 49 64 81 strs := []string{"Hao", "Chen", "MegaEase"}upstrs := gMap(strs, func(s string) string  {  return strings.ToUpper(s)})print(upstrs) // HAO CHEN MEGAEASE dict := []string{" zero ", " one ", " Ii. ", " 3 ", " boss ", " wu ", " lu ", " Retailer, ", "  ", " nine "}strs =  gMap(nums, func (elem int) string  {  return  dict[elem]})print(strs) //  zero   one   Ii.   3   boss   wu   lu   Retailer,      nine 
Generic Reduce

Next , Let's take a look at our Reduce function ,reduce The function is to synthesize a pile of data into a .

func gReduce[T1 any, T2 any] (arr []T1, init T2, f func(T2, T1) T2) T2 {  result := init  for _, elem := range arr {    result = f(result, elem)  }  return result}

The function is simple to implement , But it doesn't feel very elegant .

  • There are also two types T1 and T2, The former is the type of output data , The latter is the type of data exported .
  • Because to synthesize a data , So you need to have the initial value of this data init, yes T2 type
  • And custom functions func(T2, T1) T2, Will take this. init The value is passed to the user , Then the user returns after processing .

Here is an example of how to use —— Find the sum of an array

nums := []int {0,1,2,3,4,5,6,7,8,9}sum := gReduce(nums, 0, func (result, elem int) int  {    return result + elem})fmt.Printf("Sum = %d \n", sum)
Generic filter

filter Function is mainly used for filtering , Put some of the data that meet the conditions (filter in) Or it doesn't meet the conditions (filter out) Filter out the data , The following is a related code example

func gFilter[T any] (arr []T, in bool, f func(T) bool) []T {  result := []T{}  for _, elem := range arr {    choose := f(elem)    if (in && choose) || (!in && !choose) {      result = append(result, elem)    }  }  return result}func gFilterIn[T any] (arr []T, f func(T) bool) []T {  return gFilter(arr, true, f)}func gFilterOut[T any] (arr []T, f func(T) bool) []T {  return gFilter(arr, false, f)}

among , Users need to pick up from a bool Function of , We will send the data to the user , Then the user just needs to tell me whether it's OK or not , So we will return a filtered array to the user .

such as , We want to filter out all the odd numbers in the array

nums := []int {0,1,2,3,4,5,6,7,8,9}odds := gFilterIn(nums, func (elem int) bool  {    return elem % 2 == 1})print(odds)

Business examples

just as 《Go Programming model :Map-Reduce》 The business example in , Let's do it again here .

First , We first identify an employee object and related data

type Employee struct {  Name     string  Age      int  Vacation int  Salary   float32}var employees = []Employee{  {"Hao", 44, 0, 8000.5},  {"Bob", 34, 10, 5000.5},  {"Alice", 23, 5, 9000.0},  {"Jack", 26, 0, 4000.0},  {"Tom", 48, 9, 7500.75},  {"Marry", 29, 0, 6000.0},  {"Mike", 32, 8, 4000.3},}

then , We want to unify the salaries of all employees , We can use the previous reduce function

total_pay := gReduce(employees, 0.0, func(result float32, e Employee) float32 {  return result + e.Salary})fmt.Printf("Total Salary: %0.2f\n", total_pay) // Total Salary: 43502.05

We have this function gReduce The function is a little verbose , You also need to pass an initial value , In the user's own function , And care about result Let's define a better version .

Generally speaking , We use it reduce Most of the time, functions are basically statistical summation or several numbers , therefore , Can we define it more directly ? Like this CountIf(), It's better than the above Reduce It's a lot cleaner .

func gCountIf[T any](arr []T, f func(T) bool) int {  cnt := 0  for _, elem := range arr {    if f(elem) {      cnt += 1    }  }  return cnt;}

We do summation , We can also write a Sum The generic .

  • Handle T Data of type , return U Result of type
  • then , The user only needs to give me one that needs statistics T Of U Type of data is OK .

The code is as follows :

type Sumable interface {  type int, int8, int16, int32, int64,        uint, uint8, uint16, uint32, uint64,        float32, float64}func gSum[T any, U Sumable](arr []T, f func(T) U) U {  var sum U  for _, elem := range arr {    sum += f(elem)  }  return sum}

In the above code, we used a called Sumable The interface of , It defines U type , Can only be Sumable The types in , That is, integer or floating point , This support can make our generic code more robust .

therefore , We can do the following .

1) Statistical age is greater than 40 Number of employees aged

old := gCountIf(employees, func (e Employee) bool  {    return e.Age > 40})fmt.Printf("old people(>40): %d\n", old) // ld people(>40): 2

2) Statistics show that the salary exceeds 6000 The number of employees of yuan

high_pay := gCountIf(employees, func(e Employee) bool {  return e.Salary >= 6000})fmt.Printf("High Salary people(>6k): %d\n", high_pay) //High Salary people(>6k): 4

3) The statistical age is less than 30 The salary of a - year-old employee

younger_pay := gSum(employees, func(e Employee) float32 {  if e.Age < 30 {      return e.Salary  }   return 0})fmt.Printf("Total Salary of Young People: %0.2f\n", younger_pay)//Total Salary of Young People: 19000.00

4) Count the vacation days of all employees

total_vacation := gSum(employees, func(e Employee) int {  return e.Vacation})fmt.Printf("Total Vacation: %d day(s)\n", total_vacation)//Total Vacation: 32 day(s)

5) Filter out employees without vacation

no_vacation := gFilterIn(employees, func(e Employee) bool {  return e.Vacation == 0})print(no_vacation)//{Hao 44 0 8000.5} {Jack 26 0 4000} {Marry 29 0 6000}

What about? , You probably understand the meaning of generic programming .

( The full text after )


Focus on CoolShell Wechat public account and wechat applet

( Please indicate the author and source of this article cool shell – CoolShell , Do not use for any commercial purpose )

——=== visit Cool shell 404 page Looking for lost children . ===——
Loading...

版权声明
本文为[Cool shell]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/09/20210909130416494f.html

Scroll to Top