C＋＋/D/Python性能比较续

周末抽空做了点小测试，根据http://blog.vckbase.com/jzhang/archive/2006/03/28/18807.html中m网友修改的算法，python版本中读取所有行以后就做一个排序，再去除重复项。这个算法在我的机器上执行时间是1735ms左右，属于python版本中最快的一个。

D版本暂还没想到有更优化的做法，D在处理以char[]作key的关联数组时，判断方法是先判断hash，如果hash相等，则继续做字符串判断。它执行时间是1120ms左右。

以D版本为基础，自己写了一个C＋＋的Email类：

class Email
{
private:
        string mail;
        size_t hash;
        friend bool operator < (const Email& lhs, const Email& rhs);
public:
        Email (const char* mail_)
                : mail(mail_), hash(my_hash(mail_))
        {
        }
};

bool operator < (const Email& lhs, const Email& rhs)
{
        if (lhs.hash == rhs.hash)
                return lhs.mail < rhs.mail;
        return lhs.hash < rhs.hash;
}

把它插入set并判断是否有重复。

这个程序由于string的大量拷贝，以及大量内存分配，执行时间相当长，在我的机器上是5s左右。D和python版本由于对象拷贝成本较低，加上都有内存分配策略，自然有一些优势。

退而求其次，既然hash冲突的几率较低，试试只保存hash：

class Email
{
private:
        size_t hash;
        friend bool operator < (const Email& lhs, const Email& rhs);
public:
        Email (const char* mail_)
                : hash(my_hash(mail_))
        {
        }
};

bool operator < (const Email& lhs, const Email& rhs)
{
        return lhs.hash < rhs.hash;
}

这次测试就比较快了，耗时仅1020ms左右，比D版本还要快，当然它不是完善的版本。

考虑到构造成本，于是改为只用一个set<int>来保存hash值再测试，这次耗时是930ms。

实际上可以做一个改进的C＋＋版本，一次性读入文件的全部内容到一个大缓冲区，把所有的\n字符修改为\0，用一个动态数组保存缓冲区的所有字符串指针，hash值也须计算并保存到数组。再用D的索引方式，先hash比较，再字符串比较，效率应该也不低。

实现了一个：

#include <iostream>
#include <string>
#include <set>
#include <fstream>
#include <iterator>
#include <sys/time.h>
using namespace std;

size_t my_hash (const char* str)
{
        size_t ret = 0;
        while (*str)
                ret = 11 * ret + *str++;
        return ret;
}

class Email
{
private:
        size_t hash;
        const char* mail;
        friend bool operator < (const Email& lhs, const Email& rhs);
public:
        Email (const char* mail_)
                : hash(my_hash(mail_)), mail(mail_)
        {
        }
};

bool operator < (const Email& lhs, const Email& rhs)
{
        if (lhs.hash == rhs.hash)
                return strcmp(lhs.mail, rhs.mail) < 0;
        return lhs.hash < rhs.hash;
}

int main(int argc, char** argv)
{
        if (argc < 3)
        {
                cout << "Wrong arguments" << endl;
                return 1;
        }

        FILE* fin = fopen(argv[1], "r");
        if (!fin)
        {
                cout << "Invalid input file" << endl;
                return 2;
        }
        FILE* fout = fopen(argv[2], "w");
        if (!fout)
        {
                fclose(fin);
                cout << "Invalid output file" << endl;
                return 3;
        }

        timeval start, end;

        const int BUF_SIZE = 20 * 1024 * 1024;
        char* buffer = new char[BUF_SIZE];
        memset(buffer, 0, BUF_SIZE);

        gettimeofday(&start, 0);
        set<Email> emails;

        size_t read = fread (buffer, BUF_SIZE, 1, fin);
        char* begin = buffer;
        char* current = buffer;

        while (*current != '\0')
        {
                if (*current == '\n')
                {
                        *current = '\0';
                        if (emails.insert(begin).second){
                                fputs(begin, fout);
                                fwrite("\n", 1, 1, fout);
                        }
                        begin = current + 1;
                }
                ++ current;
        }

        fclose(fout);
        fclose(fin);

        gettimeofday(&end, 0);

        printf("Time used: %d ms\n", ((end.tv_sec - start.tv_sec) * 1000 + (end.tv_usec - start.tv_usec) / 1000));

        delete[] buffer;
        return 0;
}

memset不是必须的，不过我不知道如何获取读入的大小。fread读取后，如果读到EOF，则返回值为0。所以我这里用memset先初始化内存，但不把它计入耗时。new操作也没计入，因为其它语言比如python、D在启动时都由运行时做了类似工作。

这个程序在我的机器上耗时为1350ms左右。我想可慢在set上，对象拷贝？内存分配？

做了几个优化版本，没多大提高。

重新测试了下：
A、python(m网友版本）：
lijie t # python test.py
1689.0411377
lijie t # python test.py
1711.40599251
lijie t # python test.py
1699.63312149
lijie t # python test.py
1712.00013161
lijie t # python test.py
1713.8838768

B、D版本：
lijie t # ./testd email.txt email-new.txt
1091
lijie t # ./testd email.txt email-new.txt
1070
lijie t # ./testd email.txt email-new.txt
1062
lijie t # ./testd email.txt email-new.txt
1062
lijie t # ./testd email.txt email-new.txt
1096

C、C＋＋只比较hash，set<Email>版本：
lijie t # ./test3 email.txt email-new.txt
Time used: 981 ms
lijie t # ./test3 email.txt email-new.txt
Time used: 1000 ms
lijie t # ./test3 email.txt email-new.txt
Time used: 980 ms
lijie t # ./test3 email.txt email-new.txt
Time used: 986 ms
lijie t # ./test3 email.txt email-new.txt
Time used: 987 ms

D、C＋＋只比较hash，set<int>版本：
lijie t # ./test4 email.txt email-new.txt
Time used: 951 ms
lijie t # ./test4 email.txt email-new.txt
Time used: 953 ms
lijie t # ./test4 email.txt email-new.txt
Time used: 947 ms
lijie t # ./test4 email.txt email-new.txt
Time used: 950 ms
lijie t # ./test4 email.txt email-new.txt
Time used: 962 ms

E、C＋＋大缓冲区，比较hash和字符串，set<Email>版本：
lijie t # ./test5 email.txt email-new.txt
Time used: 1375 ms
lijie t # ./test5 email.txt email-new.txt
Time used: 1359 ms
lijie t # ./test5 email.txt email-new.txt
Time used: 1369 ms
lijie t # ./test5 email.txt email-new.txt
Time used: 1378 ms
lijie t # ./test5 email.txt email-new.txt
Time used: 1396 ms

F、C＋＋大缓冲区，比较字符串版本：
lijie t # ./test6 email.txt email-new.txt
Time used: 1168 ms
lijie t # ./test6 email.txt email-new.txt
Time used: 1169 ms
lijie t # ./test6 email.txt email-new.txt
Time used: 1171 ms
lijie t # ./test6 email.txt email-new.txt
Time used: 1179 ms
lijie t # ./test6 email.txt email-new.txt
Time used: 1169 ms

从C、E和F来看，对象拷贝成本是比较高的，E版本仅仅比C版本多了个const char*成员变量，hash值比较散，很少会真的执行到strcmp。保持E版本对象结构不变，把operator <里面的实现改为C版本，测试结果如下：
lijie t # ./test5 email.txt email-new.txt
Time used: 1355 ms
lijie t # ./test5 email.txt email-new.txt
Time used: 1360 ms
lijie t # ./test5 email.txt email-new.txt
Time used: 1348 ms
lijie t # ./test5 email.txt email-new.txt
Time used: 1353 ms
lijie t # ./test5 email.txt email-new.txt
Time used: 1379 ms

效率只提高了一点点，这个版本仅仅比C版本多了个成员变量拷贝，竟然慢了这么多。说明Email对象的2个成员变量拷贝成本的确很高。

F版本相比之下反而效率很不错，主要原因是email数据不够复杂，仅通过前几位就可以比较出结果。如果每行数据比较长，而且很多行要到后几个字符才能比较出来，肯定就不那么快了。

hash值的计算虽然执行了一系列乘法，不过还是相当迅速。

D语言版本执行了hash值和字符串比较，是比较完善的，效率很不错。C＋＋相应版本看来要提高set的效率才能达到。

jzhang的第一个python版本在我的机器上执行如下：
lijie t # python test2.py
3122.9569912 ms
lijie t # python test2.py
3209.42997932 ms
lijie t # python test2.py
3141.47305489 ms
lijie t # python test2.py
3129.57286835 ms
lijie t # python test2.py
3196.03514671 ms

我做了点修改，执行速度提高了一些：

#remove duplicated email address from file
import datetime
from time import time
if __name__ == "__main__":
start = time()
hashtable = {}
f = file("email.txt","r")
f2 = file("email_new.txt","w")
for line in f.xreadlines():
  if not hashtable.has_key(line):
   hashtable[line] = 1
   f2.write(line)
f.close()
f2.close()
print (time() - start) * 1000, "ms"

在我的机器上执行结果如下：
lijie t # python test1.py
2239.22801018 ms
lijie t # python test1.py
2301.00703239 ms
lijie t # python test1.py
2282.06086159 ms
lijie t # python test1.py
2296.57006264 ms
lijie t # python test1.py
2281.25810623 ms

不过还是没有m网友的效率高。

在F版本的基础上，借鉴m网友的做法，实现一个G版本：

G、排序并去除重复元素，比较hash和字符串版本：

#include <iostream>
#include <string>
#include <fstream>
#include <iterator>
#include <sys/time.h>
#include <vector>
using namespace std;

size_t my_hash (const char* str)
{
        size_t ret = 0;
        while (*str)
                ret = 11 * ret + *str++;
        return ret;
}

class Email
{
private:
        size_t hash;
        const char* mail;
        friend bool operator < (const Email& lhs, const Email& rhs);
public:
        Email (const char* mail_)
                : hash(my_hash(mail_)), mail(mail_)
        {
        }

        bool operator == (const Email& rhs)
        {
                if (hash == rhs.hash)
                        return strcmp(mail, rhs.mail) == 0;
                return false;
        }

        const char* getEmail()const
        {
                return mail;
        }
};

bool operator < (const Email& lhs, const Email& rhs)
{
        if (lhs.hash == rhs.hash)
                return strcmp(lhs.mail, rhs.mail) < 0;
        return lhs.hash < rhs.hash;
}

int main(int argc, char** argv)
{
        if (argc < 3)
        {
                cout << "Wrong arguments" << endl;
                return 1;
        }

        FILE* fin = fopen(argv[1], "r");
        if (!fin)
        {
                cout << "Invalid input file" << endl;
                return 2;
        }
        FILE* fout = fopen(argv[2], "w");
        if (!fout)
        {
                fclose(fin);
                cout << "Invalid output file" << endl;
                return 3;
        }

        timeval start, end;

        const int BUF_SIZE = 20 * 1024 * 1024;
        char* buffer = new char[BUF_SIZE];
        memset(buffer, 0, BUF_SIZE);

        gettimeofday(&start, 0);
        vector<Email> emails;

        size_t read = fread (buffer, BUF_SIZE, 1, fin);
        char* begin = buffer;
        char* current = buffer;

        while (*current != '\0')
        {
                if (*current == '\n')
                {
                        *current = '\0';
                        emails.push_back(begin);
                        begin = current + 1;
                }
                ++ current;
        }
        fclose(fin);
        sort(emails.begin(), emails.end());
        emails.erase (unique( emails.begin(), emails.end() ), emails.end());

        for (vector<Email>::const_iterator iter = emails.begin();
             iter != emails.end();
             iter ++)
        {
                fputs((*iter).getEmail(), fout);
                fwrite("\n", 1, 1, fout);
        }

        fclose(fout);

        gettimeofday(&end, 0);

        printf("Time used: %d ms\n", ((end.tv_sec - start.tv_sec) * 1000 + (end.tv_usec - start.tv_usec) / 1000));

        delete[] buffer;

        return 0;
}

在我的机器上执行如下：
lijie t # ./test7 email.txt email-new.txt
Time used: 676 ms
lijie t # ./test7 email.txt email-new.txt
Time used: 675 ms
lijie t # ./test7 email.txt email-new.txt
Time used: 671 ms
lijie t # ./test7 email.txt email-new.txt
Time used: 669 ms
lijie t # ./test7 email.txt email-new.txt
Time used: 673 ms

比F版本快了2倍，也快过了其它所有版本。不过由于数据是vector保存的，在数据大量重复的情况下，性能可能会有较大的降低。

把operator<和operator==的实现改为strcmp比较，执行结果如下：
lijie t # ./test8 email.txt email-new.txt
Time used: 1275 ms
lijie t # ./test8 email.txt email-new.txt
Time used: 1267 ms
lijie t # ./test8 email.txt email-new.txt
Time used: 1297 ms
lijie t # ./test8 email.txt email-new.txt
Time used: 1296 ms
lijie t # ./test8 email.txt email-new.txt
Time used: 1271 ms

修改了下，增加了计时，修正了fread使用错误。

#include <iostream>
#include <string>
#include <fstream>
#include <iterator>
#include <vector>
using namespace std;

#ifdef _WIN32
# include <windows.h>
#else // _WIN32
# include <sys/time.h>
#endif // _WIN32

size_t my_hash (const char* str)
{
        size_t ret = 0;
        while (*str)
                ret = 11 * ret + *str++;
        return ret;
}

class Email
{
private:
        size_t hash;
        const char* mail;
        friend bool operator < (const Email& lhs, const Email& rhs);
public:
        Email (const char* mail_)
                : hash(my_hash(mail_)), mail(mail_)
        {
        }

        bool operator == (const Email& rhs)
        {
                if (hash == rhs.hash)
                        return strcmp(mail, rhs.mail) == 0;
                return false;
        }

        const char* getEmail()const
        {
                return mail;
        }
};

bool operator < (const Email& lhs, const Email& rhs)
{
        if (lhs.hash == rhs.hash)
                return strcmp(lhs.mail, rhs.mail) < 0;
        return lhs.hash < rhs.hash;
}

#ifndef _WIN32
class Timer
{
        timeval begin, end;
public:
        void start () {gettimeofday(&begin, 0);}
        void stop () {gettimeofday(&end, 0);}
        size_t milliseconds () const {
                return (end.tv_sec - begin.tv_sec) * 1000 + (end.tv_usec - begin.tv_usec) / 1000;
        }
};
#else // _WIN32
class Timer
{
        DWORD begin, end;
public:
        void start () {begin = GetTickCount();}
        void stop () {end = GetTickCount();}
        size_t milliseconds () const {
                return end - begin;
        }
};
#endif // _WIN32

int main(int argc, char** argv)
{
        if (argc < 3)
        {
                cout << "Wrong arguments" << endl;
                return 1;
        }

        for (int i=0; i<10; ++i) {

       FILE* fin = fopen(argv[1], "r");
        if (!fin)
        {
                cout << "Invalid input file" << endl;
                return 2;
        }
        FILE* fout = fopen(argv[2], "w");
        if (!fout)
        {
                fclose(fin);
                cout << "Invalid output file" << endl;
                return 3;
        }

        Timer total, part;
        total.start();
        part.start();

        const int BUF_SIZE = 20 * 1024 * 1024;

        char* buffer = new char[BUF_SIZE];
        if (!buffer){
                // cout << "Alloc buffer failed" << endl;
                return 4;
        }

        part.stop();
        // cout << "Alloc buffer, " << part.milliseconds() << " ms used." << endl;
        part.start();

        size_t read = fread (buffer, 1, BUF_SIZE, fin);
        fclose(fin);
        buffer[read] = '\0';
        part.stop();
        // cout << "Read file, " << part.milliseconds() << " ms used." << endl;
        part.start();

        vector<Email> emails;

        char* begin = buffer;
        char* current = buffer;

        while (*current != '\0')
        {
                if (*current == '\n')
                {
                        *current = '\0';
                        emails.push_back(begin);
                        begin = current + 1;
                }
                ++ current;
        }

        part.stop();
        // cout << "Put emails into vector, " << part.milliseconds() << " ms used." << endl;
        part.start();

        sort(emails.begin(), emails.end());
        part.stop();
        // cout << "Sort emails, " << part.milliseconds() << " ms used." << endl;
        part.start();

        emails.erase (unique( emails.begin(), emails.end() ), emails.end());
        part.stop();
        // cout << "Unique emails, " << part.milliseconds() << " ms used." << endl;
        part.start();

        for (vector<Email>::const_iterator iter = emails.begin();
             iter != emails.end();
             iter ++)
        {
                fputs((*iter).getEmail(), fout);
                fwrite("\n", 1, 1, fout);
        }

        fclose(fout);

        part.stop();
        // cout << "Write emails into new file, " << part.milliseconds() << " ms used." << endl;

        total.stop();

        cout << "Total used: " << total.milliseconds() << " ms." << endl;

        delete[] buffer;
        }

        return 0;
}

使用“-O3 -fomit-frame-pointer -funroll-loops -mtune=pentium4”选项编译，耗时从680ms减少到620ms

优化文件读写版：

#include <iostream>
#include <string>
#include <fstream>
#include <iterator>
#include <vector>
using namespace std;

// config
#define USE_CACHE
//#define PROFILE
// end config

#ifdef _WIN32
# include <windows.h>
#else // _WIN32
# include <sys/time.h>
#endif // _WIN32

#ifndef _WIN32
class Timer
{
    timeval begin, end;
public:
    void start () {gettimeofday(&begin, 0);}
    void stop () {gettimeofday(&end, 0);}
    size_t milliseconds () const {
        return (end.tv_sec - begin.tv_sec) * 1000 + (end.tv_usec - begin.tv_usec) / 1000;
    }
};
#else // _WIN32
class Timer
{
    DWORD begin, end;
public:
    void start () {begin = GetTickCount();}
    void stop () {end = GetTickCount();}
    size_t milliseconds () const {
        return end - begin;
    }
};
#endif // _WIN32

#ifdef PROFILE
# define PROFILE_OUTPUT(timer,info) \
    timer.stop(); \
    cout << info << ": " << timer.milliseconds() << " ms used." << endl; \
    timer.start()
#else // PROFILE
# define PROFILE_OUTPUT(timer,info)
#endif // PROFILE

size_t my_hash (const char* str)
{
    size_t ret = 0;
    while (*str)
            ret = 11 * ret + *str++;
    return ret;
}

class Email
{
private:
    size_t hash;
    const char* mail;
    friend bool operator < (const Email& lhs, const Email& rhs);
public:
    Email (const char* mail_)
        : hash(my_hash(mail_)), mail(mail_)
    {
    }

    bool operator == (const Email& rhs)
    {
        if (hash == rhs.hash)
            return strcmp(mail, rhs.mail) == 0;
        return false;
    }

    const char* getEmail() const
    {
        return mail;
    }

    size_t getLength() const
    {
        return strlen(mail);
    }
};

bool operator < (const Email& lhs, const Email& rhs)
{
    if (lhs.hash == rhs.hash)
        return strcmp(lhs.mail, rhs.mail) < 0;
    return lhs.hash < rhs.hash;
}

#ifdef USE_CACHE
class OfstreamBuffer
{
    ofstream& ofs;
    size_t buf_size;
    size_t offset;
    char* buffer;

public:
    OfstreamBuffer (ofstream& ofs_, size_t buf_size_)
        : ofs(ofs_), buf_size(buf_size_), offset(0)
    {
        buffer = new char[buf_size_];
    }

    ~OfstreamBuffer ()
    {
        flush();
        delete[] buffer;
    }

    void write (const char* ptr, size_t size)
    {
        while (size > 0)
        {
            size_t copy_size = buf_size - offset;
            if (copy_size > size)
                copy_size = size;
            memcpy (buffer + offset, ptr, copy_size);
            offset += copy_size;
            ptr += copy_size;
            size -= copy_size;

            if (offset == buf_size)
                flush ();
        }
    }

    void flush ()
    {
        if (offset > 0)
        {
            ofs.write(buffer, offset);
            offset = 0;
        }
        ofs.flush();
    }
};
#else// USE_CACHE
class OfstreamBuffer
{
    ofstream& ofs;

public:
    OfstreamBuffer (ofstream& ofs_, size_t buf_size_)
        : ofs(ofs_)
    {
    }

    void write (const char* ptr, size_t size)
    {
        ofs.write(ptr, size);
    }

    void flush ()
    {
        ofs.flush();
    }
};
#endif // USE_CACHE

int main(int argc, char** argv)
{
    if (argc < 3)
    {
        cout << "Wrong arguments" << endl;
        return 1;
    }

    for (int i=0; i<1; ++i) {

        ifstream ifs(argv[1], ios::binary);
        if (!ifs)
        {
            cout << "Invalid input file" << endl;
            return 2;
        }

        ofstream ofs(argv[2], ios::binary);
        if (!ofs)
        {
            cout << "Invalid output file" << endl;
            return 3;
        }

        Timer total, part;
        total.start();
        part.start();

        ifs.seekg(0, ios_base::end);
        size_t file_size = (size_t)ifs.tellg() + 1;
        cout << "file size: " << file_size << endl;
        ifs.seekg(0, ios_base::beg);

        char* buffer = new char[file_size];
        if (!buffer){
            cout << "Alloc buffer failed" << endl;
            return 4;
        }

        PROFILE_OUTPUT(part, "Alloc buffer");

        ifs.read(buffer, file_size);
        buffer[file_size] = '\0';

        PROFILE_OUTPUT(part, "Read file");

        vector<Email> emails;
        emails.reserve(1000000);

        char* begin = buffer;
        char* current = buffer;

        while (*current != '\0')
        {
            if (*current == '\n')
            {
                *current = '\0';
                emails.push_back(begin);
                begin = current + 1;
            }
            ++ current;
        }

        PROFILE_OUTPUT(part, "Put emails into vector");

        sort(emails.begin(), emails.end());

        PROFILE_OUTPUT(part, "Sort emails");

        emails.erase (unique( emails.begin(), emails.end() ), emails.end());

        PROFILE_OUTPUT(part, "Unique emails");

        OfstreamBuffer ofsBuffer (ofs, 4 * 1024);

        for (vector<Email>::const_iterator iter = emails.begin();
             iter != emails.end();
             iter ++ )
        {
            ofsBuffer.write(iter->getEmail(), iter->getLength());
            ofsBuffer.write("\n", 1);
        }
        ofsBuffer.flush();

        PROFILE_OUTPUT(part, "Write emails into new file");

        total.stop();
        cout << "Total used: " << total.milliseconds() << " ms." << endl;

        delete[] buffer;
    }

    return 0;
}

这个版本在windows上用dev-cpp所带的gcc 3.4.2来编译，最好成绩是609ms。在cygwin里可以达到650ms。

posted on 2006-04-03 11:00 qiezi 阅读(1611) 评论(27) 编辑收藏引用所属分类: C＋＋、杂谈

# re: C＋＋/D/Python性能比较续 2006-04-03 20:24 dwbclz

使用您的最优程序并未有600+的效率，大约在1400+。

如果不sort，可以到900-，不过那样不能保证结果正确。

fread函数用法有误，第二个参数应该和第三个交换，
然后就可以得到返回的数值了。
您的buffer不能那么处理，因为去除“\r\n”的时候，
buffer经过了重新排列，实际的Buffer结尾比“\0”所在位置
要靠前。您的疏忽使结果多了一些。
应加入buffer[read]=0;

多多讨论，呵呵，我觉得这个程序还是值得研究的。
有一些通用的优化思想在里面。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-03 21:02 芋头

注意编译时要打开优化选项，不打开选项自然会差很多，不过这个成绩是在我的机器上的，所有测试都是同一台机器上，都打开了优化选项-O2。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-03 21:15 芋头

多谢。buffer[read]=0这个，因为开始没得到read，所以直接把全部内容给memset了。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-03 21:24 芋头

我刚在cygwin里测试了一下，这个环境里差不多是1400＋。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-03 21:34 芋头

你所说的“结果多了一些”，我这里并没有出现，我的每个测试都是和python版本作了比较的。这里处理的方式就是把所有\n替换成\0，相当于分割字符串了，没有考虑\r，实际上如果每行都多一个\r的话，并不会影响到结果。

打算在cygwin里测试一下python的效率，网络不太好没装上。白天的测试是在gentoo里面进行的，不能保证所有机器都有这个速度，但它和python的耗时对比是我自己的机器上得出的。另外，我的机器编译选项是打开SSE等优化选项的，编译时也要O2。

等晚点网络好了再测试一下cygwin 回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-04 07:26 dwbclz

“结果多了一些”是由于C库的不同。
如果看看C库函数的实现，自然会明白。
C函数把“\r\n”替换成“\n”，所以Buffer会
缩并。如果C库在缩并以后在末尾添‘\0’，那么你的
结果毫无问题。否则，就会有缩并前的数据来骚扰你。
多了\r会影响结果。因为“j@j.cn\r”!=“j@j.cn”

cygwin的环境应该是更接近于Windows的。您的这个结果
跟我的一样。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-04 07:28 芋头

jzhang的python版本在我的cygwin里执行时间是5秒多点，超过我这个程序的4倍。（接近4倍，没超过）

今天早晨在cygwin测试的执行时间比昨天高，可能昨天受到某些后台程序的影响。

李杰@lijie ~
$ python email.py
2006-04-04 07:24:00.968750
2006-04-04 07:24:06.113750

李杰@lijie ~
$ python email.py
2006-04-04 07:24:08.454125
2006-04-04 07:24:13.634125

李杰@lijie ~
$ python email.py
2006-04-04 07:24:15.921875
2006-04-04 07:24:21.203875

李杰@lijie ~
$ python email.py
2006-04-04 07:25:12.718750
2006-04-04 07:25:17.904750

李杰@lijie ~
$ python email.py
2006-04-04 07:25:20.515625
2006-04-04 07:25:25.693625

－－－－－－－－－－－－－－－－－－－－
李杰@lijie ~
$ ./test email.txt email-new.txt
Time used: 1262 ms

李杰@lijie ~
$ ./test email.txt email-new.txt
Time used: 1370 ms

李杰@lijie ~
$ ./test email.txt email-new.txt
Time used: 1222 ms

李杰@lijie ~
$ ./test email.txt email-new.txt
Time used: 1490 ms

李杰@lijie ~
$ ./test email.txt email-new.txt
Time used: 1235 ms

李杰@lijie ~
$ ./test email.txt email-new.txt
Time used: 1238 ms 回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-04 07:44 芋头

不同平台的测试成绩差异过大。。

jzhang的python版本在我的gentoo上测试是3.2秒，在cygwin里是5.2秒。

m网友的python版本在我的gentoo上是1.735秒左右，在我的cygwin里是1.8秒。

我的C＋＋版本在gentoo上是0.68秒，在cygwin里是1.235秒。

以上测试编译时都打开了-O2、-msse选项。我没在windows里安装编译器。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-04 08:33 dwbclz

主要是想要知道，性能的差别原因何在。
因为IO？还是其它的什么？IO的可能性比较大。
能具体测试一下吗？我这里没有Linux不好对比回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-04 09:32 芋头

Alloc buffer, 0 ms used.
Read file, 56 ms used.
Read 19388869 bytes.
Put emails into vector, 117 ms used.
Sort emails, 227 ms used.
Unique emails, 21 ms used.
Write emails into new file, 276 ms used.
Total used: 700 ms.

这是在gentoo 2006.0下执行的情况，输出文件是715247行，文件大小是17779266。

这边电脑的cygwin还没安装，测试要晚点了。前面的cygwin测试是在家里电脑上，不过2台电脑配置相近。
m网友的python版本执行时间是1735左右，jzhang的python版本执行时间为3200左右。

cygwin肯定会慢一些，不过慢这么多似乎不大可能。。关键是m网友的python在cygwin里面执行只比gentoo下慢了100ms，什么原因？

有没有可能跟编译器有关？gentoo下面是gcc 3.4.4。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-04 09:36 芋头

你所说的缩并，意思是不是先读入到buffer,然后\r\n被\n代替，后面的前移，最后面数据就是多出来的？如果这样的话的确是有很多多余的。我已经修改为size_t read = fread(buffer, 1, BUF_SIZE, fin), buffer[read] = '\0';多谢回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-04 11:29 芋头

同一程序，同一机器，编译器版本也一样，在cygwin里测试的结果：

$ ./test71 email.txt email-new.txt
Alloc buffer, 0 ms used.
Read file, 95 ms used.
Read 19388869 bytes.
Put emails into vector, 145 ms used.
Sort emails, 239 ms used.
Unique emails, 22 ms used.
Write emails into new file, 885 ms used.
Total used: 1392 ms.

整个都要慢一点，还算正常，主要是写文件慢太多了。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-04 12:08 芋头

用gcc 3.4.2在windows xp上编译，执行如下：
C:\>test71 email.txt email-new.txt
Alloc buffer, 0 ms used.
Read file, 109 ms used.
Read 18608870 bytes.
Put emails into vector, 141 ms used.
Sort emails, 234 ms used.
Unique emails, 16 ms used.
Write emails into new file, 640 ms used.
Total used: 1140 ms.

回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-04 16:13 芋头

做了点修改，修正了fread使用，增加了个跨平台的计时器类，发在文中最后面一段。里面有些输出我注释了，有这些输出会增加大约100ms执行时间，重定向到文件也会有10+ms影响。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-04 19:03 dwbclz

我也修正了一个版本，还是那个Blog。
在Windows下可以跑到750ms以内。
还是发在那个Blog上了，CSDN的Blog容量比较大啊，呵呵。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-05 09:17 芋头

to dwbclz:

你的版本在我的gentoo上用-O3编译，最好成绩可以达到640ms：
lijie new # ./histest email.txt email-new.txt
time : 640.00 (ms)
time : 680.00 (ms)
time : 650.00 (ms)
time : 670.00 (ms)
time : 650.00 (ms)
time : 670.00 (ms)
time : 650.00 (ms)
time : 660.00 (ms)
time : 670.00 (ms)
time : 670.00 (ms)

我那个什么缓存都没做的版本，在linux下最好成绩可以达到620ms。

我昨天做了点优化，在cygwin里面最好成绩是870ms，还是不够快。优化主要是增加了一个写缓冲，写文件时先写到缓冲区，满了就flush一下。不过这个版本在linux下反而慢了100ms左右，估计是linux下文件操作本身就有缓存，我这样做反而增加了memcpy的开销。

另外，标准库中的文件流并没有影响到速度，在windows上反而比我原来的FILE要快。不过在linux下，这个又相反，使用fstream以后，慢了近100ms。

我汗。。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-05 09:48 芋头

我把这问题提到D语言论坛上，有人说做出了一个400ms的D语言版本，不过在我这里测试是3600ms，相差太多，其他人最好的版本在我这里也要1800ms，达不到我第一个D语言版本的效率。不知道还会不会再提高。

就处理速度来说600＋已经够快了我感觉。绝不可能达到400ms 回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-05 11:44 芋头

想到另一个优化方式，不知道是否可行。

由于我的程序是把文件全部内容读到一个连续的缓冲区，这样只需要用查找出重复的email，把这部分内存置为0。然后调用fwrite把缓冲区写入文件，计算写了多少个字节，如果小于读入的字节数，说明后面还有数据，就需要跳过那些置为0的字节。再循环fwrite->跳过0。。。直到遍历完文件大小

这样省去了erase开销，节省几毫秒。另外，由于Email对象只有2个成员变量，是否可以直接把vector resize到一个比较大的数值(超过emails的大小)，直接操作vector的数据区，这样又减少了push_back时对象拷贝的开销，这个开销在我这里还是比较明显的。。。有点黑客手段了，为了效率不择手段了。。。。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-05 13:28 dwbclz

to cpunion
多谢您提供的测试数据。
您的算法应该不适合使用写缓存。我的算法是大量计算中
夹杂IO操作，所以运算和IO异步了。您的算法似乎必
须要等运算结束才可以Write，所以写缓存可能效果
不佳。

erase可以省，不过不用全置0，其实那个unique算法
可以变成unique_copy，或者模拟unique_copy。这样
可以省掉一些数据拷贝，减少了一个循环。

库函数的使用可能也可以做文章，我的那个程序调用fopen的时候
使用了"rb"和"wb"，据我测试，这省掉至少100ms。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-05 13:50 芋头

多谢dwbclz。

由于我在cygwin里面使用写缓存效率提高了很多，所以暂时还是保留了。unique_copy可能省不了多少时间，最多十几毫秒的样子，所以暂时没改它。
我现在改成使用fstream来操作，打开文件时使用ios::binary标志，提高了不少效率，在cygwin里可以达到650ms以下。

使用b标志打开、读取文件会提高速度，这个竟然忘了。。哎。。现在很难找到C++项目来做，荒废了都。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-05 14:08 芋头

用dev-cpp所带的g++编译器在windows上编译，最好成绩是609ms。关掉自己做的cache，测试是1000ms左右。这个修改版我还是追加文章里最后一段。

不过在gentoo里面测试又是不同结果，这个版本在打开自己做的cache时，执行时间是640ms，关闭时执行时间是700ms。反而不如windows和cygwin里面的执行情况，我原以为在gentoo里面会更高。。。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-05 18:02 芋头

经测试，我上面说的优化方案不可行。

现有的：（加了输出，增加了100ms左右）
lijie new # ./newtestnew2 email.txt email-new.txt
file size: 19388870
Alloc buffer: 0 ms used.
Read file: 73 ms used.
Put emails into vector: 165 ms used.
Sort emails: 180 ms used.
Unique emails: 32 ms used.
Write emails into new file: 288 ms used.
Total used: 741 ms.

设想的优化方案：
lijie new # ./newtestnew3 email.txt email-new.txt
file size: 19388870
Alloc buffer: 0 ms used.
Read file: 63 ms used.
Put emails into vector: 203 ms used.
Sort emails: 609 ms used.
Erase repeated emails: 81 ms used.
Write emails into new file: 122 ms used.
Total used: 1081 ms.

这样优化以后，很明显写文件的时间减少了，不过由于缓冲区中的\n没有替换为\0，必须在各个email中保存长度，增加了插入vector和排序的时间，总时间反而增加了许多。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-05 21:42 芋头

如果把email对象的指针再保存到一个vector里面，排序时对这个指针数组排序，可能会提高很多，代码没拷回来，明天再看。。。我只想看看用C＋＋可以做到什么样的效率回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-06 08:31 dwbclz

呵呵，不一定要把\n替换为\0，可以把\r替换成\0。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-06 09:57 芋头

很难再优化了，测试了上面说的优化方案，虽然某一项性能会有提高，不过必定会增加一项耗时的操作。回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-07 07:42 dwbclz

今天早晨，把我的程序又改了一下，去掉了C库的读写缓存，效率有少量
提高。
setvbuf(m_file, 0, _IONBF, 0);
这个函数对于写操作提升较多，对于读操作收获较小

我也开Blog了，有空去看看？
http://blog.csdn.net/dwbclz/ 回复更多评论

# re: C＋＋/D/Python性能比较续 2006-04-07 09:16 芋头

OK. 收藏了。

setvbuf应该会有提高。不过，setvbuf(m_file, 0, _IONBF, 0); 是关掉缓存吧？如果你自己做了的话，应该会有提高，如果没做的话，是否可以通过设置缓存来替代自己做的缓存？这个我没测试，我还是以使用C＋＋标准库为优先，除非它对性能损耗过大才考虑自己做。。

你的blog现在访问不了，CSDN好像经常这样。有时间我先看看可以达到什么样的效率。回复更多评论