吴尼玛

吴尼玛 查看完整档案

武汉编辑武汉理工大学  |  电子与通信工程 编辑科大讯飞  |  Cplusplus开发 编辑填写个人主网站
编辑

学技术简单记,吴尼玛带你记笔记。

个人动态

吴尼玛 发布了文章 · 4月18日

Linux命令行参数解析——getopt_long

  • 在linux中,一切皆文件,所有的可执行程序都可以通过命令行启动,程序启动时通常都会带上各种参数以控制程序的行为。所以解析命令行参数通常是一个可执行程序的第一步,下面就来介绍下经常用到的命令行参数的解析函数——getopt_long。
  • 我们先来了解一下命令行参数。命令行参数可以分为两类,一类是短选项,一类是长选项。在命令行中"-"表示短选项,"--"则表示长选项。例如,在linux中最常用的ls命令中“-a,-A,-b”都是短选项,而它们对应的长选项则是“--all,--almost-all, --escape”。它们还都可选择性的添加额外参数,比如“--block-size=SIZE”。
  • getopt_long支持处理长短选项的命令行解析,函数在<getopt.h>头文件中。其函数定义是:

    int getopt_long(int argc, char * const argv[], const char *optstring, const struct option *longopts, int *longindex); 
  • 接下来介绍一下其参数以及返回值。

    • argc和argv和main函数的两个参数一致。
    • optstring: 表示短选项字符串。
      形式如“a“,分别表示程序支持的命令行短选项有-a、-b、-c、-d,冒号含义如下:

        1. 只有一个字符,不带冒号——只表示选项, 如-c。
        2. 一个字符,后接一个冒号——表示选项后面带一个参数,如-a 100。
        3. 一个字符,后接两个冒号——表示选项后面带一个可选参数,即参数可有可无, 如果带参数,则选项与参数之间不能有空格,如-b123。

    • longopts:表示长选项结构体。其结构以及解释如下:

      struct option { 
      const char *name;// 表示的是长选项名称 
      int has_arg;// 表示选项后面是否携带参数。有3个值。
      // no_argument(或者是0),参数后面不跟参数值。
      // required_argument(或者是1),参数输入格式为:--参数 值 或者 --参数=值。
      // optional_argument(或者是2),参数输入格式只能为:--参数=值。
      int *flag;//用来决定函数的返回值。如果flag是null,则函数会返回与该项option匹配的val值,如果flag不是null,则函数返回0,并将flag指针参数指向与该项option匹配的val值。
      int val; //和flag联合决定返回值 
      } 
      • longindex:longindex不是null的话则指向的变量将记录longopts的下标值。
    • 返回值:

      1. 如果短选项找到,那么将返回短选项对应的字符。
      2. 如果长选项找到,且flag为null,返回val,flag不为null,返回0。
      3. 如果发生错误,如:未识别选项或者必须加参数的选项丢失参数,返回“?”,如果在optstring中设置了第一个字符为“:”,丢失参数返回“:”。
      4. 当缩写长选项引起歧义时或者不需要的选项强加了参数,都会返回“?”。
      5. 返回-1表示选项处理全部结束。
      6. 如果在输入的argv[]中包含了独立的“--”字符串,解析到这里返回-1,停止选项的解析。
  • 还有一些需要了解的全局变量:

    • optarg(指针):表示当前选项对应的参数值。
    • optind:表示的是下一个将被处理到的参数在argv中的下标值。
    • opterr:如果opterr = 0,遇到错误将不会输出错误信息到标准输出流。opterr在非0时,向屏幕输出错误。
    • optopt:表示出错或者未识别的选项。
  • 注意事项:

    • longopts的最后一个元素必须是全0填充,否则会报段错误
    • 短选项中每个选项都是唯一的。而长选项如果简写,也需要保持唯一性。
  • 下面是一个简单的例子:

    /* 程序运行参数结构体 */
    struct InputArgs
    {
      std::string user_id;
      std::string user_name;
      std::string pwd;
    
      void printArgs();
    
      bool checkArgs()
      {
        if (user_id.empty())
        {
          return false;
        }
    
        if (user_name.empty())
        {
          return false;
        }
    
        if (pwd.empty())
        {
          return false;
        }
    
        return true;
      }
    };
    
    InputArgs g_input_arg_info;
    
    void InputArgs::printArgs(){
        printf("ARGS:  --= %s\n", userId.c_str());
        printf("        --userName = %s\n", user_name.c_str());
        printf("        --pwd = %s\n", pwd.c_str());
    }
    
    /* 参数解析 */
    const char* short_options = "i:n:p:";
    struct option long_options[] = {
        { "userId", required_argument, NULL, 'i' },
        { "userName", required_argument, NULL, 'n' },
        { "pwd", required_argument, NULL, 'p' },
        { 0, 0, 0, 0 }, 
    };
    
    void print_usage(){
        printf("DESCRIPTION\n");
        printf("  --userId, -i\n");
        printf("  --userName, -n\n");
        printf("  --pwd, -p\n");
    }
    
    void print_arg(int argc, char *argv[])
    {
      for (int i = 0; i < argc; i++)
      {
        printf("%s\n", argv[i]);
      }
    }
    
    int parse_arg(int argc, char *argv[])
    {
      print_arg(argc, argv);
      int c;
      std::string opt;
      while ((c = getopt_long(argc, argv, short_options, long_options, NULL)) !=
             -1)
      {
        switch (c)
        {
        case 'i':
          opt = optarg;
          g_input_arg_info.user_id = opt;
          break;
        case 'n':
          opt = optarg;
          g_input_arg_info.user_name = opt;
          break;
        case 'p':
          opt = optarg;
          g_input_arg_info.pwd = opt;
          break;
        default:
          return -1;
        }
      }
    
      if (false == g_input_arg_info.checkArgs())
      {
        return -2;
      }
    
      return 0;
    }
    
    int main(int argc, char *argv[])
    {
      if (0 != parse_arg(argc, argv))
      {
        print_usage();
        printf("parse input args failed!\n");
        return 1;
      }
    
      g_input_arg_info.printArgs();
    
      // do things here
    }
查看原文

赞 0 收藏 0 评论 0

吴尼玛 发布了文章 · 4月5日

CMake编译遇到这种ABI不兼容问题不要慌

最近,在Linux下使用CMake编译程序的时候遇到一个问题,特此做一个记录。

事情是这样的,我编译的程序使用了2个第三方库,在写好CMakeLists后,启动编译,然后就报链接错误,一直报一堆找不到定义。

类似这样的一堆:

‘***** std::__cxx11 *******’未定义的引用

我仔细检查代码和CMakeLists,各种修改尝试无果。最后,在同事和搜索引擎的帮助下终于找到问题所在了。

问题出在我使用的GCC和第三方库编译的时候使用的GCC版本差异太大,两者的ABI不兼容。

参考GCC提供的手册<Dual ABI>,事情就清晰了。

在GCC5.1发布的libstdc++中,添加了新的特性,其中包括了std::string和std::list的新实现。新的实现使得两者都符合了C++11的标准。但是,为了与现存代码兼容,libstdc++保留了老的实现,与新实现并存。具体怎么实现的呢?相比于老的实现,GCC5.1添加了__cxx11命名空间,在新的实现中的string和list,实际上是std::__cxx11::string和std::__cxx11::list。新旧ABI不兼容。

那么,问题怎么解决呢?

也很简单,就是统一你的程序和第三方库使用的实现版本。如果你有第三方库源码,那统一重新编译下就行。如果第三方库是已经编译好的那也没关系,GCC为我们提供了一个选择新旧实现的宏定义-D_GLIBCXX_USE_CXX11_ABI

-D_GLIBCXX_USE_CXX11_ABI=0 表示使用旧的实现
-D_GLIBCXX_USE_CXX11_ABI=1 表示使用新的实现

按需添加到CMakeLists中就可以了。

查看原文

赞 0 收藏 0 评论 0

吴尼玛 发布了文章 · 4月3日

C++大厂面试真题

C++标准库的map和set有什么区别,如何实现的?

  • map和set都是C++的关联容器,其底层实现都是红黑树。
  • map和set区别在于:

    • map中的元素是key-value(键-值)对:关键字起到索引的作用,值则表示与索引相关联的数据;set是关键字的简单集合,set中的元素都只包含一个关键字。
    • set的迭代器是const的,不允许修改元素的值;map允许修改value,但不允许修改key。
    其原因是map和set是根据关键字排序来保证其有序性的,如果允许修改关键字的话,那么首先需要删除该键,然后调节树平衡,再插入修改后的键值,再重新调节树平衡。这样会破坏map和set的结构,导致迭代器失效。
    • map支持下标操作,set不支持下标操作。

map底层为什么要用红黑树实现?

  • 红黑树的特点:红黑树是二叉查找树,但在每个节点增加一个存储为表示节点的颜色,可以是红色或黑色,通过对任意一条从根到叶子的路径上各个节点着色方式的限制,红黑树确保没有一条路径会比其他路径长两倍。因此,它是一种弱平衡二叉树,相对于严格的平衡二叉(AVL)树来说,它的旋转次数少,所以对于查找、插入、删除较多的情况下,通常使用红黑树。
  • AVL是严格平衡的,频繁的插入和删除,会引起频繁的再平衡,导致效率降低;红黑树是弱平衡的,算是一种折中,插入最多旋转2次,删除最多旋转3次。所以红黑树在查找、插入、删除的复杂度都是O(logn),且性能稳定,所以STL里面很多结构包括map底层都是使用的红黑树。

简述weak_ptr的作用

  • weak_ptr是为了配合shared_ptr而引入的一种智能指针,因为没有重载operator*和->,所以它不能像普通指针那样使用。
  • weak_ptr最大作用在于协助shared_ptr工作,像旁观者那样观测资源的使用情况。weak_ptr可以从一个shared_ptr或者另一个weak_ptr对象构造,获得资源的观测权。但weak_ptr没有共享资源,它的构造不会引起shared_ptr引用计数的增加。
  • 使用weak_ptr的成员函数use_count()可以观测资源的引用计数,另一个成员函数expired()的功能等价于use_count()==0,表示被观测的资源已经不存在。weak_ptr也可以使用成员函数lock()从被观测的shared_ptr获得一个可用的shared_ptr对象, 从而操作资源。但当expired()==true的时候,lock()函数将返回一个存储空指针的shared_ptr。
  • 简单来说就是:

    • 观测shared_ptr资源使用情况。
    • 解除shared_ptr循环引用问题.

C/C++的参数入栈顺序为什么是从右向左?

  • 从右向左压栈的顺序是与C/C++支持可变参数有关的。C/C++要求在声明参数可变的函数时,需要有至少一个确定的参数。为什么呢?因为需要有一个参数为函数提供可变参数的类型(否则函数怎么知道如何解析后续的可变参数?比如,可变参数列表中有两个参数,一个int型,一个byte型,函数在解析可变参数表时,怎么知道这5字节的数据到底应该如何去解析)如果一个可变参数的参数类型事先确定的话,这个参数就没有存在的意义了。
  • 如果参数入栈顺序是从左向右压栈,第一个参数(即描述可变参数表各变量类型的那个参数)将被放在栈底,由于可变参的函数第一步就需要解析可变参数表的各参数类型,即第一步就需要得到上述参数,因此,将它放在栈底是很不方便的。当然,从左向右压栈的话也可以实现可变参的功能,但是这样的话,该功能实现起来会复杂些。

一般程序的虚拟内存空间为什么是4g?

  • 因为寻址空间取决于cpu地址线条数,如32位机,寻址空间为2^32 = 4G,所以最大只支持4G的寻址空间,即使插了8G的内存条也只能使用4G内存。

Duilib为什么绘图性能不好?

  • (答案仅供参考)Duilib是DirectUI思想的一种实现。DirectUI通俗来说就是在窗口上指定一块区域(仅仅是一个区域,不是一个实体控件)通过各种消息模拟一个控件的功能。完全可以在一个对话框类的OnMouseMove、OnLButtonDown等函数中模拟一个按钮出来。但是模拟的控件一多就混乱了,为了统一管理,逻辑上更清晰类似于实体控件。把每种控件封装成类处理各种消息,并通过自定义的消息分发机制把消息分发到各个模拟控件里。这种模拟的方式绘制和消息处理效率相比于实体控件要低。
  • Duilib的图片绘制代码中也有影响性能的地方,所有的控件的图片绘制都是调用CControlUI的DrawImage函数,而此函数调用了CRenderEngine的DrawImageString函数。在绘制图片时,DrawImageString会解析图片字符串的属性,然后找到对片的HBITMAP资源,最后调用真正的绘图函数去绘制。问题就在于每绘制一个图片都会再次解析一次字符串,当界面比较复杂,而且图片字符串也比较复杂时,这个解析的过程就影响了程序效率。当然这可以通过缓存图片资源解析结果的方式来优化。

什么是内存泄露?如何检查内存泄露?

  • 内存泄漏是指在程序中动态申请的内存或者资源在使用完后,没有释放。这样可能导致程序使用的内存不断增大,最终会因系统内存不足,而导致程序崩溃或其他错误。
  • 在Windows下可以通过任务管理器查看内存使用情况,可以简单分析是否有内存泄漏。也有很多像VLD这样的内存泄漏检测工具。如果是使用VC库来写程序的话,在Debug版本中也可以使用VC的C运行库中提供的像_CrtCheckMemory、_CrtCheckMemory、_CrtMemCheckpoint、_CrtMemDifference、_CrtMemDumpAllObjectsSince等函数来检测和定位内存泄漏问题。

C++程序崩溃的一般原因是什么?怎么定位崩溃问题?

  • 程序崩溃一般有3个原因:

    • 操作了野指针
    • 内存访问错误(包括格式化数据类型错误、索引越界等)
    • 堆栈溢出
  • 在Windows下我们一般会在编译程序时保留其pdb文件,设置崩溃时生成dump文件。因此,可以通过VS或者Windbg结合pdb文件来分析崩溃产生的dump。大部分时候,通过Windbg的“!analyze -v”命令我们就能定位到崩溃问题的代码行。如果崩溃的代码行不是实际引起问题的地方,我们也可以通过相关代码的上下文结合log以及崩溃前操作等现象来分析崩溃原因。最后,还可以通过dump查看崩溃时其他的堆栈或者线程信息,做进一步分析。
查看原文

赞 0 收藏 0 评论 0

吴尼玛 发布了文章 · 3月7日

《More Effective C++》总结笔记(三)

效率

条款16:谨记80-20法则

  • 80-20法则说:一个程序80%的资源用于20%的代码身上。是的。80%的执行时间花在大约20%的代码身上,80%的内存被大约20%的代码使用,80%的磁盘访问动作由20%的代码执行,80%的维护力气花在20%的代码上面。
  • 不必拘泥于法则的数字,其基本重点是:软件的整体性能几乎总是由其构成要素(代码)的一小部分决定。
  • 从某个角度看,80-20法则暗示,大部分时候你所产出的代码,其性能坦白说是平凡的,因为80%的时间中,其效率不会影响系统整体性能。或许这不至于对你的自尊心造成太大打击,但应该多少会降低你的压力。从另一个角度看,这个法则暗示,如果你的软件有性能上的问题,你将面临悲惨的前景,因为你不只需要找出造成问题的那一小段瓶颈所在,还必须找出办法来大幅提升其性能。这些工作中,最麻烦的还是找出瓶颈所在。
  • 找性能瓶颈的方法不能靠猜。可行之道是完全根据观察或实验来识别出造成你心痛的那20%代码。而辨识之道就是借助某个程序分析器。然而并不是任何分析器都足堪大任,它必须可以直接测量你所在意的资源。

条款17:考虑使用lazy evaluation(缓式评估)

  • 一旦你采用lazy evaluation,就是以某种方式撰写的你classes,使它们延缓运算,直到那些运算结果刻不容缓地被迫切需要为止。如果其预算结果一直不被需要,运算也就一直不执行。
  • lazy evaluation在许多领域中都可能有用途:可避免非必要的对象复制,可区别operator[]的读取和写动作,可避免非必要的数据库读取动作,可避免非必要的数值计算动作。

条款18:分期摊还预期的计算成本

  • 此条款背后的哲学可称为超急评估(over-eager evaluation):在被要求之前就先把事情做下去。
  • over-eager evaluation背后的观念是,如果你预期程序常常会用到某个计算,你可以降低每次计算的平均成本,办法就是设计一份数据结构以便能够极有效率地处理需求。
  • 其中个最简单的一个做法就是将“已经计算好而有可能再被需要”的数值保留下来(所谓caching)。另一种做法则是预先取出(prefetching)。prefetching的一个典型例子就是std的vector数组扩张的内存分配策略(每次扩大两倍)。
  • 条款17和18看似矛盾,实际都体现了计算机中一个古老的思想:用空间换时间。结合起来看,它们是不矛盾的。当你必须支持某些运算而其结果并不总是需要的时候,lazy evaluation可以改善程序效率。当你必须支持某些运算而其结果几乎总是被需要,或其结果常常被多次需要的时候,over-eager evaluation可以改善程序效率。

条款19:了解临时对象的来源

  • C++真正的所谓的临时对象时不可见的——不会在你的源代码中出现。只要你产生一个non-heap object而没有为它命名,便诞生了一个临时对象。此等匿名对象通常发生于两种情况:一是当隐式类型转换被施行起来以求函数调用能够成功;二是当函数返回对象的时候。
  • 任何时候只要你看到一个reference-to-const参数,就极可能会有一个临时对象被产生出来绑定至该参数上。任何时候只要你看到函数返回一个对象,就会产生临时对象(并于稍后销毁)。学些找出这些架构,你对幕后成本(编译器行为)的洞察力将会有显著地提升。

条款20:协助完成“返回值优化(RVO)”

  • 如果函数一定得以by-value方式返回对象,你绝对无法消除之。从效率的眼光来看,你不应该在乎函数返回了一个对象,你应该在乎的是那个对象的成本几何。你需要做的,是努力找出某种方法以降低被返回对象的成本,而不是想尽办法消除对象本身。
  • 我们可以用某种特殊写法来撰写函数,使它在返回对象时,能够让编译器消除临时对象的成本。我们的伎俩是:返回所谓的constructor arguments以取代对象。考虑分数(rational numbers)的operator*函数,一个有效率而且正确的做法是:
const Rational operator*(const Rational& lhs, const Rational& rhs)
{
    return Rational(lhs.numerator() * rhs.numerator(), lhs.denominator() * rhs.denominator());
}
  • C++允许编译器将临时对象优化,使它们不存在。于是如果你这样调用operator*:
Rational a = 10;
Rational b(1,2);
Rational c = a * b;
  • 你的编译器得以消除“operator*内的临时对象”及“被operator*返回的临时对象”。它们可以将return表达式所定义的对象构造于c的内存内。
  • 你可以将此函数声明为inline,以消除调用operator*所花费的额外开销。这就是返回一个对象最有效率的做法。

条款21:利用重载技术(overload)避免隐式类型转换(implicit type conversions)

  • 考虑以下代码:
class UPInt { // 这个class用于无限精密的整数
plublic:
    UPInt();
    UPInt(int value);
    ...
};
const UPInt operator+(const UPInt& lhs, const UPInt& rhs);
UPInt upi1, upi2;
...
UPInt upi3 = upi1 + upi2;
upi3 = upi1 + 10;
upi3 = 10 + upi2;
  • 因为有隐式转换,所以以上语句都能执行成功。但这样执行会产生临时对象,这对执行效率是有影响的。
  • 如果有其他做法可以让operator+在自变量类型混杂的情况下呗调用成功,那便消除了了类型学转换的需求。如果我们希望能够对UPInt和int进行加法,我们需要做的就是将我们的意图告诉编译器,做法是声明数个函数,每个函数有不同的参数表:
const UPInt operator+(const UPInt& lhs, const UPInt& rhs); // 将UPInt和UPInt相加
const UPInt operator+(const UPInt& lhs, const int& rhs); // 将UPInt和int相加
const UPInt operator+(const int& lhs, const UPInt& rhs); // 将int和UPInt相加
  • 但是不要写出以下函数:
const UPInt operator+(const int& lhs, const int& rhs);
  • 因为,C++存在很多游戏规则,其中之一就是:每个“重载操作符”必须获得至少一个“用户定制类型”的自变量。int不是用户定制类型,所以我们不能够将一个只获得int自变量的操作符加以重载,这会改变ints的加法意义。

条款22:考虑以操作符复合形式(op=)取代其独身形式(op)

  • 要确保操作符的复合形式(例如,operator+=)和其独身形式(例如,operator+)之间的自然关系能够存在,一个好方法就是以前者为基础实现后者:
const Rational operator+(const Rational& lhs, const Rational& rhs)
{
    return Rational(lhs) += rhs;
}
  • 一般而言,复合操作符比其对应的独身版本效率高,因为独身版本通常必须返回一个新对象,而我们必须因此负担一个临时对象的构造和析构成本。至于复合版本则是直接将结果写入其左端自变量,所以不需要产生一个临时对象来放置返回值。
  • 操作符我复合版本比其对应的独身版本有着更高效率的倾向。身为一位程序库设计者,你应该两者都提供;身为一位应用软件开发者,如果性能是重要因素的话,你应该考虑以复合版本操作符取代其独身版本。

条款23:考虑使用其他程序库

  • 不同的设计者面对不同的特性会给予不同的优先权。他们的设计各有不同的牺牲。于是,很容易出现“两个程序库提供类似机能,却又相当不同的性能表现”的情况。
  • 所以一旦你找出程序的性能瓶颈(通过分析器),你应该思考是否有可能因为改用另一个程序库而移除了那些瓶颈。

条款24:了解virtual functions、multiple inheritance、virtual base classes、runtime type identification的成本

  • 虚函数的第一个成本:你必须为每个拥有虚函数的class耗费一个vtbl空间,其大小视虚函数的个数(包括继承而来的)而定。
  • 虚函数的第二个成本:你必须在每一个拥有虚函数的对象内付出“一个额外指针”的代价。
  • inline意味着在编译期将调用端的调用动作被调用函数的函数本体取代,而virtual则意味着直到运行期才直到哪个函数被调用。因此虚函数的第三个成本就是:你事实上等于放弃了inlining。
  • 多重继承往往导致virtual base classes(虚拟基类)的需求。virtual base classes可能导致对象内的隐藏指针增加。
  • RTTI让我们得以在运行期获得objects和classes的相关信息,它们本存放在类型为type_info的对象内。你可以利用typeid操作符取得某个class相应的type_info对象。
  • RTTI的设计理念是:根据class的vtbl来实现。举个例子,vtbl数组中,索引为0的条目可能内含一个指针,指向“该vtbl所对应的class”的相应的type_info对象。运用这种实现方法,RTTI的空间成本就只需在每一个class vtbl内增加一个条目,再加上每个class所需的一份type_info对象空间。
查看原文

赞 0 收藏 0 评论 0

吴尼玛 发布了文章 · 2月15日

青蛙跳问题为什么是斐波那契数列

  • 在面试中我们可能会遇到青蛙跳的问题:一只青蛙一次可以跳上一级台阶,或者跳上二级台阶。那么如果总共有N级台阶,问这只青蛙总共有多少种跳法?
  • 首先,我们考虑最简单的情况,如果只有一级台阶,那显然青蛙只有一种跳法。如果只有二级台阶,那么青蛙就有两种跳法,一种是每次跳一级,总共跳二次,另一种就是直接跳二级。
  • 接下来,再来看N级的(N大于2)的情况。我们先把N级台阶的跳法看做一个N的函数,记为f(N)。考虑N>2时,第一次跳就有两种跳法,一种是第一次只跳一级,此时跳法数就是后面剩下的N-1级台阶的跳法数,即为f(N-1);另一种则是第一次跳二级,那么此时的跳法数就是后面剩下的N-2级台阶的跳法数,即为f(N-2)。所以,N级台阶的跳法总数就是f(N)=f(N-1)+f(N-2)。显然这就是一个N>0的斐波那契数列。
  • C++实现递归解法
#include<iostream> 
using namespace std; 

long long RecursiveFibonacci(unsigned int n)
{
    if(n == 1 || n == 2)
        return n;

    return RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2);
}

int main() 
{
    cout << "RecursiveFibonacci(1)=" << RecursiveFibonacci(1) << endl;
    cout << "RecursiveFibonacci(2)=" << RecursiveFibonacci(2) << endl;
    cout << "RecursiveFibonacci(3)=" << RecursiveFibonacci(3) << endl;
    cout << "RecursiveFibonacci(5)=" << RecursiveFibonacci(5) << endl;
    cout << "RecursiveFibonacci(10)=" << RecursiveFibonacci(10) << endl;
    cout << "RecursiveFibonacci(50)=" << RecursiveFibonacci(50) << endl;
    cout << "RecursiveFibonacci(100)=" << RecursiveFibonacci(100) << endl;
}
  • 很显然,递归实现效率是非常低的,其时间复杂度是n的指数级。因为递归存在着大量的重复计算,大家也可以自己跑代码试试,递归去计算n=50就非常慢了。
  • 所以,优化思路就是从前往后计算,先根据f(1)和f(2)算f(3),在根据f(2)和f(3)算f(4),以此类推算出f(N)。其时间复杂度是O(n)。
  • C++实现非递归解法
#include<iostream> 
using namespace std; 

long long NonRecursiveFibonacci(unsigned int n)
{
    if(n == 1 || n == 2)
        return n;

    long long n1 = 1;
    long long n2 = 2;
    long long result = 0;
    for (unsigned int i = 3; i <= n; i++)
    {   
        result = n1 + n2;
        n1 = n2;
        n2 = result;
    }
    return result;
}

int main() 
{
    cout << "NonRecursiveFibonacci(1)=" << NonRecursiveFibonacci(1) << endl;
    cout << "NonRecursiveFibonacci(2)=" << NonRecursiveFibonacci(2) << endl;
    cout << "NonRecursiveFibonacci(3)=" << NonRecursiveFibonacci(3) << endl;
    cout << "NonRecursiveFibonacci(5)=" << NonRecursiveFibonacci(5) << endl;
    cout << "NonRecursiveFibonacci(10)=" << NonRecursiveFibonacci(10) << endl;
    cout << "NonRecursiveFibonacci(50)=" << NonRecursiveFibonacci(50) << endl;
    cout << "NonRecursiveFibonacci(100)=" << NonRecursiveFibonacci(100) << endl;
}
查看原文

赞 0 收藏 0 评论 0

吴尼玛 发布了文章 · 2月5日

《More Effective C++》总结笔记(二)——异常

异常

条款9:利用destructors避免泄露资源

  • 只要坚持这个规则,把资源封装在对象内(类似智能指针shared_ptr),通常便可以在exceptions出现时避免泄露资源。
  • 简单来说就是,当有资源可能在函数抛异常时而无法释放,这时可以将资源封装到对象内(RAII),利用对象的析构函数来自动释放资源,这样即使有exceptions发生,也不会有资源泄露。

条款10:在constructors内阻止资源泄露(resource leak)

  • C++只会析构已构造完成的对象。对象只有在其constructor执行完毕才算是完成构造妥当。
  • 由于C++不自动清理那些“构造期间抛出exceptions”的对象,所以你必须设计你的constructors,使它们在那种情况下亦能自我清理。通常这只需要将所有可能的exceptions捕捉起来,执行某种清理工作,然后重新抛出exception,使它继续传播出去即可。
  • 但是,更优雅的做法实际上是将这些需要在constructor内初始化的对象视为资源,将它们交由智能指针来管理。
  • 结论是:如果你以auto_ptr(C++11后使用shared_ptr或者unique_ptr)对象来取代pointer class members,你便对你的constructors做了强化工事,免除了“exceptions出现时发生资源泄露”的危机,不再需要在destructors内亲自动手释放资源,并允许const member pointers得以和non-const member pointers有着一样优雅的处理方式。

条款11:禁止异常(exceptions)流出destructors之外

Session::Session()
{
  try {
    logDestruction(this);
  }
  catch (...) {
  }
}
  • 这里的catch语句块看起来什么都没做,但是外表容易骗人。这个语句块阻止了“logDestruction所抛出的exceptions”传出Session destructor之外。
  • 有两个好理由支持我们“全力阻止exceptions传出destructors之外”。第一,它可以避免terminate函数在exception传播过程的栈展开(stack-unwinding)机制中被调用;第二,它可以协助确保destructors完成其应该完成的所有事情。

条款12:了解“抛出一个exception”与“传递一个参数”或“调用一个虚函数”之间的差异

  • “抛出exception”与“传递参数”的相同点是:它们的传递方式有3中:by value(传值),by reference(传引用),by pointer(传指针)。然而视你所传递的是参数或exceptions,发生的事情可能完全不同。原因是当你调用一个函数,控制权最终会回到调用端(除非函数失败以至于无法返回),但是当你抛出一个exception,控制权不会再回到抛出端。
  • “抛出exception”与“传递参数”的区别一:C++特别声明,一个对象被抛出作为exception时,总是会发生复制(copy)。即使catch语句参数时by reference,或者抛出对象声明为static也一样会发生复制。且复制动作永远是以对象的静态类型为本。
  • “exception objects必定会造成复制行为”这一事实也解释了“传递参数”和“抛出exception”之间的另一个不同:后者常常比前者慢。
  • 一般而言,你必须使用一下语句:

throw;
才能重新抛出当前的exception,其间没有机会让你改变被传播的exception的类型。此外,它也比较有效率,因为不需要产生新的exception object。

  • “抛出exception”与“传递参数”的区别二:函数调用过程中将一个临时对象传递给一个non-const reference参数时不允许的,但对exception则属合法。
  • “抛出exception”与“传递参数”的区别三:一般而言,调用函数传递参数过程中允许的隐式转换在“exceptions与catch子句相匹配”的过程中使不会发生的。
  • “exceptions与catch子句相匹配”的过程中,仅有两种转换可以发生。第一种是“继承架构中的类转换”。第二种是从一个“有型指针”转为“无型指针”(所以一个参数为const void*的catch子句,可捕捉任何指针类型的exception)。
  • “抛出exception”与“传递参数”的区别四:catch子句总是依出现顺序做匹配尝试。与虚函数调用比较,虚函数采用”best fit“(最佳吻合)策略,而exception处理机制采用”first fit“(最先吻合)策略。因此,绝对不要将”针对base class而设计的catch子句“放在”针对derived class而设计的catch子句“之前。

条款13:以by reference方式捕捉exceptions

  • 相比于by reference方式,以by value方式捕获exception,会使被传递的对象发生两次复制,产生两个副本。其中一个构造动作用于“任何exceptions都会产生的临时对象”身上,另一个构造动作用于“将临时对象复制到catch的参数上”。
  • 千万不要抛出一个指向局部对象的指针,因为该局部对象会在exception传离其scope时被销毁,因此catch子句会获得一个指向“已被销毁的对象”的指针。
  • 如果catch by reference,你就可以避开对象删除问题(by pointer会面对的)——它会让你动辄得咎,做也不是,不做也不是;你也可以避开exception objects的切割问题(派生类对象的exception objects被捕捉并被视为基类对象的exception objects,将失去其派生成分。对象切割问题是由于静态编联导致的,使用引用和指针时不会发生);你可以保留捕捉C++标准exceptions的能力;你也约束了exception objects需被复制的次数。

条款14:明智运用exception specifications

  • exception specification示例,一个只抛出int类型exceptions的函数声明为:
void fun() throw(int);
  • 如果函数抛出一个并未列入exception specification的exception,这个错误会在运行时期被检验出来,于是特殊函数unexpected会被自动调用。unexpected的默认行为是调用terminate。
  • 想要避免这种unexpected的方法就是:

    • 不应该将templates和exception specifications混合使用。
    • 如果A函数内调用了B函数,而B函数无exception specifications,那么A函数本身也不要设定exception specifications。
    • 处理“系统”可能抛出的exceptions(如bad_alloc)。
  • C++允许你以不同类型的exceptions取代非预期的exceptions。如果非预期函数的替代者重新抛出当前的exception,该exception会被标准类型bad_exception取而代之。
void convertUnexpected()
{
  throw;
}

set_unexpected(convertUnexpected);
  • 如果你做了上述安排,并且每一个exception specifications都含有bad_exception,或者其基类,你就再也不必担心程序会于是非预期的exception时中止执行。

了解异常处理(exception handling)的成本

  • 为了让exception的相关成本最小化,只要能够不支持exceptions,编译器便不支持;请将你对try语句块和exception specifications的使用限制于非用不可的地点,并且在真正异常的情况下才抛出exceptions。
查看原文

赞 0 收藏 0 评论 0

吴尼玛 发布了文章 · 1月31日

C++程序性能优化指南

原则

  • 《More Effective C++》书中效率部分第一条就是80—20准则。说得是——大约 20%的代码使用了 80%的程序资源;大约 20%的代码耗用了大约 80%的运行时间;大约 20%的代码使用了 80%的内存。因此,一些简单的优化也能显著提高程序性能。
  • 先完成程序功能,再考虑性能优化的事,否则会出现代码可读性差,过度抽象等问题。
  • 大部分的性能优化其实都是在做时间和空间的权衡,空间换时间,或者时间换空间。
  • 良好的代码风格和代码规范能有效的避免性能问题的出现,所以codereview也很重要。
  • 我们真正想大幅度的提升程序性能需要借助程序分析器(profiler)寻找出程序的性能瓶颈,针对这个瓶颈进行代码层面,算法层面,架构层面等多方面的优化。

常用优化方法

  • 空间足够时,可以将经常需要读取的资源,缓存在内存中。
  • 尽量减少大内存对象的构造与析构,考虑缓存暂时不用的对象,等待后续继续使用。
  • 尽量使用C++11的右值语义,减少临时对象的构造。
  • 简单的功能函数可以使用内联。少用继承,多用组合,尽量减少继承层级。
  • 在循环遍历时,优化判断条件,减少循环次数。
  • 优化线程或进程的同步方式,能用原子操作的就不用锁。能应用层同步的就不用内核对象同步。
  • 优化堆内存的使用,如果有内存频繁的申请与释放,可以考虑内存池。
  • 优化线程的使用,节省系统资源与切换造成的性能损耗,线程使用频繁的可以考虑线程池。
  • 尽量使用事件通知,谨慎使用轮循或者sleep函数。
  • 界面开发中,耗时的业务代码不要放在UI线程中执行,使用单独的线程去异步处理耗时业务,提高界面响应速度。
  • 经常重构、优化代码结构。优化算法或者架构,从设计层面进行性能的优化。
查看原文

赞 0 收藏 0 评论 0

吴尼玛 发布了文章 · 1月24日

PC客户端离线安装包和下载器安装包的优劣点

  • 目前,PC客户端软件所使用的主流的安装包有2种,一种是离线安装包,一种是下载器安装包(以下简称下载器)。
  • 离线安装包最大的优点是安装快(只涉及解压),但其实你从官网下载离线安装包的用时和你用下载器下载安装的用时是理论上来说是差不多的。只是离线安装包的耗时主要在浏览器(或者其他渠道,比如360软件管家),下载器主要耗时在我们安装程序中。
  • 离线安装包还有一个好处是如果我们把它放到360软件管家之类的市场,用户安装的时候就走的是他们的流量,会节省我们的流量。
  • 那么为什么现在大部分软件都采用下载器的方式呢?

    • 下载器能保证你所获取的软件一定是官方的版本。因为有些软件下载站点会给你的软件加壳,修改,甚至加木马然后放在他们的网站上给用户下载,这时用户下载到的会是被篡改过的软件。
    • 下载器能保证你获取的软件版本一定是最新的。发布离线安装包需要每次所有渠道都要更新,还要控制好发布时机,以免出现刚安装完就提示更新的情况。
    • 下载器可以打广告,或者提供更新内容预览。因为下载比较耗时所以可以做轮播图片。不过个人觉得这也不一定算优点,我自己就从来不看这些内容,直接最小化了。
  • 总体来说,离线安装包和下载器各有优劣,以目前每个家庭平均都到20M的网速来说,下载器可能是更优的方案。但是离线安装包也有其存在的价值,比如放在360渠道等。
查看原文

赞 0 收藏 0 评论 0

吴尼玛 发布了文章 · 1月15日

c++关键字typeid

  • typeid是c++的一个关键字,typeid操作符的返回结果是标准库类型type_info对象的引用。
  • 但是,C++标准并没有明确定义type_info,其具体实现依赖于各个编译器。标准只规定了typeid操作符必需实现如下四种操作:
操作说明
t1 == t2如果两个对象t1和t2类型相同,则返回true;否则返回false
t1 != t2如果两个对象t1和t2类型不同,则返回true;否则返回false
t.name()返回类型的C-style字符串。由编译器决定,不一定就是真实的类型名
t1.before(t2)判断t1是否位于t2的前面。类型排列顺序与编译器相关,基类不一定位于派生类的前面。
  • type_info的成员函数name返回类型的C-style字符串,但这个返回的类型名与程序中使用的相应类型名不一定一致,其返回值的实现由编译器决定,标准只要求每个类型返回的字符串是唯一的。
  • 和sizeof操作符类似,typeid的操作对象既可以是数据类型,也可以是表达式。
  • 使用typeid判断各种类型示例代码如下:
#include<iostream>  
#include <typeinfo>  
using namespace std;  

class Base{};
class Derived:public Base{};
void func1();
int func2(int n);

int main()  
{  
    int a = 10;
    int* b = &a;
    float c;
    double d;

    cout << typeid(a).name() << endl;
    cout << typeid(b).name() << endl;
    cout << typeid(c).name() << endl;
    cout << typeid(d).name() << endl;
    cout << typeid(Base).name() << endl;
    cout << typeid(Derived).name() << endl;
    cout << typeid(func1).name() << endl;
    cout << typeid(func2).name() << endl;
}  
  • Mac下使用clang++编译运行结果如下:
i
Pi
f
d
4Base
7Derived
FvvE
FiiE
  • 不像Java、C#等动态语言,C++运行时能获取到的类型信息非常有限,标准也定义的很模糊,如同“鸡肋”一般。在实际工作中,我们一般只使用type_info的“==”运算符来判断两个类型是否相同。
  • 再来看看下面的示例代码:
#include<iostream>  
#include <typeinfo>  
using namespace std; 

class Base{};
class Drived: public Base{};

int main()
{
    Base* pb;
    Drived d;
    pb = &d;

    if(strcmp(typeid(*pb).name(), typeid(Base).name()) == 0)
    {
        cout << "this is Base" << endl;
    }
    else if(strcmp(typeid(*pb).name(), typeid(Drived).name()) == 0)
    {
        cout << "this is Drived" << endl;
    }
    
    if(strcmp(typeid(d).name(), typeid(Base).name()) == 0)
    {
        cout << "this is Base" << endl;
    }
    else if(strcmp(typeid(d).name(), typeid(Drived).name()) == 0)
    {
        cout << "this is Drived" << endl;
    }
}
  • Mac下使用clang++编译运行结果如下:
this is Base
this is Drived
  • 从运行结果中可以看出,即使用基类指针指向派生类,但使用typeid判断的基类指针类型依然是基类指针。因此我们不能用typeid来判断基类指针实际指向的是否是某个派生类。
查看原文

赞 0 收藏 0 评论 0

吴尼玛 发布了文章 · 1月10日

一文读懂C++内存对齐

操作系统64位和32位有什么区别?

  • 64位操作系统意味着其cpu拥有更大的寻址能力。理论上来说,其性能相比于32位操作系统会提升1倍。但是这也需要在64位操作系统上运行的软件也是64位的。
  • 软件中数据类型的的字节数大小其实和操作系统是多少位的没有关系,而是由编译器决定的。也就是说数据结构占多少位取决于在软件编译时我们选择的是64位还是32位的编译器。其具体占位数在编译器已经决定了。

数据类型对应字节数

  • 下面是不同位数编译器下基本数据类型对应的字节数。

32位编译器:

char :1个字节
char*(即指针变量): 4个字节
short int : 2个字节
int:  4个字节
unsigned int : 4个字节
float:  4个字节
double:   8个字节
long:   4个字节
long long:  8个字节
unsigned long:  4个字节

64位编译器:

char :1个字节
char*(即指针变量): 8个字节
short int : 2个字节
int:  4个字节
unsigned int : 4个字节
float:  4个字节
double:   8个字节
long:   8个字节
long long:  8个字节
unsigned long:  8个字节
  • 总结:32位和64位编译器的基本数据类型字节数主要差别在64位的指针和long为8字节。

C++内存对齐

  • 众所周知,为了保证每个对象拥有彼此独立的内存地址,C++空类的内存大小为1字节。而非空类的大小与类中非静态成员变量和虚函数表的多少有关。其中,类中非静态成员变量的大小则与编译器的位数以及内存对齐的设置有关。
  • 类中的成员变量在内存中并不一定是连续的。它是按照编译器的设置,按照内存块来存储的,这个内存块大小的取值,就是内存对齐。
  • 内存对齐有2个规则:

    • 第一个成员变量放在类中内存offset为0的地方,之后的成员变量的对齐按照#pragma pack(n)指定的数值和这个成员变量类型所占字节数中,比较小的那个进行(成员变量间补齐)。
    • 在成员变量完成各自内存对齐之后,类(结构或联合)本身也要进行内存对齐,对齐按照#pragma pack(n)指定的数值和类中最大成员变量类型所占字节数中,比较小的那个进行(类中最后一个成员变量结尾后补齐),类大小需要是对齐值得整数倍。
  • \#pragma pack(n)作为一个预编译指令用来设置内存对齐的字节数。需要注意的是,n的缺省数值是编译器设置的,一般为8,合法的数值分别是1、2、4、8、16。

延伸知识:C++空类大小

  • C++标准指出,不允许一个对象(当然包括类对象)的大小为0,不同的对象不能具有相同的地址。这是由于:

    • new需要分配不同的内存地址,不能分配内存大小为0的空间
    • 避免除以sizeof(T)时得到除以0错误故使用一个字节来区分空类。
  • 需要注意的是,这并不代表一个空基类也需要加一个字节到子类中去。这种情况下,空基类并不是独立的,它附属于子类。子类继承空基类后,子类如果有自己的数据成员,则空基类的那一个字节并不会加到子类中去。
查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 7 次点赞
  • 获得 2 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 2 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2020-01-04
个人主页被 1.5k 人浏览