10亿个数找是否重复的实现方案?
对于64位操作系统来说,内存的上限是2^64,每个整数4个字节的话,那么10亿个数为4*10^10即2^32字节的数据量,因此直接放到内存当中来进行查找操作是不现实的。
可以考虑采用BitMap来进行检查是否重复,一个int可以存储32bit的数据,每个bit依次代表1、2、3、4、5、6 …,因此,2^32次方字节的数据量可以缩小为2^27个int即可表示完成的10亿个数据。
然后再使用位操作来确定数组当中是否存在重复的数。
10亿个数找最小的10个实现方案和时间复杂度?
1、分治算法: 将10亿个数据分成100份,每份1000万个数据,找到每份数据中最大的100个,最后在剩下的10010000个数据里面找出最大的10000个。如果100万数据选择足够理想,那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下:用快速排序的方法,将数据分为2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大堆个数N小于10000个,就在小的那堆里面快速排序一次,找第10000-n大的数字;递归以上过程,就可以找到第1w大的数。参考上面的找出第1w大数字,就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^64=4MB,一共需要101次这样的比较。
2、最小堆: 首先读入前10000个数来创建大小为10000的最小堆,建堆的时间复杂度为O(mlogm)(m为数组的大小即为10000),然后遍历后续的数字,并于堆顶(最小)数字进行比较。如果比最小的数小,则继续读取后续数字;如果比堆顶数字大,则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为O(nmlogm),空间复杂度是10000(常数)。
Mysql中2000w个数要多少层,计算公式是什么?
首先一个mysql的页大概是16k,页头和页尾的大小大概是1k左右,因此实际有效的存储记录的空间为15k。
假设记录大小为1kb,一个mysql的页可以存储的记录条数为15条,对于InnoDB来说的话,所有的数据页都是存储在B+树的叶子节点上的,我们以聚集索引来回答这个问题。
对于聚集索引的非叶子页面来说,其中的记录仅仅为 “主键id(8Bytes)+指向下一个记录的指针(4Bytes)”,因此一个页面能存储的记录条数为15kb/16b = 1280条记录。
- 对于一级索引页来说可以存储1280条records
- 对于二级索引来说可以存储1280x1280条records
- 对于聚集索引的叶子节点来说可以存储1280x1280x15 = 2000w条
因此,Mysql中存储2000w条记录大概需要3层索引就搞定了,但是针对不同的操作系统指针的大小不同,所以这个数据只是一个理论值。
多个线程访问一个数据,怎么保证线程安全?
多线程场景下访问数据之所以会存在问题是由于线程一般属于同一个进程,因此线程之间的内存区域是可以共享的。
因此,对于多个线程去读取、修改同一内存地址的值可能会出现线程安全问题,如:线程A修改了读取了变量,在这期间线程b也读取了变量并修改之后放回原处,此时线程A对该变量的运算就会出现问题。
对于线程安全问题的解决办法主要是进行加锁,即某一个时刻只有一个线程能够占用这个变量,对其进行修改、读写等操作,这样一来就不会出现线程安全问题。
Java当中的保障线程安全的机制有很多,比如sychorinzed、Lock类的锁,以及ConccurentHashMap等线程安全的容器等。
多个线程访问账户金额,怎么保证金额数据一致?
-
免责声明
- 本文发布的信息,最终解释权归作者所有,如有疑问或需要进一步了解,请直接与作者联系。
- 本文部分信息来源于网络,其版权归原作者所有,本文使用该信息仅出于分享给求职者,无任何商业用途,如有侵权,请联系作者删除。
- 本文发布的信息旨在为应届生和社会人士提供了解相关企业招聘信息的便利,不涉及任何机密信息,且所有信息均为网络公开获取。 本人亦无任何渠道可以了解任何机密信息, 如果您认为某些内容存在侵权、泄密问题,请及时联系作者删除。
若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏
更多央国企信息、面试辅导、简历修改等,请关注知识星球:[成都央国企指南]