精华内容
下载资源
问答
  • 前言: 最近看了一篇文章<>,第一次知道“布隆过滤器”,查了些资料,觉得有必要整理一下。布隆过滤器是什么?...布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一...
    e58da80a109538fab74a0774232d631a.png

    前言:

    最近看了一篇文章<>,第一次知道“布隆过滤器”,查了些资料,觉得有必要整理一下。

    • 布隆过滤器是什么?
    • 它有什么缺点?
    • 布隆过滤器的测试
    • 解决缓存击穿的问题

    一、布隆过滤器是什么?

    百度百科:

    布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。

    图解:

    它本身是一个很长的二进制向量,既然是二进制的向量,那么显而易见的,存放的不是0,就是1。

    现在我们新建一个长度为16的布隆过滤器,默认值都是0,就像下面这样:

    f2bac2f826ab1e965594e774f857a642.png

    现在需要添加一个数据:

    我们通过某种计算方式,比如Hash1,计算出了Hash1(数据)=5,我们就把下标为5的格子改成1,就像下面这样:

    f2bac2f826ab1e965594e774f857a642.png

    我们又通过某种计算方式,比如Hash2,计算出了Hash2(数据)=9,我们就把下标为9的格子改成1,就像下面这样

    e2cc3303b6c08cf0665d3f695948af8f.png

    还是通过某种计算方式,比如Hash3,计算出了Hash3(数据)=2,我们就把下标为2的格子改成1,就像下面这样:

    8918747f247d44df3beb265345a84128.png

    这样,刚才添加的数据就占据了布隆过滤器“5”,“9”,“2”三个格子。

    可以看出,仅仅从布隆过滤器本身而言,根本没有存放完整的数据,只是运用一系列随机映射函数计算出位置,然后填充二进制向量。

    二、它有什么优缺点?

    优点:可以高效的查询和插入,它可以告诉你一条数据一定不存在或者可能存在。并且占用非常少的内存空间。

    例如:在10亿条数据中判断一条数据的是否存在?

    如果用HashSet来处理,他的时间复杂度是O(1),但是他的空间复杂度呢?哈希值是integer类型,一条数据的哈希值占用的空间是4个字节,一共10亿*4/1024/1024/1024约等于3.7G,占用空间太大了。

    如果用布隆过滤器呢,因为integer的最大2147483647,所以我们需要定义一个长度为m的bit型数组,如我们所知,每个位置只占一个bit,每个位置只有0和1两种状态, 假如一个数据是哈希是2,我们就可以把数组坐标2的部位标记为1,这个bit数组将是00100.....000;再来一个数据的哈希是5,这个bit数据将是:00100100...000,以此类推。这样就可以存储所有可能的值。8个bit一个字节,占用的空间是2147483647/8/1024/1024=256M

    缺点:布隆过滤器期有一定的误差率,数据越多,误差率越大。为了减少误差率,我们可以使用多个不同的哈希函数生成多个哈希值,并对每个生成的哈希值指向的 bit 位置 1。例如上面图解。

    如果要判断一个数据是否存在,我们只需要判断他的不同哈希函数值在 bit 位置中对应的是否为1就可以了,如果有不为1,肯定不存在;如果都为1,可能存在也可能不存在,这是因为哈希值(又叫散列)具有“散列冲突”(两个散列值相同,两个输入值很可能是相同的,也可能不同)的原因。

    布隆过滤器删除困难,为什么呢?你想想,你要删除一个数据,把对应bit位置的数据改为0,假如别的数据的哈希值也占用这个位置,不就乱套了。

    算法特点:1、因使用哈希判断,时间效率很高。空间效率也是其一大优势。2、有误判的可能,需针对具体场景使用。3、因为无法分辨哈希碰撞,所以不是很好做删除操作。

    三、布隆过滤器的测试

    测试代码一

    public class BloomFilterTest {  private static final int insertions = 1000000; //100w  @Test public void bfTest(){ //初始化一个存储string数据的布隆过滤器,初始化大小100w,不能设置为0 BloomFilter bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions,0.001); //初始化一个存储string数据的set,初始化大小100w Set sets = new HashSet<>(insertions); //初始化一个存储string数据的set,初始化大小100w List lists = new ArrayList(insertions);  //向三个容器初始化100万个随机并且唯一的字符串---初始化操作 for (int i = 0; i < insertions; i++) { String uuid = UUID.randomUUID().toString(); bf.put(uuid); sets.add(uuid); lists.add(uuid); }  int wrong = 0;//布隆过滤器错误判断的次数 int right = 0;//布隆过滤器正确判断的次数 for (int i = 0; i < 10000; i++) { String test = i%100==0?lists.get(i/100):UUID.randomUUID().toString();//按照一定比例选择bf中肯定存在的字符串 if(bf.mightContain(test)){ if(sets.contains(test)){ right ++; }else{ wrong ++; } } }  System.out.println("=================right====================="+right);//100 System.out.println("=================wrong====================="+wrong); } }

    测试代码二

     private static int size = 1000000;//预计要插入多少数据 private static double fpp = 0.01;//期望的误判率 private static BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp); public static void main(String[] args) { //插入数据 for (int i = 0; i < 1000000; i++) { bloomFilter.put(i); } int count = 0; for (int i = 1000000; i < 2000000; i++) { if (bloomFilter.mightContain(i)) { count++; System.out.println(i + "误判了"); } } System.out.println("总共的误判数:" + count); }

    不同的数据结构有不同的适用场景和优缺点,你需要仔细权衡自己的需求之后妥善适用它们,布隆过滤器就是践行这句话的代表。

    四、缓存击穿的问题

    什么是缓存击穿?

    正常情况下,我们会把经常用的数据放入缓存中,一个请求进来,先去缓存中查询,如果有数据就返回,如果没有就查询数据库,然后再把数据库中的数据放入缓存中。

    但是呢,假如数据也没有数据呢?这样大量的请求就会不断的去查询数据库,造成数据库压力过大甚至崩溃。

    为什么不把所有的数据都放入缓存呢?

    因为所有数据都放入缓存,会消耗大量的空间,也不符合缓存的初衷,不能暴力的把所有数据都放入缓存。

    怎么解决呢?

    可以使用布隆过滤器,缓存所有的key相关的信息,上面已经说过了,布隆过滤不仅效率高,而且占用空间小。如果布隆过滤器判断不存在就不用查缓存或者数据库了。

    展开全文
  • 前言:最近看了一篇文章<>,第一次知道“布隆过滤器”,查了些资料,觉得有必要整理一下。...布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算...
    f25a782b1bed90b66d5ad97c773db3c7.png

    前言:

    最近看了一篇文章<>,第一次知道“布隆过滤器”,查了些资料,觉得有必要整理一下。

    • 布隆过滤器是什么?
    • 它有什么缺点?
    • 布隆过滤器的测试
    • 解决缓存击穿的问题

    一、布隆过滤器是什么?

    百度百科:

    布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。

    图解:

    它本身是一个很长的二进制向量,既然是二进制的向量,那么显而易见的,存放的不是0,就是1。

    现在我们新建一个长度为16的布隆过滤器,默认值都是0,就像下面这样:

    51f11bf6cab1f03213d370de23b5940b.png

    现在需要添加一个数据:

    我们通过某种计算方式,比如Hash1,计算出了Hash1(数据)=5,我们就把下标为5的格子改成1,就像下面这样:

    8cef184ce748f8b157d5ae0035981c52.png

    我们又通过某种计算方式,比如Hash2,计算出了Hash2(数据)=9,我们就把下标为9的格子改成1,就像下面这样

    a1f47d740d87e33254059b05093dacd3.png

    还是通过某种计算方式,比如Hash3,计算出了Hash3(数据)=2,我们就把下标为2的格子改成1,就像下面这样:

    88c31d21fcebc50556cb6d98a8c989a3.png

    这样,刚才添加的数据就占据了布隆过滤器“5”,“9”,“2”三个格子。

    可以看出,仅仅从布隆过滤器本身而言,根本没有存放完整的数据,只是运用一系列随机映射函数计算出位置,然后填充二进制向量。

    二、它有什么优缺点?

    优点:可以高效的查询和插入,它可以告诉你一条数据一定不存在或者可能存在。并且占用非常少的内存空间。

    例如:在10亿条数据中判断一条数据的是否存在?

    如果用HashSet来处理,他的时间复杂度是O(1),但是他的空间复杂度呢?哈希值是integer类型,一条数据的哈希值占用的空间是4个字节,一共10亿*4/1024/1024/1024约等于3.7G,占用空间太大了。

    如果用布隆过滤器呢,因为integer的最大2147483647,所以我们需要定义一个长度为2147483647的bit型数组,如我们所知,每个位置只占一个bit,每个位置只有0和1两种状态, 假如一个数据是哈希是2,我们就可以把数组坐标2的部位标记为1,这个bit数组将是00100.....000;再来一个数据的哈希是5,这个bit数据将是:00100100...000,以此类推。这样就可以存储所有可能的值。8个bit一个字节,占用的空间是2147483647/8/1024/1024=256M

    缺点:布隆过滤器期有一定的误差率,数据越多,误差率越大。为了减少误差率,我们可以使用多个不同的哈希函数生成多个哈希值,并对每个生成的哈希值指向的 bit 位置 1。例如上面图解。

    如果要判断一个数据是否存在,我们只需要判断他的不同哈希函数值在 bit 位置中对应的是否为1就可以了,如果有不为1,肯定不存在;如果都为1,可能存在也可能不存在,这是因为哈希值(又叫散列)具有“散列冲突”(两个散列值相同,两个输入值很可能是相同的,也可能不同)的原因。

    布隆过滤器删除困难,为什么呢?你想想,你要删除一个数据,把对应bit位置的数据改为0,假如别的数据的哈希值也占用这个位置,不就乱套了。

    算法特点:1、因使用哈希判断,时间效率很高。空间效率也是其一大优势。2、有误判的可能,需针对具体场景使用。3、因为无法分辨哈希碰撞,所以不是很好做删除操作。

    三、布隆过滤器的测试

    测试代码一

    public class BloomFilterTest {  private static final int insertions = 1000000; //100w  @Test public void bfTest(){ //初始化一个存储string数据的布隆过滤器,初始化大小100w,不能设置为0 BloomFilter bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions,0.001); //初始化一个存储string数据的set,初始化大小100w Set sets = new HashSet<>(insertions); //初始化一个存储string数据的set,初始化大小100w List lists = new ArrayList(insertions);  //向三个容器初始化100万个随机并且唯一的字符串---初始化操作 for (int i = 0; i < insertions; i++) { String uuid = UUID.randomUUID().toString(); bf.put(uuid); sets.add(uuid); lists.add(uuid); }  int wrong = 0;//布隆过滤器错误判断的次数 int right = 0;//布隆过滤器正确判断的次数 for (int i = 0; i < 10000; i++) { String test = i%100==0?lists.get(i/100):UUID.randomUUID().toString();//按照一定比例选择bf中肯定存在的字符串 if(bf.mightContain(test)){ if(sets.contains(test)){ right ++; }else{ wrong ++; } } }  System.out.println("=================right====================="+right);//100 System.out.println("=================wrong====================="+wrong); } }

    测试代码二

     private static int size = 1000000;//预计要插入多少数据 private static double fpp = 0.01;//期望的误判率 private static BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp); public static void main(String[] args) { //插入数据 for (int i = 0; i < 1000000; i++) { bloomFilter.put(i); } int count = 0; for (int i = 1000000; i < 2000000; i++) { if (bloomFilter.mightContain(i)) { count++; System.out.println(i + "误判了"); } } System.out.println("总共的误判数:" + count); }

    不同的数据结构有不同的适用场景和优缺点,你需要仔细权衡自己的需求之后妥善适用它们,布隆过滤器就是践行这句话的代表。

    四、缓存击穿的问题

    什么是缓存击穿?

    正常情况下,我们会把经常用的数据放入缓存中,一个请求进来,先去缓存中查询,如果有数据就返回,如果没有就查询数据库,然后再把数据库中的数据放入缓存中。

    但是呢,假如数据也没有数据呢?这样大量的请求就会不断的去查询数据库,造成数据库压力过大甚至崩溃。

    为什么不把所有的数据都放入缓存呢?

    因为所有数据都放入缓存,会消耗大量的空间,也不符合缓存的初衷,不能暴力的把所有数据都放入缓存。

    怎么解决呢?

    可以使用布隆过滤器,缓存所有的key相关的信息,上面已经说过了,布隆过滤不仅效率高,而且占用空间小。如果布隆过滤器判断不存在就不用查缓存或者数据库了。

    展开全文
  • 优点是判断元素是否属于集合、元素的插入和删除都只要用O(1)的时间。缺点是当n很大时占空间很大,有一个办法是一个数组位置存放一个大数而非只放一位0或1,大数的二进制串就是A中一段元素的特征函数值。符号表 ·...

    集合
    · 用位向量实现ADT集合并进行集合的并、交等运算:
    用一个n位的向量v来存储集合A的特征函数值(为1为属于集合,为0不属于集合)可以唯一地表示集合A。优点是判断元素是否属于集合、元素的插入和删除都只要用O(1)的时间。缺点是当n很大时占空间很大,有一个办法是一个数组位置存放一个大数而非只放一位0或1,大数的二进制串就是A中一段元素的特征函数值。

    符号表
    ·符号表是以集合为基础,支持成员运算(判断是否属于集合)、插入元素、删除元素三种运算的抽象数据类型。可以用表示集合的链表或位向量或一个定长数组来存储,但缺点在于受数组大小限制,并且储存空间一般没有得到充分利用。

    · 用散列表实现符号表

    散列:建立键值与其存储位置的关系,是一种映射。xi –> H(xi)

    1.开散列 将集合中元素划分为有限个类,每一个类称为一个桶,x属于第i个桶当且仅当H(x) = i 。
    这里写图片描述
    如图中的情况,等概论情况下的成功查找平均时间为,(2×1+1×2)/3(有两个元素1步可找到,有一个2步找到)

    2.闭散列 每个桶都只存放集合中的一个元素。
    使用线性探测法,加入元素的时候从H(x)开始找一个空桶放下去,若H(x)已被占,则继续往后找,H(x)+1,…,H(x)max,0,1,…H(x)-1 直到找到空桶。 查找元素时从H(x)开始往后找,如果一直找到空桶了都还没找到x则x不在集合中,但如果做过删除运算时这样可能出错(遇到了被删掉元素的空桶判断停下,其实x还在后面)。所以加入state数组给每个桶标记,为0时表示从未被占,1为曾被占,2为被占。

    实现散列所需考虑的:
    1.散列函数的选取
    我们所希望的是将n个元素均匀散列到B个桶中去:
    ①除余法 选择一个正整数m,m不超过桶数B,H(k) = k%m
    ②数乘法 选择一个纯小数a(0 < a < 1), H(k) = (int)(B(ka-(int)ka))
    ③平方取中法 当桶数B不是10的方幂,而键是0~n之间的整数时,可选取与B互质的整数c使得Bc^2与n^2大致相等, H(k) = (int)(k^2 / c)%B
    ④基数转换法 将键值看成用另一个进制表示的数后,再将它转换为原来进制表示的数,取其中若干位作为散列函数值。一般取大于原来基数的数作为转换的基数,并且这两个基数互质。
    ⑤随机数法 H(k) = random(k) 通常当键的长度不等时采用此法构造效果较好

    2.解决冲突
    为避免散列表中成块的连续地址被占用的聚集现象应该采用跳跃式的重新散列技术:
    ①二次散列技术
    ②随机重新散列技术
    ③双重散列技术 使用两个散列函数来产生探索序列 Hi(x) = (H(x)+iH’(x))%B i=1,2,…,B-1 (其中H’(x)的值应与B互质)

    · 计算平均查找长度(假设成功查找的概率为P,不成功为V-P)
    哈希表等概率情况下查找成功和查找不成功的平均查找长度的计算

    作业题

    9.1 hash

    这里写图片描述

    (k、m较小,视作m进制的哈希映射)

    #include<cstdio>     
    #include<iostream>    
    #define MAX 1000000 + 7    
    #define HashMAX 6*6*6*6*6*6 + 7      
    using namespace std;    
    
    char str[MAX];    
    int i;    
    bool hash[HashMAX];    
    
    int main()    
    {    
        int n,m,k;    
        scanf("%d %d %d",&n,&m,&k);    
        scanf("%s",str);    
    
        if(k > n)    
        {    
            printf("0\n");    
            return 0;    
        }    
        int ans = 0;    
    
        int a = 0;    
        for(i = k-1; i >=0; i--)    
            a = a*m+(str[i]-'a');    
        hash[a] = true;    
        ans ++;    
    
        int val = 1; //第k个位置权重     
        i = 0;    
        while(++i < k) val*=m;    
    
        for(i = k; i < n; i++)    
        {    
            a = a/m + (str[i]-'a')*val;    
            if(!hash[a])    
            {    
                ans++;    
                hash[a] = true;     
            }    
        }    
    
        printf("%d",ans);    
    
        return 0;    
    }

    9.2 寻人启事

    这里写图片描述
    这里写图片描述

    (这里用了一个网络上找到的字符串哈希函数,冲突用链表解决)

    #include<cstdio>  
    #include<iostream>  
    #include<cstring>  
    #define MAX 1000000+7  
    using namespace std;  
    int i;  
    
    struct Person  
    {  
        char name[6];  
        Person * next;  
    }*per[MAX];  
    
    int getHash(char str[6])  
    {  
        int h = 5381;  
        int i;  
        for(i = 0; i < strlen(str); i++)  
            h = (((h<<5)+h)+str[i])%(MAX);  
        return h;  
    }  
    
    char c[6];  
    
    int main()  
    {  
        memset(per,0,sizeof(per));  
        Person *tmp;  
        int n,m;  
        scanf("%d%d",&n,&m);  
        for(i = 0; i < n; i++)  
        {  
            scanf("%s",c);  
            int hash = getHash(c);  
            tmp = new Person;  
            strcpy(tmp->name,c);  
            tmp->next = per[hash];  
            per[hash] = tmp;      
        }  
    
        int ans = 0;  
        for(i = 0; i < m; i++)  
        {  
            scanf("%s",c);  
            tmp = per[getHash(c)];  
            while(tmp)  
            {  
                if(strcmp(c,tmp->name)==0)  
                {  
                    ans++;  
                    break;  
                }  
                tmp = tmp->next;  
            }  
        }  
        printf("%d\n",ans);  
    
        return 0;  
    }

    9.3 学生管理

    这里写图片描述
    这里写图片描述

    (纯链表模拟的哈希,链表调了不知道多久,错因在于在函数中开了指针指向哈希串中的某个位置然后delete掉这个指针,这样哈希串那个位置就被delete掉了…(我还以为知道释放掉指针地址原来是释放指向的地址啊Orz))

    #include<cstdio>  
    #include<iostream>  
    #include<cstring>  
    using namespace std;  
    #define MAX 100000+7  
    int i,j;  
    char s[6];  
    struct Student  
    {  
        char name[6];  
        Student * next;  
    }*stu[MAX];  
    
    int getHash(char str[6])  
    {  
        int h = 5381;  
        int len = strlen(str);  
        for(int i = 0; i < len; i++)  
            h = (((h<<5)+h)+str[i])%(MAX);  
        return h;  
    }  
    
    bool qur(char str[6])  
    {  
        int h = getHash(str);  
    
        if(!stu[h]->next) return 0;  
    
        Student * tmp = new Student;  
        Student * tmp1 = new Student;  
        tmp->next = NULL;  
        tmp1->next = NULL;  
    
        tmp = stu[h];  
        while(tmp->next)  
        {  
            tmp1 = tmp->next;  
            if(strcmp(tmp1->name,str) == 0) return 1;  
            tmp = tmp->next;  
        }  
        return 0;  
    }  
    
    void add(char str[6])  
    {  
        int h = getHash(str);  
        Student * tmp = new Student;  
        tmp->next = NULL;  
        strcpy(tmp->name,str);  
        if(!qur(tmp->name))  
        {  
            tmp->next = stu[h]->next;  
            stu[h]->next = tmp;  
        }  
        return;  
    }  
    
    void del(char str[6])  
    {  
        int h = getHash(str);  
    
        if(stu[h]->next == NULL)   
        {  
            printf("The student does not exist!\n");        
            return;   
        }  
    
        Student * tmp = new Student;  
        Student * tmp1 = new Student;  
        tmp = stu[h];  
        while(tmp->next)  
        {  
            tmp1 = tmp->next;  
            if(strcmp(tmp1->name,str) == 0)  
            {  
                tmp->next = tmp1->next;  
                delete(tmp1);  
                tmp1 = NULL;  
                return;  
            }  
            tmp = tmp->next;  
        }  
        printf("The student does not exist!\n");     
        return;   
    }  
    
    int main()  
    {    
        Student * tmp = new Student;  
        tmp->next = NULL;  
        for(i = 0; i < MAX; i++)  
        {  
            stu[i] = new Student;  
            stu[i]->next = NULL;  
        }   
    
        int n,op;  
        scanf("%d",&n);  
        for(i = 0; i < n; i++)  
        {  
            scanf("%d%s",&op,s);  
            switch(op)  
            {  
                case 1:  
                    add(s);  
                    break;  
                case 2:  
                    del(s);  
                    break;  
                case 3:  
                {  
                    if(qur(s) == 1) printf("Yes\n");  
                    else printf("No\n");  
                    break;  
                }  
            }  
        }  
        return 0;  
    }

    9.4 有趣的方程

    这里写图片描述

    (奇怪的题目..三个for..楼下是泡泡打的..if没考虑全还wa了一次..)

    #include<cstdio>  
    #include<cmath>  
    #include<iostream>  
    using namespace std;  
    ///----------------------------------------------  
    int main() {  
        int tcase=0;  
        int icase=0;  
        for (scanf("%d",&tcase); ++icase<=tcase; ) {  
    
            //--0 init  
    
            //--1 read  
            int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d);  
    
            //--2 work  
            int ans=0;  
            for (int x1=-100; x1<=100; x1++) if (x1)  
            for (int x2=-100; x2<=100; x2++) if (x2)  
            for (int x3=-100; x3<=100; x3++) if (x3) {  
                int tmp=a*x1*x1+b*x2*x2+c*x3*x3;  
                //tmp==-d*x4*x4  
                int tmp2=tmp/-d;  
                if (tmp2*-d!=tmp) continue;  
                if (tmp2<=0) continue;  
                int x4=sqrt(tmp2);  
                if (x4*x4!=tmp2) continue;  
                if (x4>100) continue;  
                ans+=2;  
            }  
    
            //--3 print  
            printf("%d\n",ans);  
        }  
        return 0;  
    }
    展开全文
  • 在MATLAB中调用,两个多面体输入形式可以是各自的顶点竖向量集合,也可以是MATLAB规定的线性规划条件形式,输出重叠体各个顶点的竖向量集合,而且线性规划形式和顶点集合形式可以通过附带的程序相互转化。...
  • 算法之回溯法

    2019-04-17 18:43:19
    回溯法 求解步骤 ...3,是否为当前可选集合中的最后一个元素,是则回溯,重新判断上一个节点,否则判断可选集合中的下一个元素 注:若上一个节点选择的是上一个可选集合中的最后一个元素,则再次回溯。 ...

    回溯法

    求解步骤
    1,定义给定问题的解向量解空间【子集树/排列树】
    2,设计剪支函数【限界函数及约束函数】
    3,深度优先遍历结合剪支得出解
    求解过程
    1,是否为完全解,是则输出;
    2,是否为部分解,是则进行下一个解分量的判断;
    3,是否为当前可选集合中的最后一个元素,是则回溯,重新判断上一个节点,否则判断可选集合中的下一个元素
    注:若上一个节点选择的是上一个可选集合中的最后一个元素,则再次回溯。

    练习一:求解部分和问题
    题目内容:
    给出N个正整数组成的数组A,求能否从中选出若干个,使他们的和为K。如果可以,输出:“YES”,否则输出"NO"。

    输入格式:
    第1行:2个数N、K, N为数组的长度, K为需要判断的和(2 ≤N ≤ 20,1 ≤ K ≤ 10^9)
    第2 到第 N + 1行:每行1个数,对应数组的元素A[i] (1 ≤ A[i]≤ 10^6)

    输出格式:
    如果可以,输出:“YES”,否则输出"NO"。
    样例输入
    4 13
    1
    2
    4
    7
    样例输出
    YES

    算法描述【非递归】
    输入:需要判断的和k,数组长度n,数组元素
    输出:判断结果YES/NO
    1,初始化状态向量result[i]=-1;[-1未初始状态,0表示选入,1表示不选入,2表示已无可选情况]
    2,num=0;
    3,while(num>=0)
    3.1result[num]++,判断该元素下一状态是否可行;
    3.2若该状态可行,则转步骤3.3;若发生冲突,则result[num]++试探下一状态;
    3.3若判断函数返回成功标志,输出YES,结束算法;
    3.4若num<n-1且处于可选状态内,num++,判断下一元素的状态;
    3.5若result[num]>=2,即已无可选状态时,重置num的状态,num–,回溯至其根结点判断其状态。
    4,判断所有状态皆无成功结果,输出NO,算法结束。

    c++实现

    #include<iostream>
    using namespace std;
    int n, k;
    int number[20]; 
    int *result=new int[n];
    int check(int num)
    {
    	int sum = 0;
    	for (int i = 0; i < n; i++)
    	{
    		if (result[i] == 0)
    			sum = sum + number[i];
    	}
    	if (sum < k) {
    		return 1;
    	}
    	if (sum == k)return 2;
    	else return 0;
    }
    int main(){
    	cin >> n >> k;
    	for (int a = 0; a < n; a++)
    	{
    		cin >> number[a];
    		result[a] = -1;//表示第a个元素的状态1表未采用,0表采用,-1为初始状态
    	}
    	int num = 0;
    	while (num >= 0) {
    		result[num] ++;//判断下一个可选状态
    		int temp = check(num);
    		if(result[num] < 2 && temp == 0)
    		{
    			result[num]++;//不可选
    		}
    		if (temp==2)
    		{
    			cout << "YES"; return 0;
    		}
    		if (num < n-1&&result[num]<2)num++;//进行下一阶段的判断
    		if(result[num]>=2) 
    			result[num--] = -1;//重置num状态,回溯到上一节点
    	}
    	cout << "NO";//无可选搭配
    	return 0;
    }
    

    注意
    1,需有输出结果,判断是否重置回溯的时候需用if判断是否执行,而非直接else【漏掉对NO情况的判断】;
    2,发生冲突时,result[num]++一次即可,避免遗漏对于元素处于不加入状态的情况;
    3,直接在while循环结束后进行失败标志的输出即可。
    4,对于和的判断,每次判断时在函数中根据标志状态计算,避免回溯时对sum的计算复杂。

    练习2求解最小机器重量设计问题

    题目内容:
    设某一机器由n个部件组成,部件编号为1-n,每一种部件都可以从m个不同的供应商处购得,供应商编号为1~m。设wij是从供应商j处购得的部件i的重量,cij是相应的价格。对于给定的机器部件重量和机器部件价格,计算总价格不超过d的最小重量机器设计。(注意:输出结果中第一行最后没有空格。比如下面的输出样例中1 3 1后面没有空格。)

    输入格式:
    第1行输入3个正整数n,m和d。接下来n行输入wij(每行m个整数),最后n行输入cij(每行m个整数),这里1≤n、m≤100。

    输出格式:
    输出的第1行包括n个整数,表示每个对应的供应商编号,第2行为对应的最小重量。

    输入样例:
    3 3 7
    1 2 3
    3 2 1
    2 3 2
    1 2 3
    5 4 2
    2 1 2

    输出样例:
    1 3 1
    4

    算法描述
    矩阵weight[i][j]存储供应商j部件i的重量,value[i][j]存储价格,result[i]存储部件i所选供应商,r[i]为最终结果
    输入:部件数n,供应商m,最大价格d,各供应商所提供不同部件价格及重量
    输出:采用的各部件来源,总重量
    1,初始化j=-1;
    2,k=0;
    3,while(k>=0)
    3.1result[k]++;
    3.2若仍有可选供应商且无法满足约束条件【总价格不大于d】,则对下一供应商的判断;
    3.3若result[k]<m且k==n-1即已有搜寻结果且已搜寻至最后一个部件,则计算其重量sum,与temp比较大小,若较小,则更新temp的值,并将所选供应商存入最终结果r[i]中;否则,舍弃,该选择定非最优解;
    3.4若result[k]<m且k<n-1,即该部件供应商已有搜寻结果但尚有部件未进行搜寻,判断已选择供应商部件的重量,与temp进行大小比较,若小于,则k++,对下一部件的供应商进行搜寻;否则,此结点定非最优解,进行下一轮循环;
    3.5若result[k]>=m即该部件已无可选供应商,则回溯,result[k]=-1,k–即重置当前部件的供应商结果,回溯至上一节点的选择。
    4,输出结果。

    c++实现

    #include<iostream>
    using namespace std;
    int n, m; int d;
    int weight[10][10];
    int value[10][10];
    int *result = new int[n];
    int check(int i)
    {
    	int sum = 0;
    	for (int a = 0; a <= i; a++)
    		sum = sum + value[a][result[a]];//约束条件:判断所选部件的价值是否超过最大价值
    	if (sum > d)return 0;//超过则返回0
    	else return 1;
    }
    int main()
    {
    	cin >> n >> m >> d;
    	for (int i = 0; i < n; i++)
    	{
    		for (int j = 0; j < m; j++)
    			cin >> weight[i][j];
    	}
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++)
    			cin >> value[i][j];
    	}
    	for (int a = 0; a < n; a++)
    		result[a] = -1;
    	int k = 0; int temp = 99999;  int *r = new int[n];
    	//k表示正在探索适合部件的编号
    	while (k >= 0) {
    		result[k]++;//进行下一供应商的部件判断
    		while (result[k] < m&&check(k) == 0)//无法满足约束条件判断下一供应商直至无可选供应商
    			result[k]++;
    		//走到了一个叶子节点,比较其重量,存入较少的结果
    		if (result[k] < m&&k == n - 1) {
    			int sum = 0;
    			for (int a = 0; a <= k; a++)
    				sum = sum + weight[a][result[a]];
    			if (sum < temp)
    			{
    				temp = sum;
    				for (int a = 0; a <=k; a++)
    					r[a] = result[a];
    			}
    		}
    		//有可选供应商进行下一部件的判断
    		if (result[k] < m&&k < n - 1) {
    			int sum = 0;
    			for (int a = 0; a <= k; a++)
    				sum = sum + weight[a][result[a]];
    			if(sum<temp)
    				k++; 
    			else 
    				continue;
    		}
    		//无可选供应商,回溯至上一节点
    		if (result[k] >= m)
    			result[k--] = -1;
    	    
    	}
    	for (int a = 0; a < n; a++)
    	{
    		cout << r[a] + 1;
    		if (a < n - 1)cout << " ";
    	}
    	cout << "\n";
    	cout << temp;
    	return 0;
    }
    
    展开全文
  • Elasticsearch相关性算法主要分为三大部分:布尔模型,TF/IDF,向量空间模型 布尔模型:and,or,not根据这些条件来匹配文档,判断搜索词是否在文档中。 TF/IDF:相关性算法--TF/IDF 这篇文章里已经介绍了相关内容...
  • 用来检索一个元素是否集合中,如果判断不在,那肯定不在;如果判断在,可能判断错误 优点:空间效率和查询时间远远超过一般的算法。 缺点:有一定的误识别率和删除困难。 图片来自极客时间 A通过映射函数,将a,b...
  • 布隆过滤器区块链

    2020-05-21 15:12:09
    它是一种基于概率的数据结构,主要用来判断某个元素是否集合内,它具有运行速度快(时间效率),占用内存小的优点(空间效率),但是有一定的误识别率和删除困难的问题。它能够告诉你某个元素一定不在集合内或可能...
  • 它是一种基于概率的数据结构,主要用来判断某个元素是否集合内,它具有运行速度快(时间效率),占用内存小的优点(空间效率),但是有一定的误识别率和删除困难的问题。它能够告诉你某个元素一定不在集合内或可能在...
  • BF由一个很长的二进制向量和一系列随机映射的函数组成,通过多个Hash函数将一个元素映射到一个Bit Array中的多个点,查询的时候仅当所有的映射点都1才能判断元素存在于集合内;BF用于检索一个元素是否在一个集合中...
  • 布隆过滤器的简介什么是布隆过滤器?布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制...在日常生活中,包括在设计计算机软件时,我们经常判断一个元素是否在一个集合中。比如:要检查一个单
  • 如果一个黑名单网站包含100亿个黑名单网页,每个网页最多占64B,设计一个系统,判断当前的URL是否在这个黑名单当中,要求额外空间不超过30GB,允许误差率万分之一。 解题思路 布隆过滤器 基础介绍 布隆过滤器...
  • redis-布隆过滤器原理

    2019-09-19 16:27:44
    判断某个值是否在某个集合中。 特点 1、存储空间小: 因为它的原理是由一个长度m的位数组(二进制向量),一个字节有8个位,如果我们使用四个hash函数来运算,那么每个key就会占用四个位,一个字节可表示两个key。...
  • 算法题目如果一个黑名单网站包含100亿个黑名单网页,每个网页最多占64B,设计一个系统,判断当前的URL是否在这个黑名单当中,要求额外空间不超过30GB,允许误差率万分之一。解题思路:布隆过滤器基础介绍布隆过滤...
  • 算法题目如果一个黑名单网站包含100亿个黑名单网页,每个网页最多占64B,设计一个系统,判断当前的URL是否在这个黑名单当中,要求额外空间不超过30GB,允许误差率万分之一。解题思路:布隆过滤器基础介绍布隆过滤...
  • 【算法】布隆过滤器

    2020-08-25 15:05:37
    如果一个黑名单网站包含100亿个黑名单网页,每个网页最多占64B,设计一个系统,判断当前的URL是否在这个黑名单当中,要求额外空间不超过30GB,允许误差率万分之一。 解题思路:布隆过滤器 基础介绍 布隆过滤器...
  • 空间效率和查询时间都远远超过其他算法,⽤于检索⼀个元素是否在⼀个集合中的技术。它实际上是⼀个很⻓的⼆ 进制向量和⼀系列随机映射函数。 什么使用布隆过滤器? 布隆过滤器可以用来避免缓存击穿,在海量数据...
  • 布隆过滤器

    2020-02-13 07:32:38
    布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。(来源:百度百科) 1.1. 是什么可以理解一个很长的数组, 将大批量的...
  • 1.6 我想声明一个指针,并它分配一些空间,但却不行。这样的代码有什么问题?char*p;*p=malloc(10); 声明风格 1.7 怎样声明和定义全局变量和函数最好? 1.8 如何在C中实现不透明(抽象)数据类型? 1.9 如何生成...
  • 1.6 我想声明一个指针,并它分配一些空间,但却不行。这样的代码有什么问题?char *p; *p=malloc(10); 4 声明风格 4 1.7 怎样声明和定义全局变量和函数最好? 4 1.8 如何在C中实现不透明(抽象)数据类型? ...
  • 《你必须知道的495个C语言问题》

    热门讨论 2010-03-20 16:41:18
    1.6 我想声明一个指针,并它分配一些空间,但却不行。这样的代码有什么问题?char *p; *p=malloc(10); 4 声明风格 4 1.7 怎样声明和定义全局变量和函数最好? 4 1.8 如何在C中实现不透明(抽象)数据类型? ...
  • 实例017 判断代码中的括号是否匹配 实例018 修改可执行文件中的资源 1.3 程序调试 实例019 创建调试程序 实例020 在Release版本中进行调试 实例021 在VC中如何进行远程调试 实例022 利用简单断点进行程序调试...
  • 实例017 判断代码中的括号是否匹配 实例018 修改可执行文件中的资源 1.3 程序调试 实例019 创建调试程序 实例020 在Release版本中进行调试 实例021 在VC中如何进行远程调试 实例022 利用简单断点进行程序调试...
  • </li><li>可用于判断一个元素是否在一个集合中,查询效率很高(1-N,最优能逼近于1)</li><li>图示 ...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    设计一个构造函数,当对象结束时,要释放整个二叉搜索树所占的内存空间(提示,通过后序遍历算法找到叶结点,并删除叶结点,不断重复此过程,直到整科树空); 2、实现1所要求的代码后,运行设计好的代码,将...
  • 增加了Tick事件驱动的支持,根据OnTick方法判断Tick是否到来,若无新Tick,则一致阻塞状态, 此方法提高了性能。 2016.11.8 QuickLib(期货行情交易接口) 1.67 增加了查询合约保证金比例的方法 ...
  • 3.7.1 改动向量(Change Vector) 112 3.7.2 Redo记录 112 3.7.3 检查点 115 3.7.4 SCN号 116 3.7.5 数据库恢复 118 3.7.6 恢复过程 120 3.8 Oracle MAA介绍 123 3.9 小结 125 第4章 OEM 126 4.1 ...
  • IDF算法以及向量空间模型 25_ElasticSearch 揭秘lucene的相关度分数算法 26_ElasticSearch 四种常见的相关度分数优化方法 27_ElasticSearch用function_score自定义相关度分数算法 28_ElasticSearch误拼写时...

空空如也

空空如也

1 2
收藏数 29
精华内容 11
关键字:

判断集合是否为向量空间