-
前言在数据结构和算法中,红黑树(Red-Black Tree)是一种自平衡的二叉搜索树,它在保证数据有序的同时,也保证了树的平衡性,从而提高了搜索、插入和删除操作的效率。下面我们将深入探讨红黑树的定义、与二叉树的区别、以及它的用途,并通过一个例子来加深理解。红黑树的定义红黑树是一种特殊的二叉搜索树,它在每个节点上附加一个颜色属性,可以是红色或黑色。红黑树需要满足以下五个性质(也称为“红黑性质”):每个节点要么是红色,要么是黑色。根节点是黑色。每个叶节点(NIL或空节点)是黑色。如果一个节点是红色的,则它的两个子节点都是黑色的(从每个叶子到根的所有路径上不能有两个连续的红色节点)。对于每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。这些性质确保了红黑树的平衡性,使得在插入、删除等操作时,树的高度能够保持在对数级别,从而保证了操作的效率。红黑树与二叉树的区别二叉树是一种简单的数据结构,每个节点最多有两个子节点(通常称为左子节点和右子节点)。然而,二叉树并不保证树的平衡性,这可能导致在插入或删除节点后,树的高度急剧增加,从而降低了搜索、插入和删除操作的效率。相比之下,红黑树通过引入颜色属性和红黑性质,保证了树的平衡性。在插入或删除节点时,红黑树会进行一系列旋转和重新着色操作,以保持树的平衡性。这些操作保证了红黑树的高度始终保持在对数级别,从而保证了操作的效率。红黑树的用途红黑树在许多场景中都有广泛的应用,包括但不限于:关联数组:红黑树可以用作一种关联数组,其中键存储在每个节点中,并且节点的颜色用于维护树的平衡。这种数据结构允许在O(log n)的时间内进行搜索、插入和删除操作。内存管理:在操作系统中,红黑树可以用于管理内存分配和释放。通过将内存块表示为红黑树的节点,并使用红黑性质来维护树的平衡性,操作系统可以在O(log n)的时间内找到可用的内存块或释放已使用的内存块。路由表:在计算机网络中,路由器使用路由表来决定数据包的转发路径。由于路由表需要频繁地进行更新和查找操作,因此使用红黑树来存储路由表可以提高这些操作的效率。例子:使用红黑树实现有序集合假设我们有一个有序集合,需要支持插入、删除和查找操作。由于红黑树具有自动排序和平衡的特性,因此它非常适合用于实现这样的有序集合。以下是一个简单的Python示例,使用红黑树(通过Python内置的collections.OrderedDict实现,尽管它不是纯粹的红黑树实现,但提供了类似的功能)来实现有序集合:from collections import OrderedDict class OrderedSet: def __init__(self): self._dict = OrderedDict() def add(self, item): self._dict[item] = True def remove(self, item): if item in self._dict: del self._dict[item] def __contains__(self, item): return item in self._dict def __iter__(self): return iter(self._dict) def __len__(self): return len(self._dict) # 使用示例 s = OrderedSet() s.add(3) s.add(1) s.add(4) s.add(1) # 重复添加不会改变集合 print(s) # 输出:OrderedDict([(1, True), (3, True), (4, True)]) print(3 in s) # 输出:True s.remove(3) print(s) # 输出:OrderedDict([(1, True), (4, True)])虽然这个示例中使用了OrderedDict而不是纯粹的红黑树实现,但它展示了红黑树在有序集合中的应用。在实际应用中,我们可以使用更高效的红黑树库来实现类似的功能。
-
Bitmap:说明:采用一个bit来标记某个value,可以节省存储空间。优点是占用内存少,比如N为一亿(10000 0000),只需要N/8=1250 0000个byte,约等于12Mb。缺点为不能重复数据进行排序和查找思想:利用一个byte中的8个bit来表示8个数。某数出现,利用映射将对应bit位置1。比如元素3,在8bit的映射为:00010000再来个元素5,在8bit的映射为:00010100映射表为:A[0]->0~7;A[1]->8~15;A[2]->16~23;…….具体实现:(例子为32位)#include #define BITSPERWORD 32#define SHIFT 5#define MASK 0x1F//#define N 10000000#define N 100 int a[1 + N/BITSPERWORD];//申请内存的大小 void set(int i) {// a[i>>SHIFT] |= (1<<(i& MASK)); a[i/BITSPERWORD] |= (0x01<<(i%BITSPERWORD));}//clr 初始化所有的bit位为0void clr(int i) {// a[i>>SHIFT] &= ~(1<<(i & MASK)); a[i/BITSPERWORD] &= ~(0x01<<(i%BITSPERWORD));}//test 测试所在的bit为是否为1int test(int i){ return a[i>>SHIFT] & (0x01<<(i & MASK));} int main(){ int i; for (i = 0; i < N; i++) clr(i); for(i=0;ia[i/BITSPERWORD]或a[i>>SHIFT],实现i/32,即求出操作bit所在数的下标。0x01<<(i%BITSPERWORD)或(1<<(i& MASK)),取得该操作bit的具体位置。 实例: 1、 已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。 思路:8位数,0000 0000~9999 9999,范围为一亿。需要10^8个bit,12M左右字节。 实现: int const nArraySize = 100000000 /(sizeof(int)*8) + 1;int Bitmap[nArraySize];void MapPhoneNumberToBit(int nNumber){ Bitmap[nNumber/ (8*sizeof(int))] |= 0x00000001<<(nNumber%(8*sizeof(int)));} 2、2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。思路:用两个bit来表示一个数。0表示整数未出现,1表示出现一次,2表示出现多次。在遍历这些数的时候,如果对应位置的值是0,则将其置为1;如果是1,将其置为2;如果是2,则保持不变。注意控制与置位的分离。 实现#include unsigned char flags[1000]; //数组大小自定义 unsigned get_val(int idx) { // | 8 bit | // |00 00 00 00| //映射3 2 1 0 // |00 00 00 00| //表示7 6 5 4 // …… // |00 00 00 00| int i = idx/4; //一个char 表示4个数, int j = idx%4; unsigned ret = (flags[i]&(0x3<<(2*j)))>>(2*j); //0x3是0011 j的范围为0-3,因此0x3<<(2*j)范围为00000011到11000000 如idx=7 i=1 ,j=3 那么flags[1]&11000000, 得到的是|00 00 00 00| //表示7 6 5 4 return ret; } unsigned set_val(int idx, unsigned int val) { int i = idx/4; int j = idx%4; unsigned tmp = (flags[i]&~((0x3<<(2*j))&0xff)) | (((val%4)<<(2*j))&0xff); flags[i] = tmp; return 0; } unsigned add_one(int idx) { if (get_val(idx)>=2) { //这一位置上已经出现过了?? return 1; } else { set_val(idx, get_val(idx)+1); return 0; } } //只测试非负数的情况; //假如考虑负数的话,需增加一个2-Bitmap数组. int a[]={1, 3, 5, 7, 9, 1, 3, 5, 7, 1, 3, 5,1, 3, 1,10,2,4,6,8,0}; int main() { int i; memset(flags, 0, sizeof(flags)); printf("原数组为:"); for(i=0;i < sizeof(a)/sizeof(int); ++i) { printf("%d ", a[i]); add_one(a[i]); } printf("\r\n"); printf("只出现过一次的数:"); for(i=0;i < 100; ++i) { if(get_val(i) == 1) printf("%d ", i); } printf("\r\n"); return 0; } 3、给你一个文件,里面包含40亿个整数,写一个算法找出该文件中不包含的一个整数, 假设你有1GB内存可用。如果你只有10MB的内存呢?思路:40亿个整数(40*10^8*4byte~16GB)。A、 内存为1G显然无法将16G的数据直接放入1G内存,采用bitmap算法,40*10^8bit= 0.5G(大约),满足1G的内存。B、 内存为10M如果我们只有10MB的内存,明显使用BitMap也无济于事了。 内存这么小,注定只能分块处理。比如分块的大小是1000,那么第1块的范围就是0到999,第2块的范围就是1000 到1999……实际上并不保存这些数,而是给每一个块设置一个计数器。 这样每读入一个数,就在它所在的块对应的计数器加1。处理结束之后,我们找到一个块,它的计数器值小于块大小(1000),说明了这一段里面一定有数字是文件中所不包含的。然后我们单独处理这个块即可。
-
快排是一种使用广泛的排序,它比merge需要的空间更小,而且改进过的快排速度很快,平均O(nlgn)。快排也用到了递归的思想,所以我才说递归很重要的嘛。我们大概看一下快排的基本过程:选择一个数,把小于它的放左边,不小于它的放右边。没了。那么很显然,这个算法的特点和难点就是“怎么选出一个合适的点”和“怎么实现‘放’”。选择肯定是超重要的,还记得上一节的“递归树”吗,如果采用“二路归并”,在这里就是分为2个序列,那么最好是把分开的点选在中间,因为树高是通过最长路径来计算的。另一个问题就是怎么实现这个“通过一个点把比它小的全放左边比它大的全放右边”。我们大概可以这样做:一个flag从最左端开始移动,一个flag从最右端开始移动,当碰到一个左侧的点大于被选择点,并且一个右侧的点小于被选择的点时,交换它们。当然,在执行的时候我们可以把选中的那个点放在数组的最右边,当然也可以不动,比如我们直接选择最左端和最右端的点当作我们的判断点。那么我们来实现一哈://先实现一下主函数template <typename T>void QuickSort( T a[ ], int n ){ if (n <= 1) return; Qsort( a, 0, n-1 );} //是的,这就完了哈哈,我们赶紧来实现一哈核心功能Qsort():template <typename T>void Qsort( T a[ ], int Left, int Right ){ if ( Left >= Right) //说明已经不能再divide了 return; int i = Left, j = Right; T pivot = a[ Left ]; //选最左端点为pivot while ( i < j ) { while ( i < j && a[ j ] >= pivot ) //这里需要 i < j 为了控制不过界 --j; //当a[ j ]比pivot大时,继续递减,直到减到不满足条件 a[ i ] = a[ j ]; //把 j 位置上的值赋给 i ,而第一个i正是pivot while ( i < j && a[i] >= pivot ) ++i; a[ j ] = a[ i ]; //继上,把这个i赋给j上一次的位置,很巧妙吧 } a[ i ] = pivot; Qsort( a, Left, i - 1 ); Qsort( a, i + 1, Right ); //分别去i-1和i+1,跳过i}简单分析一下,1)为什么要从j开始计算呢?因为我们把pivot设在了最左端,这个位置一定要当作第一个被交换的位置,才能保证程序的顺利运行(所以如果pivot在最右端,你会了吗?)。2)为什么最后是a[ i ] = pivot;结尾呢?很简单,回到程序,我们先从j计算,再计算i的移动,那么很显然是把i的位置和pivot交换啊~~不过,正如很多书上所说(就当是吧),因为现实中很多序列并不是完全无序的,取第一个比较冒险,有可能出现最差解,所以有以下2种取法:1.随机(我感觉挺好的,他们说计算量耗费大)。2.3数取中值:就是第1,最后,中间3个元素取他们的中值作为pivot。实现方法很简单:void mid3( T a[], int L, int R ){ int C = ( L + R ) / 2; if ( a[ L ] > a[ C ] ) swap( a[ C ], a[ L ] ); if ( a[ C ] > a[ R ] ) swap( a[ C ], a[ R ] ); if ( a[ R ] > a[ L ] ) swap( a[ R ], a[ L ] ); swap( a[ C ], a[ Left + 1 ] ); return a[ Left + 1 ] ;}先讲结果:分别把左中右3个数排序,然后把中数放到第2个位置。当然调用的时候也需稍作调整,此处不再赘述。一个不需要注意的地方是:这3个数比较并无特别的规则,只需要两两比较就好了(C32=3而已)。时间复杂度我就不证了,最坏是O(n2),当每次pivot都取第一个的时候。堆排序我们先不讲了,等到聊到优先队列的时候再说吧。那么,我们第一个话题似乎就结束了~~BTW,你有没有觉得用c++写这段代码好多啊,要不然,我们用python大概写一下?def qsort(a): if len(a) <= 1: return a pivot = a[len(a)//2] # 使用py3.x,2.x的话不需要// left = [x for x in a if x < pivot] mid = [x for x in a if x == pivot] right = [x for x in a if x > pivot] return qsort(left) + mid + qsort(right) # 已经实现一次划分了是不是有点恐怖,这么复杂的算法,仅仅不到10行······补充一个Python版普通实现:def quick_sort(array, l, r): if l < r: q = partition(array, l, r) quick_sort(array, l, q - 1) quick_sort(array, q + 1, r) def partition(array, l, r): x = array[r] i = l - 1 for j in range(l, r): if array[j] <= x: i += 1 array[i], array[j] = array[j], array[i] array[i + 1], array[r] = array[r], array[i+1] return i + 1作者:吃个小烧饼链接:https://www.jianshu.com/p/bad507d62f08来源:简书著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
-
-
使用HashSet判断主键是否存在 HashSet 实现 Set 接口,由哈希表(实际上是 HashMap )实现,但不保证 set 的迭代顺序,并允许使用 null 元素。HashSet 的时间复杂度跟 HashMap 一致,如果没有哈希冲突则时间复杂度为 O(1) ,如果存在哈希冲突则时间复杂度不超过 O(n) 。所以,在日常编码中,可以使用 HashSet 判断主键是否存在。 案例:给定一个字符串(不一定全为字母),请返回第一个重复出现的字符。 /** 查找第一个重复字符 */ public static char findFirstRepeatedChar(String string) { // 检查空字符串 if (Objects.isNull(string) || string.isEmpty()) { return null; } // 查找重复字符 char[] charArray = string.toCharArray(); Set charSet = new HashSet<>(charArray.length); for (char ch : charArray) { if (charSet.contains(ch)) { return ch; } charSet.add(ch); } // 默认返回为空 return null; } 复制 其中,由于 Set 的 add 函数有个特性——如果添加的元素已经再集合中存在,则会返回 false 。可以简化代码为: if (!charSet.add(ch)) { return ch; } 复制 使用HashMap存取键值映射关系 简单来说,HashMap 由数组和链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的。如果定位到的数组位置不含链表,那么查找、添加等操作很快,仅需一次寻址即可,其时间复杂度为 O(1) ;如果定位到的数组包含链表,对于添加操作,其时间复杂度为 O(n) ——首先遍历链表,存在即覆盖,不存在则新增;对于查找操作来讲,仍需要遍历链表,然后通过key对象的 equals 方法逐一对比查找。从性能上考虑, HashMap 中的链表出现越少,即哈希冲突越少,性能也就越好。所以,在日常编码中,可以使用 HashMap 存取键值映射关系。 案例:给定菜单记录列表,每条菜单记录中包含父菜单标识(根菜单的父菜单标识为 null ),构建出整个菜单树。 /** 菜单DO类 */ @Setter @Getter @ToString public static class MenuDO { /** 菜单标识 */ private Long id; /** 菜单父标识 */ private Long parentId; /** 菜单名称 */ private String name; /** 菜单链接 */ private String url; } /** 菜单VO类 */ @Setter @Getter @ToString public static class MenuVO { /** 菜单标识 */ private Long id; /** 菜单名称 */ private String name; /** 菜单链接 */ private String url; /** 子菜单列表 */ private List<MenuVO> childList; } /** 构建菜单树函数 */ public static List<MenuVO> buildMenuTree(List<MenuDO> menuList) { // 检查列表为空 if (CollectionUtils.isEmpty(menuList)) { return Collections.emptyList(); } // 依次处理菜单 int menuSize = menuList.size(); List<MenuVO> rootList = new ArrayList<>(menuSize); Map<Long, MenuVO> menuMap = new HashMap<>(menuSize); for (MenuDO menuDO : menuList) { // 赋值菜单对象 Long menuId = menuDO.getId(); MenuVO menu = menuMap.get(menuId); if (Objects.isNull(menu)) { menu = new MenuVO(); menu.setChildList(new ArrayList<>()); menuMap.put(menuId, menu); } menu.setId(menuDO.getId()); menu.setName(menuDO.getName()); menu.setUrl(menuDO.getUrl()); // 根据父标识处理 Long parentId = menuDO.getParentId(); if (Objects.nonNull(parentId)) { // 构建父菜单对象 MenuVO parentMenu = menuMap.get(parentId); if (Objects.isNull(parentMenu)) { parentMenu = new MenuVO(); parentMenu.setId(parentId); parentMenu.setChildList(new ArrayList<>()); menuMap.put(parentId, parentMenu); } // 添加子菜单对象 parentMenu.getChildList().add(menu); } else { // 添加根菜单对象 rootList.add(menu); } } // 返回根菜单列表 return rootList; } 复制 使用 ThreadLocal 存储线程专有对象 ThreadLocal 提供了线程专有对象,可以在整个线程生命周期中随时取用,极大地方便了一些逻辑的实现。 常见的 ThreadLocal 用法主要有两种: 1、保存线程上下文对象,避免多层级参数传递; 2、保存非线程安全对象,避免多线程并发调用。 保存线程上下文对象,避免多层级参数传递 这里,以 PageHelper 插件的源代码中的分页参数设置与使用为例说明。 设置分页参数代码: /** 分页方法类 */ public abstract class PageMethod { /** 本地分页 */ protected static final ThreadLocal<Page> LOCAL_PAGE = new ThreadLocal<Page>(); /** 设置分页参数 */ protected static void setLocalPage(Page page) { LOCAL_PAGE.set(page); } /** 获取分页参数 */ public static <T> Page<T> getLocalPage() { return LOCAL_PAGE.get(); } /** 开始分页 */ public static <E> Page<E> startPage(int pageNum, int pageSize, boolean count, Boolean reasonable, Boolean pageSizeZero) { Page<E> page = new Page<E>(pageNum, pageSize, count); page.setReasonable(reasonable); page.setPageSizeZero(pageSizeZero); Page<E> oldPage = getLocalPage(); if (oldPage != null && oldPage.isOrderByOnly()) { page.setOrderBy(oldPage.getOrderBy()); } setLocalPage(page); return page; } } 复制 使用分页参数代码: /** 虚辅助方言类 */ public abstract class AbstractHelperDialect extends AbstractDialect implements Constant { /** 获取本地分页 */ public <T> Page<T> getLocalPage() { return PageHelper.getLocalPage(); } /** 获取分页SQL */ @Override public String getPageSql(MappedStatement ms, BoundSql boundSql, Object parameterObject, RowBounds rowBounds, CacheKey pageKey) { String sql = boundSql.getSql(); Page page = getLocalPage(); String orderBy = page.getOrderBy(); if (StringUtil.isNotEmpty(orderBy)) { pageKey.update(orderBy); sql = OrderByParser.converToOrderBySql(sql, orderBy); } if (page.isOrderByOnly()) { return sql; } return getPageSql(sql, page, pageKey); } ... } 复制 使用分页插件代码: /** 查询用户函数 */ public PageInfo<UserDO> queryUser(UserQuery userQuery, int pageNum, int pageSize) { PageHelper.startPage(pageNum, pageSize); List<UserDO> userList = userDAO.queryUser(userQuery); PageInfo<UserDO> pageInfo = new PageInfo<>(userList); return pageInfo; } 复制 如果要把分页参数通过函数参数逐级传给查询语句,除非修改 MyBatis 相关接口函数,否则是不可能实现的。 保存非线程安全对象,避免多线程并发调用 在写日期格式化工具函数时,首先想到的写法如下: /** 日期模式 */ private static final String DATE_PATTERN = "yyyy-MM-dd"; /** 格式化日期函数 */ public static String formatDate(Date date) { return new SimpleDateFormat(DATE_PATTERN).format(date); } 复制 其中,每次调用都要初始化 DateFormat 导致性能较低,把 DateFormat 定义成常量后的写法如下: /** 日期格式 */ private static final DateFormat DATE_FORMAT = new SimpleDateFormat("yyyy-MM-dd"); /** 格式化日期函数 */ public static String formatDate(Date date) { return DATE_FORMAT.format(date); } 复制 由于 SimpleDateFormat 是非线程安全的,当多线程同时调用 formatDate 函数时,会导致返回结果与预期不一致。如果采用 ThreadLocal 定义线程专有对象,优化后的代码如下: /** 本地日期格式 */ private static final ThreadLocal<DateFormat> LOCAL_DATE_FORMAT = new ThreadLocal<DateFormat>() { @Override protected DateFormat initialValue() { return new SimpleDateFormat("yyyy-MM-dd"); } }; /** 格式化日期函数 */ public static String formatDate(Date date) { return LOCAL_DATE_FORMAT.get().format(date); } 复制 这是在没有线程安全的日期格式化工具类之前的实现方法。在 JDK8 以后,建议使用 DateTimeFormatter 代替 SimpleDateFormat ,因为 SimpleDateFormat 是线程不安全的,而 DateTimeFormatter 是线程安全的。当然,也可以采用第三方提供的线程安全日期格式化函数,比如 apache 的 DateFormatUtils 工具类。 注意:ThreadLocal 有一定的内存泄露的风险,尽量在业务代码结束前调用 remove 函数进行数据清除。 使用 Pair 实现成对结果的返回 在 C/C++ 语言中, Pair (对)是将两个数据类型组成一个数据类型的容器,比如 std::pair 。 Pair 主要有两种用途: 1、把 key 和 value 放在一起成对处理,主要用于 Map 中返回名值对,比如 Map 中的 Entry 类; 2、当一个函数需要返回两个结果时,可以使用 Pair 来避免定义过多的数据模型类。 第一种用途比较常见,这里主要说明第二种用途。 定义模型类实现成对结果的返回 函数实现代码: /** 点和距离类 */ @Setter @Getter @ToString @AllArgsConstructor public static class PointAndDistance { /** 点 */ private Point point; /** 距离 */ private Double distance; } /** 获取最近点和距离 */ public static PointAndDistance getNearestPointAndDistance(Point point, Point[] points) { // 检查点数组为空 if (ArrayUtils.isEmpty(points)) { return null; } // 获取最近点和距离 Point nearestPoint = points[0]; double nearestDistance = getDistance(point, points[0]); for (int i = 1; i < points.length; i++) { double distance = getDistance(point, point[i]); if (distance < nearestDistance) { nearestDistance = distance; nearestPoint = point[i]; } } // 返回最近点和距离 return new PointAndDistance(nearestPoint, nearestDistance); } 复制 函数使用案例: Point point = ...; Point[] points = ...; PointAndDistance pointAndDistance = getNearestPointAndDistance(point, points); if (Objects.nonNull(pointAndDistance)) { Point point = pointAndDistance.getPoint(); Double distance = pointAndDistance.getDistance(); ... } 复制 使用 Pair 类实现成对结果的返回 在 JDK 中,没有提供原生的 Pair 数据结构,也可以使用 Map::Entry 代替。不过, Apache 的 commons-lang3 包中的 Pair 类更为好用,下面便以 Pair 类进行举例说明。 函数实现代码: /** 获取最近点和距离 */ public static Pair<Point, Double> getNearestPointAndDistance(Point point, Point[] points) { // 检查点数组为空 if (ArrayUtils.isEmpty(points)) { return null; } // 获取最近点和距离 Point nearestPoint = points[0]; double nearestDistance = getDistance(point, points[0]); for (int i = 1; i < points.length; i++) { double distance = getDistance(point, point[i]); if (distance < nearestDistance) { nearestDistance = distance; nearestPoint = point[i]; } } // 返回最近点和距离 return Pair.of(nearestPoint, nearestDistance); } 复制 函数使用案例: Point point = ...; Point[] points = ...; Pair<Point, Double> pair = getNearestPointAndDistance(point, points); if (Objects.nonNull(pair)) { Point point = pair.getLeft(); Double distance = pair.getRight(); ... } 复制 定义 Enum 类实现取值和描述 在 C++、Java 等计算机编程语言中,枚举类型(Enum)是一种特殊数据类型,能够为一个变量定义一组预定义的常量。在使用枚举类型的时候,枚举类型变量取值必须为其预定义的取值之一。 用 class 关键字实现的枚举类型 在 JDK5 之前, Java 语言不支持枚举类型,只能用类(class)来模拟实现枚举类型。 /** 订单状态枚举 */ public final class OrderStatus { /** 属性相关 */ /** 状态取值 */ private final int value; /** 状态描述 */ private final String description; /** 常量相关 */ /** 已创建(1) */ public static final OrderStatus CREATED = new OrderStatus(1, "已创建"); /** 进行中(2) */ public static final OrderStatus PROCESSING = new OrderStatus(2, "进行中"); /** 已完成(3) */ public static final OrderStatus FINISHED = new OrderStatus(3, "已完成"); /** 构造函数 */ private OrderStatus(int value, String description) { this.value = value; this.description = description; } /** 获取状态取值 */ public int getValue() { return value; } /** 获取状态描述 */ public String getDescription() { return description; } } 复制 用 enum 关键字实现的枚举类型 JDK5 提供了一种新的类型—— Java 的枚举类型,关键字 enum 可以将一组具名的值的有限集合创建为一种新的类型,而这些具名的值可以作为常量使用,这是一种非常有用的功能。 /** 订单状态枚举 */ public enum OrderStatus { /** 常量相关 */ /** 已创建(1) */ CREATED(1, "已创建"), /** 进行中(2) */ PROCESSING(2, "进行中"), /** 已完成(3) */ FINISHED(3, "已完成"); /** 属性相关 */ /** 状态取值 */ private final int value; /** 状态描述 */ private final String description; /** 构造函数 */ private OrderStatus(int value, String description) { this.value = value; this.description = description; } /** 获取状态取值 */ public int getValue() { return value; } /** 获取状态描述 */ public String getDescription() { return description; } } 复制 其实,Enum 类型就是一个语法糖,编译器帮我们做了语法的解析和编译。通过反编译,可以看到 Java 枚举编译后实际上是生成了一个类,该类继承了 java.lang.Enum<E> ,并添加了 values()、valueOf() 等枚举类型通用方法。 定义 Holder 类实现参数的输出 在很多语言中,函数的参数都有输入(in)、输出(out)和输入输出(inout)之分。在 C/C++ 语言中,可以用对象的引用(&)来实现函数参数的输出(out)和输入输出(inout)。但在 Java 语言中,虽然没有提供对象引用类似的功能,但是可以通过修改参数的字段值来实现函数参数的输出(out)和输入输出(inout)。这里,我们叫这种输出参数对应的数据结构为Holder(支撑)类。 Holder 类实现代码: /** 长整型支撑类 */ @Getter @Setter @ToString public class LongHolder { /** 长整型取值 */ private long value; /** 构造函数 */ public LongHolder() {} /** 构造函数 */ public LongHolder(long value) { this.value = value; } } 复制 Holder 类使用案例: /** 静态常量 */ /** 页面数量 */ private static final int PAGE_COUNT = 100; /** 最大数量 */ private static final int MAX_COUNT = 1000; /** 处理过期订单 */ public void handleExpiredOrder() { LongHolder minIdHolder = new LongHolder(0L); for (int pageIndex = 0; pageIndex < PAGE_COUNT; pageIndex++) { if (!handleExpiredOrder(pageIndex, minIdHolder)) { break; } } } /** 处理过期订单 */ private boolean handleExpiredOrder(int pageIndex, LongHolder minIdHolder) { // 获取最小标识 Long minId = minIdHolder.getValue(); // 查询过期订单(按id从小到大排序) List<OrderDO> orderList = orderDAO.queryExpired(minId, MAX_COUNT); if (CollectionUtils.isEmpty(taskTagList)) { return false; } // 设置最小标识 int orderSize = orderList.size(); minId = orderList.get(orderSize - 1).getId(); minIdHolder.setValue(minId); // 依次处理订单 for (OrderDO order : orderList) { ... } // 判断还有订单 return orderSize >= PAGE_SIZE; } 复制 其实,可以实现一个泛型支撑类,适用于更多的数据类型。 定义 Union 类实现数据体的共存 在 C/C++ 语言中,联合体(union),又称共用体,类似结构体(struct)的一种数据结构。联合体(union)和结构体(struct)一样,可以包含很多种数据类型和变量,两者区别如下: 1、结构体(struct)中所有变量是“共存”的,同时所有变量都生效,各个变量占据不同的内存空间; 2、联合体(union)中是各变量是“互斥”的,同时只有一个变量生效,所有变量占据同一块内存空间。 当多个数据需要共享内存或者多个数据每次只取其一时,可以采用联合体(union)。 在Java语言中,没有联合体(union)和结构体(struct)概念,只有类(class)的概念。众所众知,结构体(struct)可以用类(class)来实现。其实,联合体(union)也可以用类(class)来实现。但是,这个类不具备“多个数据需要共享内存”的功能,只具备“多个数据每次只取其一”的功能。 这里,以微信协议的客户消息为例说明。根据我多年来的接口协议封装经验,主要有以下两种实现方式。 使用函数方式实现 Union Union 类实现: /** 客户消息类 */ @ToString public class CustomerMessage { /** 属性相关 */ /** 消息类型 */ private String msgType; /** 目标用户 */ private String toUser; /** 共用体相关 */ /** 新闻内容 */ private News news; ... /** 常量相关 */ /** 新闻消息 */ public static final String MSG_TYPE_NEWS = "news"; ... /** 构造函数 */ public CustomerMessage() {} /** 构造函数 */ public CustomerMessage(String toUser) { this.toUser = toUser; } /** 构造函数 */ public CustomerMessage(String toUser, News news) { this.toUser = toUser; this.msgType = MSG_TYPE_NEWS; this.news = news; } /** 清除消息内容 */ private void removeMsgContent() { // 检查消息类型 if (Objects.isNull(msgType)) { return; } // 清除消息内容 if (MSG_TYPE_NEWS.equals(msgType)) { news = null; } else if (...) { ... } msgType = null; } /** 检查消息类型 */ private void checkMsgType(String msgType) { // 检查消息类型 if (Objects.isNull(msgType)) { throw new IllegalArgumentException("消息类型为空"); } // 比较消息类型 if (!Objects.equals(msgType, this.msgType)) { throw new IllegalArgumentException("消息类型不匹配"); } } /** 设置消息类型函数 */ public void setMsgType(String msgType) { // 清除消息内容 removeMsgContent(); // 检查消息类型 if (Objects.isNull(msgType)) { throw new IllegalArgumentException("消息类型为空"); } // 赋值消息内容 this.msgType = msgType; if (MSG_TYPE_NEWS.equals(msgType)) { news = new News(); } else if (...) { ... } else { throw new IllegalArgumentException("消息类型不支持"); } } /** 获取消息类型 */ public String getMsgType() { // 检查消息类型 if (Objects.isNull(msgType)) { throw new IllegalArgumentException("消息类型无效"); } // 返回消息类型 return this.msgType; } /** 设置新闻 */ public void setNews(News news) { // 清除消息内容 removeMsgContent(); // 赋值消息内容 this.msgType = MSG_TYPE_NEWS; this.news = news; } /** 获取新闻 */ public News getNews() { // 检查消息类型 checkMsgType(MSG_TYPE_NEWS); // 返回消息内容 return this.news; } ... } 复制 Union 类使用: String accessToken = ...; String toUser = ...; List<Article> articleList = ...; News news = new News(articleList); CustomerMessage customerMessage = new CustomerMessage(toUser, news); wechatApi.sendCustomerMessage(accessToken, customerMessage); 复制 主要优缺点: 优点:更贴近 C/C++ 语言的联合体(union); 缺点:实现逻辑较为复杂,参数类型验证较多。 使用继承方式实现 Union Union 类实现: /** 客户消息类 */ @Getter @Setter @ToString public abstract class CustomerMessage { /** 属性相关 */ /** 消息类型 */ private String msgType; /** 目标用户 */ private String toUser; /** 常量相关 */ /** 新闻消息 */ public static final String MSG_TYPE_NEWS = "news"; ... /** 构造函数 */ public CustomerMessage(String msgType) { this.msgType = msgType; } /** 构造函数 */ public CustomerMessage(String msgType, String toUser) { this.msgType = msgType; this.toUser = toUser; } } /** 新闻客户消息类 */ @Getter @Setter @ToString(callSuper = true) public class NewsCustomerMessage extends CustomerMessage { /** 属性相关 */ /** 新闻内容 */ private News news; /** 构造函数 */ public NewsCustomerMessage() { super(MSG_TYPE_NEWS); } /** 构造函数 */ public NewsCustomerMessage(String toUser, News news) { super(MSG_TYPE_NEWS, toUser); this.news = news; } } 复制 Union 类使用: String accessToken = ...; String toUser = ...; List<Article> articleList = ...; News news = new News(articleList); CustomerMessage customerMessage = new NewsCustomerMessage(toUser, news); wechatApi.sendCustomerMessage(accessToken, customerMessage); 复制 主要优缺点: 优点:使用虚基类和子类进行拆分,各个子类对象的概念明确; 缺点:与 C/C++ 语言的联合体(union)差别大,但是功能上大体一致。 在 C/C++ 语言中,联合体并不包括联合体当前的数据类型。但在上面实现的 Java 联合体中,已经包含了联合体对应的数据类型。所以,从严格意义上说, Java 联合体并不是真正的联合体,只是一个具备“多个数据每次只取其一”功能的类。 使用泛型屏蔽类型的差异性 在 C++ 语言中,有个很好用的模板(template)功能,可以编写带有参数化类型的通用版本,让编译器自动生成针对不同类型的具体版本。而在 Java 语言中,也有一个类似的功能叫泛型(generic)。在编写类和方法的时候,一般使用的是具体的类型,而用泛型可以使类型参数化,这样就可以编写更通用的代码。 许多人都认为, C++ 模板(template)和 Java 泛型(generic)两个概念是等价的,其实实现机制是完全不同的。 C++ 模板是一套宏指令集,编译器会针对每一种类型创建一份模板代码副本; Java 泛型的实现基于"类型擦除"概念,本质上是一种进行类型限制的语法糖。 泛型类 以支撑类为例,定义泛型的通用支撑类: /** 通用支撑类 */ @Getter @Setter @ToString public class GenericHolder<T> { /** 通用取值 */ private T value; /** 构造函数 */ public GenericHolder() {} /** 构造函数 */ public GenericHolder(T value) { this.value = value; } } 复制 泛型接口 定义泛型的数据提供者接口: /** 数据提供者接口 */ public interface DataProvider<T> { /** 获取数据函数 */ public T getData(); } 复制 泛型方法 定义泛型的浅拷贝函数: /** 浅拷贝函数 */ public static <T> T shallowCopy(Object source, Class<T> clazz) throws BeansException { // 判断源对象 if (Objects.isNull(source)) { return null; } // 新建目标对象 T target; try { target = clazz.newInstance(); } catch (Exception e) { throw new BeansException("新建类实例异常", e); } // 拷贝对象属性 BeanUtils.copyProperties(source, target); // 返回目标对象 return target; } 复制 泛型通配符 泛型通配符一般是使用"?"代替具体的类型实参,可以把"?"看成所有类型的父类。当具体类型不确定的时候,可以使用泛型通配符 "?";当不需要使用类型的具体功能,只使用Object类中的功能时,可以使用泛型通配符 "?"。 /** 打印取值函数 */ public static void printValue(GenericHolder<?> holder) { System.out.println(holder.getValue()); } /** 主函数 */ public static void main(String[] args) { printValue(new GenericHolder<>(12345)); printValue(new GenericHolder<>("abcde")); } 复制 在 Java 规范中,不建议使用泛型通配符"?",上面函数可以改为: /** 打印取值函数 */ public static <T> void printValue(GenericHolder<T> holder) { System.out.println(holder.getValue()); } 复制 泛型上下界 在使用泛型的时候,我们还可以为传入的泛型类型实参进行上下界的限制,如:类型实参只准传入某种类型的父类或某种类型的子类。泛型上下界的声明,必须与泛型的声明放在一起 。 上界通配符(extends): 上界通配符为 ”extends ”,可以接受其指定类型或其子类作为泛参。其还有一种特殊的形式,可以指定其不仅要是指定类型的子类,而且还要实现某些接口。例如: List<? extends A> 表明这是 A 某个具体子类的 List ,保存的对象必须是A或A的子类。对于 List<? extends A> 列表,不能添加 A 或 A 的子类对象,只能获取A的对象。 下界通配符(super): 下界通配符为”super”,可以接受其指定类型或其父类作为泛参。例如:List<? super A> 表明这是 A 某个具体父类的 List ,保存的对象必须是 A 或 A 的超类。对于 List<? super A> 列表,能够添加 A 或 A 的子类对象,但只能获取 Object 的对象。 PECS(Producer Extends Consumer Super)原则:作为生产者提供数据(往外读取)时,适合用上界通配符(extends);作为消费者消费数据(往里写入)时,适合用下界通配符(super)。 在日常编码中,比较常用的是上界通配符(extends),用于限定泛型类型的父类。例子代码如下: /** 数字支撑类 */ @Getter @Setter @ToString public class NumberHolder<T extends Number> { /** 通用取值 */ private T value; /** 构造函数 */ public NumberHolder() {} /** 构造函数 */ public NumberHolder(T value) { this.value = value; } } /** 打印取值函数 */ public static <T extends Number> void printValue(GenericHolder<T> holder) { System.out.println(holder.getValue()); } ———————————————— 版权声明:本文为CSDN博主「栾还是恋」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/2301_78008478/article/details/131367225
-
依赖倒置,控制反转,依赖注入及Google Guice1. 依赖倒置依赖字面意思事物之间具有的一种关系。在面向对象编程中我将其理解为一种对象之间引用的持有关系。任何系统都无法避免依赖,如果一个类或接口在系统中没有被依赖,那么他们就不应该出现在系统之中。举个简单的例子说明依赖关系:师徒四人去西天取经。我们说说唐僧,他有个徒弟,其他的东西我们暂且忽略。如果把唐僧师徒一个具体类的话,他在收服了悟空之后应该有这样的依赖关系。我们从唐僧角度考虑的话,他应该是依赖于悟空的,没有他,他可取不到经。那么我们可以说唐僧依赖于他的徒弟。在代码中,他们的关系如下:public class TangSeng { WuKong wuKong = new WuKong();}有了徒弟,唐僧就可以跟他愉快地取经了。中途遇到妖怪,也可以让徒弟去打妖怪了。public class TangSeng { WuKong wuKong = new WuKong(); public void letsFight(String name) { wuKong.fight(); }}那么问题了,唐僧在后面还会收徒弟。当他收齐之后情况应该是这样的。这里他就依赖于四个徒弟了,也就是说徒弟越多,他的依赖就越多。依赖多的话会产生什么影响呢?首先,遇到妖怪了,让谁出场是个问题了,总不能天天让一个人吃苦,这就不是一个好的领导了。所以,出战的方法也得修改。public class TangSeng { WuKong wuKong = new WuKong(); BaJie baJie = new BaJie(); LaoSha laoSha = new LaoSha(); XiaoBaiLong xiaoBaiLong = new XiaoBaiLong(); public void letsFight(String name) { if (name.equals("wuKong")) { wuKong.fight(); } else if (name.equals("baJie")) { baJie.fight(); } else if (name.equals("laoSha")) { laoSha.fight(); } else { runAway(); } } private void runAway() { System.out.println("Bye Bye ~"); }}这里代码量虽然只稍微上来一点,但是我们得看到更本质的东西。徒弟每增加一个徒弟,唐僧的依赖就会多一个,对应的代码可能就得修改一下。而且,唐僧直接依赖于具体的徒弟类,如果某个徒弟除了问题,那唐僧是不是也可能会出问题。因为他有一个具体的徒弟类,而且还会调用到具体的方法。这种耦合性比较高的代码,后期维护起来会比较糟糕,修改一个地方,其他地方可能也要跟着做很多更改。所以我们需要换个角度考虑一下。依赖倒置上面分析了问题出现在什么地方。主要是类之间直接的依赖关系导致的高耦合,那么要如何改变这种依赖关系呢?这就要改变我们思考的方式了,我们应该更多的依赖于接口(广泛概念上的接口)而不是具体的类,即要依赖于接口,而不是依赖于具体。无论是悟空,八戒还是沙僧,他们对于唐僧而言都是徒弟。我们可以将徒弟抽象成一个接口。如下:这里,具体类之间的直接依赖关系就被改变了。由类与具体类之间的依赖,转换成了类与接口之间的依赖。即唐僧类依赖于TuDi接口,而四个徒弟也依赖于TuDi接口,他们实现了接口。从上往下的依赖关系,在TuDi与徒弟实现类这里发生了改变,成了徒弟向上依赖于TuDi接口。这种倒置,就是依赖倒置。下面看看这种倒置对代码产生的影响:public class TangSeng { List<TuDi> ts = new ArrayList<TuDi>(); public TangSeng(List<TuDi> ts) { this.ts = ts; } public void letsFight(TuDi tudi) { tudi.fight(); }}实例化的语句没有了,具体类和实例对象也没有了。TuDi的具体实现对于唐生而言已经无所谓了,能打就行了。2. 控制反转(IOC)继续用上面的例子分析。我们知道师徒四人会遇到妖怪,但是遇到的妖怪是哪个?跟谁打?这个我们可能没法确定,但是在代码实现时,如果需要指定他们要面对的妖怪,我们可能就要在类中实例化这个妖怪了。public class TangSeng { List<TuDi> ts = new ArrayList<TuDi>(); LionMonster lion = new LionMonster(); public TangSeng(List<TuDi> ts) { this.ts = ts; } public void letsFight(TuDi tudi) { tudi.fight(lion); }}这里就等于写死了,他们只会跟狮子怪干架。妖怪是应用程序自己主动指定创建的。如果我们更改这种模式,他们跟哪个妖怪打架可以动态改变,由其他的配置控制。就是我们可以在需要的时候,将对象实例传递过去,这是被动的过程。这种由主动变成被动的方式,就是我理解中的反转控制。 具体的实现可能有多种方式,反射就是一种比较经典的实现。public class TangSeng { List<TuDi> ts = new ArrayList<TuDi>(); Property pro = new Property(); public TangSeng(List<TuDi> ts) { this.ts = ts; } public Monster getMonster() { Class monsterClass = Class.forName(pro.getClassName()); return monsterClass.newInstance(); } public void letsFight(TuDi tudi) { tudi.fight(getMonster); }}pro.getClassName()返回的值,可以通过配置文件更改成指定的类。3. 依赖注入(Dependency injection)注入我们再看看唐僧类中妖怪战斗的方法,圣僧是铁定上不了场的,这里我们是通过接口声明参数的,但是当真正调用方法的时候,这个地方肯定是要有个具体的徒弟实现类。所以问题就是这个徒弟怎么来。通过上面的讨论我们已经有两种方法可以实现了。其一,在代码中直接实例化好,然后传入对象,可以是通过工厂返回的对象。其二,通过配置文件指定徒弟类,在运行时动态生成徒弟类。后者变是反转控制的一种实现。反转控制是一个概念,他具体的实现方式可能有很多种。大部分场景是通过IOC容器,根据配置文件来实现注入。Druid的依赖注入都是通过Google Guice实现的,所以这里简单介绍一下它。4. Google GuiceGoogle Guice 是一款轻量级的依赖注入框架。<dependency> <groupId>com.google.inject</groupId> <artifactId>guice </artifactId> <version>4.1.0</version> </dependency> <dependency> <groupId>aopalliance</groupId> <artifactId>aopalliance</artifactId> <version>1.0</version></dependency>4.1 使用实例场景1:唐僧被妖怪抓走了,大师兄刚刚化缘回来。各位师兄弟的反应如下,沙僧:大师兄!师父被妖怪抓走了!!八戒:分行李吧!!悟空:我去看看是哪路妖怪,如此胆大!!于是,悟空出发了!!以下是悟空类,悟空多了一个拯救师父的任务public class Wukong implements Tudi { private String name = "wukong"; private Skill skill; public void toSaveMaster(){ //悟空使用它的技能(skill)对付妖怪 skill.Effect(); } @Override public void fight(Monster monster) { System.out.println("WuKong is fighting with " + monster); }}那我们知道悟空会很多的法术,妖怪也是千奇百怪,所以要对症下药,选择正确的技能才能在损失最小的情况下快速地救出师傅。那这里的技能就又要用我们上面的思想来处理了://把Skill定义为一个接口public interface Skill { public void Effect();} //下面是悟空的几个技能class Fire implements Skill{ @Override public void Effect() { System.out.println("悟空在喷火!!对敌方造成火属性伤害100"); }}class Water implements Skill{ @Override public void Effect() { System.out.println("哇!!悟空在喷水!!对敌方造成水属性伤害100"); }}class Wind implements Skill{ @Override public void Effect() { System.out.println("悟空在刮风!!对敌方造成风属性伤害100"); }}这里我们知道了悟空会法术(Skill接口),还知道了他的技能清单(Skill的实现类)。接下来就是根据地方选择正确的技能了。例如对面是白骨精,那我们就选择喷水技能打伤害吧(我也不知道为什么,感觉会很有效!)。那我们要做的就是把悟空的技能接口和接口的实现类Water绑定到一起。不使用框架的操作。Wukong wukong = new Wukong(); wukong.skill=new Water();使用Guice,需要做的步骤如下:1. 创建接口;2. 接口实现;3. 将接口和实现类绑定; 4. 创建接口实例。前两步已经在上面的代码中完成了,接口为Skill,实现类就是喷火、喷水、刮风。接下来我们进行接口的绑定。步骤三:将接口和实现类绑定public class SkillModule implements Module { @Override public void configure(Binder binder) { binder.bind(Skill.class).to(Water.class); } //接口和实现类绑定的一种方式就是通过实现配置模块,实现其config方法来完成。这种绑定关系,我们也可以通过配置文件指定。步骤四:创建接口的实例public static void main(String[] args) { //将配置传入 Injector injector = Guice.createInjector(new SkillModule()); skill = injector.getInstance(Skill.class); Wukong wukong = new Wukong(); wukong.skill=skill; wukong.toSaveMaster(); } 运行结果如下: 哇!!悟空在喷水!!对敌方造成水属性伤害1004.2 Guice中的注解@ImplementedBy:用于注解接口,直接指定接口的实现类而不需要在Module中实现接口的绑定;Demo//定义接口时即指定其实现类为Water@ImplementedBy(Water.class)public interface Skill { public void Effect();}在Main方法中的代码也做相应的更改:public static void main(String[] args) { Injector injector = Guice.createInjector(); skill = injector.getInstance(Skill.class); Wukong wukong = new Wukong(); wukong.skill=skill; wukong.toSaveMaster(); }运行结果一样,但是整个代码工程中少了配置module的过程。但是谁又能在定义接口时就知道其实现类呢,我觉得用处不是特别大。@Inject:使用该注解,可以将对象实例直接注入到一个对其依赖的类中。可以用在某个类的构造方法中:Demopublic class Wukong implements Tudi { private static String name = "wukong"; private static Skill skill; @Inject public Wukong(Skill skill) { this.skill = skill; } public void toSaveMaster(){ skill.Effect(); } @Override public void fightMonster() { System.out.println("WuKong is fighting !!"); }}Main方法也变了public static void main(String[] args) { Injector injector = Guice.createInjector(); Wukong wukong = injector.getInstance(Wukong.class); wukong.toSaveMaster(); }运行结果一样。@Singleton用来注解类,可以确保调用injector.getInstance时创建的是一个单例类。@Named:当一个接口实多个绑定时可以使用该注解区分。改写SkillModule类public class SkillModule implements Module { @Override public void configure(Binder binder) { binder.bind(Skill.class).annotatedWith(Names.named("Water")).to(Water.class); binder.bind(Skill.class).annotatedWith(Names.named("Fire")).to(Fire.class); }}在看看这个注解是如何发挥作用的public static void main(String[] args) { Injector injector = Guice.createInjector(new SkillModule()); @Named("Water") Skill waterSkill = injector.getInstance(Skill.class); Wukong wukong = new Wukong(); wukong.skill = waterSkill; wukong.toSaveMaster(); @Named("Fire") Skill fireSkill = injector.getInstance(Skill.class); wukong.skill = fireSkill; wukong.toSaveMaster(); }这样就可以把一个接口绑定到多个实现类上,根据不同的Name可以创建不同的实例。但是在实际中无法通过编译,还没有看出是什么问题,所以不建议使用该注解。Guice很强大,这里只是简单记录。啥?啥是控制反转,依赖注入啊!?转自 https://zhuanlan.zhihu.com/p/96108992
-
前言在算法和数据结构中,深度优先搜索(DFS)和广度优先搜索(BFS)是两个常用的遍历算法。它们在解决各种问题时都发挥着重要作用。但在实际开发中,深度优先和广度优先哪个更常用?本文将探讨这个问题,并提供一些案例和观点供读者参考。深度优先搜索深度优先搜索是一种递归的搜索算法,其主要思想是尽可能深地搜索一个分支,直到无法继续下去,然后回溯到前一个节点,再继续搜索其他分支。这种搜索方式常用于以下情况:树和图的遍历:深度优先搜索可以用于遍历树和图的节点。例如,在文件系统中,我们可以使用深度优先搜索来遍历目录结构,查找特定文件。回溯算法:回溯算法常用深度优先搜索来遍历所有可能的解空间。例如,在解决八皇后问题或求解数独等问题时,深度优先搜索可以帮助我们逐步探索所有可能的解。拓扑排序:在有向无环图中,深度优先搜索可以用于执行拓扑排序,确定任务或事件的执行顺序。广度优先搜索广度优先搜索是一种迭代的搜索算法,其主要思想是从起始节点开始,逐层遍历相邻节点,直到找到目标节点或遍历完整个图。这种搜索方式常用于以下情况:最短路径问题:广度优先搜索可以用于寻找无权图中两个节点之间的最短路径。例如,在迷宫游戏中,我们可以使用广度优先搜索来找到从起点到终点的最短路径。网络分析:广度优先搜索可以用于分析社交网络或互联网中的关系。例如,寻找两个人之间的最短社交路径或确定网页之间的相关性。生成树和图的连通性:广度优先搜索可以用于生成树的构建和判断图的连通性。例如,在无向图中,我们可以使用广度优先搜索来构建最小生成树或判断两个节点是否连通。实际应用中的选择在实际开发中,选择深度优先搜索还是广度优先搜索取决于具体情况和问题要求。以下是一些考虑因素:目标:如果问题要求我们找到最短路径或最优解,通常广度优先搜索是更合适的选择。例如,求解迷宫最短路径或找到两个人之间的最短社交路径。空间复杂度:深度优先搜索通常使用递归或栈来实现,需要较少的额外空间。而广度优先搜索需要使用队列来存储节点,可能需要更多的内存空间。时间复杂度:在某些情况下,深度优先搜索可能需要更多的时间来遍历整个图,因为它会尽可能深地搜索一个分支。而广度优先搜索可以更快地找到目标节点或达到特定层数。数据结构:问题的数据结构也可能影响选择。对于树或图等数据结构,我们可以根据其特点选择合适的搜索算法。在实际开发中,我们经常会根据具体问题的需求来选择深度优先搜索或广度优先搜索。有时候,问题可能需要结合两者来解决,或者选择其他更适合的算法。了解深度优先搜索和广度优先搜索的原理和应用场景,可以帮助我们更好地应对各种问题,并选择合适的算法来解决。
-
I. 问题介绍 八数码问题是一种经典的智力游戏,也是一种搜索算法的经典案例。该问题是指在一个3x3的棋盘上,有8个方块和一个空格,每个方块上标有1~8的数字,空格可以和相邻的方块交换位置,目标是通过交换方块的位置,使得棋盘上的数字排列成目标状态。 对于八数码在程序中的处理,我们通过拉直的方式,将八数码棋盘拉成一条字符串,用0来表示空位,用1-8的数字来表示相应的数码。这样一来就可以将二维的矩阵作为一维的向量处理,大大简化了问题。通过移动规则,用一维字符串上的索引来表示二维矩阵中的移动规则。 我们可以通过移动规则,用来产生某种棋盘可移动的所有情况。某一个节点下均连接了若干个子节点,这就形成了一个逻辑上的树结构。 既然八数码的移动可以看作为一个树结构,那么我们就可以对这个树进行搜索。搜索方式为广度优先搜索、宽度优先搜索、启发式搜索。 II. 思路设计 程序使用open表与close表来组织节点的搜索。open表用来保存待搜索的节点,close表用来保存以搜索的节点。实现搜索本质上是对open表与close表进行维护,两者中更重要的是维护好open表。我们可以通过open表中不同的取值方式,来实现广度优先搜索、宽度优先搜索与启发式搜索。 下图为open表与close表的示意图,先将open表中的某一节点取出来,判断其是否为目标节点,若不是目标节点,则将其展开,展开时要判断子节点是否再close表中,避免重复搜索,并将其子节点加入open表的尾部,再把展开的节点丢入close表,这就是搜索的基本过程。 搜索的关键在于open表中的节点如何取,这也是实现不同搜索方式的关键。 广度优先搜索 广度优先搜索的实现方式为:每次弹出open表中的第一个节点。如下图所示,在节点1展开完成后,open表继续弹出第一个节点,也就是节点2,节点2展开又形成新的节点5与节点6;当节点2完成展开后,open表将会弹出节点3;节点3完成展开后,open表将会弹出节点4;当节点2、3、4均完成展开后,接下来再展开节点5,然后是节点6……。 子节点将会在open表的尾部不断累积,要先将open表前面的父节点遍历完成后,才能开始遍历子节点。通过这种方式,实现了广度优先搜索。 深度优先搜索 深度优先搜索的实现方式为:每次弹出open表的最后一个节点。如下图所示,在节点1完成展开后,open表弹出最后一个节点4,节点4展开形成节点5、6,并将其加入到open表的尾部,接下来将会弹出最后一个节点6,节点6的子节点又会加入到open表的尾部,接下来继续弹出最后一个节点,这个节点则是节点6的子节点。 子节点将会在open表的尾部不断弹出,每次都向更深层次的子节点搜索,这样就实现了深度遍历搜索。 启发式搜索 广度优先搜索与深度优先搜索虽然是有序的搜索,但其本质上还是盲目的搜索,搜索过程中程序并不知道目标在什么地方。启发式搜索其实就是告诉了程序,目标在哪里,让程序倾向于朝着目标距离小的方搜索。 如下图所示,启发式搜索在展开节点时,会先计算节点与目标之间的距离,并在下一步优先展开距离小的节点。这样一来程序就会避免展开很多不必要的节点,极大提高程序的搜索效率。 我们需要做的是定义一个代价函数,用来计算节点与目标节点之间的距离,这个距离也被称为代价。在open表弹出节点时,将会弹出代价最小的节点,一步步靠进目标节点。 计算距离的函数有很多,我定义了三种代价函数,一种是字符串对位距离,一种是曼哈顿距离,一种是欧式距离。我认为字符串距离存在着缺陷,比如索引2与索引3,他们在字符串中的距离只有1,但是在实际的网格中,他们的距离是大于1的,因此我个人更加倾向于曼哈顿距离与欧式距离,实践证明亦是如此。 III. 代码实现 在代码的实现中,我将广度优先搜索、深度优先搜索、启发式搜索全部整合到了一个框架中,可以通过修改全局变量,实现不同的模式。 我在代码中做了许多鲁棒性的操作,本来的想法是,将八数码问题很容易的扩展到十五数码问题,但是后来才想到,代码处理节点的方式是将其拉成一条字符串,这样以来,10以上的数字就没有办法表示了,因为他们占了两位字符,只能放弃了这个想法。但把代码中的鲁棒性操作都保留了下来。 check函数 用于检查用户的输入是否符合规范。若不符合,则抛出异常。 def check(): """检查用户输入""" # 检查节点长度是否符合要求 check_len = len(start) == len(target) and len(start) ** 0.5 % 1 == 0 assert check_len, f'请检查开始节点与目标节点的长度是否合理 开始节点长度{len(start)} 目标节点长度{len(target)}' # 检查节点中的数字是否符合要求 # 节点中的数字查全 check_recall = lambda x: all([str(flag) in x for flag in range(int(len(start)))]) assert check_recall(start) and check_recall(target), f'请检查开始节点与目标节点是否输入正确 开始节点{start} 目标节点{target}' # 检查搜索模式 assert mode in ALLOW_MODE, f'搜索模式 {mode} 不支持' # 检查搜索方式 if mode == ALLOW_MODE[2]: cod = list(cost_func.values()) count = 0 for i in cod: if i: count += 1 # 只允许有一个True assert count == 1, f'请检查代价方程的选择是否合理, {cod}' get_rules函数 本来的想法是将八数码扩展到更多数码的情况,因而使用get_rules产生空位的移动规则。函数的思想为:将字符串的索引还原至网格的坐标内,并获取上下左右四个方位的索引值,再将越界值删除,最后保存在字典内。 def get_rules(): # 用于存放规则的字典 rules = dict() # 字符串长度 length = len(start) # 棋盘的边长 size = int(length ** 0.5) # 遍历所有索引 for i in range(length): # 将坐标还原至网格 row, col = i // size, i % size # 获取四个方位的坐标 up, down, left, right = i - size, i + size, i - 1, i + 1 d = [up, down, left, right] # 若当前索引处于边界,删除越界值 if row == 0: d.remove(up) if row == size - 1: d.remove(down) if col == 0: d.remove(left) if col == size - 1: d.remove(right) # 创建键值对 rules[i] = d return rules swap_puzzle函数 swap_puzzle函数用于交换两个数码的位置,实际上就是移动空位。参数node表示要进行交换操作的节点,i和j表示要交换哪两处的索引。字符串可以通过索引访问,但不可通过索引修改,因此要将其先转换为列表,交换完成后再还原为字符串。 def swap_puzzle(node, i, j): """交换数码盘""" temp = list(node) temp[i], temp[j] = temp[j], temp[i] return ''.join(temp) expand函数 expand函数用于展开节点,根据空位的移动规则,生成某一节点的所有未遍历的子节点。参数info的格式如下:[节点,距离,展开次数],info不仅仅是一个节点,而是一个携带了节点与距离信息的列表。并在展开节点时,计算出各子节点与目标节点的距离。 def expand(info): node = info[0] zero_idx = node.index("0") infos = [] for idx in RULES[zero_idx]: new_node = swap_puzzle(node, zero_idx, idx) if new_node not in close: infos.append([new_node, cost(new_node, **cost_func), info[2]+1]) return infos cost函数 用于计算代价,也就是当前节点与目标节点之间的距离。我在函数中提供了三种代价函数,一种是直接计算字符串的对位距离,一种是曼哈顿距离,一种是欧式距离。计算曼哈顿距离与欧式距离时,要先将索引还原到网格坐标中。 def cost(node, str_dis=True, mhd_dis=False, o_dis=False): """ 计算代价函数 :param now: 字符串类型 表示当前节点 :param str_dis: 布尔类型 表示是否使用字符串距离(将当前节点与目标节点的字符索引做差) :param mhd_dis: 布尔类型 表示是否曼哈顿距离(将字符串还原至网格坐标中) :param o_dis: 布尔类型 是否使用欧式距离(将字符串还原至网格坐标中) :return: """ cost = 0 # 遍历每个字符及其索引 for i, char in enumerate(node): # 将网络视为为一条向量(字符串) # 用这条向量计算代价 # "541203786"情况下遍历了310个节点 if str_dis: cost += abs(i - target.index(char)) # 0 1 2 # 3 4 5 # 6 7 8 # 将字符串还原为网格,计算其曼哈顿距离 # 曼哈顿距离为 x轴距离+y轴距离 else: # 计算这个索引属于哪一行 row = i // 3 # 计算这个索引属于哪一列 con = i % 3 # 获取目标位置的行和列 end_idx = target.index(char) end_row = end_idx // 3 end_con = end_idx % 3 # 计算曼哈顿距离 # "541203786"情况下遍历了240个节点 if mhd_dis: cost += abs(row-end_row) + abs(con-end_con) # 计算欧几里得距离(欧式距离) # "541203786"情况下遍历了214个节点 elif o_dis: cost += ((row-end_row) ** 2 + (con-end_con) ** 2)**0.5 return cost print_node函数、find_path函数、final_print函数 这三个函数对于算法没有直接的意义,算是工具函数,是用来向控制台输出最后的移动路径的。这里在产生移动路径时,程序的搜索树的结构为,键为子节点,值为父节点,这种设计可以更方便的帮助程序找到移动路径。 def print_node(node): """将节点以特定格式输出""" length = len(start) size = int(length ** 0.5) for i in range(0, length, size): print(' '.join(node[i: i + size])) def find_path(): """ 通过nodes找到路径 """ path = [] # 树的结构为 键为子节点 值为父节点 son = target while True: father = tree[son] path.append(son) if father != -1: son = father else: break return path def final_print(): """最终的输出""" print("\n移动顺序如下") total_path = find_path() for path in total_path + [target]: print_node(path) print() print(f"遍历节点个数: {len(close)} 移动步数: {len(total_path)}") print(f"累计用时: {time.time() - start_time:.2f}秒") 主程序 主程序中规定了全局变量,全局变量包括了初始节点,目标节点,模式设置等一系列参数,提供了多种选项与功能。 在程序的主循环中,实现了根据不同的模式弹出不同的节点。在启发式搜索弹出节点时,不仅仅参考了节点与目标节点之间的距离,还参考了展开次数。可以理解为,程序不仅要通过最短的距离找到目标节点,还要尽量减少节点展开的次数。 if __name__ == '__main__': # 开始节点 start = "541203786" # start = "134082576" # 目标节点 target = "123804765" # 是否随机打乱开始状态 shuffle_start = False ALLOW_MODE = ['广度优先搜索', '深度优先搜索', '启发式搜索'] # 搜索模式 支持的模式:0 广度优先搜索 1 深度优先搜索 2 启发式搜索 mode = ALLOW_MODE[2] cost_func = {'str_dis': False, 'mhd_dis': False, 'o_dis': True} # open表 open = [] # close表 close = [] # 搜索树 tree = dict() RULES = get_rules() # 检查变量是否设置正确 check() print(f"搜索方式 {mode} ", end='') if mode == ALLOW_MODE[2]: print(f"{'字符串距离' if cost_func['str_dis'] else ''}", end='') print(f"{'曼哈顿距离' if cost_func['mhd_dis'] else ''}", end='') print(f"{'欧式距离' if cost_func['o_dis'] else ''}", end='') print() if shuffle_start: # 随机打乱初始节点 start = list(start) random.shuffle(start) start = ''.join(start) print('初始节点') print_node(start) # 将第一个节点放入open表中 [节点,代价,步数] open.append([start, cost(start, **cost_func), 0]) # tree['root'] = start tree[start] = -1 # 获取程序开始时间 start_time = time.time() while len(open) > 0: # 输出日志信息 print(f"\r正在搜索...{time.time() - start_time:.0f}s 已遍历节点数:{len(close)}", end='') # 不同的模式弹出不同的节点 if mode == ALLOW_MODE[0]: # info = open.pop(0) elif mode == ALLOW_MODE[1]: info = open.pop(-1) elif mode == ALLOW_MODE[2]: info = min(open, key=lambda x: x[1] + x[2]) open.remove(info) # 获取节点值 node = info[0] # 将节点保存至close表 close.append(node) # 判断是否为目标节点 if node == target: final_print() break # 展开节点 infos = expand(info) open.extend(infos) for info in infos: tree[info[0]] = node else: # while循环正常结束,open表为空,所有节点搜索完毕 print("问题无解") print(f"遍历节点个数: {len(close)}") print(f"累计用时: {time.time() - start_time:.2f}秒") IV. 实验结果 对于541203786这种情况: 盲目搜索 当使用广度优先搜索时,遍历节点72085个,移动步数21步,累计时间121.94秒。时间消耗与遍历节点数每个人可能不同,因为这个结果受到移动规则中的排列顺序影响较大。广度优先搜索移动步数较少,因为其按层搜索,每一层就是一个移动。 当使用深度优先搜索时,遍历节点45147个,移动步数43797步,累计时间61.71秒。深度优先搜索遍移动步数较多,因为其大多数情况展开一次就是一个移动。 上述两种为盲目搜索的实验结果,两种搜索中的运气成分还是比较多的。 启发式搜索: 使用字符串对位距离:遍历节点数727个,移动步数23步,累计用时0.11秒。启发式相较于盲目搜索的几万个搜索节点,可以说是提升巨大,但代价函数不合适的情况下,可能会找到多余的移动步数。 曼哈顿距离:遍历节点数605个,移动步数21步,累计用时0.09秒。相较字符串的对位距离,曼哈顿距离显然在每个数值上都优于字符串对位距离,原因可能是前文提到的字符串对位距离的不合理性。 欧式距离:遍历节点数837个,移动步数21步,累计用时0.13秒。结果依然优于字符串对位距离,但要略差于曼哈顿距离。 V.总结 在八数码问题中,启发式搜索无疑碾压盲目搜索,但启发式搜索也不一定是快最优的解。报告仅针对一种初始状态做了实验,还需要更多的实验次数来支撑实验结果,还有更多的代价函数等待应用,此外,还可以通过调节展开次数与距离之间的占比,以获取更佳的效果。 ———————————————— 版权声明:本文为CSDN博主「G.E.N.」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/qq_63708623/article/details/129740686
-
前言 好久不见,困扰了我许久的阴霾终于散去了,但是随之而来的是学校堆积如山的任务考试,这段时间不可否认我的学习效率和学习效果不是很佳,但是我之前就说过学习是需要贯穿程序猿一生的事情,流水不争先,争的是滔滔不绝,如果屏幕前的您真的遇到了不如意,不妨放慢脚步,放松自己,然后再投入到自己的事业中. MySQL 我们日后工作大部分时间可能就是在对各种各样的数据库进行CURD,但是我们要掌握的却远远不止于此,这部分我没有写博客,是因为这部分的知识,不太好用文字的形式讲解,希望大家 可以多去使用使用,几遍下来就可以记住了. MySQL背后的数据结构 前面都是引子,这才是我想通过这篇博客分享给大家的东西. 先说好,我现在默认兄弟们是了解MySQL的,所以新手看不懂不要骂阿涛!! 在日常使用中,我们使用查询的频率是要远远高于其他操作的,因此我们创建了索引,这样我们在查询数据的时候,就避免了每次都要遍历数据的尴尬,但是与此同时可能会拖慢增删改的步伐,但是正是因为我们查找的频率要远高于其他操作,所以总体上索引是利大于弊的. 在开始讲解数据结构的时候,我们就说过了,数据结构是组织数据的形式,那么我们想一想可以用什么数据结构来组织数据库中的庞大的数据呢? Hash表?Hash表固然可以达到O(1)的时间复杂度,但是,数据表的结构注定了它没有办法返回一个范围内的数据. 二叉树?我们之前在使用二叉树的时候,有不少时候是可以感觉到,当数据量非常之大的时候,是有可能导致那个stack overflow错误的,因此我们可以使用B+树这个为数据库索引量身定做的数据结构,在了解B+树之前,我们先来了解一下B树. B树 B树也可以叫做B-树,注意这里不是叫B减数,就是叫做B数. B数可以认为是一棵N叉搜索树,二叉搜索树的概念之前我有专门的博客,二叉搜索树就是根的左子树的值比根小,右子树的值比根大,不存在两个一样的值. 那么根据名字我们可以想象到N叉搜索树的模样,现在根节点下面就不仅仅是挂着两两个子树了,可以挂好多棵子树,这样子在数据量相同的情况下,是不是总体树的高度就降低下来了? 我们可以看到B树与普通树的不同还远远不止与上述特点. 首先我们的每个节点现在可以存储多个值了,然后就比如我们节点中的值有两个,那么这棵子树就可以有它的三棵子树,左边是小的区间的,中间的树介于两个值之间,右边的值大的区间, 但是我们还是要抓住搜索树的本质特点,左子树的值永远要小于根节点的值,右子树的值永远要大于根节点的值. B+树 B+树又在B树的基础上进行了优化. 可以看到总体上还是能看出这是一个N叉搜索树的样子的,但是其中还是有一点玄机的. 首先现在如果一个节点中有两个值,那么就只有两个子节点了,我们可以看到的是,子节点会把父亲节点给加上去,然后在B+树的最底层会以一种类似于链表的形式把所有的数据给连接起来. B+树的特点: 1.一个节点可以存储N个key,N个key划分出了N个区间,而不是B树的N+1区间 2.每个节点中的key值,都会在子结点中存在,同时该key也是子节点的最大值 3.B+树的叶子节点,是首尾相连,类似于一个链表 4.整棵树的所有数据都是包含在叶子节点中的,由于叶子节点是完整的数据集合,所以我们只在叶子节点这里存储数据表的每一行的数据,而非叶子节点,只存key值即可 B+树的优势: 1.当前一个节点保存更多的key,最终树的高度是相对更矮的,查询的时候减少了IO访问次数,和B一样的效果 2.所有的查询最终都会落实在叶子节点上,查询任何一个数据最终的IO访问次数是一样的,即使提前找到了最终还是需要一直往下找到叶子节点为止,那里才是one piece. B+树的这个稳定查询是很重要的,这个稳定是很关键的,稳定能够让程序猿对于程序的执行效率有一个更准确的评估 input-output:显示数据到显示屏上,从键盘输入数据,把数据写到硬盘上,从硬盘读数据,把数据写到网卡上,从网卡读数据,我们这里的IO特指访问硬盘 3.B+树的所有的叶子节点构成链表,比较方便进行范围查询: 查询学号>5并且<11的人,只需要先找到5所在的位置,再找到11所在的位置,从5沿着链表遍历到11,中间结果既是所求. 4.由于数据都在叶子节点上,非叶子节点只存储key,所以非叶子节点占用空间十分小,这里的非叶子节点就有可能在内存中缓存部分,又进一步减少了IO次数 刚才的B+树就是MySOL组织数据的方式,当你看到一张"表"的时候,实际上不一定就是按照"表格"的结构在硬盘上组织的,也有可能是按照这样树形结构组织,具体是哪种结构,取决于你的表里有没有索引,以及数据库使用了哪种存储引擎. 上面的树形结构就是"索引",如果这一列不能比较,就没有办法创建索引,幸运的是,MySOL里面的各种类型,都能比较,数字,字符串,时间日期,MySOL是不可以自定义类型的,上述结构默认Id是表的主键了,如果表里面有多个索引,表的数据还是按照id为主键,构建出B+树,通过叶子节点组织所有的数据行,其次针对name这一列,会构建另一个B+树,但是这个B+树的叶子节点就不再存储这一行的完整数据,而是存主键ID,此时根据mane来查询,查到叶子节点得到的只是主键id,还需要再通过主键id去主键的B+树里面再查询一次,一共查询两次B+树,上述过程称之为"回表",这个过程都是MySOL自动完成的,用户感知不到. 希望我的这篇博客对兄弟们能有所帮助,还是那句话,百年大道,你我共勉! ———————————————— 版权声明:本文为CSDN博主「Ricardo_M_CYT」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/Ricardo_M_CYT/article/details/129403619
-
0. 前言cv::Mat 类是用于保存图像(以及其他矩阵数据)的数据结构,该数据结构是所有 OpenCV 类和函数的核心,这是 OpenCV 库的一个关键元素,用于处理图像和矩阵(从计算和数学的角度来看,图像本质上是一个矩阵),同时 cv::Mat 数据结构结合了优雅的内存管理机制,因此,使用起来十分高效。此数据结构在应用程序开发中广泛使用,因此再进一步学习前我们必须熟悉 cv::Mat 数据结构。1. cv::Mat 数据结构1.1 cv::Mat 简介cv::Mat 数据结构基本上由两部分组成:标头 (header) 和数据块 (data block)。标头包含与矩阵相关的所有信息(尺寸大小、通道数、数据类型等)。我们已经介绍了如何访问包含在 cv::Mat 标头中的一些属性,例如,通过使用 cols 、rows 或 channels 访问矩阵的列数、行数或通道数;数据块包含图像的所有像素值,标头中包含一个指向这个数据块的指针变量,即 data 属性。cv::Mat 数据结构的一个重要特性是内存块仅在明确请求时才被复制,大多数操作只是简单地复制 cv::Mat 标头,这样多个对象本质上同时指向同一个数据块,这种内存管理模型使应用程序更高效,同时可以避免内存泄漏。1.2 cv::Mat 属性接下来,我们通过编写测试程序 (mat.cpp) 来测试 cv::Mat 数据结构的不同属性。1. 首先,声明 opencv 头文件和 c++ i/o 流文件:#include#include#include2. 创建函数来生成新的灰度图像,其所有像素具有相同的默认值:cv::Mat function() {// 创建新图像并返回cv::Mat ima(500, 500, CV_8U, 50);return ima;}默认情况下, cv::Mat 对象在创建时的大小为零,但也可以指定初始大小:cv::Mat image1(240,320,CV_8U,100);1如果指定图像初始大小,就需要指定每个矩阵元素的类型,以上代码使用 CV_8U 类型,对应创建的图像像素为 1 字节 (8 位),字母 U 表示它是无符号的;还可以使用字母 S 声明有符号整数类型。对于彩色图像,需要指定三个通道 (CV_8UC3),也可以声明大小为 16 或 32 的整数(同样可以为有符号或无符号)图像,例如,CV_16SC3 表示 16 位有符号整数类型。除了整数类型,还可以使用 32 位或 64 位浮点数,例如,CV_32F 表示 32 位浮点数。3. 在主函数中,创建六个窗口来显示图像处理结果:cv::namedWindow("Image 1");cv::namedWindow("Image 2");cv::namedWindow("Image 3");cv::namedWindow("Image 4");cv::namedWindow("Image 5");cv::namedWindow("Image");4. 创建多个不同的图像矩阵(具有不同的尺寸、通道和默认值),并等待按键被按下:// 创建一个尺寸为 240x320 的图像,创建时直接定义像素值cv::Mat image1(240,320,CV_8U,100);cv::imshow("Image", image1); // 显示图像cv::waitKey(0);// 当尺寸或数据类型不同时,需要重新分配内存image1.create(200,200,CV_8U);image1 = 200;cv::imshow("Image", image1); // 显示图像cv::waitKey(0);// 创建一个由红色填充的图像,OpenCV 中色彩通道顺序为 BGRcv::Mat image2(240,320,CV_8UC3,cv::Scalar(0,0,255));// 也可以使用以下方法定义// cv::Mat image2(cv::Size(320,240),CV_8UC3);// image2= cv::Scalar(0,0,255);cv::imshow("Image", image2); // 显示图像cv::waitKey(0);图像(或矩阵)的每个元素可以由多个值组成(例如,彩色图像具有三个通道,因此每个坐标点都有三个像素值),因此,OpenCV 引入了一种简单的数据结构,用于将像素值传递给函数,即 cv::Scalar 结构体,一般用来保存一个值或者三个值。例如,要创建一个用红色像素初始化的彩色图像:cv::Mat image2(240,320,CV_8UC3,cv::Scalar(0,0,255));1同样,灰度图像的初始化也可以通过使用此结构完成 (cv::Scalar(100))。图像尺寸大小通常也需要作为参数传递给函数,我们已经知道 cols 和 rows 属性可用于获取 cv::Mat 实例的维度。尺寸大小信息也可以通过 cv::Size 结构提供,它只包含矩阵的高度和宽度,size() 方法可以获取当前矩阵大小。cv::Size 结构是许多必须指定矩阵大小的方法中常用的格式。例如,使用以下方式创建图像:cv::Mat image2(cv::Size(320,240),CV_8UC3);15. 使用 imread 函数读取图像并将其复制到另一个图像矩阵:// 读取图像cv::Mat image3 = cv::imread("1.png");// 令 image4 和 image1 指向同一个数据块 image3cv::Mat image4(image3);image1 = image3;// image2 和 image5 是 image3 的副本image3.copyTo(image2);cv::Mat image5 = image3.clone();6. 对复制后的图像应用图像转换函数 (cv::flip()),显示创建的所有图像,然后等待按键:// 水平翻转图像cv::flip(image3,image3,1);// 检查图像cv::imshow("Image 3", image3);cv::imshow("Image 1", image1);cv::imshow("Image 2", image2);cv::imshow("Image 4", image4);cv::imshow("Image 5", image5);cv::waitKey(0);7. 使用创建的函数来生成一个新的灰色图像:// 使用 function 函数创建灰度图像cv::Mat gray = function();cv::imshow("Image", gray); // 显示图像cv::waitKey(0);8. 加载一个彩色图像,在加载过程中将其转换为灰度图像,然后,将其值转换为浮点矩阵:// 将图像读取为灰度图像image1= cv::imread("1.png", cv::IMREAD_GRAYSCALE);// 将图像转换为值在 [0, 1] 区间内的浮点图像image1.convertTo(image2,CV_32F,1/255.0,0.0);cv::imshow("Image", image2); // 显示图像1.3 完整代码示例完整代码 (mat.cpp) 如下所示:#include#include#includecv::Mat function() {// 创建新图像并返回cv::Mat ima(500,500,CV_8U,50);return ima;}int main() {// 创建一个尺寸为 240x320 的图像,创建时直接定义像素值cv::Mat image1(240,320,CV_8U,100);cv::imshow("Image", image1); // 显示图像cv::waitKey(0);// 当尺寸或数据类型不同时,需要重新分配内存image1.create(200,200,CV_8U);image1 = 200;cv::imshow("Image", image1); // 显示图像cv::waitKey(0);// 创建一个由红色填充的图像,OpenCV 中色彩通道顺序为 BGRcv::Mat image2(240,320,CV_8UC3,cv::Scalar(0,0,255));// 也可以使用以下方法定义// cv::Mat image2(cv::Size(320,240),CV_8UC3);// image2= cv::Scalar(0,0,255);cv::imshow("Image", image2); // 显示图像cv::waitKey(0);// 读取图像cv::Mat image3 = cv::imread("1.png");// 令 image4 和 image1 指向同一个数据块 image3cv::Mat image4(image3);image1 = image3;// image2 和 image5 是 image3 的副本image3.copyTo(image2);cv::Mat image5 = image3.clone();// 水平翻转图像cv::flip(image3,image3,1);// 检查图像cv::imshow("Image 3", image3);cv::imshow("Image 1", image1);cv::imshow("Image 2", image2);cv::imshow("Image 4", image4);cv::imshow("Image 5", image5);cv::waitKey(0);// 使用 function 函数创建灰度图像cv::Mat gray = function();cv::imshow("Image", gray); // 显示图像cv::waitKey(0);// 将图像读取为灰度图像image1= cv::imread("1.png", cv::IMREAD_GRAYSCALE);// 将图像转换为值在 [0, 1] 区间内的浮点图像image1.convertTo(image2,CV_32F,1/255.0,0.0);cv::imshow("Image", image2); // 显示图像// 使用 cv::Matx 创建一个 3x3 的双精度 (double-precision) 矩阵cv::Matx33d matrix(3.0, 2.0, 1.0,2.0, 1.0, 3.0,1.0, 2.0, 3.0);// 使用 cv::Matx 创建一个 3x1 的双精度矩阵 (向量)cv::Matx31d vector(5.0, 1.0, 3.0);// 矩阵相乘cv::Matx31d result = matrix*vector;std::cout << result;cv::waitKey(0);return 0;}编译后,运行此程序查看生成图像(生成的纯色图像未列出):$ g++ mat.cpp -o mat `pkg-config --cflags --libs opencv4`$ ./mat122. 探索 cv::Mat 数据结构2.1 cv::Mat 对象的创建图像的数据块可以使用 create() 方法分配或重新分配。当图像先前已被分配时,它的旧内容首先被释放,出于效率考虑,如果新分配的尺寸大小和类型与现有的尺寸大小和类型匹配,则不会执行新的内存分配:image1.create(200,200,CV_8U);1当没有引用指向给定的 cv::Mat 对象时,分配的内存会自动释放,这样可以避免在 C++ 中经常与动态内存分配相关的常见内存泄漏问题,这是 OpenCV 中的一个关键机制,通过让 cv::Mat 类实现引用计数和浅复制来实现。因此,当一个图像分配给另一个图像时,图像数据(即像素)不会被复制,两个图像都将指向同一个内存块,按值传递或按值返回的图像同样也是如此。保留引用计数,以便仅当对图像的所有引用都被销毁或分配给另一个图像时才会释放内存:cv::Mat image4(image3);image1= image3;应用于以上图像 (image3、image4 和 image1) 之一的任何变换也将影响其他图像;如果希望创建图像内容的深层副本,需要使用 copyTo() 方法,在这种情况下,将在目标图像上调用 create() 方法;另一种生成图像副本的方法是 clone() 方法,它创建一个相同的新图像:image3.copyTo(image2);cv::Mat image5= image3.clone();如果需要将一个图像复制到另一个不一定具有相同数据类型的图像中,则必须使用 convertTo() 方法:image1.convertTo(image2,CV_32F,1/255.0,0.0);1以上代码中,源图像 image3 被复制到浮点图像 image2 中。convertTo() 方法包括两个可选参数——比例因子和偏移量。需要注意的是,两个图像的通道数必须相同。cv::Mat 对象的分配模型还允许我们安全地编写返回图像的函数(或类方法):cv::Mat function() {// 创建新图像并返回cv::Mat ima(500,500,CV_8U,50);return ima;}可以从主函数 main() 中调用这个函数 function():cv::Mat gray= function();1如果我们调用函数 function(),那么变量 gray 将保存由函数 function() 创建的图像,而无需分配额外的内存。事实上,从 funtion() 返回的 cv::Mat 实例只是 ima 图像的浅拷贝。当 ima 局部变量超出范围时,该变量被释放,但由于关联的引用计数器指示其内部图像数据正在被另一个实例(即变量 gray )引用,因此不会释放其内存块。需要注意的是,在创建类实例时,不要返回图像的类属性。接下来,我们介绍一个容易出错的实现示例:class ErrorExample {// 图像属性cv::Mat ima;public:ErrorExample(): ima(240, 320, CV_8U, cv::Scalar(100)){}cv::Mat method() {return ima;}}在以上代码中,如果一个函数调用这个类的方法,它会获得一个图像属性的浅拷贝。如果以后这个副本被修改,类属性也会被修改,这会影响类的后续行为(反之亦然),为了避免这类错误,我们应该返回属性的副本。2.2 OpenCV 输入和输出数组查看 OpenCV 文档,可以看到许多方法和函数都接受 cv::InputArray 类型的参数作为输入。该类型是一个简单的代理类,引入此类型用于概括 OpenCV 中数组的概念,从而避免重复实现具有不同输入参数类型的相同方法或函数的多个版本,这意味着可以通过提供 cv::Mat 对象或其他兼容类型作为参数,该类只是一个接口,所以不应该在代码中显式地声明它。cv::InputArray 也可以使用 std::vector 类构造,这意味着这类对象可以用作 OpenCV 方法和函数的输入。其他兼容类型包括 cv::Scalar 和 cv::Vec;相应的,还存在一个 cv::OutputArray 代理类,用于指定某些方法或函数返回的数组。小结cv::Mat 数据结构是 OpenCV 中最基础也是最核心的数据结构,通过此数据结构构成了 OpenCV 图像处理所用的复杂类和函数。本节中,我们介绍了 cv::Mat 结构的基本用法,包括如何创建空白/非空白图像、修改图像数据类型以及复制图像内容等操作,并且深入探索了创建 cv::Mat 数据结构时的内存分配方式,最后介绍了 OpenCV 输入和输出数组的两个代理类,包括 cv::InputArray 和 cv::OutputArray。————————————————版权声明:本文为CSDN博主「盼小辉丶」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/LOVEmy134611/article/details/126692582
-
一:初识GNN 1.什么是GNN 图(Graph) 在讨论GNN之前,我们先来了解一下什么是图。在计算机科学中,图是由节点和边两部分组成的一种数据结构。图G可以通过节点集合V和它包含的边E来进行描述。如下图所示: GNN GNN全称----图神经网络,它是一种直接作用于图结构上的神经网络。我们可以把图中的每一个节点 V VV 当作个体对象,而每一条边 E EE 当作个体与个体间的某种联系,所有节点组成的关系网就是最后的图 U UU。 这里的V , E , U V, E , UV,E,U都可以编码成一个特征向量,所以实际上GNN还是做的是提取特征的工作而已。GNN的一个典型应用是节点分类,我们希望利用GNN提取出每个节点 V VV 的特征向量,来预测每个节点的标签。同样的,也可以通过节点与节点间的特征,来预测出对应边 E EE 的标签。当然,也可以利用所以节点提取出的特征,来预测整个图 V VV 的标签。 如下图: 2.GNN与CNN、RNN的区别 那都是提取特征的神经网络,那为什么要利用图模型来提取呢?CNN的卷积和RNN的递归方式不行吗? 答案还真不行,或者说十分麻烦。 因为GNN面向的输入对象其实都是结构不规则、不固定的数据结构,而CNN面向的图像数据和RNN面向的文本数据的格式都是固定的,所以自然不能混为一谈。因此,面对本身结构、彼此关系都不固定的节点特征,必须需要借助图结构来表征它们的内在联系。 3.GNN的应用领域 GNN应用的领域自然都是由结构不规则、不固定的数据组成的场合了。比如下图所示的场景: 其中的交通流量感知、医疗领域是当前GNN应用最为火热的领域,以上仅供参考。接下来,我们来一起探究GNN的工作原理是什么,到底是如何提取、更新每个节点的特征呢? 二:GNN原理 1.邻接矩阵 首先引入邻接矩阵(Adjacency Matrix)的概念,它来表示节点与节点间的连接关系,即Edge的关系,矩阵的具体样式如下图所示: 2.聚合操作 GNN的输入一般是每个节点的起始特征向量和表示节点间关系的邻接矩阵,有了这两个输入信息,接下来就是聚合操作了。所谓的聚合,其实就是将周边与节点 V i ViVi 有关联的节点{V a , V b , . . . Va,Vb,...Va,Vb,...}加权到V i ViVi上,当作一次特征更新。同理,对图中的每个节点进行聚合操作,更新所有图节点的特征。 聚合操作的方式多种多样,可根据任务的不同自由选择,如下图所示: 当然对这个图节点进行完了一次聚合操作后,还需要再进行一波 w ww 的加权,这里的 w ww 需要网络自己学习。 3.多层迭代 CNN,RNN都可以有多个层,那么GNN也当然可以。一次图节点聚合操作与 w ww 加权,可以理解为一层,后面再重复进行聚合、加权,就是多层迭代了。一般GNN只要3~5层即可,所以训练GNN对算力要求很低。如下图所示: ———————————————— 版权声明:本文为CSDN博主「江南綿雨」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/weixin_43702653/article/details/123779738
-
总所周知,质数(prime number)又称素数,除了1和自身外,不能被其他的自然数整除。那么我们今天就来看看一个简单的寻找素数的算法,欧拉筛。欧拉筛是在埃氏筛的基础上做了一定的改进,大幅降低时间复杂度。欧拉筛输入区间范围n输出素数列表思想通过打表的方式,构建素数表,这张表包含了n个元素,包括素数和合数素数是无法通过其他素数相乘得到的,利用这一原理,可以将所有能够被素数相乘得到的值设置为合数过程创建一个大小为n的列表isPrime,元素值代表是否为素数。创建一个新的可变列表prime,元素值代表素数遍历isPrime,若元素值为1,则将其加入prime列表。将该元素与prime中的所有素数相乘:若该元素为素数,那么会遍历prime列表,得到的结果是最小素数相乘的合数若该元素为合数,那么将为其添加新的最小质数,直到遇到初始质数。(同样也是最小质数相乘)算法n=int(1e5+1)prime=[]isPrime=[1 for i in range(n+1)]# 欧拉筛构建1-n的所有质数for i in range(2,n+1):if isPrime[i]==1:# 质数加入队列prime.append(i)# 删除质数集构成的合数for j in range(len(prime)):if prime[j]*i# 合数去掉了isPrime[prime[j]*i]=0else:break# 通过最小质数来构建即可if i%prime[j]==0:# 当然第一次遇到还是要乘上去的,这样才会倍增breakprint(prime)len(prime) # 664579复杂度时间复杂度约等于O ( N ) O(N)O(N),它只对每个元素遍历一次————————————————版权声明:本文为CSDN博主「快乐小虎鲸biubiu」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/qq_45957458/article/details/127640262
-
【LetMeFly】1700.无法吃午餐的学生数量:真假模拟(极简代码) + 奇技淫巧 力扣题目链接:https://leetcode.cn/problems/number-of-students-unable-to-eat-lunch/ 学校的自助午餐提供圆形和方形的三明治,分别用数字 0 和 1 表示。所有学生站在一个队列里,每个学生要么喜欢圆形的要么喜欢方形的。 餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里,每一轮: 如果队列最前面的学生 喜欢 栈顶的三明治,那么会 拿走它 并离开队列。 否则,这名学生会 放弃这个三明治 并回到队列的尾部。 这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。 给你两个整数数组 students 和 sandwiches ,其中 sandwiches[i] 是栈里面第 i 个三明治的类型(i = 0 是栈的顶部), students[j] 是初始队列里第 j 名学生对三明治的喜好(j = 0 是队列的最开始位置)。请你返回无法吃午餐的学生数量。 示例 1: 输入:students = [1,1,0,0], sandwiches = [0,1,0,1] 输出:0 解释: - 最前面的学生放弃最顶上的三明治,并回到队列的末尾,学生队列变为 students = [1,0,0,1]。 - 最前面的学生放弃最顶上的三明治,并回到队列的末尾,学生队列变为 students = [0,0,1,1]。 - 最前面的学生拿走最顶上的三明治,剩余学生队列为 students = [0,1,1],三明治栈为 sandwiches = [1,0,1]。 - 最前面的学生放弃最顶上的三明治,并回到队列的末尾,学生队列变为 students = [1,1,0]。 - 最前面的学生拿走最顶上的三明治,剩余学生队列为 students = [1,0],三明治栈为 sandwiches = [0,1]。 - 最前面的学生放弃最顶上的三明治,并回到队列的末尾,学生队列变为 students = [0,1]。 - 最前面的学生拿走最顶上的三明治,剩余学生队列为 students = [1],三明治栈为 sandwiches = [1]。 - 最前面的学生拿走最顶上的三明治,剩余学生队列为 students = [],三明治栈为 sandwiches = []。 所以所有学生都有三明治吃。 示例 2: 输入:students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1] 输出:3 提示: 1 <= students.length, sandwiches.length <= 100 students.length == sandwiches.length sandwiches[i] 要么是 0 ,要么是 1 。 students[i] 要么是 0 ,要么是 1 。 方法一:真模拟 真模拟就是真的按照题意,将students变成队列,sandwich变成栈 然后每次从头到尾依次出队,遇到与栈顶元素相同的就“走人” 所有同学都出队过一次也没有匹配到三明治的话,谁都吃不到了,就返回剩余学生的数量。 时间复杂度O ( n 2 ) O(n^2)O(n 2 ),其中n nn是学生个数。(其实遍历不了这么多) 空间复杂度O ( n ) O(n)O(n) AC代码 C++ class Solution { public: int countStudents(vector& students, vector& sandwiches) { queue q; for (int& t : students) { q.push(t); } stack st; for (int i = sandwiches.size() - 1; i >= 0; i--) { st.push(sandwiches[i]); } while (true) { int thisSandwich = st.top(); st.pop(); bool found = false; for (int i = q.size(); i > 0; i--) { int thisStudent = q.front(); q.pop(); if (thisStudent == thisSandwich) { found = true; break; } else { q.push(thisStudent); } } if (!found) { return q.size(); } else if (q.empty()) { return 0; } } return -1; // Fake Return } }; 方法二:假模拟 真的要学生一个一个地出队入队吗? 当然不!假如栈顶三明治是1,那么只要队列中存在1就能匹配上啊 谁先匹配上的不影响结果。 除非剩下学生全是0😉,那所有人都吃不到了。 打住,刚刚说什么,“剩下学生全是0”? 哦哦,这不就是终止条件嘛! 我们只需要从前到后遍历三明治(模拟出栈的过程),如果有学生与这个三明治匹配,那就拿走去吃,否则(所有学生与三明治都不匹配),模拟终止,谁都吃不到了~~(论1的重要性)~~ 如果三明治遍历完了,那就说明所有同学都吃到了,那就返回0 时间复杂度O ( n ) O(n)O(n),其中n nn是学生个数 空间复杂度O ( 1 ) O(1)O(1) AC代码 C++ class Solution { public: int countStudents(vector& students, vector& sandwiches) { // s[0]代表学生中0的数量,s[1]代表学生中1的数量 int s[2] = {(int)count(students.begin(), students.end(), 0), (int)students.size() - s[0]}; // cout << s[0] << ' ' << s[1] << endl; for (int& t : sandwiches) { if (s[t]) // 匹配 s[t]--; // 走人 else // 无人可匹 return s[0] + s[1]; // 谁都别想吃了 } return 0; } }; 注意,这里是学生0和三明治0匹配,不是0和1匹配。 代码简化(行数压缩) class Solution { public: int countStudents(vector& students, vector& sandwiches) { int s[2] = {(int)count(students.begin(), students.end(), 0), (int)students.size() - s[0]}; for (int& t : sandwiches) if (s[t]) s[t]--; else return s[0] + s[1]; return 0; } }; 方法三:奇技淫巧 - 计时器 方法三对应于方法一,也是真模拟。 不同之处在于方法一中,我们需要判断“是否所有学生都出队过一次” 不同的是,方法三中,没有对此进行判断,而是当没有学生能与栈顶三明治匹配时,不断地进行“出队入队出队入队出队入队…” 直到把学生累死,查看尸体个数就行了。 怎么累死呢? 我们在程序中设置一个计时器,对于100个学生这种数量级,一般几毫秒就能模拟完。(我们把几毫秒看成是“午饭时间30min”) 那么好,我们执行个“1000毫秒”,1000ms / 5ms * 30min = 60,000min = 1000h = 41.666…天 让所有学生不吃一口三明治不断排队40多天,肯定累死了。 那么,剩下的学生就是答案。 时间复杂度:不易衡量。如果所有学生都能吃完,那么就是O ( n 2 ) O(n^2)O(n 2 ),其中n nn是学生个数;如果有学生不能吃到,那程序就会执行大约1秒 空间复杂度O ( n ) O(n)O(n) AC代码 C++ class Solution { public: int countStudents(vector& students, vector& sandwiches) { // 构建队列和栈 queue q; for (int& t : students) { q.push(t); } stack st; for (int i = sandwiches.size() - 1; i >= 0; i--) { st.push(sandwiches[i]); } 开始模拟 time_t start = clock(); while (clock() - start < 1000 && q.size()) { if (q.front() == st.top()) q.pop(), st.pop(); else { int thisStudent = q.front(); q.pop(); q.push(thisStudent); } } return q.size(); } }; 同步发文于CSDN,原创不易,转载请附上原文链接哦~ Tisfy:https://letmefly.blog.csdn.net/article/details/127402719 ———————————————— 版权声明:本文为CSDN博主「Tisfy」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/Tisfy/article/details/127402719
-
上一篇文章我们介绍了数组、链表、栈、队列这4种常用的数据结构,这篇文章我们主要介绍下树、图、堆、散列表这4种数据结构以及一些基础算法。数据结构 树(Tree):树是典型的非线性结构,它是包括2个结点的有穷集合K。图(Graph):图是另一种非线性数据结构。在图结构中,数据结点一般称为顶点,而边是顶点的有序偶对。堆(Heap):堆是一种特殊的树形数据结构,一般讨论的堆都是二叉堆。散列表(Hash table):散列表源自于散列函数(Hash function),其思想是如果在结构中存在关键字和T相等的记录,那么必定在F(T)的存储位置可以找到该记录,这样就可以不用进行比较操作而直接取得所查记录。基础算法 数据结构研究的内容:就是如何按一定的逻辑结构,把数据组织起来,并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。算法研究的目的是为了更有效的处理数据,提高数据运算效率。数据的运算是定义在数据的逻辑结构上,但运算的具体实现要在存储结构上进行。一般有以下几种常用运算:检索:检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值,找具有该字段值的节点。插入:往数据结构中增加新的节点。删除:把指定的结点从数据结构中去掉。更新:改变指定节点的一个或多个字段的值。排序:把节点按某种指定的顺序重新排列。例如递增或递减。智能云网智能云网社区是华为专为开发者打造的“学习、开发、验证、交流”一站式支持与服务平台,该平台涵盖多领域知识。目前承载了云园区网络,云广域网络,数通网络开放可编程,超融合数据中心网络,数通网络设备开放社区共五个场景。为了响应广大开发者需求,还提供了开发者交流、API 体验中心、多媒体课件、SDK工具包、开发者工具以及远程实验室共六大工具,让开发者轻松开发。欢迎各位前来体验。《戳我了解更多》
推荐直播
-
华为AI技术发展与挑战:集成需求分析的实战指南
2024/11/26 周二 18:20-20:20
Alex 华为云学堂技术讲师
本期直播将综合讨论华为AI技术的发展现状,技术挑战,并深入探讨华为AI应用开发过程中的需求分析过程,从理论到实践帮助开发者快速掌握华为AI应用集成需求的框架和方法。
去报名 -
华为云DataArts+DWS助力企业数据治理一站式解决方案及应用实践
2024/11/27 周三 16:30-18:00
Walter.chi 华为云数据治理DTSE技术布道师
想知道数据治理项目中,数据主题域如何合理划分?数据标准及主数据标准如何制定?数仓分层模型如何合理规划?华为云DataArts+DWS助力企业数据治理项目一站式解决方案和应用实践告诉您答案!本期将从数据趋势、数据治理方案、数据治理规划及落地,案例分享四个方面来助力企业数据治理项目合理咨询规划及顺利实施。
去报名
热门标签