蓄水池采样算法解决的是在给定但长度未知的大数据集中,随机等概率抽取一个数据。如果知道数据的长度,可以用随机数rand()%n得到一个确切的随机位置,或者分块取值来构造随机,那么该位置的对象就是所求的对象,选中的概率是1/n。那长度未知特别是如果这个大数据集不能一次性放入内存中,蓄水池抽样算法就非常有用,在我的项目中采用的蓄水池随机抽样还加入了权重的计算。

其中方法中核心代码,也就是蓄水池抽样就是如下代码。

if (i < spotQuantity)
{
    titleIndexList.Add(i);
    eigenValueList.Add(tempEigenValue);
}
else
{
    double minEigenValue = eigenValueList.Min();
    int minIndex = eigenValueList.IndexOf(minEigenValue);

    if (tempEigenValue > minEigenValue)
    {
        eigenValueList[minIndex] = tempEigenValue;
        titleIndexList[minIndex] = i;
    }
}

首先从计算出的要抽取多少数量,根据数据循环,先让抽取数量的数据放入池子中titleIndexList,并且将对应数据的权重放入到抽取数据的权重列表。 在后面的循环中,判断抽取的权重如果大于已经抽取的最小权重则替换最小权重的数据为当前循环的数据。 如果你不是按照权重,则可以产生一个随机数,如果随机数落在已经抽取队列的数组下标内,则替换掉原来的下标数据也能实现随机性。

        public static void WeightedSampling(List<article> articleList, int grade)
        {
            //根据传入的grade 计算一个抽样数量。
            double sampleFactor = (double)Math.Pow((double)1 / (1 + grade), Math.E);
            var spotQuantity = (int)Math.Ceiling(articleList.Count() * sampleFactor);
            //如果规则抽的数量已经超过随机抽取数则不再抽取
            var spotedCount = articleList.Where(t => t.isspot == 1).Count();
            if (spotedCount >= spotQuantity)
                return;
            //如果数量不足则补齐
            spotQuantity -= spotedCount;
            var spotTitleList = articleList.Where(t => t.isspot != 1).ToList();
            //实例化池子和数据权重List
            List<int> titleIndexList = new List<int>();
            List<double> eigenValueList = new List<double>();

            if (spotArticle.Count() <= spotQuantity)
            {
                for (int i = 0; i < spotArticle.Count(); i++)
                {
                    spotArticle[i].isspot = 1;
                }
            }
            else
            {
                var random = new Random();
                for (int i = 0; i < spotTitleList.Count; i++)
                {
                    double tempWeight = spotTitleList[i].eigenvalue;
                    double tempEigenValue = Math.Pow(random.NextDouble(), 1 / tempWeight);

                    if (i < spotQuantity)
                    {
                        titleIndexList.Add(i);
                        eigenValueList.Add(tempEigenValue);
                    }
                    else
                    {
                        double minEigenValue = eigenValueList.Min();
                        int minIndex = eigenValueList.IndexOf(minEigenValue);

                        if (tempEigenValue > minEigenValue)
                        {
                            eigenValueList[minIndex] = tempEigenValue;
                            titleIndexList[minIndex] = i;
                        }
                    }
                }
                //将抽取出来的对象isspot 抽取标志设置为1
                foreach (var index in titleIndexList)
                {
                    spotTitleList[index].isspot = 1;
                }
            }
        }

该方法对于我们平时项目中抽取不知道数据长度的随机数是非常好用的算法,同时该算法不复杂其时间复杂度为O(n)。

作者:|XSpringSun|,原文链接: https://www.cnblogs.com/SunSpring/p/16308794.html

文章推荐

ShardingSphere-proxy-5.0.0分布式雪花ID生成(三)

附001.Python多版本环境管理

《Unix 网络编程》05:TCP C/S 程序示例

使用 oh-my-posh 美化 windows terminal,让其接近oh-my-zsh

[SQLServer]NetCore中将SQLServer数据库备份为Sql脚本

RabbitMQ 工作队列

Jetson Nano配置YOLOv5并实现FPS=25

MongoDB是什么?非关系型数据库的优点?安装使用教程

Electron+Vue3+TypeScript+Vite +Vue.

苗大东:京东基于强化学习的电商搜索排序算法

数据分析:线性回归

Blazor和Vue对比学习(基础1.9):表单输入绑定和验证,VeeV...