频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
记一次随机字符串生成算法的随机概率与性能的提升
2015-03-31 08:46:36           
收藏   我要投稿
一、前言背景

 

前几天我部门一个和银行对接的项目中出现了业务Id重复的现象,导致了很多之前不可预见的bug。由于该项目有资金流动,涉及到金钱交易,故不敢有任何闪失。于是leader把同事写的Handler.ashx.cs发给我瞧了瞧,其中的一处流水号生成代码引起了我的注意。代码如下:

 

 

string[] str1 = new string[] { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" };

string[] str2 = new string[] { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z" };

string[] str3 = new string[] { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };

Random r = new Random();

int s1 = r.Next(0, str1.Length - 1);

string a1 = str1[s1];

 

r = new Random();

int s2 = r.Next(0, str2.Length - 1);

string a2 = str2[s2];

 

r = new Random();

int s3 = r.Next(0, str3.Length - 1);

string a3 = str3[s3];

 

string lsh = a1 + a2 + a3;

 

由于交易有可能中途失败,所以每次重新交易的时候,订单号是不变的,但是会重新生成流水号。也就是说在交易开始的时候生成固定订单号,到最终交易结束,这一个业务流程有可能一次性成功,有可能重复多次才能成功,毕竟交易有可能第一次就失败,也有可能连续失败好几次。

 

业务Id=交易订单号+流水号,其中订单号预留9位,流水号规定为3位由大小写英文字母和数字组成的随机字符串。由于订单号是固定且唯一的,那么只要保证生成的流水号是唯一的就能够保证业务Id是唯一的。不过流水号的唯一性的适应范围是依赖订单号的,类似于根据订单号分组,然后每一组里面的流水号不能重复。

 

于是我又急急忙忙问了维护该项目的同事,按照以往惯例,一笔交易最多失败多少次才能成功,同事说最多不会超过10-12次吧。那么也就是说同一个订单号最多也就生成12个流水号,而由大小写英文字母和阿拉伯数字组成的三位随机字符串最多有238328种。但是再看前面同事的代码可以看出,同事生成的随机字符串组成方式是[ 大写英文字母+小写英文字母+阿拉伯数字 ],而按照这种固定的组合方式,最多只能生成26*26*10=6760种三位随机字符串,显然重复概率偏大。

 

 

 

然后再瞧一瞧上面的代码,可以看出同事是使用与时间相关的默认种子值,初始化 Random 类的新实例。并且实例化了3个Random对象,很显然3个Random对象极有可能会产生一模一样的随机数。默认情况下,Random 类的无参数构造函数使用系统时钟生成其种子值,而参数化构造函数可根据当前时间的计时周期数采用Int32值。 但是,因为时钟的分辨率有限,所以,如果使用无参数构造函数连续创建不同的 Random 对象,就会创建生成相同随机数序列的随机数生成器。

 

 

 

经过了这么一分析,显然这种生成三位随机字符串的方式存在极大的重复隐患。由于博主一贯主张在公司干活的首要目标是快速解决问题,于是博主决定先去网上找一找,看看有没有比较通用靠谱的代码。但是几近波折,发现大多不如意,好吧,抡起袖子自己造轮子吧!

 

 

 

二、技术实现

 

1、Random 类是伪随机数生成器,伪随机数是以相同的概率从一组有限的数字中选取的。 所选数字并不具有完全的随机性,因为它们是用一种确定的数学算法选择的,但是从实用的角度而言,其随机程度已足够了。但是针对上述场景用起来总觉得随机性偏弱,于是博主在MSDN有了新的发现,发现了一个可以生成强随机数的类:RNGCryptoServiceProvider。该类可以使用加密服务提供程序 (CSP) 提供的实现来实现加密随机数生成器 (RNG),显然随机性要大于Random类。

 

 

private int GetRandomInt(int maxValue)

{

    if (maxValue < 0)

    {

        throw new ArgumentOutOfRangeException("maxValue", "maxValue 小于零。");

    }

    S_rng.GetBytes(S_buffer);

    int value = BitConverter.ToInt32(S_buffer, 0);

    value = value % (maxValue + 1);

    if (value < 0) value = -value;

    return value;

}

 

 

 

2、同事既然把生成随机字符串的方式固定为[ 大写英文字母+小写英文字母+阿拉伯数字 ],显然这样子不对,还可以有诸如[ 大写英文字母+大写英文字母+大写英文字母 ]、[ 大写英文字母+阿拉伯数字+大写英文字母 ]等等其他组合方式的。也就是数学里面的组合,从n个不同元素中任意取出m个元素进行组合,允许组合内有重复元素,比如生成4位随机字符串就是[ 大写英文字母+小写英文字母+阿拉伯数字+阿拉伯数字 ]。

 

为了便于支持多种数据类型的元素进行可重复组合,采用泛型。

 

 

private void GetAllCombination<T>(List<T[]> values, T[] array, T[] buffer, int index)

{

    if (index == 0)

    {

        foreach (T value in array)

        {

            buffer[0] = value;

            T[] tmp = new T[buffer.Length];

            buffer.CopyTo(tmp, 0);

            int l = tmp.Length;

            for (int i = 0; i < l / 2; i++)

            {

                T t = tmp[i];

                tmp[i] = tmp[l - i - 1];

                tmp[l - i - 1] = t;

            }

            values.Add(tmp);

        }

    }

    else

    {

        foreach (T value in array)

        {

            buffer[index] = value;

            GetAllCombination(values, array, buffer, index - 1);

        }

    }

}

 

private List<T[]> GetAllCombination<T>(T[] array, int m)

{

    List<T[]> values = new List<T[]>();

    T[] buffer = new T[m];

    GetAllCombination(values, array, buffer, m - 1);

    return values;

}

 

 

 

3、为了保证RandomString类的同一个实例对象生成的随机字符串都是唯一的,博主特意在内部弄了一个容器,并且加锁以支持多线程访问。

 

 

/// <summary>

/// 生成一个由大小写英文字母和数字组成的随机字符串

/// </summary>

/// <returns></returns>

public string Next()

{

    while (true)

    {

        string indexType = CombinationType[GetRandomInt(CombinationType.Count - 1)].Item2;

        string randomString = string.Empty;

        foreach (var item in indexType)

        {

            randomString += GetRandomChar(item.ToString());

        }

 

        lock (this._lockObj)

        {

            if (!this._listRandomString.Contains(randomString))

            {

                this._listRandomString.Add(randomString);

                return randomString;

            }

        }

    }

}

 

 

 

4、扩展属性

 

 

/// <summary>

/// 随机字符串的位置组合信息

/// </summary>

public List<Tuple<int, string, int>> CombinationType { get; private set; }

/// <summary>

/// RandomString对象实例最多可以产生的随机字符串

/// </summary>

public int Count { get; private set; }

 

 

 

三、结语思考

 

以上关键代码均以贴出,博主也只是阐述自己的思考方式,借助此文抛砖引玉,希望得到大家指点。由于组合用的是递归算法,则必然导致性能低下,可否有大神还有其他方式进行优化?

 

 

 

 

通过性能测试可以看出,当m为13时开始出现瓶颈。

点击复制链接 与好友分享!回本站首页
上一篇:设计模式-单例模式
下一篇:Struts2--- 一步步的产生史
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站