求助一个函数的精简，请教怎么提升这个函数的效率，当个课题吧 ：）

maker

回复 15# dtooboss


    上层函数已经包含多进程控制了，这个本身已经是多进程中的函数了。。。

supersp

楼主1楼的代码,似乎距离算的多了..
我的跟4楼的算的一样..
时间好像很长啊,30ms一个较长的字符串..
下面这个算法只有一个算距离的方法,相似度转换一下就可以

#include <Math.au3>
#Include <Array.au3>


$S ='1000101011001110101010011000'
$P ='011100000110011111101000110100010000'
MsgBox (0,"",execSTR($s,$p))


Func execSTR($strA, $strB);返回字符距离
        $lenA = StringLen($strA)
        $lenB = StringLen($strB)
        Dim $c[$lenA+1][$lenB+1]

        For $i=0 To $lenA-1 Step 1 
                $c[$i][$lenB]= $lenA - $i
        Next
        For $j=0 To $lenB-1 Step 1
                $c[$lenA][$j] = $lenB - $j
        Next
        $c[$lenA][$lenB] = 0


        For $i = $lenA-1 To 0 Step -1
                For $j = $lenB-1 To 0 Step -1
                        if(StringMid($strB,$j,1) == StringMid($strA,$i,1)) Then
                                $c[$i][$j] = $c[$i+1][$j+1]
                        else
                                $c[$i][$j] = minValue($c[$i][$j+1], $c[$i+1][$j], $c[$i+1][$j+1]) + 1
                        EndIf
                Next
        Next
;        _ArrayDisplay($c)
        return $c[0][0]
EndFunc

Func minValue($a,$b,$c)
        Return _Min(_Min($a,$b),_Min($a,$c))
EndFunc

maker

回复 17# supersp


    怎么我检测完整个文档都34秒多了，是不是我太笨了，用的不对？

supersp

额,是很慢...
写代码之前没预知到..每次检测循环的次数 Len1+len2+len1*len2 ,并不算多..
但不知道到底是哪一步影响了速度,  数组问题,是StringMid影响了耗时..

另外，楼主的代码我怎么测试不对呢。。
难道我的相似度理解错了?

对于“123456a”和“123456”两个字符串,，增加/减少一个“a”,仅需要一 次就相等。这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离+1”的倒数。也就是说，“123456a”和“123456”的距离为1，相似度 为1/2=0.5 , 不是么?
按楼主的*100算, 完全相同的是100,操作一次的应该是50,操作2次的应该是33 才对啊..

afan

额,是很慢...
写代码之前没预知到..每次检测循环的次数 Len1+len2+len1*len2 ,并不算多..
但不知道到底是 ...
supersp 发表于 2010-4-15 09:39

123456a = 7个字符
123456 = 6个字符
位置相同的有6个字符，它们的相似度就是 6/7*100=86

123456a = 7个字符
123475 = 6个字符
位置相同的有4个字符，它们的相似度就是 4/7*100=57 ，我是这样理解的

lainline

我有个主意不知道行不行

1、把被搜索字符串格式化成固定长度
2、把被搜索字符串合并为一个字符串
3、搜索目标字符串能搜到特定位置评分加100
3、把目标字符串拆分为两个字符串分别搜索 如果能搜到 评分加100/2
4、把目标字符串拆分为三个字符串分别搜索 能搜到评分加100/3
一直继续
直到拆分的字符串剩余两个

我觉得应该尽早读取并关闭文件把文件内容导入内存 而不使用FileReadLine($mfile)这句要读硬盘影响速度

maker

回复 19# supersp


很抱歉因为我的疏忽浪费大家时间了，我把我的算法写入一楼了

maker

回复 21# lainline


   你好， 我觉得读文件影响的速度远不如计算比率占用时间长

之前也有考虑过用规范字串长度，但是因为像素取值是固定，且取值数组维度不同，故没有用得上，后期处理规范更会影响原始正确率

supersp

咳..根据那个俄国某某科学家提出的..
字符距离指的是编辑次数..
123a456787
1234567
只要3次操作,插如"a",添加8,添加7..
或者删除"a",删除"8",删除"7"
所以距离是3..

你的4次操作分别是3/7 , 4/7 , 0 , 1/7...不知道怎么转化成相似度的
如果按照你们的理解, 是字符串中百分之多少的字符相似?
那么应该是 (长串-距离)/长串?

lxz

学习一下.....

maker

回复 24# supersp


    你好，我取(相同个数/短串)是考虑实际环境的，因为字串长的会多出干扰元素，短串更接近实际正确标示

netegg

回复 1# maker
能不能具体说说你所指的相似度指的是什么

maker

回复 27# netegg


    呵呵，相似度就是相同字符个数在整个字串中的占有率，取最大相同数和短串长度来计算，比较的时候字串不能穿插字符和删减字符，以短串整行移动步进做比较

supersp

如果是这样..
你的0,1组合的字符串..
完全可以当做二进制数来运算
步进可以<<的方式进行, 然后进行 XOR 运算, 再求出结果中的0的连续位数,可轻松得出相同长度..
这样,检查一个字符串, 只需要步进的循环次数..

maker

回复 29# supersp


    恩，只有0和1，只是我对进制转换、逻辑运算不熟悉，也没想出怎么处理来