jzhang 阅读(3906) 评论(153)
VCKbase的论坛上有人提了一个问题:
遇到的问题是,我把E-mail地址收集在txt文件中(每行一个E-mail地址,共78000行),要求是把其中重复的E-mail地址全部去掉。考虑编程方便,我用了CString类,但似乎效率不高。我写出来的整理78000份E-mail地址的需要近7分钟的时间

我给他用Python实现了一个(这个版本是修改过的,当时我随手实现的一个版本做错了,呵呵)
这里算法的主要内容就是利用hash_table来判断email是否已经重复出现,这比字符串的查找要快的多。

#remove duplicated email address from file
import datetime
if __name__ == "__main__":
 t = datetime.datetime(2000,1,1)
 print str(t.today())
 hashtable = {}
 f = file("email.txt","r")
 f2 = file("email_new.txt","w")
 line = f.readline();
 while len(line)>0:
  if not hashtable.has_key(line): 
   hashtable[line] = 1
   f2.write(line)
  line = f.readline();
 f.close()
 f2.close()
 t2 = datetime.datetime(2000,1,1)
 print str(t2.today())
  
上面的算法在我的机器上:P4 2.8G,512M 内存,耗时大约300ms,跟他的7分钟差了天了。而我当时错误的算法,需要2分半钟,所以我贴到我们内部的BBS上,我的一个同学实现了如下算法(C):
#include 
#include 
#include 
#include "list.h"
#define HASH_SIZE 262157
#define LINE_MAX_LEN 1024
struct list_node {
 struct list_head head;
 int len;
 char *str;
};
struct list_head hash_table[HASH_SIZE];
static inline int
hash_string (const char *ptr, int len)
{
 unsigned int hash = 0;
 
 for (hash = 0; len; len--, ptr++) {
  /* (31 * hash) will probably be optimized to ((hash << 5) - hash). */
  hash = 31 * hash + *ptr;
 }
 
 return (hash % HASH_SIZE);
}
static inline int
cmpfn(const struct list_node *node, int len, char *str)
{
 return ((node->len == len) && (memcmp(node->str, str, len) == 0));
}
int main(int argc, char **argv)
{
 int i, hash, len;
 struct list_node *node;
 char buf[LINE_MAX_LEN];
 FILE *fp_in, *fp_out;
 
 if(argc != 3) {
  printf("error: \nplease use eml as:\n eml infile outfile\n");
  return -1;
 }
 fp_in = fopen(argv[1], "r");
 if(!fp_in) {
  printf("error: could not open infile %s\n", argv[1]);
  return -1;
 }
 fp_out = fopen(argv[2], "w");
 if(!fp_out) {
  printf("error: could not open infile %s\n", argv[2]);
  return -1;
 }
 for(i=0; istr = (char *)malloc(len + 1);
   node->len = len;
   memcpy(node->str, buf, len);
   node->str[len] = '\0';
   list_append(&(hash_table[hash]), node);
  }
 }
 return 0;
}
还有.h文件:

#ifndef _LINUX_LIST_H
#define _LINUX_LIST_H
extern inline void prefetch(const void *x)
{
 return;
}
/*
 * Simple doubly linked list implementation.
 *
 * Some of the internal functions ("__xxx") are useful when
 * manipulating whole lists rather than single entries, as
 * sometimes we already know the next/prev entries and we can
 * generate better code by using them directly rather than
 * using the generic single-entry routines.
 */
struct list_head {
 struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
 struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \
 (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
/*
 * Insert a new entry between two known consecutive entries. 
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void
__list_add(struct list_head *new,
    struct list_head *prev, struct list_head *next)
{
 next->prev = new;
 new->next = next;
 new->prev = prev;
 prev->next = new;
}
/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void
list_add(struct list_head *new, struct list_head *head)
{
 __list_add(new, head, head->next);
}
/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void
list_add_tail(struct list_head *new, struct list_head *head)
{
 __list_add(new, head->prev, head);
}
/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void
__list_del(struct list_head *prev, struct list_head *next)
{
 next->prev = prev;
 prev->next = next;
}
/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty on entry does not return true after this, the entry is in an undefined state.
 */
static inline void
list_del(struct list_head *entry)
{
 __list_del(entry->prev, entry->next);
 entry->next = (void *) 0;
 entry->prev = (void *) 0;
}
/**
 * list_del_init - deletes entry from list and reinitialize it.
 * @entry: the element to delete from the list.
 */
static inline void
list_del_init(struct list_head *entry)
{
 __list_del(entry->prev, entry->next);
 INIT_LIST_HEAD(entry);
}
/**
 * list_move - delete from one list and add as another's head
 * @list: the entry to move
 * @head: the head that will precede our entry
 */
static inline void
list_move(struct list_head *list, struct list_head *head)
{
 __list_del(list->prev, list->next);
 list_add(list, head);
}
/**
 * list_move_tail - delete from one list and add as another's tail
 * @list: the entry to move
 * @head: the head that will follow our entry
 */
static inline void
list_move_tail(struct list_head *list, struct list_head *head)
{
 __list_del(list->prev, list->next);
 list_add_tail(list, head);
}
/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
static inline int
list_empty(struct list_head *head)
{
 return head->next == head;
}
static inline void
__list_splice(struct list_head *list, struct list_head *head)
{
 struct list_head *first = list->next;
 struct list_head *last = list->prev;
 struct list_head *at = head->next;
 first->prev = head;
 head->next = first;
 last->next = at;
 at->prev = last;
}
/**
 * list_splice - join two lists
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 */
static inline void
list_splice(struct list_head *list, struct list_head *head)
{
 if (!list_empty(list))
  __list_splice(list, head);
}
/**
 * list_splice_init - join two lists and reinitialise the emptied list.
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 *
 * The list at @list is reinitialised
 */
static inline void
list_splice_init(struct list_head *list, struct list_head *head)
{
 if (!list_empty(list)) {
  __list_splice(list, head);
  INIT_LIST_HEAD(list);
 }
}
/**
 * list_entry - get the struct for this entry
 * @ptr: the &struct list_head pointer.
 * @type: the type of the struct this is embedded in.
 * @member: the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
 ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
/**
 * list_for_each - iterate over a list
 * @pos: the &struct list_head to use as a loop counter.
 * @head: the head for your list.
 */
#define list_for_each(pos, head) \
 for (pos = (head)->next, prefetch(pos->next); pos != (head); \
         pos = pos->next, prefetch(pos->next))
/**
 * list_for_each_safe - iterate over a list safe against removal of list entry
 * @pos: the &struct list_head to use as a loop counter.
 * @n:  another &struct list_head to use as temporary storage
 * @head: the head for your list.
 */
#define list_for_each_safe(pos, n, head) \
 for (pos = (head)->next, n = pos->next; pos != (head); \
  pos = n, n = pos->next)
/**
 * list_for_each_entry - iterate over list of given type
 * @pos: the type * to use as a loop counter.
 * @head: the head for your list.
 * @member: the name of the list_struct within the struct.
 */
#define list_for_each_entry(pos, head, member)    \
 for (pos = list_entry((head)->next, typeof(*pos), member), \
       prefetch(pos->member.next);   \
      &pos->member != (head);      \
      pos = list_entry(pos->member.next, typeof(*pos), member), \
       prefetch(pos->member.next))
/*this is the begin of listhelp ;-)*/
#define LIST_FIND(head, cmpfn, type, args...)  \
({       \
 const struct list_head *__i = (head);  \
       \
 do {      \
  __i = __i->next;   \
  if (__i == (head)) {   \
   __i = NULL;   \
   break;    \
  }     \
 } while (!cmpfn((const type)__i , ## args)); \
 (type)__i;     \
})
#define LIST_FIND_W(head, cmpfn, type, args...) \
({      \
 const struct list_head *__i = (head); \
      \
 do {     \
  __i = __i->next;  \
  if (__i == (head)) {  \
   __i = NULL;  \
   break;   \
  }    \
 } while (!cmpfn((type)__i , ## args)); \
 (type)__i;    \
})
static inline int
__list_cmp_same(const void *p1, const void *p2)
{
 return p1 == p2;
}
/* Is this entry in the list? */
static inline int
list_inlist(struct list_head *head, const void *entry)
{
 return LIST_FIND(head, __list_cmp_same, void *, entry) !=NULL;
}
/* Delete from list. */
#ifdef CONFIG_NETFILTER_DEBUG
#define LIST_DELETE(head, oldentry)     \
do {         \
 if (!list_inlist(head, oldentry))    \
  printk("LIST_DELETE: %s:%u `%s'(%p) not in %s.\n", \
         __FILE__, __LINE__, #oldentry, oldentry, #head); \
        else list_del((struct list_head *)oldentry);   \
} while(0)
#else
#define LIST_DELETE(head, oldentry) list_del((struct list_head *)oldentry)
#endif
/* Append. */
static inline void
list_append(struct list_head *head, void *new)
{
 list_add((new), (head)->prev);
}
/* Prepend. */
static inline void
list_prepend(struct list_head *head, void *new)
{
 list_add(new, head);
}
/* Insert according to ordering function; insert before first true. */
#define LIST_INSERT(head, new, cmpfn)    \
do {        \
 struct list_head *__i;     \
 for (__i = (head)->next;    \
      !cmpfn((new), (typeof (new))__i) && __i != (head); \
      __i = __i->next);     \
 list_add((struct list_head *)(new), __i->prev);  \
} while(0)
/* If the field after the list_head is a nul-terminated string, you
   can use these functions. */
static inline int
__list_cmp_name(const void *i, const char *name)
{
 return strcmp(name, i + sizeof (struct list_head)) == 0;
}
static inline int
__list_cmp_nameptr(const void *i, const char *name)
{
 return strcmp(name, ((char *)
        *(unsigned long *) (i +
       sizeof (struct list_head)))) ==
     0;
}
/* Returns false if same name already in list, otherwise does insert. */
static inline int
list_named_insert(struct list_head *head, void *new)
{
 if (LIST_FIND(head, __list_cmp_name, void *,
        new + sizeof (struct list_head)))
   return 0;
 list_prepend(head, new);
 return 1;
}
static inline int
list_nameptr_insert(struct list_head *head, void *new)
{
 if (LIST_FIND(head, __list_cmp_nameptr, void *,
        new + sizeof (struct list_head)))
   return 0;
 list_prepend(head, new);
 return 1;
}
/* Find this named element in the list. */
#define list_named_find(head, name)   \
LIST_FIND(head, __list_cmp_name, void *, name)
#define list_nameptr_find(head, name)   \
LIST_FIND(head, __list_cmp_nameptr, void *, name)
#endif
在我的机器上测试(cygwin):耗时竟然是400ms!
当然,这里包含了Cygwin的间接调用开销。

很难想象吧,Python在这里的性能竟然跟C不相上下!而且Python的代码比C不知道短了多少倍!
所以讲,Python是蛮好用的,:-).
不过,这个例子其实是个特殊情况,以前我们玩过的另外一个程序,C的性能就比Python快得多。不过代码量还是Python简短得多。有兴趣的朋友可以用自己熟悉的语言来测试一下,下面是测试文件(也是我用11行python代码产生的,有1/10的email是重复的):
这其实是一个rar,下载后请修改扩展名


评论列表
usr_root
re: 一段Python程序和C程序的对比
我也感觉python不错,目前正在学习,相信以后会很流行
周星星
re: 一段Python程序和C程序的对比
算法明显不一样,你这比较的是hash和list性能的差别,而不关python和C任何事。
我也想看看python性能如何,请问能不能把你的txt文件发一份给我?
周星星
先帮我测试一下这段C++代码所耗费的时间(release版本)

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

int main( void )
{
    vector<string> emails;
    {
        ifstream infile( "email.txt" );
        copy( istream_iterator<string>(infile), istream_iterator<string>(), back_inserter(emails) );
    }
    sort( emails.begin(), emails.end() );
    emails.erase( unique( emails.begin(), emails.end() ), emails.end() );
    {
        ofstream outfile( "email_new.txt" );
        copy( emails.begin(), emails.end(), ostream_iterator<string>(outfile,"\n") );
    }
}

周星星
我自己测试了一下
PM 2.0G 内存 1G,其实这些参数用处不大,主要要看硬盘的读写速度,我用的是笔记本硬盘。
测试结果是 499.9584毫秒,这个数字还是比较准确的,好多次都是这个值。
jzhang
C的代码也是一种hash算法
测试的文件在原文有链接的。是一个rar文件,扩展名被改成了txt
jzhang
Lua也是很有名的
不过我不打算同时学习两种脚本,Python的最大的缺点其实就是慢。我举的这个例子,其实是为了说明算法不同带来的性能差异往往比语言本身要大得多。
jzhang
看来应该把测试文件扩大10倍
这样才能体现出差异来。
jzhang
周星星你的算法比Python的慢
我测试的780000条记录的情况:
Python版本:3200 ms
C++版本:5700 ms

都是多次的平均值。我想主要是排序花的时间太多了。
jzhang
jzhang
我发现lua的语法根Python蛮像的
t1 = os.clock();
email = {}
f = io.open("email_new.txt", "wt+")
for line in io.lines("email.txt") do
if #line > 0 then
if email[line] == nil then
email[line] = 1
f:write(line, "\n")
end
end
end
f:close()

print( string.format("time used: %f seconds", os.clock() - t1) );
尤其是hash表的申明和使用,都是内置支持。就是这个end让我看着难受点,呵呵
周星星
试试hash_set的性能

#include <iostream>
#include <hash_set>
#include <string>
#include <fstream>
#include <windows.h>

int main( void )
{
    __int64 t1, t2;
    GetSystemTimeAsFileTime( (LPFILETIME)&t1 );

    std::ifstream infile( "email.txt" );
    std::ofstream outfile( "email_new.txt" );
    stdext::hash_set<std::string> emails;
    for( std::string email; infile>>email; )
    {
        if( emails.insert(email).second )
        {
            outfile << email << '\n';
        }
    }

    GetSystemTimeAsFileTime( (LPFILETIME)&t2 );
    printf( "经过了%I64d.%04I64d毫秒\n", (t2-t1)/10000, (t2-t1)%10000 );
}

我这里需要 437.4636 毫秒

jzhang
to 局部变量,你测试的是周星星的第一个版本吧?
他用的是list+排序的算法。性能比hash差得多,而且文件越大越差。
这不是语言的问题了。
不过看起来Lua的确比Python快,在相同算法的情况下。

100k的Lua能做什么?Python的体积主要也来自他的丰富的库。

ps.为什么你每次都回复3篇?....浏览器的bug?
周星星
发现几个奇怪的地方

1。我以为 set 会比 hash_set 慢一些,但发现和 hash_set 一样,仍然是 437.4636 毫秒,代码如下:
#include <iostream>
#include <set>
#include <string>
#include <fstream>
#include <windows.h>
using namespace std;

int main( void )
{
    __int64 t1, t2;
    GetSystemTimeAsFileTime( (LPFILETIME)&t1 );

    ifstream infile( "email.txt" );
    ofstream outfile( "email_new.txt" );
    set<string> emails;
    for( string email; infile>>email; )
    {
        if( emails.insert(email).second )
        {
            outfile << email << '\n';
        }
    }

    GetSystemTimeAsFileTime( (LPFILETIME)&t2 );
    printf( "经过了%I64d.%04I64d毫秒\n", (t2-t1)/10000, (t2-t1)%10000 );
}

2。同样的代码,我以为 dev-cpp 编译出来比 vc2005 慢一些,但发现每次都一样

3。我以为在调试器中运行 会比 直接在控制台下运行 慢一些,但发现结果恰恰相反,而且差距很大:
VC8中运行平均500毫秒 ,dev-cpp中运行平均430毫秒,dev-cpp编译的程序在CMD中运行平均530毫秒,dev-cpp编译的程序在CMD中运行平均530毫秒

4。g++的 hash_map 运行不起来
#include <string>
#include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx;

namespace __gnu_cxx
{
        template<> struct hash<const string>
        {
                size_t operator()(const string& s) const
                { return hash()(s.c_str()); }
        };
        template<> struct hash<string>
        {
                size_t operator()(const string& s) const
                { return hash()(s.c_str()); }
        };
}

int main( void )
{
        hash_map<string,int> a;
        a["abc"] = 1; // 这一句一执行的话,程序直接退出

        system("pause");
}

jzhang
To 周星星
你的hash版本测试的是78000的还是780000的?
周星星
re jzhang:
78000,没有修改编译器的任何优化项
jzhang
测试一下780000的那个吧,我觉得那个更加准确
几百毫秒的数据比较容易被一些其他因素干扰。
周星星
re jzhang:

1。set 内部使用的是 RB-Tree,比 hashtable 性能差,但稳定

2。^_^ 追求代码简洁的话,只需要四句:
#include <set>
#include <string>
#include <fstream>
#include <algorithm>
#include <iterator>
using namespace std;

int main( void )
{
     ifstream infile( "email.txt" );
    set<string> emails = set<string>( istream_iterator<string>(infile), istream_iterator<string>() );
    ofstream outfile( "email_new.txt" );
    copy( emails.begin(), emails.end(), ostream_iterator<string>(outfile,"\n") );
}

jzhang
呵呵,这段代码可不美
需要看几眼才能看明白一行的代码不好,:)
jzhang
跟Python版本差不多
这真是一个证明Python某些地方也挺快的好例子呀,呵呵。
其实Python慢的最重要原因之一是它的动态类型,而这个例子里
并没有体现,所以性能就跟C++不相上下了。

我现在的项目就要用STL了,希望能在1个月之内用熟
局部变量
to jzhang
我也不知道为什么每次都是3个,害得我都有点不敢回复了:(
我用的就是那个hash_set的版本, 不知道为什么那么费时间
lua自带string,math,table,io,debug库(确实是比python少多了),不过它应该主要还是用在内嵌脚本上吧,我现在研究它也是打算在一个项目中使用它处理脚本
周星星
re jzhang:
把我上一个帖子删除掉,因为我把780000说成了78000。更改如下:

我用 780000 的做测试用例,代码如下:
ifstream infile( "email.txt" );
set<string> emails = set<string>( istream_iterator<string>(infile), istream_iterator<string>() );
ofstream outfile( "email_new.txt" );
copy( emails.begin(), emails.end(), ostream_iterator<string>(outfile,"\n") );
平均值是 4900 毫秒。
sevencat
re: 一段Python程序和C程序的对比
哪位把更大的发给我,我测一下时间。
Panic
re: 星星,如果你对这个算法感兴趣,可以研究一下我的这篇
 

查找序列中给定 对象组合 的模板类

sevencat
re: 一段Python程序和C程序的对比
我怀疑大家被这个东东忽悠了。这个完全不是算法瓶颈,仅仅是文件IO瓶颈,可以试试用FILE,setvbuf(18*1024)看看。
我这里C++比PYTHON要快。我这边一般在3000MS以下。而python基本上会在4000MS以上。
jzhang
这也有可能
不知道标准库的文件缓冲区是多大,C的默认是4k吧。当然这个缓冲区越大会越快。嗯,这的确是一个因素。
sevencat
re: 一段Python程序和C程序的对比
这已经是最主要的因素了。
你可以试试一开始把数组全部读出来,开始计时,然后进行判断,再结束,再写,这样,可能就很清楚了。我不知道python的机制是什么,其实这种读大型文件,还有另外的更快的机制。
sevencat
re: 一段Python程序和C程序的对比
不过这种比较已经没啥意义了,C是那么的难用,C++是那么的更难用....
imjj
re: 一段Python程序和C程序的对比
# re jzhang: 
把我上一个帖子删除掉,因为我把780000说成了78000。更改如下: 

我用 780000 的做测试用例,代码如下: 
ifstream infile( "email.txt" ); 
set<string> emails = set<string>( istream_iterator<string>(infile), istream_iterator<string>() ); 
ofstream outfile( "email_new.txt" ); 
copy( emails.begin(), emails.end(), ostream_iterator<string>(outfile,"\n") ); 
平均值是 4900 毫秒。 
2006-03-28 15:04 | 周星星 

嗯,那这样的呢
    ifstream infile( "email.txt" );
    ofstream outfile( "email_new_my.txt" );

    unique_copy( istream_iterator<string>(infile), istream_iterator<string>(), ostream_iterator<string>(outfile,"\n"));
time_t end = time(NULL);
周星星
re imjj:
使用 unique_copy  的话,仍然需要先排序,假设email.txt内容如下:
b
a
a
b
使用 unique_copy  得到的将是
b
a
b
也就是 unique_copy  只会将相邻而重复的取 unique。
imjj
re: 周星星
嗯 受教
试了一下 果然如此
imjj
re: 一段Python程序和C程序的对比
嗯 查了Python的源码 基本搞清楚了对于这个例子Python为什么这么相当的快,在$PySrc/Objects/descrobject.c 中,对Python的Hash机制作了一些描述,总的来说,Python的Hash机制对于这种连续型的字符串有相当好的离散度,对于这个 78W 例子,python_hash() % 780000能够很均匀的分散到各个值,最大的冲突数为 8(通常的算法要到2K+)。也大概看了看Lua的实现,Lua 的Hash算法同样很适合这样的例子,但是Lua本身的开销小,所以它的速度比Lua还快。

再一个 ifstream 和 ofstream 的性能也是 C++ 实现不如这些脚本实现速度快的一个因素,当重复的调用 ofstream<< ,而不是使用 copy 等 alogrithm 的相关方法输出时,这个性能实在有点慢,而使用 fgets/fprintf 就好的多。

以下是按照类似 Python的 Hash算法实现的 C++ 版本的结果
E:\Workspace\Temp\Email>my
经过了1687.5000毫秒

E:\Workspace\Temp\Email>my
经过了1718.7500毫秒

E:\Workspace\Temp\Email>my
经过了1671.8750毫秒

E:\Workspace\Temp\Email>my
经过了1656.2500毫秒

E:\Workspace\Temp\Email>py_email.py
2.82014641526

E:\Workspace\Temp\Email>py_email.py
2.74879181572

E:\Workspace\Temp\Email>py_email.py
2.76348586203

E:\Workspace\Temp\Email>dir *.txt
2006-03-28  13:09        19,388,869 email.txt
2006-03-29  22:51        17,779,266 email_new.txt (py_email.py 写出)
2006-03-29  22:50        17,779,266 email_new_my.txt (my.exe 写出)

py_email.py 的实现参看楼主的实现
my.cpp 实现如下
使用 cl /O2 /EHsc /D_CRT_SECURE_NO_DEPRECATE my.cpp 编译

#include <cstdio>
#include <windows.h>
using namespace std;


#define c_mul(a, b) (a * b & 0xFFFFFFFF)

size_t python_hash(const char * str)
{
size_t value = str[0] << 7;
size_t len = 0;
while(*str != 0)
{
value = c_mul(1000003, value) ^ *str++;
len++;
}

value = value ^ len;
if (value == (size_t)-1)
value = (size_t)-2;
return value;

}

size_t hash(const char * str, size_t seed = 1)
{
size_t h = 0, g; 
size_t len = 0;
while (*str) { 
h = (h << 4) + *str++; 
if ((g = (h & 0xF0000000))) { 
h = h ^ (g >> 24); 
h = h ^ g; 
h = h ^ seed;

len++;

return h; 
}


#define MAX_TABLE_SIZE (780000)
#define MAX_CONFI 9

struct hash_item
{
size_t items[MAX_CONFI];
size_t item_count;
hash_item()
{
item_count = 0;
}
bool check_has(const char * str)
{
size_t key = hash(str);
for(size_t i = 0; i < item_count; i++)
{
if (items[i] == key)
return true;
}
items[item_count++] = key;
return false;
}

};


int main( void )
{
__int64 t1, t2;
    GetSystemTimeAsFileTime( (LPFILETIME)&t1 );
    FILE * fin = fopen("email.txt", "r");
FILE * fout = fopen("email_new_my.txt", "w+");

size_t hash_key_a = 0;
size_t hash_key_b = 0;
size_t pos_x = 0;
size_t pos_y = 0;
const char * buffer = NULL;
char line[255];
fgets(line, 255, fin);
hash_item * table = new hash_item[MAX_TABLE_SIZE];
while(!feof(fin))
{
buffer = line;
hash_key_a = python_hash(buffer);
pos_x = hash_key_a % MAX_TABLE_SIZE;
if (!table[pos_x].check_has(buffer))
{
fprintf(fout, "%s", buffer);
}

fgets(line, 255, fin);
}
    GetSystemTimeAsFileTime( (LPFILETIME)&t2 );
    printf( "经过了%I64d.%04I64d毫秒\n", (t2-t1)/10000, (t2-t1)%10000 );
fclose(fin);
fclose(fout);
delete [] table;
}
jzhang
imjj 真棒!
研究得这么透彻,受益匪浅。
sevencat
re: 一段Python程序和C程序的对比
可能是因为很多人被误导了,以为STL的东东效率高,其实不是那么回事。stl的基于node的都有性能问题。std::string也有性能问题。(因为都有动态分配内存过程)
ksl
STL
STL的效率不是高,而是不比你写的低,我觉得STL首先保证通用性,其次保证使用的算法复杂度,最后才考虑性能,而且不同的算法和容器使用在不同场合有不同的性能(取决于其实现),内存分配也是可定制的,通用的alloctor并不适用所有情况的需求
jzhang
通用的效率一定就低吗?
而且,作为一个标准库,性能应该是和通用性同等重要的指标,更何况还是非常常用的数据结构呢。
sevencat
re: 一段Python程序和C程序的对比
比我写的优化过后的肯定要低的。在效率要求高的地方,不太会考虑STL的东东的。
cpunion
re: 一段Python程序和C程序的对比
这个完全取决于实现。我在我的机器上测试了一下,这个python程序运行耗时:
lijie ~ # python test.py
0.437092065811
lijie ~ # python test.py
0.473711013794
lijie ~ # python test.py
0.452960014343
lijie ~ # python test.py
0.469227075577
lijie ~ # python test.py
0.42777299881
lijie ~ # python test.py
0.415369987488

415-473毫秒之间。

我用D语言写了一个,调用fopen, fgets, fputs这些函数的,运行结果如下:

lijie ~ # ./email email.txt email-new.txt
132
lijie ~ # ./email email.txt email-new.txt
137
lijie ~ # ./email email.txt email-new.txt
145
lijie ~ # ./email email.txt email-new.txt
138
lijie ~ # ./email email.txt email-new.txt
148
lijie ~ # ./email email.txt email-new.txt
143

单位是毫秒。
我查看了输出文件,是一样的。

D版本的代码如下:
import std.stdio;
import std.string;
import std.perf;

int main(char[][] argv)
{
  if (argv.length < 3) {
    writefln("Wrong arguments");
    return 1;
  }

  const int READ_SIZE = 1024;

  FILE* fin = fopen(argv[1], "r");
  FILE* fout = fopen(argv[2], "w");
  char buffer[READ_SIZE];
  int[char[]] emails;

  PerformanceCounter counter = new PerformanceCounter();
  counter.start();
  while (!feof(fin)){
    fgets(cast(char*)buffer, READ_SIZE, fin);
    char[] email = toString(cast(char*)buffer);
    if (!(email in emails)){
      emails[toString(buffer)] = 0;
      fputs(cast(char*)email, fout);
    }
  }

  fclose(fout);
  fclose(fin);
  counter.stop();

  writefln(counter.milliseconds());
  return 0;
}
由于是在上班,没花时间处理文件打开失败等情况,见谅。
cpunion
re: 一段Python程序和C程序的对比
测试大文件780000行那个:
python:单位:秒
lijie ~ # python test.py
5.0066409111
lijie ~ # python test.py
4.827917099
lijie ~ # python test.py
4.76066708565

D:单位:毫秒
lijie ~ # ./email email-2.txt email-2-new.txt
1425
lijie ~ # ./email email-2.txt email-2-new.txt
1354
lijie ~ # ./email email-2.txt email-2-new.txt
1413
cpunion
re: 一段Python程序和C程序的对比
忘了关浏览器了,而浏览器正好打开了级度耗资源的CSDN。重新测试了一下:

lijie ~ # python test.py
3.27638888359
lijie ~ # python test.py
3.31844902039
lijie ~ # python test.py
3.31299114227
^[[Alijie ~ # python test.py
3.41847610474
lijie ~ # python test.py
3.32070493698
lijie ~ #
lijie ~ # ./email email-2.txt email-2-new.txt
1131
lijie ~ # ./email email-2.txt email-2-new.txt
1128
lijie ~ # ./email email-2.txt email-2-new.txt
1114
lijie ~ # ./email email-2.txt email-2-new.txt
1125
lijie ~ # ./email email-2.txt email-2-new.txt
1122

这个D语言版本比python版本快3倍左右。由于D对C的包装也比较薄,基本上可以认为是C语言的效率。使用纯C应该会更高,不过我没能力实现出一个这么高次的关联数组。
(注:上面这个D版本使用了关联数组模拟set行为)

发太多了,好像灌水似的,见谅
jzhang
D语言?第一次看见,开了眼界了,呵呵
谢谢cpunion.
m
用快速排序达到200毫秒级算法
from datetime import datetime
if __name__ == '__main__':
print(datetime.today())
f = file(r'E:\email.txt','r')
lines1, lines2 = f.readlines(), [];
f.close()
lines1.sort()
lines2.append(lines1[-1])
for ln in range(len(lines1) - 2, -1, -1):
if lines1[ln] <> lines1[ln + 1]: 
lines2.append(lines1[ln])
f = file(r'E:\email_new.txt','w')
f.writelines(lines2)
f.close()
print(datetime.today())

m
re: 一段Python程序和C程序的对比
还可以不采用lines2,而直接在lines1上将相同的串置空串,这样效率还可以提高。
cpunion
re: 一段Python程序和C程序的对比
数据可能还是不够复杂,email仅仅前几位有差异,这样通过strcmp也只需要比较前几位,可以试着把它倒转,让尾部几个字符不同,再比较一下效率。这样使用字符串比较的应该会受到影响吧
jzhang
m,你的算法吃内存太厉害了
一次把文件全部读出来了。
wmuu
re: 一段Python程序和C程序的对比
大批量插入,hashMap会比treeMap好很多。极端情况下会差10倍以上。我以前试过了
wmuu
re: 一段Python程序和C程序的对比
c++的map是用二叉数字实现的,极端情况下每次插入会和每个已有的元素进行比较
非典型秃子
re: 一段Python程序和C程序的对比
优化一下IO的:
#include <string>
#include <iostream>
#include <fstream>
#include <iterator>
#include <windows.h>
#include <algorithm>
#include <ios>
#include <functional>
#include <vector>
using namespace std;

void splite(char * buf, long size, vector<char*>& v)
{
v.push_back(buf);
for (;size > 0 && *buf != '\0'; ++buf, --size)
{
if (*buf == '\r')
{
*buf = '\0';
buf += 2;
size -=2;
if (*buf != '\0')
v.push_back(buf);
}
}
}
struct Comp : public binary_function<char*, char*, bool>
{
bool operator()(char * lsh, char* rsh)
{
return strcmp(lsh, rsh) < 0;
}
};
struct Comp2 : public binary_function<char*, char*, bool>
{
bool operator()(char * lsh, char* rsh)
{
return strcmp(lsh, rsh) == 0;
}
};

struct iterator_string
{
struct assigner
{
assigner(vector<char>& v) : m_v(&v){}
assigner& operator=(char* src)
{
while( *src != NULL)
m_v->push_back(*src++);
m_v->push_back('\r');
m_v->push_back('\n');
return *this;
}
private:
vector<char>* m_v;
};
iterator_string(vector<char>& v) : m_assign(v){}
assigner& operator*()
{
return m_assign;
}
iterator_string& operator++() {return *this;}
iterator_string& operator++(int) {return *this;}
private:
assigner m_assign;
};

int main()
{
DWORD start = ::GetTickCount();

ifstream ifs("email.txt" , ios_base::binary | ios_base::in);
ifs.seekg(0, ios_base::end);
long size = ifs.tellg();
ifs.seekg(0, ios_base::beg);

char* buf = new char[size + 1];
ifs.read(buf, size);
buf[size] = '\0';
vector<char*> v;
v.reserve(80000);
splite(buf, size, v);

sort(v.begin(), v.end(), Comp());

vector<char> vout;
vout.reserve(size);

ofstream ofs("out.txt", ios_base::binary | ios_base::out);
unique_copy(v.begin(), v.end(), iterator_string(vout), Comp2());
ofs.write(&vout[0], vout.size());

cout <<  ::GetTickCount() - start;
return 0;
}

简单优化一下IO,没有使用任何平台相关的技巧,最好输出时间:78ms
我的机器:
p42.66 , 1G RAM,硬盘ST380011A

为什么一定要和C++比性能呢?即使比简洁,C++也不落后啊。
sevencat
re: 一段Python程序和C程序的对比
你下那个稍微大点的email.txt试试吧。
sevencat
re: 一段Python程序和C程序的对比
78000的: http://jason.rocklv.net/downloads/email2.txt (注意这是个rar)
780000的: http://jason.rocklv.net/downloads/email.rar
下第2个,用python和C++来试。
TripleX
re: 一段Python程序和C程序的对比
其实 多跑第二次的时候 基本读就没有真正的磁盘IO了 源数据都在内存里cache着 除非再做一堆磁盘IO 把cache里的老数据挤出去
另外 儿叉树未必会比hash table慢 对具体的这个问题来说 一般的字符串hash算法 算hash值需要把每个字符算一遍 如果每个串比较长 就会比较慢 虽然好的算法基本能一次查找到 但是算key的时间可能比较长 而二叉树虽然需要多次比较 但是如果任意两个串 在开头的几个字符就很可能不同的话 每次字符串比较大小只需要比较很少的几个字符 所以最终的速度非常依赖于每行字符的特征 
关于字符串的问题总是比较复杂的......
1 2 3 下一页共3页  到第

发表评论
切换编辑模式