golang非算法手撕实现总结

1.交叉打印123

1.1 使用同步channel

package main

import (
	"fmt"
	"sync"
)

func main() {
	n := 5
	ch1 := make(chan struct{})
	ch2 := make(chan struct{})
	ch3 := make(chan struct{})
	var wg sync.WaitGroup
	wg.Add(3)

	go func() {
		defer wg.Done()
		for range ch1 {
			fmt.Print("1")
			ch2 <- struct{}{}
		}
		close(ch2)
	}()

	go func() {
		defer wg.Done()
		for range ch2 {
			fmt.Print("2")
			ch3 <- struct{}{}
		}
		close(ch3)
	}()

	go func() {
		defer wg.Done()
		for i := 0; i < n; i++ {
			<-ch3
			fmt.Print("3")
			if i == n-1 {
				close(ch1) // 安全地只关闭 ch1，触发所有退出
			} else {
				ch1 <- struct{}{}
			}
		}
	}()

	ch1 <- struct{}{} // 启动第一个
	wg.Wait()
	fmt.Println()
}

1.2 使用sync.cond

package main

import (
	"fmt"
	"sync"
)

func main() {
	var wg sync.WaitGroup
	mu := sync.Mutex{}
	cond := sync.NewCond(&mu)
	turn := 0 // 先打印 0

	// 启动 3 个 goroutine
	for i := 0; i < 3; i++ {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			for j := 0; j < 10; j++ {
				cond.L.Lock()
				for turn != i {
					cond.Wait()
				}
				fmt.Println(i)
				turn = (turn + 1) % 3
				cond.Broadcast()
				cond.L.Unlock()
			}
		}(i)
	}
	wg.Wait()
}

2.单例模式，懒汉饿汉

2.1 懒汉式，sync.Once

package main

import (
	"fmt"
	"sync"
)

var (
	lazySingletonInstance *Singleton
	lazySingletonOnce     sync.Once
)

type Singleton struct {
	name string
}

func getSingleton() *Singleton {
	lazySingletonOnce.Do(func() {
		lazySingletonInstance = &Singleton{
			name: "Singleton",
		}
	})
	return lazySingletonInstance
}

func main() {
	s1 := getSingleton()
	s2 := getSingleton()
	fmt.Printf("%p,%p", s1, s2)
}

2.2 饿汉式

package main

import "fmt"

var EagerSingelton = &Singleton{name: "singleton"}

type Singleton struct {
	name string
}

func getSingleton() *Singleton {
	return EagerSingelton
}
func main() {
	s1 := getSingleton()
	s2 := getSingleton()

	fmt.Printf("%p,%p", s1, s2)
}

3.限流算法

3.1 滑动窗口

package main

import (
	"fmt"
	"sync"
	"time"
)

type SlidingWindowLimiter struct {
	limit      int           // 最大请求数
	window     time.Duration // 窗口大小
	count      int           // 当前窗口计数
	lastWindow time.Time     // 当前窗口起始时间
	lock       sync.Mutex
}

func NewSlidingWindowLimiter(limit int, window time.Duration) *SlidingWindowLimiter {
	return &SlidingWindowLimiter{
		limit:      limit,
		window:     window,
		lastWindow: time.Now(),
	}
}

func (s *SlidingWindowLimiter) Allow() bool {
	s.lock.Lock()
	defer s.lock.Unlock()

	now := time.Now()
	if now.Sub(s.lastWindow) >= s.window {
		// 新窗口，重置计数
		s.count = 0
		s.lastWindow = now
	}

	if s.count >= s.limit {
		return false
	}

	s.count++
	return true
}

func main() {
	limiter := NewSlidingWindowLimiter(5, 2*time.Second) // 2秒最多5次
	for i := 1; i <= 15; i++ {
		if limiter.Allow() {
			fmt.Println(i, "允许")
		} else {
			fmt.Println(i, "限流")
		}
		time.Sleep(300 * time.Millisecond)
	}
}

3.2 令牌桶

package main

import (
	"fmt"
	"time"
)

var (
	ratePerSec = 2
	buckets    = make(chan struct{}, ratePerSec)
)

func main() {
	// 生成令牌
	go func() {
		ticker := time.NewTicker(time.Second / time.Duration(ratePerSec))
		for range ticker.C {
			select {
			case buckets <- struct{}{}:
			default:
				// 桶满就丢弃
			}
		}
	}()

	// 模拟请求
	for i := 0; i < 20; i++ {
		select {
		case <-buckets:
			fmt.Println(time.Now().Format("15:04:05.000"), "请求", i, "允许")
		default:
			fmt.Println(time.Now().Format("15:04:05.000"), "请求", i, "被限流")
		}
		time.Sleep(time.Millisecond * 300)
	}
}

3.3 漏桶

package main

import (
	"fmt"
	"sync"
	"time"
)

type leakyBucktes struct {
	cap      float64
	rate     float64
	current  float64
	lastTime time.Time
	lock     sync.Mutex
}

func NewLeakyBuckets(cap, rate float64) *leakyBucktes {
	return &leakyBucktes{
		cap:      cap,
		rate:     rate,
		lastTime: time.Now(),
	}
}
func (this *leakyBucktes) Allow() bool {
	fmt.Println(this.current)
	this.lock.Lock()
	defer this.lock.Unlock()

	elapsed := time.Now().Sub(this.lastTime).Seconds()
	leaked := elapsed * this.rate

	if this.current-float64(leaked) < 0 {
		this.current = 0
	} else {
		this.current -= float64(leaked)
	}
	this.lastTime = time.Now()

	if this.current < this.cap {
		this.current++
		return true
	} else {
		return false
	}
}
func main() {
	cap := 5.0
	rate := 2.0 // 每秒漏掉2个
	tick := 300 * time.Millisecond

	bucket := NewLeakyBuckets(cap, rate)
	for i := 0; i < 50; i++ {
		if bucket.Allow() {
			fmt.Printf("Allow %2d | current=%.2f\n", i, bucket.current)
		} else {
			fmt.Printf("Reject %2d | current=%.2f\n", i, bucket.current)
		}
		time.Sleep(tick)
	}
}

#手撕题#