问一个关于算法的问题，请大家讨论
samana
有50，000个html的文件放在一个文件夹下，里面有些文件包含有电话号码，要将这些电话号码整理出来并且要求不重复放到一个html文件里，求一
个快速有效的算法。
da zhou
昨天一个同学去面试，对方出了这么一道题目，请大家讨论并不吝你的解法。
有50，000个html的文件放在一个文件夹下，里面有些文件包含有电话号码，要将这些电话号码整理出来并且要求不重复放到一个html文件里，求一
个快速有效的算法。
--
DaZhou
-----------------------------
dazhou.li@gmail.com
samana
2.要求是读取出来的电话号码不重复
3.文件读取写入的速率
On 9月4日, 上午10时23分, da zhou <dazhou...@gmail.com> wrote:
> 这个谈不上什么算法吧.
>
> 一个线程池机制的读取分析模块,用正则匹配电话号码.
>
> 然后用张表放这些匹配出来的电话号码,入库的时候,检查重复数据. 5W个找完了,写到文件中就是了.
>
> 2009/9/4 samana <smit...@gmail.com>
>
> > 昨天一个同学去面试，对方出了这么一道题目，请大家讨论并不吝你的解法。
>
> > 有50，000个html的文件放在一个文件夹下，里面有些文件包含有电话号码，要将这些电话号码整理出来并且要求不重复放到一个html文件里，求一
> > 个快速有效的算法。
>
> --
> DaZhou
> -----------------------------
ka-bar
读取每一个文件，发现电话号码时，检测是否已在哈希表中，不存在则插入哈希表。
最后将哈希表内容写入html中。
如果是windows系统，就用windowsAPI打开文件，不用C库中的函数。
--------------------------------------------------
From: "samana" <smi...@gmail.com>
Sent: Friday, September 04, 2009 10:28 AM
To: "高性能服务器研发与运营邮件列表" <dev4s...@googlegroups.com>
Subject: Re: 问一个关于算法的问题，请大家讨论
Zhang
第一次回复，呵呵。
我觉的，你和你同学都想偏了。这个题目用数学抽象以下。可以形容为：
在一个无序大数组里，剔除重复数的高效算法。（这个百度或google下，就可以找到的）
如果我理解有误，请见谅。个人觉得如果主管不是这个意思的话，这个题目确实不是什么算法问题。并且鄙视这个主管。
|
|
|
|
qiaojie
samana
但是从这个实际题目上，无序数组里的数据是分布在50,000文件里，按照你讲的思路就是先将文件里的数据全部导入一个数据集合中，这种想法没错
我先说下我的思路，抛砖引玉吧。
1.文件挑选。将文件分组，利用线程池机制检索文件是否含有电话号码，有则标记
2.数据集合。确定后含有电话号码的文件后，是先将所有电话号码放入数据集合进行唯一剔除
3.剔除算法。在一个数据集合里，如何更有效的挑出唯一的电话号码并生成一个html文件
On 9月4日, 下午2时49分, qiaojie <qiao...@gmail.com> wrote:
> 随便鄙视别人是不对的。这是一道很有现实意义的工程问题，可以考察的地方很多，如果我是面试官的话，除了考察他的算法能力，还可以从他思考的全面性以及实现的细节上全面的考察他的工程经验。
>
> 2009/9/4 Zhang <hyzzfj...@yahoo.cn>
>
> > 第一次回复，呵呵。
> > 我觉的，你和你同学都想偏了。这个题目用数学抽象以下。可以形容为：
> > 在一个无序大数组里，剔除重复数的高效算法。（这个百度或google下，就可以找到的）
> > 如果我理解有误，请见谅。个人觉得如果主管不是这个意思的话，这个题目确实不是什么算法问题。并且鄙视这个主管。
>
> > --------------------------------------------------
> > From: "samana" <smit...@gmail.com<http://cn.mc921.mail.yahoo.com/mc/compose?to=smit...@gmail.com>
>
> > Sent: Friday, September 04, 2009 10:28 AM
> > To: "高性能服务器研发与运营邮件列表" <dev4s...@googlegroups.com<http://cn.mc921.mail.yahoo.com/mc/compose?to=dev4s...@googlegroups.com>
>
> > Subject: Re: 问一个关于算法的问题，请大家讨论
>
> > >日期: 2009年9月4日,周五,上午11:14
> > >创建哈希表。
> > >读取每一个文件，发现电话号码时，检测是否已在哈希表中，不存在则插入哈希 表。
> > >最后将哈希表内容写入html中。
> > >如果是windows系统，就用windowsAPI打开文件，不用C库中的函数。
>
> > > 1.50,000个文件里有的含有电话号码，有的不含
> > > 2.要求是读取出来的电话号码不重复
> > > 3.文件读取写入的速率
>
> > > On 9月4日, 上午10时23分, da zhou <dazhou...@gmail.com<http://cn.mc921.mail.yahoo.com/mc/compose?to=dazhou...@gmail.com>>
> > wrote:
> > >> 这个谈不上什么算法吧.
>
> > >> 一个线程池机制的读取分析模块,用正则匹配电话号码.
>
> > >> 然后用张表放这些匹配出来的电话号码,入库的时候,检查重复数据. 5W个找完了,写到文件中就是了.
>
> > >> 2009/9/4 samana <smit...@gmail.com<http://cn.mc921.mail.yahoo.com/mc/compose?to=smit...@gmail.com>
>
> > >> > 昨天一个同学去面试，对方出了这么一道题目，请大家讨论并不吝你的解法。
>
> > 有50，000个html的文件放在一个文件夹下，里面有些文件包含有电话号码，要将这些电话号码整理出来并且要求不重复放到一个html文件里，求一
> > >> > 个快速有效的算法。
>
> > >> --
> > >> DaZhou
> > >> -----------------------------
> > >> dazhou...@gmail.com<http://cn.mc921.mail.yahoo.com/mc/compose?to=dazhou...@gmail.com>
>
> > ------------------------------
> > 好玩贺卡等你发，邮箱贺卡全新上线！ >
>
> > <http://cn.rd.yahoo.com/mail_cn/tagline/card/*http://card.mail.cn.yaho...>
>
>
chuang
扫描之后得到的号码必然要存放到进行排重操作的.
所以,我的思路是,开多线程进行文件的扫描,线程间有一个大家都可以访问的内存区,扫描之后的号码要到这个区域进行排重操作.
而这个区域的数据结构的选择, 目前看来似乎不能用位图了,那就用hash好了.
--
豆瓣:http://www.douban.com/people/Lichuang/
blog:http://www.cppblog.com/converse/
关中刀客
的处理，这方面的需求可能会不断的改变更加，好的做法还是用脚本去实现，程序将数据传递给不同的脚本，这些脚本根据功能去分析自己关心的数据即可。读文
件没有什么可说的了，多个线程，不断的读。对于插入的话，直接的字符串判断插入不是很好，可以先哈希一下判断，在插入。
On 9月4日, 下午3时20分, chuang <lichuang1...@gmail.com> wrote:
> 扫描文件为了加速, 可以使用多线程来进行扫描.
> 扫描之后得到的号码必然要存放到进行排重操作的.
>
> 所以,我的思路是,开多线程进行文件的扫描,线程间有一个大家都可以访问的内存区,扫描之后的号码要到这个区域进行排重操作.
> 而这个区域的数据结构的选择, 目前看来似乎不能用位图了,那就用hash好了.
>
> 2009/9/4 samana <smit...@gmail.com>
>
>
>
>
>
> > "在一个无序大数组里，剔除重复数的高效算法".从狭义上可以这么理解。
> > 但是从这个实际题目上，无序数组里的数据是分布在50,000文件里，按照你讲的思路就是先将文件里的数据全部导入一个数据集合中，这种想法没错
> > 我先说下我的思路，抛砖引玉吧。
> > 1.文件挑选。将文件分组，利用线程池机制检索文件是否含有电话号码，有则标记
> > 2.数据集合。确定后含有电话号码的文件后，是先将所有电话号码放入数据集合进行唯一剔除
> > 3.剔除算法。在一个数据集合里，如何更有效的挑出唯一的电话号码并生成一个html文件
>
> > On 9月4日, 下午2时49分, qiaojie <qiao...@gmail.com> wrote:
>
> > 随便鄙视别人是不对的。这是一道很有现实意义的工程问题，可以考察的地方很多，如果我是面试官的话，除了考察他的算法能力，还可以从他思考的全面性以及实现的细-节上全面的考察他的工程经验。
> blog:http://www.cppblog.com/converse/- 隐藏被引用文字 -
>
> - 显示引用的文字 -
杨光
doledole
<thread-x>
thread-1 --> BUFFER -->|--------|
| |
thread-2 --> BUFFER -->| DATA |
| |
thread-n --> BUFFER -->|--------|
线程1~n分析数据，并将数据写入各自的buffer
线程x从这些buffer中获取数据，并做相关处理
这样做的好处是只要处理好线程对BUFFER读写操作（如：用环形缓存）
就能实现lockless的构建
On 11月10日, 下午5时56分, 杨光 <yangguang2...@gmail.com> wrote:
> 使用多线程。1线程从文件里读去电话号码，放入一个BUFFER。2线程处理BUFFER，写入文件（比较号码内存表）。写过的号码放入一个内存表里（该线程可-以多个）。
>
> 2009/9/4 关中刀客 <guanzhongda...@gmail.com>
>
>
>
> > 我近期将要做一个类似的功能，以实际的考察我分析说说我的看法吧，对于定制的需求，如从文件中查找email,tel等，我认为没有必要在程序里面直接
> > 的处理，这方面的需求可能会不断的改变更加，好的做法还是用脚本去实现，程序将数据传递给不同的脚本，这些脚本根据功能去分析自己关心的数据即可。读文
> > 件没有什么可说的了，多个线程，不断的读。对于插入的话，直接的字符串判断插入不是很好，可以先哈希一下判断，在插入。
>
> > On 9月4日, 下午3时20分, chuang <lichuang1...@gmail.com> wrote:
> > > 扫描文件为了加速, 可以使用多线程来进行扫描.
> > > 扫描之后得到的号码必然要存放到进行排重操作的.
>
> > > 所以,我的思路是,开多线程进行文件的扫描,线程间有一个大家都可以访问的内存区,扫描之后的号码要到这个区域进行排重操作.
> > > 而这个区域的数据结构的选择, 目前看来似乎不能用位图了,那就用hash好了.
>
> > > 2009/9/4 samana <smit...@gmail.com>
>
> > > > "在一个无序大数组里，剔除重复数的高效算法".从狭义上可以这么理解。
> > > > 但是从这个实际题目上，无序数组里的数据是分布在50,000文件里，按照你讲的思路就是先将文件里的数据全部导入一个数据集合中，这种想法没错
> > > > 我先说下我的思路，抛砖引玉吧。
> > > > 1.文件挑选。将文件分组，利用线程池机制检索文件是否含有电话号码，有则标记
> > > > 2.数据集合。确定后含有电话号码的文件后，是先将所有电话号码放入数据集合进行唯一剔除
> > > > 3.剔除算法。在一个数据集合里，如何更有效的挑出唯一的电话号码并生成一个html文件
>
> > > > On 9月4日, 下午2时49分, qiaojie <qiao...@gmail.com> wrote:
>
> > 随便鄙视别人是不对的。这是一道很有现实意义的工程问题，可以考察的地方很多，如果我是面试官的话，除了考察他的算法能力，还可以从他思考的全面性以及实现的细--节上全面的考察他的工程经验。
> > > - 显示引用的文字 -- 隐藏被引用文字 -
>
> - 显示引用的文字 -
张沈鹏
NAME
uniq - report or omit repeated lines
SYNOPSIS
uniq [OPTION]... [INPUT [OUTPUT]]
DESCRIPTION
Filter adjacent matching lines from INPUT (or standard input), writing to OUTPUT (or
standard output).
With no options, matching lines are merged to the first occurrence.
Mandatory arguments to long options are mandatory for short options too.
-c, --count
prefix lines by the number of occurrences
-d, --repeated
only print duplicate lines
-D, --all-repeated[=delimit-method]
print all duplicate lines delimit-method={none(default),prepend,separate} Delim‐
iting is done with blank lines.
-f, --skip-fields=N
avoid comparing the first N fields
-i, --ignore-case
ignore differences in case when comparing
-s, --skip-chars=N
avoid comparing the first N characters
-u, --unique
only print unique lines
-z, --zero-terminated
end lines with 0 byte, not newline
-w, --check-chars=N
compare no more than N characters in lines
--help display this help and exit
--version
output version information and exit
A field is a run of blanks (usually spaces and/or TABs), then non-blank characters.
Fields are skipped before chars.
Note: 'uniq' does not detect repeated lines unless they are adjacent. You may want to
sort the input first, or use `sort -u' without `uniq'. Also, comparisons honor the
rules specified by `LC_COLLATE'.
AUTHOR
Written by Richard M. Stallman and David MacKenzie.
REPORTING BUGS
Report uniq bugs to bug-co...@gnu.org
GNU coreutils home page: <http://www.gnu.org/software/coreutils/>
General help using GNU software: <http://www.gnu.org/gethelp/>
Report uniq translation bugs to <http://translationproject.org/team/>
COPYRIGHT
Copyright © 2009 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or
later <http://gnu.org/licenses/gpl.html>.
This is free software: you are free to change and redistribute it. There is NO WAR‐
RANTY, to the extent permitted by law.
SEE ALSO
comm(1), join(1)
The full documentation for uniq is maintained as a Texinfo manual. If the info and uniq
programs are properly installed at your site, the command
info coreutils 'uniq invocation'
should give you access to the complete manual.
GNU coreutils 8.0 November 2009 UNIQ(1)
Manual page uniq(1) line 56
