C# 蓄水池抽样
2024-09-03 17:16:13
蓄水池采样算法解决的是在给定但长度未知的大数据集中,随机等概率抽取一个数据。如果知道数据的长度,可以用随机数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)。
最新文章
- PHP常见的低级错误
- iOS 如何设置导航的滑动返回手势, 和系统饿一样
- CSS3学习(圆角、图片、阴影、背景、渐变、文本、字体、2D、3D、过渡等)
- HTTP Keep-Alive模式
- 安装Nginx的Dockerfile实例
- Yii Model中添加默认搜索条件
- ";A transport-level error has occurred when sending the request to the server,指定的网络名不在可用";的解决办法
- [每日自动更新]Hillstone 山石网科 StoneOS ISP路由表配置文件
- apple-touch-icon,shortcut icon和icon的区别(手机站发送到手机桌面图标自定义)
- Android内存Activity泄露:Threads
- HDU5806 NanoApe Loves Sequence Ⅱ (BestCoder Round #86 C)二分
- HDU5643-King&#39;s Game
- json 转 javaBean
- Gson解析json繁杂数据
- .NET - 代码重构技巧
- 怎样用Java编写一段代码引发内存泄露
- CVE-2014-4113:飓风熊猫(HURRICANE PANDA)Win64bit提起权0day破绽
- java工程开发之图形化界面之(第一课)
- 标准会话对象——StandardSession
- 记录使用nodejs时,未正确使用import导致的错误
热门文章
- Qt QComboBox之setEditable和currentTextChanged及其源码分析
- Spring Boot-Profile
- Spring-JdbcTemplate(注入到spring容器)-01
- 使用 LOAD DATA LOCAL INFILE,sysbench 导数速度提升30%
- pycharm的安装指导教程以及破解
- switch 用法
- 四、初识Java
- 2021.08.05 P1340 兽径管理(最小生成树)
- Android第五六周作业
- python基础练习题(题目 猴子吃桃问题:猴子第一天摘下若干个桃子,当即吃了一半,还不瘾,又多吃了一个第二天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时,见只剩下一个桃子了。求第一天共摘了多少)