日期:2014-05-18  浏览次数:20787 次

算法效率问题求解
有2万多个字符串,每个都是32字符长,现在要编写一个程序将他们两两比较找出其中所有相同的,我算了一下要比较4亿多次。即使1毫秒比较一次也要100个小时。。。
重算法上讲有没有办法将比较时间保证在1小时内的?

------解决方案--------------------
他们两两比较找出其中所有相同的
---只要求找出其中相同的吗?如果题目只让你找出其中相同的,没必要两两比较,你可以先进行排序啊!按字符asc码什么的进行排序,快速排序时间复杂度O(nlgn),桶排序O(n)
对排好序的进行字符串,从头到尾的扫描一遍,复杂度O(n)

比你两两比较O(n*n)好多了

一毫秒比较一次,你从哪搞来的....
------解决方案--------------------
这个问题我已经做过,大概几分钟就算完了吧。

我当时用了dictionary 字典,每找到一个和其他的不同的,就放到字典中,并记录是第几个字符串
.....


大概2-3分钟就好了。
------解决方案--------------------
1毫秒比较一次?开玩笑了,你当计算机是人脑啊,1毫秒起码可以比较1万次的。至于效率,就看你用什么来存放了,往往开销是用在了内存的分配上和IO的读取上的。
------解决方案--------------------
用 字典:

创建字典的两个方法
1 引用 c:\windows\system32\scrrun.dll 然后 dim d as new Dictionary
2 Set d = CreateObject("Scripting.Dictionary")
字典的四个属性
CompareMode 决定key的比较方法 BinaryCompare(默认方法) 二进制方式比较,即a,A是不同字符
TextCompare '文本方式比较,即a,A是相同字符
vbDatabaseCompare 仅用于 Microsoft Access。进行基于您自己数据库中信息的比较。
如果用recordset做key的话vbDatabaseCompare方式就有用了,因为用的少没有测试过
Count 计算字典中的条目数量 s = d.count s 是一个long值
Key 也就是Item的代码通常是整数或字符串,可以是除数组外的任何类型,在一个字典中每一个key都是唯一的
一般利用这个特点去除重复值
Item 可以是任何对象(不含自定义数据):数字,字符串,数组,对象(窗体,控件,文件。。。。)
字典的六个方法
Add 向字典添加内容 d.add "a",10000,或 d("王先生")= "010-87654321"
向字典添加对象 set d("mysheet") = Sheet1 Set d("mybook") = ThisWorkbook
注意 set 关键字
Exists 判断keys中有没有要找的key,返回 true 或 false
s = d.exists("王先生"), s 是 true 因为上面已经添加了王先生
Keys 学过英文吧?Key的复数形式,返回一个一维数组 arr= d.keys
Items 同上 arr = d.items
Remove 按照key从字典中删除一个项目 d.remove("王先生")
RemoveAll 清空字典 d.RemoveAll 此时 d.count 为 0
字典简单,好学又好用 总共10种属性方法!
 
字典就像一个只有两列的表,字典的行数可以有多少?
取决于内存的大小。字典更像数据库,数组的混合体
字典的两个列的“名字” 分别是 “key” 和 “item”
key 是 item 的 “代号” 方便我们在程序中调用
key通常是整数或字符串,可以是除数组外的任何类型
注意数字1 和字符串“1”是不同的
item 可以把它想象成一个 垃圾桶 什么都可以 往里面装。
数字,字符串,数组,对象(窗体,控件,文件。。。。),

------解决方案--------------------
探讨
用 字典:

创建字典的两个方法
1 引用 c:\windows\system32\scrrun.dll 然后 dim d as new Dictionary
2 Set d = CreateObject("Scripting.Dictionary")
字典的四个属性
    CompareMode    决定key的比较方法 BinaryCompare(默认方法) 二进制方式比较,即a,A是不同字符
        TextCompare    '文本方式比较,即a,A是相同字符
        vbDatabaseCompare  仅用于 Microsoft Access。进行基于您自己数据库中信息的比较。
        如果用recordset做key的话vbDatabaseCompare方式就有用了,因为用的少没有测试过
    Count      计算字典中的条目数量  s = d.count  s 是一个long值
    Key    也就是Item的代码通常是整数或字符串,可以是除数组外的任何类型,在一个字典中每一个key都是唯一的
        一般利用这个特点去除重复值
    Item        可以是任何对象(不含自定义数据):数字,字符串,数组,对象(窗体,控件,文件。。。。)
字典的六个方法
    Add    向字典添加内容 d.add "a",10000,或 d("王先生")= "010-87654321"
        向字典添加对象 set d("mysheet") = Sheet1 Set d("mybook") = ThisWorkbook
        注意 set 关键字
    Exists      判断keys中有没有要找的key,返回 true 或 false
        s = d.exists("王先生"), s 是 true 因为上面已经添加了王先生
    Keys        学过英文吧?Key的复数形式,返回一个一维数组 arr= d.keys
    Items      同上  arr = d.items
    Remove      按照key从字典中删除一个项目 d.remove("王先生")