2 csf5842 csf5842 于 2016.04.14 20:14 提问

用c 语言或者c++程序语言编写DGIM算法(近似计算窗口中1-bit的个数的算法)。 5C

1:以01stream.txt文件,好像不能上传附件,文件内容为01所组成的数据流,为自己所写程序的输入,读取中文件中的01数据流;
2:设定窗口大小1000,以不超过50%的相对误差回答任意时刻,当前窗口中有多少个1-bit;
3:设定窗口大小2000,以不超过10%的相对误差回答任意时刻,当前窗口中有多少个1-bit;
4:编写一个精确计算当前窗口中1-bit个数的精确程序,比较精确程序在运行时间和空间和DGIM算法的差异。
没有头绪,有熟悉这种算法的大神么,谢谢了。
大数据相关的

1个回答

devmiao
devmiao   Ds   Rxr 2016.04.14 23:31
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
大数据DGIM算法,C语言实现代码
对于该查询,若空间足够,可以通过空间复杂度O(N),时间复杂度O(1)的简单的加减得到查询结果。所以这里要讨论的是对于N非常大的情况,即假设由于存储空间有限,我们不能存储整个窗口的数据。 根据滑动窗口共有2N种表示简单推算,任何能给出确切结果的算法都需要O(N)的空间,即该问题必须寻找近似算法。Datar-Gionis-Indyk-Motwani Algorithm(DGIM算法)是其中一种:该...
Big Data(2): DGIM算法实现-1
题目要求:(1) In Amazon, for every product X we keep 0/1 stream of whether that product was sold inthe n-th transaction. We want to answer queries, how many times have we sold X in the lastK sales. Suppose
二路归并排序算法实现-完整C语言程序
/*********************************************************************************************** 1.设定两个指针,最初位置分别为两个已经排序序列的起始位置 2.比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 3.重复步骤3直到某一指针达到序列尾 4.将另一序列剩下的所有
大数据算法之——DGIM算法
    最近学习大数据,遇到了DGIM算法,其题目如下: In Amazon, for every product X we keep 0/1 stream of whether that product was sold inthe n-th transaction. We want to answer queries, how many times have we sold X in t...
快速开平方根算法
人们很早就在Quake3源代码中发现了类似如下的C代码,它可以快速的求1/sqrt(x),在3D图形向量计算方面应用很广 float invSqrt(float x) { float xhalf = 0.5 * x; int i = *(int*)&x; // get bits for floating value i = 0x5f3759df - (i >> 1); // gives
计算一棵完整二叉树的结点数 C实现
题目描述 分析 学过图论的我们知道,一棵层数为h的完整二叉树的最大节点数为2^h-1(节点的层数:从根开始定义起,根为第1层,根的子节点为第2层…)。那么问题来了,若结点范围是在2^(h-1)和2^h之间,怎么算呢?一种很直接的方法便是等于左子树的结点数+右子树的节点数+1。至此,我们就大概知道代码怎么写了。如果刚好是满二叉树,那么节点数便是2^h-1;如果不是,那么就左子树、右子树的结点数分别加
C语言和java中生成随机数的原理和方法
C语言一.函数 1:int rand(void) 该函数会产生一个[0,RAND_MAX]的伪随机数,那什么是伪随机数? 相当于一个序列a1-an,第一次使用会返回a1, 第二次使用会返回a2….第n次返回an,这样每次调用rand()都能产生一个不同的数,只要整个序列的规律不明显,整个函数看起来就是随机的。 而这个序列是计算机通过调用srand((int)time(NULL))函数随机产生
凯撒加密算法C语言实现
#include#includechar encrypt(char ch,int n)/*加密函数,把字符向右循环移位n*/{while(ch>=A&&ch{  return (A+(ch-A+n)%26);}while(ch>=a&&ch{  return (a+(ch-a+n)%26);}return ch;}void menu()/*菜单,1.加密,2.解密,
c语言实现 FCFS和SJF调度算法
c语言实现 FCFS和SJF调度算法 在vc6.0已经调试通过
计算二叉树中叶子结点的数目
编写递归算法,计算二叉树中叶子结点的数目。 二叉链表类型定义: typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; } BiTNode, *BiTree;