TimothyQiu's Blog

keep it simple stupid

那么 C 语言也可能有类了哟

4 Comments

今天看到 C 语言委员会的提案 N1875,顿时有种「卧槽」的感觉,因为它的标题是:Adding classes to C。这要是通过了,那可真就变成名副其实的 C with Classes 了呀~

纵观提案全文,主要从 C++ 中吸收「类」的概念和用法,但是没有虚函数之类的东西。如果算上单独的「访问限制符」、「单一继承」提案,一个 C 语言的类,很可能类似于:

class Car: public Vehicle
{
public:  // 这是单独的另一个提案引入的
    // 构造函数
    initCar() {
        initVehicle();  // 需要显式调用父类构造函数
        countWheels_ = 4;
    }

    // 构造函数
    initCar(int speedMax, int countWheels) {
        initVehicle(speedMax);  // 需要显式调用父类构造函数
        countWheels_ = countWheels;
    }

    // 析构函数
    deleteCar() {
        deleteVehicle();  // 需要显式调用父类析构函数
    }

    int getWheelsCount() const {    // 也有 const 哟
        return this->countWheels_;  // 也有 this 指针
    }

private:
    int countWheels_;
};

使用时,构造写法有点奇怪,也没说构造失败会怎样,析构也需要手动显式调用:

Car car;  // 相当于 initCar()
Car tank.initCar(80, 16);

tank.deleteCar();  // 析构函数需要显式调用
car.deleteCar();

从目前的样子看,这样的「类」更类似于语法糖。当然,这只是个提案而已,会不会最终被批准,还得拭目以待。

以上。

mosh

No Comments

SSH 用起来有一个不方便的地方,就是断线就要重连,不用个 screen / tmux 啥的浑身不舒服。这种现象在台式机上还好,因为网络稳定,但到了笔记本 / 手机之类的设备上,从休眠中恢复、网络断开啥的并不鲜见。mosh 的全称是 mobile shell,顾名思义,正是专为解决这些「移动」客户端的烦恼而设计的 (b ̄(I) ̄)b

安装非常简单,各大平台都有二进制包可以直接使用,比如:

pacman -S mosh     # Arch Linux
brew install mosh  # Mac OS X

官网上列有一大堆其它平台的安装方法和源码编译指南:https://mosh.mit.edu/#getting

安装好的 mosh 分三部分:

其中,我们直接使用的是 mosh。用法和 ssh 一样,比如连接服务器:

mosh user@host

mosh 会先通过 SSH 连接到服务器,然后启动服务器上的 mosh-server,启动成功后 SSH 被断开,一切就交给本地的 mosh-client 来和远程的 mosh-server 用 UDP 在 60000-61000 端口通信了。

如果要透过 moshssh 传其它参数,那么就需要麻烦一些了,比如:

# 指定 SSH 端口
# mosh 自己的 -p 参数用来是指定 mosh-server 和 mosh-client 通信的 UDP 端口的
mosh --ssh="ssh -p 1024" user@host

使用过程中,如果网络延迟比较大,你会发现 mosh 不像 SSH 一样需要「盲打」,而是直接打出带下划线的字符。这就是 mosh 提供的「预测」模块的作用:在延迟比较大的时候,根据本地输入提前输出预期的结果,等收到远程服务器的实际结果后替换之。

网络意外断开时,窗口顶部会提示断开的时间和可用的转义序列,等网络恢复、顶部的提示消失,一切就会跟啥事都没发生过一样……

CoolShell 解题记

2 Comments

吃完饭在微博上看到 CoolShell 上发了一个解谜游戏,类似于很久以前很流行的那种黑客游戏。咱自然是要试试的啦~由于中午在父母家吃饭,电脑上没有任何 IDE 之类的,于是只能用在线 IDE 了。

严重剧透请注意!

阅读剩余部分...

用 STL 寻找前 K 个最大的数

1 Comment

前几天找资料,顺手看到了这篇博文,讲了博主如何优化自己以前的算法的过程。于是立马想起了 GoingNative 2013 上的演讲 C++ Seasoning 以及前不久看到的这篇 From goto to std::transform。于是不禁想,「寻找前 K 大数」这样的任务,能不能直接用 C++ 标准库来完成?如果能的话,性能又如何呢?于是我重新登录了那个以前做了两道题就尘封多年的 OJ 帐号……

凭着最直观最 naïve 想法,第一个版本我用了 std::sort 来代替手工排序。不出所料,这样的做法跑了 562 ms,要排到 700 名开外的样子。

#include <stdio.h>
#include <algorithm>
#include <functional>
#include <vector>

int main()
{
    int numVillagers;
    int topCount;

    while (scanf("%d %d\n", &numVillagers, &topCount) == 2) {
        if (numVillagers == 0 && topCount == 0) {
            break;
        }

        std::vector<int> wealth(numVillagers);
        for (int i = 0; i < numVillagers; i++) {
            scanf("%d", &(wealth[i]));
        }
        std::sort(wealth.begin(), wealth.end(), std::greater<int>());

        if (topCount > numVillagers) {
            topCount = numVillagers;
        }

        for (int i = 0; i < topCount - 1; i++) {
            printf("%d ", wealth[i]);
        }
        printf("%d\n", wealth[topCount - 1]);
    }
}

于是优化:考虑到每次新建 std::vector 的开销,把 wealth 拎出来放到循环外,reserve() 题目中的最大值,每次在循环里重新 resize() 后,时间顿时缩短到了 296 ms,可以排到 180+ 的样子。

std::vector<int> wealth;
wealth.reserve(100000);

而在前面说过的演讲中,我还听到了一个之前从未留意的函数 std::nth_element。其作用是确保调用后第 N 个元素是范围内第 N 大的元素。调用后,[begin, N) 内的任意元素都小于 (N, end) 内的任意元素。

std::nth_element(wealth.begin(), wealth.begin() + topCount, wealth.end(), std::greater<int>());
std::sort(wealth.begin(), wealth.begin() + topCount, std::greater<int>());

尝试修改成以上的略显罗嗦的代码后,程序运行时间缩短到了 171 ms,可以排到 70+ 的样子。时间上和博文中给出的最小堆实现相同,但是内存占用要比它大很多。

既然上面是先用 std::nth_element 大致排序了一下,而后再用 std::sort 排序前半部分,那么,STL 里是否存在一次性只排 [begin, N] 范围内的数,而无视 (N, end) 内的顺序的函数呢?答案是存在,可以直接使用 std::partial_sort 解决。

#include <stdio.h>
#include <algorithm>
#include <functional>
#include <vector>

int main()
{
    int numVillagers;
    int topCount;

    std::vector<int> wealth;
    wealth.reserve(100000);

    while (scanf("%d %d\n", &numVillagers, &topCount) == 2) {
        if (numVillagers == 0 && topCount == 0) {
            break;
        }

        wealth.resize(numVillagers);
        for (int i = 0; i < numVillagers; i++) {
            scanf("%d", &(wealth[i]));
        }

        if (topCount > numVillagers) {
            topCount = numVillagers;
        }

        std::partial_sort(wealth.begin(), wealth.begin() + topCount, wealth.end(), std::greater<int>());

        for (int i = 0; i < topCount - 1; i++) {
            printf("%d ", wealth[i]);
        }
        printf("%d\n", wealth[topCount - 1]);
    }
}

此时的程序执行时间 156 ms,排名第 25 位。而截止到此时,我个人其实什么都没有干,实际任务都交给了 STL。

如同各种 MyStringMyVector 一样,一般情况下自己去实现这些通用算法在 STL 面前几乎没有任何优势。尤其是 C++11 带来 lambda 表达式以来,大大方便了 <algorithm> 中各种算法的使用,我觉得不去用 STL 的理由越发稀少了。

以上。

定位工具 Git Bisect

No Comments

经过 @Neuron Teckid 童鞋的提点,发现了 git bisect 这个非常有意思的工具。

话说,我第一眼把 bisect 看成了 biscuit,以为 Git 也开始学 Android 卖萌了呢……结果一查字典,这个词是「等分」的意思……

假设某天你发现你编译出的程序里有个 Bug,该如何找出它是从哪个版本开始引入的呢?在版本历史中找出有 Bug 和无 Bug 两个版本,用简单的二分查找法就可以定位啦。git bisect 正是用来帮助你完成这种二分查找法的自动化的。

基本用法

git bisect start         # 初始化二分查找
git bisect bad           # 标记当前版本存在问题
git bisect good 38a63d9  # 标记 38a63d9 版本没有问题

至少标记了一个没有问题的版本(Good)和一个有问题的版本(Bad)后,Git 就会开始二分查找的过程,不断检出 Good 和 Bad 中间的版本等待你检查后作出标记。每次检出后 Git 都会提示你还剩多少文件、大致还剩余多少次比较:

Bisecting: 441 revisions left to test after this (roughly 9 steps)

比如上面这三步后,Git 检出了中间版本 b17ff03。你编译运行后发现这个版本没有问题,就可以用 git bisect good 将当前版本标记为没有问题。此时 Git 就会再把 b17ff03 和最初版本之间的区域二分,检出中间版本等待你的检查。

等一切完成以后,就可以用 git bisect reset 返回开始前的版本。

自动查找

手动标记 Good / Bad 可以帮助人类从挑选下一个合适的版本的工作中解放出来。(似乎可以理解为 C++ 从 forstd::for_each 的抽象过程。)但这还是远远不够的,因为测试某个版本是否正常的重任依旧需要人类的介入。

所幸你可以指定一个检测用的程序,让 git bisect 自动完成整个定位的过程。这个程序必须在当前版本没有问题时返回 0,而 1 到 127 之间的值则表示有问题(特殊值 125 表示没法确定)。

git bisect run <cmd>...

例如,让你从一个陌生的代码库里找到能够编译和不能编译的临界提交,我们可以通过传入 make 来实现自动化查找:

git bisect start HEAD 38a63d9  # 简单写法:初始化二分查找,HEAD 有问题,而 38a63d9 没有
git bisect run make            # 利用 make 来检测某个版本是否能够通过编译

而后,Git 就会自己用二分查找法不断检出中间版本,每次检出后都会运行 make,根据 make 的返回值来确定当前版本是否存在问题(是否能够通过编译)。

以上。