Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

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

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitc46aa23

Browse files
committed
Perf improvement for Seq.windowed, adapted from suggestion originally by Jon Harrop
For larger windows, Array.Copy is *much* faster than Array.init. For smaller windows, Array.init is faster. Threshold of 32 is based on testing with various data types on various hardware - goal is to err on the high side for the threshold, so that at least nobody encounters a perf regression due to this change.Also added to the unit tests for Seq.windowed, which were a bit light. (changeset 1258476)
1 parent301a6f3 commitc46aa23

File tree

2 files changed

+86
-29
lines changed
  • src/fsharp

2 files changed

+86
-29
lines changed

‎src/fsharp/FSharp.Core.Unittests/FSharp.Core/Microsoft.FSharp.Collections/SeqModule2.fs‎

Lines changed: 68 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,14 @@ open NUnit.Framework
77

88
openFSharp.Core.Unittests.LibraryTestFx
99

10+
typeSeqWindowedTestInput<'t>=
11+
{
12+
InputSeq:seq<'t>
13+
WindowSize:int
14+
ExpectedSeq:seq<'t[]>
15+
Exception:Type option
16+
}
17+
1018
[<TestFixture>]
1119
typeSeqModule2()=
1220

@@ -1114,24 +1122,66 @@ type SeqModule2() =
11141122

11151123
[<Test>]
11161124
memberthis.Windowed()=
1117-
// integer Seq
1118-
letresultInt= Seq.windowed5(seq[1..10])
1119-
letexpectedInt=
1120-
seq{for iin1..6do
1121-
yield[| i; i+1; i+2; i+3; i+4|]}
1122-
VerifySeqsEqual expectedInt resultInt
1123-
1124-
// string Seq
1125-
letresultStr=Seq.windowed2(seq["str1";"str2";"str3";"str4"])
1126-
letexpectedStr= seq[[|"str1";"str2"|];[|"str2";"str3"|];[|"str3";"str4"|]]
1127-
VerifySeqsEqual expectedStr resultStr
1128-
1129-
// empty Seq
1130-
letresultEpt= Seq.windowed2 Seq.empty
1131-
VerifySeqsEqual Seq.empty resultEpt
1132-
1133-
// null Seq
1134-
CheckThrowsArgumentNullException(fun()-> Seq.windowed2null|> ignore)
1125+
1126+
lettestWindowed config=
1127+
try
1128+
config.InputSeq
1129+
|> Seq.windowed config.WindowSize
1130+
|> VerifySeqsEqual config.ExpectedSeq
1131+
with
1132+
|_when Option.isNone config.Exception-> Assert.Fail()
1133+
| ewhen e.GetType()=(Option.get config.Exception)->()
1134+
|_-> Assert.Fail()
1135+
1136+
{
1137+
InputSeq= seq[1..10]
1138+
WindowSize=1
1139+
ExpectedSeq=seq{for iin1..10doyield[| i|]}
1140+
Exception= None
1141+
}|> testWindowed
1142+
{
1143+
InputSeq= seq[1..10]
1144+
WindowSize=5
1145+
ExpectedSeq=seq{for iin1..6doyield[| i; i+1; i+2; i+3; i+4|]}
1146+
Exception= None
1147+
}|> testWindowed
1148+
{
1149+
InputSeq= seq[1..10]
1150+
WindowSize=10
1151+
ExpectedSeq=seq{yield[|1..10|]}
1152+
Exception= None
1153+
}|> testWindowed
1154+
{
1155+
InputSeq= seq[1..10]
1156+
WindowSize=25
1157+
ExpectedSeq= Seq.empty
1158+
Exception= None
1159+
}|> testWindowed
1160+
{
1161+
InputSeq= seq["str1";"str2";"str3";"str4"]
1162+
WindowSize=2
1163+
ExpectedSeq= seq[[|"str1";"str2"|];[|"str2";"str3"|];[|"str3";"str4"|]]
1164+
Exception= None
1165+
}|> testWindowed
1166+
{
1167+
InputSeq= Seq.empty
1168+
WindowSize=2
1169+
ExpectedSeq= Seq.empty
1170+
Exception= None
1171+
}|> testWindowed
1172+
{
1173+
InputSeq=null
1174+
WindowSize=2
1175+
ExpectedSeq= Seq.empty
1176+
Exception= Some typeof<ArgumentNullException>
1177+
}|> testWindowed
1178+
{
1179+
InputSeq= seq[1..10]
1180+
WindowSize=0
1181+
ExpectedSeq= Seq.empty
1182+
Exception= Some typeof<ArgumentException>
1183+
}|> testWindowed
1184+
11351185
()
11361186

11371187
[<Test>]

‎src/fsharp/FSharp.Core/seq.fs‎

Lines changed: 18 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1185,17 +1185,24 @@ namespace Microsoft.FSharp.Collections
11851185
letwindowed windowSize(source:seq<_>)=
11861186
checkNonNull"source" source
11871187
if windowSize<=0then invalidArg"windowSize"(SR.GetString(SR.inputMustBeNonNegative))
1188-
seq{letarr= Microsoft.FSharp.Primitives.Basics.Array.zeroCreateUnchecked windowSize
1189-
letr= ref(windowSize-1)
1190-
leti= ref0
1191-
use e= source.GetEnumerator()
1192-
while e.MoveNext()do
1193-
arr.[!i]<- e.Current
1194-
i:=(!i+ 1)% windowSize
1195-
if!r=0then
1196-
yield Array.init windowSize(fun j-> arr.[(!i+j)% windowSize])
1197-
else
1198-
r:=(!r- 1)}
1188+
seq{
1189+
letarr= Array.zeroCreateUnchecked windowSize
1190+
letr= ref(windowSize-1)
1191+
leti= ref0
1192+
use e= source.GetEnumerator()
1193+
while e.MoveNext()do
1194+
arr.[!i]<- e.Current
1195+
i:=(!i+ 1)% windowSize
1196+
if!r=0then
1197+
if windowSize<32then
1198+
yield Array.init windowSize(fun j-> arr.[(!i+j)% windowSize])
1199+
else
1200+
letresult= Array.zeroCreateUnchecked windowSize
1201+
Array.Copy(arr,!i, result,0, windowSize-!i)
1202+
Array.Copy(arr,0, result, windowSize-!i,!i)
1203+
yield result
1204+
else r:=(!r- 1)
1205+
}
11991206

12001207
[<CompiledName("Cache")>]
12011208
letcache(source:seq<'T>)=

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp