IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 游戏开发 -> 【golang/方法记录】有序列表的简易实现 -> 正文阅读

[游戏开发]【golang/方法记录】有序列表的简易实现

说在前面

  • go version:go1.14.1 windows/amd64

实现

  • 借助golang中的sort包可以方便的使用二分查找。
    func Search(n int, f func(int) bool) int {
    	// Define f(-1) == false and f(n) == true.
    	// Invariant: f(i-1) == false, f(j) == true.
    	i, j := 0, n
    	for i < j {
    		h := int(uint(i+j) >> 1) // avoid overflow when computing h
    		// i ≤ h < j
    		if !f(h) {
    			i = h + 1 // preserves f(i-1) == false
    		} else {
    			j = h // preserves f(j) == true
    		}
    	}
    	// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
    	return i
    }
    
  • 借助二分查找可以方便的实现有序列表。

代码

  • 例如有序的uint64切片

    func SeachUint64List(arr []uint64, x uint64) int {
    	return sort.Search(len(arr), func(i int) bool {
    		return arr[i] >= x
    	})
    }
    
    func InsertOrderedUint64List(arr []uint64, x uint64) []uint64 {
    	i := SeachUint64List(arr, x)
    
    	arr = append(arr, 0)
    	copy(arr[i+1:], arr[i:])
    	arr[i] = x
    
    	return arr
    }
    
    func main() {
    	var arr []uint64
    
    	arr = InsertOrderedUint64List(arr, 12)
    	arr = InsertOrderedUint64List(arr, 2)
    	arr = InsertOrderedUint64List(arr, 102)
    	arr = InsertOrderedUint64List(arr, 1)
    	arr = InsertOrderedUint64List(arr, 14542)
    	arr = InsertOrderedUint64List(arr, 112)
    	arr = InsertOrderedUint64List(arr, 142)
    
    	fmt.Println(arr)
    	// [1 2 12 102 112 142 14542]
    }
    
  • 其他的可以通过定义结构体,并使用Key进行排序,例如

    type Node struct {
    	Key   uint64
    	Value string
    }
    
    func SeachNodeList(arr []*Node, x uint64) int {
    	return sort.Search(len(arr), func(i int) bool {
    		return arr[i].Key >= x
    	})
    }
    
    func InsertOrderedNodeList(arr []*Node, x *Node) []*Node {
    	if x == nil {
    		return arr
    	}
    
    	i := SeachNodeList(arr, x.Key)
    
    	arr = append(arr, &Node{})
    	copy(arr[i+1:], arr[i:])
    	arr[i] = x
    
    	return arr
    }
    
    func main() {
    	var arr []*Node
    
    	arr = InsertOrderedNodeList(arr, &Node{Key: 12, Value: "ha"})
    	arr = InsertOrderedNodeList(arr, &Node{Key: 1432, Value: "ta"})
    	arr = InsertOrderedNodeList(arr, &Node{Key: 112, Value: "see"})
    	arr = InsertOrderedNodeList(arr, &Node{Key: 1452, Value: "sight"})
    	arr = InsertOrderedNodeList(arr, &Node{Key: 13332, Value: "peer"})
    	arr = InsertOrderedNodeList(arr, &Node{Key: 12, Value: "one"})
    	arr = InsertOrderedNodeList(arr, &Node{Key: 2, Value: "kiss"})
    
    	for _, node := range arr {
    		fmt.Println(*node)
    	}
    	
    	// {2 kiss}
    	// {12 one}
    	// {12 ha}
    	// {112 see}
    	// {1432 ta}
    	// {1452 sight}
    	// {13332 peer}
    }
    
  • 其他还可以进一步进行封装,例如写成package

  游戏开发 最新文章
6、英飞凌-AURIX-TC3XX: PWM实验之使用 GT
泛型自动装箱
CubeMax添加Rtthread操作系统 组件STM32F10
python多线程编程:如何优雅地关闭线程
数据类型隐式转换导致的阻塞
WebAPi实现多文件上传,并附带参数
from origin ‘null‘ has been blocked by
UE4 蓝图调用C++函数(附带项目工程)
Unity学习笔记(一)结构体的简单理解与应用
【Memory As a Programming Concept in C a
上一篇文章      下一篇文章      查看所有文章
加:2022-03-13 22:09:00  更:2022-03-13 22:09:35 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年5日历 -2024/5/25 13:36:22-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码