jzhang 阅读(4724) 评论(155)
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
我发现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试试吧。
TripleX
re: 一段Python程序和C程序的对比
其实 多跑第二次的时候 基本读就没有真正的磁盘IO了 源数据都在内存里cache着 除非再做一堆磁盘IO 把cache里的老数据挤出去
另外 儿叉树未必会比hash table慢 对具体的这个问题来说 一般的字符串hash算法 算hash值需要把每个字符算一遍 如果每个串比较长 就会比较慢 虽然好的算法基本能一次查找到 但是算key的时间可能比较长 而二叉树虽然需要多次比较 但是如果任意两个串 在开头的几个字符就很可能不同的话 每次字符串比较大小只需要比较很少的几个字符 所以最终的速度非常依赖于每行字符的特征 
关于字符串的问题总是比较复杂的......
jzhang
to 非子,你的算法和星星的是一样的
另外,测试的时候你有对比测试其他程序的吗?否则机器的差别太大了。
jzhang
To triplex
hash code算起来虽然慢,但是比起字符串比较来说,差的很远。
hash code的计算开销基本是固定的
1 2 3 下一页共3页  到第

发表评论
切换编辑模式