分类目录:算法

以下是分类 算法 下的所有文章

LRUMap的简单实现

定义: LRUMap使用最近最少使用算法,当一个元素添加或者被访问,就是最近最多使用的,内部维护一个列表,表头是最近最少使用的元素,表尾是最近最多使用的,当一个元素添加或者被访问时候,这个元素会被移动到列表表尾,而当元素数量达到最大的时候,会从表头删除一个原色。 实现: 12345678910111213141516171819202122……

按照权重返回数组中的数字

问题:有N个数字,每个数字有一个权重,例如:[1, 0.2] [5, 0.5] [8, 0.3], 要求按照权重来返回数字。 算法描述: 这个需要使用随机数产生数组索引,但是随机数产生的索引是均等概率的,由于需要按照权重来返回数字,我们需要舍弃一些数字,权重小得舍弃的多,权重大得舍弃的少。 算法: 1. 根据权重数组,生成权重次数数……

二分查找的扩展算法

二分查找已经是个家喻户晓的查找算法,并且得到了广泛的应用,大家都知道二分查找每次把一个排序的数组分成三个区间, [s, m)、 (m,e]、[m,m]三个区间,也就是取得中间的一个节点,前面一个区间,后面一个区间,中间节点是一个区间,然后对比中间节点是否是目标元素,如果不是,由于数组的有序性,可以舍弃一半的数据,因……

平均概率洗牌的问题

问题:具有100个数字的数组,需要实现洗牌,让每个数字均等概率放在每个位置上。 算法: 1. 第1次从100个数字中以均等概率随机的拿出一个放在第1个位置; 2. 第2次从剩下的99个数字中以均等概率随机拿出一个放在第2个位置; 3. 第3次从剩下的98个数字中以均等概率随机拿出一个放在第3个位置; ......... 99. ……

LMAX的Disruptor的RingBuffer学习笔记

并发queue实现的传统方法 链表:节点分散,不利于cache和批量读取,分配节点需要大量GC,size/head/tail有大量的竞争,存在CPU缓存的伪竞争问题。 数组:size/head/tail一样有大量的竞争,传统方法是在所有的写操作上做互斥,效率低下,这几个字段写在一起存在CPU缓存的伪竞争。 减少竞争点 RingBuffer也是个数组,不过,……

【转载】各种排序及其时间复杂度

本文部分来自互联网,已经不记得出处,请见谅。 1.选择排序:不稳定,时间复杂度 O(n^2)     选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的位置已经是正确的了。  2.插入排序:稳定,时间复杂度 O(n^2)     插入排序的基本思……

在多个源串中找到同位词

不考虑字母顺序,含有相同字符的单词称为同位词, 也有人称为兄弟单词,例如army和mary。本算法把输入的字符串按照字母顺序排序,然后,放入hash表,hash表的key是按字母顺序排序的字符串,值则是一个列表,列表是这些字母组成的多个同位词。 假设源数组有n个字符串,构造hash表需要O(n)的时间复杂度,查找则需要O(1)的复……

一亿个数字求top10

凡是求top多少的问题,基本都是使用堆排序,因为堆每次调整只需要log2k的时间复杂度,k是堆的大小,在此类题中是求最大或者最小的那些数字的数量,因此会将复杂度极大的进行简化。 假设一共有n个数字,求top k的数字,那么复杂度是O(nlog2k), 如果n = 100000000, k = 10, 计算得到100000000*log2^10 = 300000000, 也就是……

使用均等概率产生(0,1)的函数实现均等概率产生(0,1,2)的函数

这是一个同事和我一起讨论的一道概率方面的算法问题,边讨论边实现,在实现算法的时候对问题和解决方法都是注释满满的,代码也是自解释的,这里就不多说了,直接贴代码,看代码理解算法更可靠。 问题定义 123456789101112131415161718192021222324package com.robert.dsal.math.probability.conversion; import java.uti……

为Java 8中并行流式计算指定定制化的线程池

本文为译文,原文连接:How to specify thread-pool for Java 8 parallel streams 对流式计算的支持是Java 8的一个新特性,并行流式计算更是倍受好评的一大功能。这些功能使大规模流式计算的实现变得简单。 例如:如果我想找到1亿以内的所有质数,在Java 8中我可以这样写: range(1, 1_000_000).parallel().filter(Primes……

聚簇索引(InnoDB)快还是非聚簇(MyISAM)索引快

一个朋友问我聚簇索引快还是非聚簇索引快呢?这个问题其实很难回答,也很难进行一个实际的测试来判断到底哪个快,除了聚簇索引和非聚簇索引在原理上的不同,实际上一个存储引擎的索引快慢还受其实现方法和功能的影响,比如,事物,锁,高并发,存储策略,缓存策略等,本文就简单的从理论上进行分析,根据索引的实现原来来……

【转载】【经典】MySQL索引背后的数据结构及算法原理

本文系经典,转载自:http://www.uml.org.cn/sjjm/201107145.asp#nav-4-1   MySQL索引背后的数据结构及算法原理 张洋,发布于2011-07-14, 张洋的Blog 写在前面的话 在 编程领域有一句人尽皆知的法则“程序 = 数据结构 + 算法”,我个人是不太赞同这句话(因为我觉得程序不仅仅是数据结构加算法……