存档

文章标签 ‘算法’

Boost LRU-Cache使用方法简介

2017年11月13日 没有评论

    缓存是提高系统运行效率的常用组件,可以将“有效的”业务数据直接返回用户,避免繁琐的计算过程。除了Redis、MemCache等常用缓存系统,应用程序内部也可以根据需要设置一定容量的缓存,减少跨进程调用,提高效率。

    LRU是常用的缓存策略,可以将访问最 频繁的数据保存在有限的缓存中,提高缓存命中率。

    在C++中,可以通过map来保存数据键值对,并通过list将最近使用的数据保存在一端,从list的另一端来清除过期数据的方法实现一个缓存系统。

    然而,我们没必要自己再造一个轮子。Boost-1.65.1版本开始引入了lru_cache算法,通过模板的方式可以方便的实例化出各种类型的缓存对象。

    下面简单介绍boost lru_cache的使用方法。

#lru_cache头文件,这是个header-only库,不需要其他模块
#include <string>
#include <iostream>
using namespace std;
#include <boost/compute/detail/lru_cache.hpp>

int main()
{
    const int iCacheSize=100;
    #初始化时设置缓存容量
    boost::compute::detail::lru_cache<string, string> ssCache(iCacheSize);

    #插入数据
    ssCache.insert("ZhangSan", "Beijing");
    ssCache.insert("LiSi", "Shanghai");

    #查找并获取数据
    string s("ZhangSan");
    if(ssCache.contains(s))
    {
        #注意!get方法返回的是一个boost::optional<string>对象,而不是直接返回存入其中的Value类型的对象!
        boost::optional<string> o_Region=ssCache.get(s);
        #我们可以通过boost::optional<string>的get()来获取Value对象
        string sRegion=o_Region.get();
        cout << s << " comes from " << sRegion << endl;
    }

    return 0;
}
分类: C/C++, 开发 标签: , ,

扑克洗牌算法(c++版)

2017年3月20日 没有评论

这是三年前去一家游戏公司面试时被问到的一个问题,当时由于自己在传统软件公司做业务,对算法没有留心学习,虽勉强答出来了,但从未实现过。今天随手写了个小程序做下验证。

基本思路:将代表扑克牌的52个数字放入vector中,每次随机抽取一张放入新的vector,并将被抽取牌从原vector中删除。如此循环52次,即可得到随机化的牌面。

代码如下:

#include <iostream>
using namespace std;
#include <vector>
#include <stdlib.h>

int main()
{
  unsigned int total;
  cout << "Please input the TOTAL:" << endl;  //输入52
  cin >> total;

  //将52个数放入vCards0

  vector<unsigned int> vCards0;
  unsigned int i=1;
  while(i <= total)
  {
    vCards0.push_back(i++);
  }

  vector<unsigned int> vCards1(vCards0);   //初始化另一个vector
  unsigned int idx=0;
  srand(time(NULL));

  i=0;
  unsigned int tt=total;
  while(i < total)  //依次抽取52张牌
  {
    idx = rand() % tt;  //从vCards0中随机抽取一张牌
    --tt;
    vCards1[i++]=vCards0[idx];  //放入vCards1

    //从vCards0中删除被抽取的那张牌

    vector<unsigned int>::iterator vi=vCards0.begin();
    unsigned int j=0;
    while(j < idx)
    {
      ++j;
      ++vi;
    }
    vCards0.erase(vi);
  }

  vector<unsigned int>::iterator vib=vCards1.begin();
  vector<unsigned int>::iterator vie=vCards1.end();
  while(vib != vie)
  {
    cout << *vib++ << " ";
  }
  cout << endl;

  return 0;
}

当然网上还有一些效率更高的算法,大家有兴趣可以找来看看。

分类: C/C++ 标签: