Commit4566e64

AviAvni

authored and

cartermp

committed

remove allocations from jaro (dotnet#6050)

* remove allocations from jaro* improve perforamce* fix build* remove string concat allocations from FilterPredictions* fix build* move to struct tuple and remove the concat completely* undo

1 parent9b55ecc commit4566e64Copy full SHA for 4566e64

File tree

2 files changed

+40

-27

lines changed

src
- fsharp
  - ErrorResolutionHints.fs
- utils
  - EditDistance.fs

2 files changed

+40

-27

lines changed

`‎src/fsharp/ErrorResolutionHints.fs‎`

Lines changed: 2 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -43,6 +43,7 @@ let FilterPredictions (idText:string) (suggestionF:ErrorLogger.Suggestions) =`
`43`	`43`	`name\|> Seq.forall(fun c-> c<>' ')`
`44`	`44`
`45`	`45`	`if allSuggestions.Contains idTextthen[]else// some other parsing error occurred`
	`46`	`+letdotIdText="."+ idText`
`46`	`47`	`allSuggestions`
`47`	`48`	`\|> Seq.choose(fun suggestion->`
`48`	`49`	`// Because beginning a name with _ is used both to indicate an unused`
`@@ -53,7 +54,7 @@ let FilterPredictions (idText:string) (suggestionF:ErrorLogger.Suggestions) =`
`53`	`54`	`letsuggestion:string= demangle suggestion`
`54`	`55`	`letsuggestedText= suggestion.ToUpperInvariant()`
`55`	`56`	`letsimilarity= EditDistance.JaroWinklerDistance uppercaseText suggestedText`
`56`		`-if similarity>= highConfidenceThreshold\|\| suggestion.EndsWithOrdinal("."+ idText)then`
	`57`	`+if similarity>= highConfidenceThreshold\|\| suggestion.EndsWithOrdinal(dotIdText)then`
`57`	`58`	`Some(similarity, suggestion)`
`58`	`59`	`elif similarity< minThresholdForSuggestions&& suggestedText.Length> minStringLengthForThresholdthen`
`59`	`60`	`None`

`‎src/utils/EditDistance.fs‎`

Lines changed: 38 additions & 26 deletions

Original file line number	Diff line number	Diff line change
`@@ -23,33 +23,45 @@ let jaro (s1: string) (s2: string) =`
`23`	`23`	`letmatchRadius=`
`24`	`24`	`letminLen= Math.Min(s1.Length, s2.Length)`
`25`	`25`	`minLen/2+ minLen%2`
`26`		`-`
`27`		`-// An inner function which recursively finds the number`
`28`		`-// of matched characters within the radius.`
`29`		`-letcommonChars(chars1:string)(chars2:string)=`
`30`		`-letresult= ResizeArray(chars1.Length)`
`31`		`-for i=0to chars1.Length-1do`
`32`		`-letc= chars1.[i]`
`33`		`-if existsInWin c chars2 i matchRadiusthen`
`34`		`- result.Add c`
`35`		`- result`
`36`		`-`
`37`		`-// The sets of common characters and their lengths as floats`
`38`		`-letc1= commonChars s1 s2`
`39`		`-letc2= commonChars s2 s1`
`40`		`-letc1length= float c1.Count`
`41`		`-letc2length= float c2.Count`
`42`		`-`
	`26`	`+`
	`27`	`+let recnextChar(s1:string)(s2:string)i c=`
	`28`	`+if i< s1.Lengththen`
	`29`	`+letc= s1.[i]`
	`30`	`+ifnot(existsInWin c s2 i matchRadius)then`
	`31`	`+ nextChar s1 s2(i+1) c`
	`32`	`+else`
	`33`	`+struct(i, c)`
	`34`	`+else`
	`35`	`+struct(i, c)`
	`36`	`+`
	`37`	`+// The sets of common characters and their lengths as floats`
`43`	`38`	`// The number of transpositions within the sets of common characters.`
`44`		`-lettranspositions=`
`45`		`-let mutablemismatches=0.0`
`46`		`-for i=0to(Math.Min(c1.Count, c2.Count))-1do`
`47`		`-if c1.[i]<> c2.[i]then`
`48`		`- mismatches<- mismatches+1.0`
`49`		`-`
`50`		`-// If one common string is longer than the other`
`51`		`-// each additional char counts as half a transposition`
`52`		`-(mismatches+ abs(c1length- c2length))/2.0`
	`39`	`+letstruct(transpositions,c1length,c2length)=`
	`40`	`+let recloop i j mismatches c1length c2length=`
	`41`	`+if i< s1.Length&& j< s2.Lengththen`
	`42`	`+letstruct(ti,ci)= nextChar s1 s2 i' '`
	`43`	`+letstruct(tj,cj)= nextChar s2 s1 j' '`
	`44`	`+if ci<> cjthen`
	`45`	`+ loop(ti+1)(tj+1)(mismatches+1)(c1length+1)(c2length+1)`
	`46`	`+else`
	`47`	`+ loop(ti+1)(tj+1) mismatches(c1length+1)(c2length+1)`
	`48`	`+elsestruct(i, j, mismatches, c1length, c2length)`
	`49`	`+`
	`50`	`+letstruct(i,j,mismatches,c1length,c2length)= loop00000`
	`51`	`+`
	`52`	`+let recloop(s1:string)(s2:string)i length=`
	`53`	`+if i< s1.Length-1then`
	`54`	`+letc= s1.[i]`
	`55`	`+if existsInWin c s2 i matchRadiusthen`
	`56`	`+ loop s1 s2(i+1)(length+1)`
	`57`	`+else`
	`58`	`+ loop s1 s2(i+1) length`
	`59`	`+else`
	`60`	`+ length`
	`61`	`+letc1length= loop s1 s2 i c1length\|> float`
	`62`	`+letc2length= loop s2 s1 j c2length\|> float`
	`63`	`+`
	`64`	`+struct((float mismatches+ abs(c1length- c2length))/2.0, c1length, c2length)`
`53`	`65`
`54`	`66`	`lettLength= Math.Max(c1length, c2length)`
`55`	`67`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit4566e64

File tree

2 files changed

2 files changed

`‎src/fsharp/ErrorResolutionHints.fs‎`

`‎src/utils/EditDistance.fs‎`

0 commit comments