About
RSS

Bit Focus


日常的算法 - 顺序统计

    顺序统计指的是在一坨并没有排序的数据上找出跟顺序量有关的元素. 典型的顺序统计包括找最小值或最大值算法, 这两个算法可以说没有任何技巧而言, 暴力地遍历一次数据集合就行了, 如找最小值算法的实现 (以 C++ 面向迭代器的程序设计描述, 不考虑集合为空的情形. 以后的例子相同)
template <typename _Iterator>
_Iterator find_min(_Iterator begin, _Iterator end)
{
    _Iterator min = begin;
    for (++begin; begin != end; ++begin) {
        if (*begin < *min) {
            min = begin;
        }
    }
    return min;
}
    将这两件事情揉合在一起, 即从一个集合中同时找到最小值和最大值, 相比于分头寻找, 能够节省不少时间, 原因不仅仅是两次循环合并成一次循环, 运用一些技巧能显著地减少比较的次数.
    在每一次取出剩余元素时, 同时取出两个, 先将这两个比较大小, 然后将较小的元素与当前最小值比较, 而将较大的值与当前最大值比较取出

    +-------+-----------+-----
    | begin | begin + 1 | ...
    +-------+-----------+-----
        |         |
        +--( < )--+
            / \
           /   \
+----------+   +-------------+         +-----+
| less one |   | greater one |--( < )--| max |
+----------+   +-------------+         +-----+
      |
      |                                +-----+
      +-------------------------( < )--| min |
                                       +-----+

    这样每寻访 2 个元素, 需要 3 次元素比较, 加上判断循环是否结束需要 1 次比较, 而分开查找, 则每 1 个元素需要 2 次元素比较, 加上 1 次循环判断结束的比较. 之所以这么计较比较的次数, 因为目前计算机体系结构和分支语句非常不友好, 太多分支 (意味着大量的预测失败) 的程序会因为无法充分利用流水线而显著地降低实际执行效率.
    下面是实现的例子

Permanent Link: ?p=426 Load full text

Post tags:

 Generic Programming
 STL
 C++
 Order Statistic
 Algorithm
 Template

头文件禁区: C++ 中的 ABI

    在上一篇文章中写到了 C 的 ABI (application binary interface) 有关的内容. 而 C++ 这货也采用 header / cpp 分离的方式来组织代码, 并在编译时将头文件直接在 cpp 中插入, 这种暴力方法已经不能简单说是为了兼容 C 的各种编译期行为, 完全就是彻头彻尾地重蹈覆辙, 甚至有过之而无不及.

    首先, C++ 也会遇到 "如果直接用了动态库中修改过签名的函数怎么办" 这个全静态语言的千古难题. 而且比起 C 语言更要命的是, C++ 的类是不能进行前置声明来回避对象内存布局耦合: 前置声明就没有引用成员函数了, 那还怎么面向坑爹的对象呢? 不仅仅对象成员布局有此问题, 连同 C++ 藉由实现多态的虚函数亦面临着同样的窘境. 试想动态库中虚函数表都改得面目全非时, 使用该对象的代码却还用原来的方式访问, 那还不是各种鸡飞狗跳.
    对于如此恶劣环境下仍然想保持 ABI 兼容性的 C++ 程序员来说, 倒也不是完全无路可走. 具体的方案就不在这篇文章中赘述了, 请转到陈硕老师的 C++ 工程实践: 二进制兼容性C++ 工程实践: 避免使用虚函数作为库的接口. 两篇文章都写得非常详细.

    撇开这些跟 C 语言有关的孽缘不谈, C++ 本身也提供了一些机制来帮助程序员养成编码恶习, 比如一些函数实现可以直接写进头文件中, 而无须担忧任何链接错误. 首当这个批评的就是成员函数, 包括静态或非静态, 虚或非虚. inline 函数或者 template 函数实现要写头文件这点可以理解可以忍, 但成员函数来凑什么热闹? 成员函数的不往头文件里面写, 可以避免一些 ABI 耦合, 比如
class Date {
    int month;
    int day;
public:
    int getDay() const;
    int getMonth() const;
};
    这种情况下, 在使用
Date* date /* initialize */;
date->getDay();
不必担心内存布局耦合, 因为作为非虚的成员函数, Date::getDay() const 这样的函数签名正如 getday(Date const*) 一样, 这就回到了上一篇文章最后提到的解决方法了. 但是如果用得不恰当, 比如头脑发热认为 inline 一下能提高效率什么的, 而活生生地写成
class Date {
    int month;
    int day;
public:
    inline int getDay() const
    {
        return day;
    }

    inline int getMonth() const
    {
        return month;
    }
};

Permanent Link: ?p=404 Load full text

Post tags:

 C++
 Template
 ABI
 STL
 inline

STL 悲剧之 for_each

    这篇文章谈一个我使用 STL 中 for_each 的负面心得. 我对这个东西在当前 C++ 语法下约束是否能广泛使用持有怀疑态度, 至于能否替代所有的 for 循环, 我持完全否定观点! 如果您发现文中提及的这档子事情本质上是我不了解 STL 而自寻死路, 请不吝赐教, 在下方回复, 在下感激不尽.

    在 Google 中输入 "for_each" 然后猛击 "I’m feeling lucky", 这时我幸运地跳转到大名鼎鼎的 sgi 的网站里, 页面中有个例子
template<class T> struct print : public unary_function<T, void>
{
    print(ostream& out) : os(out), count(0) {}
    void operator() (T x) { os << x << ' '; ++count; }
    ostream& os;
    int count;
};

int main()
{
    int A[] = {1, 4, 2, 8, 5, 7};
    const int N = sizeof(A) / sizeof(int);

    print<int> P = for_each(A, A + N, print<int>(cout));
    cout << endl << P.count << " objects printed." << endl;
}
    从泛型党的视角看来, 这例子非常不错, 完备而规范地演示了 for_each 的用法. 从此泛型党成了大赢家, 除了 for_each 内部, 外面的代码再也不需要 for 这个关键字了.
    而那些说写 C++ 代码像谈话一样简短, 基本上泛型编程完全不及格的程序员, 在写上面功能的时候一般会这样做
int main()
{
    int A[] = {1, 4, 2, 8, 5, 7};
    const int N = sizeof(A) / sizeof(int);

    int i;
    for (i = 0; i < N; ++i)
        cout << A[i] << ' ';
    cout << endl << i << " objects printed." << endl;
}
    在喷这个改编版的丑陋之前, 不妨先淡定下来, 想想这个例子到底想做什么, 无非是给个数组 (或者其它什么容器) 把每个成员输出 (或者做个什么其它简单的操作), 并记录被操作的元素个数. 然而, 完成这个操作的代码量与它的功能相比, 臃肿得令人发指. 所以, 在用了几次 for_each 之后, 我完全丧失了当初的激情, 变得极其懒惰, 不愿意把简单的操作抽取到函数外部构造成一个对象然后传递给 for_each; 在维护自己以前写的代码时, 也会偷偷把 for_each 改回 for 循环, 因为有的时候我实在不知道伙伴们把我弄出来的那个函数对象类型给维护到哪里去了.
    当然, 我并不认为这是 for_each, 或者 STL, 或者泛型的错. 在我心目中, 泛型思想是风骚的, for_each 的设计是超前的, 问题出在 C++ 语法这个悲剧帝身上, 或者说, 硬要用 C++ 这个传统的面向过程加面向对象语言的语法来包装对象, 来实现类似高阶函数这种函数式编程中的特性, 是悲剧的根源所在. 不仅是 for_each, 连 find_if 等类似的 STL 函数都差不多一样的下场, 与其构造一个精妙绝伦的函数对象类型, 程序员还不如老老实实写个破循环来得实在.
    一个振奋人心的消息是, C++ 新标准即将发布了, 它会支持闭包对象, 那样的话, for_each 以及其它函数就不会像现在这么处境尴尬了.

Permanent Link: ?p=81 Load full text

Post tags:

 C++
 STL
 for_each

STL set 悲剧指导

    这篇文章谈一个我使用 STL 中 set 容器的负面心得. 是的, 我已经被这丫的杀得超神了, 快来人阻止它吧! 如果您发现文中提及的这档子事情本质上是我不了解 STL 而自寻死路, 请不吝赐教, 在下方回复, 在下感激不尽.

    最坏对数时间插入, 删除, 查询, 迭代遍历, 这些听起来都无比诱人, 它们由 STL 中的 set 容器鼎力支持. 然而, set 的只读制度是非常龌龊的, 简而言之, 只要你敢往这个坑里面放, 你就得接受它们以后再也无法修改的命运. 比如下面这段例子
#include <set>
#include <string>

using std::set;
using std::string;

struct student {
    string name;
    int grade;

    student(string const& name_, int grade_)
        : name(name_)
        , grade(grade_)
    {}

    bool operator<(student const& rhs) const
    {
        return name < rhs.name;
    }

    bool operator==(student const& rhs) const
    {
        return name == rhs.name;
    }
};

int main(void)
{
    set<student> students;
    students.insert(student("Li Lei", 5));
    students.insert(student("Han Meimei", 5));
    students.insert(student("Jim Green", 5));

    for (set<student>::iterator i = students.begin();
         students.end() != i;
         ++i)
    {
        ++(i->grade);
    }
    return 0;
}
    student 类的 key 是 name, 跟 grade 没有关系, 原则上来说, 修改后者并不会破坏 set 的存储结构. 然而, 编译器一棒子打死, 不许改, 除非剩下的成员全部 mutable 修饰.
    只读制度悲剧的根源在于, set 所谓的 key 撑死只是个假象, value_type 这玩意儿就是 key_type 本身.
    伪 key 导致的不仅仅是不能改, 重要的是还不能查! 看看 set::find 函数的参数, 要的又是阴魂不散的 key_type. 这意味着什么? 意味着 Han MM 同学报出她名字的时候, 还查不出她几年级, 而必须要利用她的名字, 伪造一个充气娃娃放进去才能找到! 看到这里我就败了, 这明摆着就是不让我用 set, 让我转投 map 么? 一个也许可行的方案是
#include <map>
#include <string>

using std::map;
using std::string;

struct student_periphery {
    int grade;
};

map<string, student_periphery> students;
这样建模的话也是够狗血的, 如果哪个函数拿着一份 student_periphery 问怎么查出学生姓名, 那就更悲剧了.

Permanent Link: ?p=79 Load full text

Post tags:

 set
 C++
 STL


. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site