博文

目前显示的是 四月, 2019的博文

面试基础-插入排序

图片
第二个排序算法,插入排序的思想是遍历数组中的每一个元素,插入到已经有序的数组中,插入的过程仍需保持数组的有序性。实际写代码时,插入的过程类似于冒泡的过程,从后往前遍历,找到合适的位置插入。插入排序是一次只关心一个元素,直接找到最终位置,冒泡排序是一次比较若干元素,找到一个最大元素放到最终位置。 测试输入:new int[]{1, 17, 6, 9, 2, 4, 100, 38, 94, 29, 46, 3, 57, 65, 19, 5}; /** * 从后往前遍历插入,这个插入过程有点像冒泡,只冒到合适的位置即可 * * @param arr */ public void sort(int[] arr) { int compareTimes = 0; int swapTimes = 0; for (int i = 1; i < arr.length; i++) { for (int j = i; j > 0; j--) { compareTimes++; if (arr[j] < arr[j - 1]) { Util.swap(arr, j, j - 1); swapTimes++; } else { break; } } } System.out.println("数组长度:" + arr.length + " 比较次数:" + compareTimes + " 交换次数:" + swapTimes); } 打印输出:数组长度:16 比较次数:61 交换次数:46 图片仍来自百度,图片能大致反应排序的思想,但仍不能完全的反应内存真实的动作,所以想自己写一个动画,来反应排序过程中数据在内存中的动画效果,包括比较过程,包括交换过程。...

面试基础-冒泡排序

图片
        多年的开发经验仍不能透彻理解一些基础的算法,按说懂个大概也行啊,言语稍微变通一下就可以啦,可更重要的是言语表达也是不在行,遇到一些姿态较高的,又爱跟你较真和抬扛的人的时候,就无奈了。想想算了吧,随他吧。可是你自己呢,别人看到的你仍是小白啊,那我就把自己当作小白,重新来过吧。         没有系统的按照教科书的顺序,只按自己想到哪,学到哪,记录到哪。 下面进入正题,先来个冒泡排序。一个最简版本,一个稍微优化版本。 测试输入:new int[]{1, 17, 6, 9, 2, 4, 100, 38, 94, 29, 46, 3, 57, 65, 19, 5}; /** * 最差的冒泡排序 * n*(n-1)次比较,0-n*(n-1)次交换 * * @param arr */ public void sort0(int[] arr) { int compareTimes = 0; int swapTimes = 0; for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length - 1; j++) { compareTimes++; if (arr[j] > arr[j + 1]) { Util.swap(arr, j, j + 1); swapTimes++; } } } System.out.println("数组长度:" + arr.length + " 比较次数:" + compareTimes + " 交换次数:" + swapTimes); } 打印输出:数组长度:16 比较次数:240 交换次数:46 /** * 稍优化一点的冒泡排序 ...

死锁产生条件和如何处理死锁

图片
死锁是在计算机系统中,两个或者两个以上的进程(或者线程),在执行过程中由于某些存在竞争的资源没有合理的管理和释放而导致线程阻塞,无法继续执行下去的状态。 图片来自百度 死锁产生的条件 1,资源互斥,资源同时只能被有限的线程占有 2,阻塞不释放,线程申请资源阻塞后,不释放已经持有的资源 3,不可剥夺,线程持有的资源,是不能被其它线程剥夺的,只能由自己使用完了释放 4,循环等待,存在一个资源等待环, 死锁会导致资源无法释放,系统hang住,这毕竟是我们不想看到的现象 在死锁产生之前,我们需预防和避免,主要思想就是破坏产生的条件,下面针对四个条件分别进行破坏~ 1,资源互斥,如果资源是可以被无限共享和使用的,那也就不存在死锁的问题了 2,线程申请资源阻塞后,释放已经持有的资源,线程返回失败 3,线程按优先级排序,优先级高的线程可以剥夺优先级低的线程持有的资源 4,申请资源的时候检测,如果此次申请如果能产生环路,则取消此次申请 其它方案 5,一次性请求所有资源 6,资源编号,按顺序申请使用 7,超时释放重试 实际方案中,应该是没有针对剥夺与资源互斥上面下手的 在死锁产生之后,我们需要处理后续的问题 1,检测死锁,终止死锁等待环中的节点 2,重启进程 《 Java并发编程实战 》中谈到,数据库系统在设计的时候考虑到了死锁的监测以及从死锁中恢复,当检测到死锁时,将选择一个事务作为牺牲者,让其它事务继续执行,应用程序可以重新发起被强行中止的事务 对于java程序,无法从死锁中恢复,所以都会在开发阶段避免死锁,在实际应用中,对于已经发生死锁的情况,通常都需要根据进程信息等,先定位到死锁的位置,然后重启来解决当时的问题,再优化死锁产生的位置,达到根治的目的 

分布式事务梳理

分布式事务目前流行的方案也有很多种,网上能找到大把的技术文章,但看人家的文章总是有各种问题,要么某些地方不好理解,要么某些地方认为不正确,还是按自己的视角来梳理一下。 目前看到的方案,2PC,3PC,TCC,事务消息,本地消息表,等等。 一,2PC 多个数据库在同一个公司,同一个网段可访问到,以及数据库支持2PC,先对多个要提交的事务先发起预提交,多个库确认可以commit了之后,再发起确认commit,当然这个方案存在一些问题,前面说的前提是一些场景上的限制,场景适用后,在发起commit阶段仍然会有可能有不一致的可能性存在,后面会有3PC,同样也是解决了部分问题,无法最终解决一致性问题。 二,3PC 3PC是在2PC的基础之上,在commit又分成了2步,进一步减少数据不一致的可能性。 三,TCC 其实TCC和2PC原理基本一样,只是TCC是不同的资源可能在不同公司,采用不同的服务的方式,多个服务需要支持一个完整的事务,这时候2PC就不适用了,TCC相当于把每个需要事务控制的服务提供确认和取消的操作,这样,在发起事务前先预先锁住资源,待所有资源都确认可以获得,再发起确认操作,中间如有某一个资源预先获取失败,则会取消其它的资源的持有。 在一篇文章又看到解释TCC又分几种类型,通用型,补偿型,异步确保型。通用型也就是刚刚说到的这种,补偿型稍微有点不一样,只提供提交和撤回操作,异步确保型则引入MQ。 对于TCC方案,后面的确认环节同样存在一定的问题,会有不一致的可能性存在,这时候就需要一些超时机制,check机制来尽可能的自动确保事务的一致性,这些机制几乎能解决因网络抖动,服务暂时不可用或者down机后快速恢复等情况引发的问题,对于一些更严重的故障,甚至比如程序出了bug,无法恢复的情况,最终也只能引入人工来修复。 四,事务消息 刚才有提到引入MQ,对于发MQ和本地的操作如何能够保证一致性呢,这个就引出了事务消息的概念,普通的MQ无法保证消息发成功和本地的业务的完全一致性,为了这个目标,在MQ系统中引用2PC的方案,先提交一次消息,然后执行业务,完成之后再次提交一次确认消息,对于没有收到确认的消息,定时轮询回查业务方,或者定期删除。 五,事务消息-本地消息表 有文章提到ebay的一个实现方案,本地消息表来保证本地事...