精华内容
下载资源
问答
  • AMS算法

    2017-05-10 23:42:00
    FILE *fp =fopen("./stream_for_ams.txt","r"); 32 33 FILE *fp =fopen( " ./stream_sample_ams.txt " , " r " ); 34 35 srand(time( 0 )); 36 for (j= 0 ;j;j++ ) 37 { 38 loc[j]=rand...
      1 #include<stdio.h>
      2 #include<stdlib.h>
      3 #include<time.h>
      4 
      5 #define N 1000//采样点的个数
      6 #define M 5//分组
      7 
      8 #define SIZE 10000
      9 
     10 typedef struct
     11 {
     12     int element;
     13     int count;
     14 }ATTRIBUTE;
     15 
     16 
     17 int main()
     18 {
     19     ATTRIBUTE attr[100000];
     20     int secmom=0;//真实二阶矩
     21     int data;//接收读取之后的值
     22     int i=0,j,k;//循环控制变量
     23     int count_tmp=0;//临时计数变量
     24     //int n=5;//采样点的个数
     25     double secmom_estima=0;
     26     ATTRIBUTE sample[10000];
     27     int tmp;
     28     int a[10000];
     29     int loc[N];//采样位置保存在数组里
     30     int sample_group[M][N];
     31     //FILE *fp =fopen("./stream_for_ams.txt","r");
     32 
     33     FILE *fp =fopen("./stream_sample_ams.txt","r");
     34 
     35     srand(time(0));
     36     for(j=0;j<N;j++)
     37     {
     38         loc[j]=rand()%SIZE;//获取随机采样位置
     39     }
     40 
     41     for(j=0;j<N;j++)//随机位置排序
     42     {
     43         for(k=j+1;k<N;k++)
     44         {
     45             if(loc[j] > loc[k])
     46             {
     47                 tmp = loc[k];
     48                 loc[k]=loc[j];
     49                 loc[j]=tmp;
     50             }
     51         }
     52     }
     53 
     54     if(fp == NULL)//文件读取失败
     55     {
     56         printf("file can't open!\n");
     57         exit(0);
     58     }
     59     while(!feof(fp))
     60     {
     61         fscanf(fp,"%d",&data);
     62         a[i]=data;//存数据
     63         /***************采样*****************/
     64         for(j=0;j<N;j++)
     65         {
     66             if(loc[j] == i)
     67             {
     68                 sample[j].element=data;
     69                 sample[j].count=0;
     70             }
     71             if(sample[j].element == data)
     72             {
     73                 sample[j].count+=1;
     74             }
     75         }
     76 
     77         /*****************真实***********************/
     78         for(j=0;j<count_tmp;j++)
     79         {
     80             if(attr[j].element == data)//如果该数据被存过则count+1
     81             {
     82                 attr[j].count +=1;
     83                 break;//扫描比对成功退出循环
     84             }
     85         }
     86         if( j == count_tmp)//如果没有该数据第一次出现
     87         {
     88             attr[count_tmp].element=data;//记录
     89             attr[count_tmp].count=1;
     90             count_tmp++;//记录第一次出现的数
     91         }
     92         printf("%.2lf%%\r", i * 100.0/ SIZE);
     93         i++;
     94     }
     95 
     96     /******************组合估计二阶矩***********************/
     97     for(i=0;i<M;i++)//分组M
     98     {
     99         for(j=0;j<N;j++)//每组N个随机位置
    100         {
    101             loc[j]=rand()%SIZE;//获取随机采样位置
    102         }
    103         for(j=0;j<N;j++)//随机位置排序
    104         {
    105             for(k=j+1;k<N;k++)
    106             {
    107                 if(loc[j] > loc[k])
    108                 {
    109                     tmp = loc[k];
    110                     loc[k]=loc[j];
    111                     loc[j]=tmp;
    112                 }
    113             }
    114         }
    115         for(j=0;j<N;j++)
    116         {
    117             if(loc[j] == i)
    118             {
    119                 sample_group[i][j]=
    120                 sample[j].count=0;
    121             }
    122             if(sample[j].element == data)
    123             {
    124                 sample[j].count+=1;
    125             }
    126         }
    127 
    128     }
    129 
    130     /************估计无组合估计二阶矩**********************/
    131     for(j=0;j<N;j++)
    132     {
    133         secmom_estima+=SIZE*(2.0*sample[j].count-1);
    134     }
    135     printf("无组合估计二阶矩:%.2lf\n",secmom_estima/N);
    136 
    137     /***********真实二阶矩*************/
    138     for(j=0;j<count_tmp;j++)
    139     {
    140         //printf("%d\t%d\n",attr[j].element,attr[j].count);
    141         secmom+=attr[j].count*attr[j].count;
    142     }
    143     printf("独立数%d\n",count_tmp);
    144     printf("真实二阶矩为:%d\n",secmom);
    145 
    146     system("pause");
    147     return 0;
    148 }

     

    转载于:https://www.cnblogs.com/SimonKly/p/6838825.html

    展开全文
  • AMS算法 大数据实验4

    2021-05-30 20:29:01
    AMS算法 实验要求: 使用自己所擅长的程序语言编写AMS算法(估计数据流元素的二阶矩)。假设所有元素为1-n,mi表示元素i的出现次数(在整个文件中的出现次数),则二阶矩等于(m1)2+(m2)2+(m3)2+…+(mn)2。 实验步骤: 1...

    AMS算法

    实验要求:

    使用自己所擅长的程序语言编写AMS算法(估计数据流元素的二阶矩)。假设所有元素为1-n,mi表示元素i的出现次数(在整个文件中的出现次数),则二阶矩等于(m1)2+(m2)2+(m3)2+…+(mn)2。

    实验步骤:

    1:以stream_for_ams.txt文件为自己所写程序的输入,读取文件中数据(数值范围是1-105);
    2:请编写一个精确算法A,来计算整个文件stream_for_ams.txt中所有数据的二阶矩的真实值(179866);
    3:假设文件中的数据为e1,e2,e3,…,eN,设采样点个数为n个,即随机从数据中选取1个位置后,利用AMS算法计算估计的二阶矩值(参看书第二版,112页);
    4:使用书上110页(组合估计)的技巧;假设有m分组,每个分组包含n个位置;对于每组计算二阶矩估计的平均值作为改组的二阶矩估计,然后用m个组的二阶矩估计的中位数,作为最终的二阶矩估计值;

    5:设真实的二阶矩为M, 令m=1,n=1, 重复实验步骤4,20次,可以得到20个的估计值(二阶矩)M1 M2 ,…,M20,计算平均误差error_sum ={[ (M1-M)2+( M2-M)2+( M3-M)2+…++( M20-M)2]/20}0.5;
    6:令m=10,n=10, 重复步骤,比较当m=1,n=1时的平均误差与m=10,n=10的平均误差。
    7: 在数据流长度未知的情况下,给定选择位置个数100(样本集合大小),综合水库采样算法和ams算法,设计编写新的算法,该算法在任意时刻都可以给出数据流中当前元素二阶矩的估计;

    实验考察要求:

    1:分析并讲解自己所编写程序;
    2:分析m=1,n=1时和m=10,n=10时,平均误差有区别的原因;
    3:结合ams和水库算法,编写出可以处理数据大小未知的情况的二阶矩估计算法;

    真实二阶矩值

    def Count_accurate():
        data_flu = {}
        sum=0
        with open("stream_for_ams.txt",'r') as f:
            while True:
                temp = f.readline()
                if temp =='':
                    break
                temp=int(temp.strip())
                if temp in data_flu:
                    data_flu[temp]+=1
                else:
                    data_flu[temp]=1
        for i in data_flu.values():
            sum+=i**2
        return sum
           
    print(Count_accurate())
    
    1798766
    
    a = {1:2,3:4}
    a[1]=5
    print(a)
    print(2 in a)
    
    {1: 5, 3: 4}
    False
    

    统计整个数据流的长度

    def Count_length():
        sum=0
        with open("stream_for_ams.txt",'r') as f:
            while True:
                temp = f.readline()
                if temp =='':
                    break
                sum+=1
        return sum
    print(Count_length())
    
    350000
    

    单个随机数的估计

    import random
    def Count_estimate():
        data_flu = {}
        sum=0
        count =0
        flag =0
        n =Count_length()
        x = random.randint(1,n)
        with open("stream_for_ams.txt",'r') as f:
            while True:
                temp = f.readline()
                if temp =='':
                    break
                count+=1
                if count<x:
                    continue
                temp=int(temp.strip())
                if flag==0:
                    data_flu[temp]=0          
                    flag =1
                if temp in data_flu:
                    data_flu[temp]+=1
    
        for i in data_flu.values():
            value = n*(2*i-1)
        return value
    print(Count_estimate())
    
    1050000
    

    m,n的估计

    import random
    #不考虑随机到的下标代表的值相同的情况
    def Count_estimate_1(m,l):
        data_flu = {}
        sum=0
        count =0#用来记录当前数据流中的访问节点
        value_ml = []
        n =Count_length()   
        R_average=[]
        random_x_index=[]
        for i in range(m*l):
            x = random.randint(1,n)
            random_x_index.append(x)
        random_x_index.sort() #对随机出来的下标进行排序
        # print(random_x_index)
        count1=0#用来记录访问到的随机位置的下标        
        count2=0
        flag =0
        with open("stream_for_ams.txt",'r') as f:
            while True:
                temp = f.readline()
                if temp =='':
                    break
                count+=1
                temp=int(temp.strip())
                if count==random_x_index[count1]:
                    flag=1#说明出现了第一个要找到下标
                    count1+=1#进入下一个下标的对比
                    if count1==len(random_x_index):#为了防止最后一个下标加一之后产生越界
                        count1-=1                             
                    if temp in data_flu:
                        data_flu[temp]+=1          
                    else:
                        data_flu[temp]=1
                    continue#如果这里加入了,下面的就不要加了,直接进入下一个数
                if flag==1:#小于 第一个要加入的下标都不计入
                    if temp in data_flu: #在的就加一,不在的就不管,只统计随机到的数
                        data_flu[temp]+=1  
        # print(list(data_flu.values()))              
        for i in data_flu.values():
            value_ml.append(i)
            print(i)
        for i in value_ml:
            estm = n*(2*i-1)
            sum+=estm
            count2+=1
            if count2%l ==0:
                R_average.append(sum/l)
                sum = 0
        R_average.sort()
        R_middle = R_average[len(R_average)//2]
        
        return R_middle
    print(Count_estimate_1(2,2))
    
    5
    2
    2
    2
    2100000.0
    

    对于m,l算法的改进

    import random
    #考虑到随机到的下标代表的值相同的情况  同时修复了随机到相同地方会出现bug的问题
    def Count_estimate_2(m,l):
        data_flu = []#用来记录不同下标随机到的数出现的次数 [[index,value,count].....]
        sum=0
        count =0#用来记录当前数据流中的访问节点
        value_ml = []
        n =Count_length()   
        R_average=[]
        random_x_index=[]
        for i in range(m*l):
            x = random.randint(1,n)
            random_x_index.append(x)
        random_x_index.sort() #对随机出来的下标进行排序
        # print(random_x_index)
        count1=0#用来记录访问到的随机位置的下标        
        count2=0
        flag =0
        with open("stream_for_ams.txt",'r') as f:
            while True:
                temp = f.readline()
                if temp =='':
                    break
                count+=1
                temp=int(temp.strip())
                while count==random_x_index[count1]:#这里用while表示如果遇到了相同的下标,那就接着后移,加入到记录当中
                    flag=1#说明出现了第一个要找到下标
                    data_flu.append([count,temp,0])
                    for i in data_flu:
                        if temp==i[1]:
                            i[2]+=1
                    count1+=1#进入下一个下标的对比
                    if count1==len(random_x_index):#为了防止最后一个下标加一之后产生越界
                        count1-=1
                        break #防止访问到最后一个元素的时候死循环                                        
                    continue#如果这里加入了,下面的就不要加了,直接进入下一个数
                if flag==1:#小于 第一个要加入的下标都不计入
                    for i in data_flu:
                        if temp==i[1]:
                            i[2]+=1
        # print(list(data_flu.values()))              
        for i in data_flu:
            value_ml.append(i[2])
            # print(i[2])
        for i in value_ml:
            estm = n*(2*i-1)
            sum+=estm
            count2+=1
            if count2%l ==0:
                R_average.append(sum/l)
                sum = 0
        R_average.sort()
        R_middle = R_average[len(R_average)//2]
        
        return R_middle
    # print(Count_estimate_2(2,2))
    
    def error_sum(m,l,t):
        sum=0
        real_value = Count_length()
        for i in range(t):
            print(Count_estimate_2(m,l))
            sum+=(Count_estimate_2(m,l)-real_value)
        return sum/t
    
    print("(1,1)重复20次 的平均误差值是",error_sum(1,1,20))
    
    9450000.0
    3850000.0
    1050000.0
    1750000.0
    1050000.0
    2450000.0
    1750000.0
    1050000.0
    3150000.0
    1050000.0
    2450000.0
    1050000.0
    2450000.0
    1050000.0
    3850000.0
    1750000.0
    1750000.0
    3150000.0
    1050000.0
    2450000.0
    (1,1)重复20次 的平均误差值是 2100000.0
    
    def error_sum(m,l,t):
        sum=0
        real_value = Count_length()
        for i in range(t):
            print(Count_estimate_2(m,l))
            sum+=(Count_estimate_2(m,l)-real_value)**2
        return (sum/t)**0.5
    
    print("(1,1)重复20次 的方差值是",error_sum(1,1,20))
    
    1050000.0
    2450000.0
    3850000.0
    3150000.0
    1050000.0
    1750000.0
    1050000.0
    1750000.0
    15750000.0
    1050000.0
    1050000.0
    3150000.0
    1750000.0
    1750000.0
    3150000.0
    1050000.0
    2450000.0
    3150000.0
    1750000.0
    1050000.0
    (1,1)重复20次 的方差值是 2016680.4407243107
    
    def error_sum(m,l,t):
        sum=0
        real_value = Count_length()
        for i in range(t):
            print(Count_estimate_2(m,l))
            sum+=(Count_estimate_2(m,l)-real_value)**2
        return (sum/t)**0.5
    
    print("(20,20)重复20次 的方差值是",error_sum(10,10,20))
    
    2450000.0
    2240000.0
    2310000.0
    3080000.0
    2170000.0
    2520000.0
    3360000.0
    2240000.0
    3010000.0
    2940000.0
    2660000.0
    2310000.0
    2380000.0
    2520000.0
    2170000.0
    2520000.0
    2380000.0
    2380000.0
    2450000.0
    3150000.0
    (20,20)重复20次 的方差值是 2146673.007237013
    

    ams算法和水库采样算法的结合

    算法思想:维持一个s的窗口大小,数据流长度小于s的时候,直接填进去,维持一个统计各个数频次的数组,超过s的时候,,这个时候开始以s/t的概率进行替换,要是替换成功就加到数组里面,,没替换成功,就看维持的数组里面是否有这个数,有的话,相应的元素计数加一
    
    
    import random
    #考虑到随机到的下标代表的值相同的情况  同时修复了随机到相同地方会出现bug的问题
    def Count_estimate_anytime(s,t):
        data_flu = []#用来记录不同下标随机到的数出现的次数 [[index,value,count].....]
        sum=0
        value_ml = []       
        with open("stream_for_ams.txt",'r') as f:
            if t<=s:
                for i in range(t):
                    temp = f.readline()
                    temp=int(temp.strip())
                    data_flu.append([i+1,temp,0])
                    for single in data_flu:
                        if temp==single[1]:
                            single[2]+=1   
            else:  
                for i in range(t):
                    temp = f.readline()
                    temp=int(temp.strip())
                    data_flu.append([i+1,temp,0])
                    for single in data_flu:
                        if temp==single[1]:
                            single[2]+=1 
                for i in range(s+1,t+1):
                    temp = f.readline()
                    if temp=='':
                        print("文件读空或者当前超过文件最大长度")
                        return 0
                    temp=int(temp.strip())  
                    x = random.randint(1,t)
                    if x<=s:
                        data_flu[x]=[i,temp,0]
                        for single in data_flu:
                            if temp==single[1]:
                                single[2]+=1 
                    else:
                        for single in data_flu:
                                if temp==single[1]:
                                    single[2]+=1     
    
        # print(list(data_flu.values()))              
        for i in data_flu:
            value_ml.append(i[2])
            # print(i[2])
        for i in value_ml:
            estm = t*(2*i-1)
            sum+=estm
    
        return sum/(len(value_ml))
    # print(Count_estimate_2(2,2))
    
    

    任意时刻的真实的二阶矩阵

    def Count_accurate_anytime(t):
        data_flu = {}
        sum=0
        with open("stream_for_ams.txt",'r') as f:
            for i in range(1,t+1):
                temp = f.readline()
                if temp=='':
                    print("文件读空或者当前超过文件最大长度")
                    return 0
                temp=int(temp.strip())  
                if temp in data_flu:
                    data_flu[temp]+=1
                else:
                    data_flu[temp]=1          
        for i in data_flu.values():
            sum+=i**2
        return sum
           
    
    s= int(input("请输入当前的窗口大小值:"))
    t = int(input("请输入当前的时间:"))
    print("当前窗口的大小是",s)
    print("当前的时间戳是",t)
    print("当前时刻精确的二阶估计矩阵值是:",Count_accurate_anytime(t))
    print("当前的算法估计的二阶矩阵是",Count_estimate_anytime(s,t))
    print("当前算法的误差是",abs(Count_accurate_anytime(t)-Count_estimate_anytime(s,t))/Count_accurate_anytime(t))
    
    当前窗口的大小是 100
    当前的时间戳是 3000
    当前时刻精确的二阶估计矩阵值是: 3128
    当前的算法估计的二阶矩阵是 3312.0
    当前算法的误差是 0.05690537084398977
    
    展开全文
  • 为了提高对分布式拒绝服务(DDoS)攻击源反向追踪的效率和准确度,提出了一个新算法,此算法在AMS (Advanced Marking Schemes)算法的基础之上与...理论分析及仿真结果证明,相对于AMS算法,新算法明显提高了IP反向追踪的性能.
  • 频度矩估计2 问题分析 ​ 使用BasicAMSBasic AMSBasicAMS算法的方差太大,直接利用MedianMedianMedian技术也不能将最终的结果...Final AMS 算法 算法 计算t=clog1δt = clog\frac{1}{\delta}t=clogδ1​个平均值 每
    展开全文
  • 频度矩估计1 问题定义 ​ 之前我们定义了不同的流模型,当Δ\DeltaΔ取不同的值的时候对应着不同的模型以及不同的解决办法。在频度矩估计问题中,我们要解决的两类问题分别是Δ=1\Delta = 1Δ=1的Vanilla ...
    展开全文
  • AMS

    2021-02-23 14:56:53
    ActivityManagerService(以下简称AMS) 主要负责四大组件的启动、切换、调度以及应 用进程的管理和调度工作。所有的APP应用都需要 与AMS打交道 Activity Manager的组成主要分为以下几个部分: 1.服务代理:由...
  • AMS相关数据结构

    2021-03-13 18:32:16
    ProcessRecord容器 永久性容器 1.mProcessNames:根据进程名字检索进程记录表 2.mPidsSelfLocked:根据进程pid检索进程记录表 3.mLruProcesses:lru进程记录表容器,这个容器使用的是最近最少使用算法对进程记录表进行...
  • AMS 595的最终项目 詹妮弗·马尔多纳多 Covid-19大流行夺走了我们最喜欢的社交活动,例如体育赛事,音乐会,毕业典礼和电影。 这是我们所有人为确保公共健康所做的牺牲。 可以使用技术来开发算法,以确定如何在安全...
  • Verilog-AMS & VHDL-AMS

    千次阅读 2005-04-24 18:14:00
    Verilog-AMS和VHDL-AMS出现还不到4年,是一种新的标准。作为硬件行为级的建模语言,Verilog-AMS和VHDL-AMS分别是Verilog和VHDL的超集,而Verilog-A则是Verilog-AMS的一个子集。Verilog-AMS硬件描述语言是符合IEEE ...
  • 2.AutomaticallyManageSigning(AMS)自动管理签名(管理账号开发者中心的签名证书(通过自构默认配置文件)) 3.开发者中心的签名证书采用签名自动管理过程: 1.Xcode会在本地电脑端的本地钥匙串中寻找开发team团队进行...
  • AMS原理分析

    千次阅读 2018-02-10 18:29:59
    一、AMS的主要作用:1、统一调度Activity(1)AMS中的重要数据类:ProcessReccord:保存该进程中包含的APK信息、内存状态信息用于内存回收、组件列表ActivityRecord:binder类可用于IPC调用(此处为WMS中调用),...
  • 数据库算法及Google搜索引擎算法的秘密
  • 前面学习过Meanshift算法,在观察这个结果标记时,会发现有这样一个问题,如下图: 汽车比较远时,用一个很小的窗口就可以把它框住,这是符合近大远小的投影原理,当比较近的时候如下: 相同大小的窗口已经不能...
  •  品佳集团携旗下代理的Infineon(英飞凌)和AMS(奥地利微电子),以英飞凌高性能16位MCU XC164为平台,辅以奥地利微电子的高精度、零温漂的动力电池电流检测芯AS8510的动力电池管理系统(BMS)解决方案。...
  • 凸包算法

    千次阅读 2013-07-03 15:53:56
     其实这个算法是在一年前得某场比赛中临时抱佛脚学的,今天重新的来温习了一遍 如何来理解凸包?一组平面上的点,求一个包含所有点的最小的凸多边形,这就是凸包问题了。这可以形象地想成这样:在地上放置一些不...
  • 1 引 言  EDA是现代电子系统设计的关键技术。硬件描述语言VHDL以其“代码复用”(code re-use)远高于传统的原理图输入法等诸多优点,逐渐成为EDA技术中主要的输入... PID控制是早发展起来的控制策略之一,其算法简单

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,936
精华内容 1,974
关键字:

ams算法