1 #Region "Microsoft.VisualBasic::ab2db79bacb79aed10ef42e61443e47e, Microsoft.VisualBasic.Core\Extensions\Math\NumberGroups.vb"
2
3     ' Author:
4     
5     '       asuka (amethyst.asuka@gcmodeller.org)
6     '       xie (genetics@smrucc.org)
7     '       xieguigang (xie.guigang@live.com)
8     
9     ' Copyright (c) 2018 GPL3 Licensed
10     
11     
12     ' GNU GENERAL PUBLIC LICENSE (GPL3)
13     
14     
15     ' This program is free software: you can redistribute it and/or modify
16     ' it under the terms of the GNU General Public License as published by
17     ' the Free Software Foundation, either version 3 of the License, or
18     ' (at your option) any later version.
19     
20     ' This program is distributed in the hope that it will be useful,
21     ' but WITHOUT ANY WARRANTY; without even the implied warranty of
22     ' MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23     ' GNU General Public License for more details.
24     
25     ' You should have received a copy of the GNU General Public License
26     ' along with this program. If not, see <http://www.gnu.org/licenses/>.
27
28
29
30     ' /********************************************************************************/
31
32     ' Summaries:
33
34     '     Module NumberGroups
35     
36     '         Function: BinarySearch, (+2 Overloads) GroupBy, GroupByImpl, Groups, Match
37     '                   Min
38     '         Interface IVector
39     
40     '             Properties: Data
41     
42     '         Class Average
43     
44     '             Properties: Average
45     
46     '             Constructor: (+2 OverloadsSub New
47     '             FunctionToString
48     '             Operators: +
49     
50     
51     
52     '     Interface INumberTag
53     
54     '         Properties: Tag
55     
56     
57     ' /********************************************************************************/
58
59 #End Region
60
61 Imports System.Runtime.CompilerServices
62 Imports Microsoft.VisualBasic.ComponentModel.DataSourceModel
63 Imports Microsoft.VisualBasic.ComponentModel.TagData
64 Imports Microsoft.VisualBasic.Language
65 Imports Microsoft.VisualBasic.Linq
66 Imports Microsoft.VisualBasic.Math.Statistics
67 Imports Microsoft.VisualBasic.Parallel
68
69 Namespace Math
70
71     ''' <summary>
72     ''' Simple number vector grouping
73     ''' </summary>
74     Public Module NumberGroups
75
76         ''' <summary>
77         ''' The numeric vector model
78         ''' </summary>
79         Public Interface IVector
80             ReadOnly Property Data As Double()
81         End Interface
82
83         <Extension>
84         Public Function Match(Of T As IVector)(a As IEnumerable(Of T), b As IEnumerable(Of T)) As Double
85             Dim target As New List(Of T)(a)
86             Dim mins = b.Select(Function(x) target.Min(x))
87             Dim result As Double = mins.Sum(Function(tt) tt.Tag)
88
89             With target
90                 For Each x In mins.Select(Function(o) o.Value)
91                     Call .Remove(item:=x)
92                     If .Count = 0 Then
93                         Exit For
94                     End If
95                 Next
96             End With
97
98             Return result * (target.Count + 1)
99         End Function
100
101         ''' <summary>
102         ''' 计算出<paramref name="target"/>集合之众的与<paramref name="v"/>距离最小的元素
103         ''' (或者说是匹配度最高的元素)
104         ''' </summary>
105         ''' <typeparam name="T"></typeparam>
106         ''' <param name="target"></param>
107         ''' <param name="v"></param>
108         ''' <returns></returns>
109         <Extension>
110         Public Function Min(Of T As IVector)(target As IEnumerable(Of T), v As T) As DoubleTagged(Of T)
111             Dim minV# = Double.MaxValue
112             Dim minX As T
113             Dim vector#() = v.Data
114
115             For Each x As T In target
116                 Dim d# = x.Data.EuclideanDistance(vector)
117
118                 If d < minV Then
119                     minV = d
120                     minX = x
121                 End If
122             Next
123
124             Return New DoubleTagged(Of T) With {
125                 .Tag = minV,
126                 .Value = minX
127             }
128         End Function
129
130         ''' <summary>
131         ''' Returns ``-1`` means no search result
132         ''' </summary>
133         ''' <param name="seq"></param>
134         ''' <param name="target#"></param>
135         ''' <param name="equals"></param>
136         ''' <returns></returns>
137         <Extension>
138         Public Function BinarySearch(seq As IEnumerable(Of Double), target#, equals As GenericLambda(Of Double).IEquals) As Double
139             With seq _
140                 .SeqIterator _
141                 .OrderBy(Function(x) x.value) _
142                 .ToArray
143
144                 Dim x As SeqValue(Of Double)
145                 Dim min% = 0
146                 Dim max% = .Length - 1
147                 Dim index%
148                 Dim value#
149
150                 If max = -1 Then
151                     ' no elements
152                     Return -1
153                 ElseIf max = 0 Then
154                     ' one element
155                     If equals(.ByRef(0).value, target) Then
156                         Return 0
157                     Else
158                         ' 序列只有一个元素,但是不相等,则返回-1,否则后面的while会无限死循环
159                         Return -1
160                     End If
161                 End If
162
163                 Do While max <> (min + 1)
164                     index = (max - min) / 2 + min
165                     x = .ByRef(index)
166                     value = x.value
167
168                     If equals(target, value) Then
169                         Return x.i
170                     ElseIf target > value Then
171                         min = index
172                     Else
173                         max = index
174                     End If
175                 Loop
176
177                 If equals(.ByRef(min).value, target) Then
178                     Return .ByRef(min).i
179                 ElseIf equals(.ByRef(max).value, target) Then
180                     Return .ByRef(max).i
181                 Else
182                     Return -1
183                 End If
184             End With
185         End Function
186
187         ''' <summary>
188         ''' 将一维的数据按照一定的偏移量分组输出
189         ''' </summary>
190         ''' <param name="source"></param>
191         ''' <returns></returns>
192         <Extension> Public Iterator Function GroupBy(Of T)(source As IEnumerable(Of T),
193                                                            evaluate As Func(Of T, Double),
194                                                            equals As GenericLambda(Of Double).IEquals,
195                                                            Optional parallel As Boolean = FalseAs IEnumerable(Of NamedCollection(Of T))
196             If Not parallel Then
197
198                 For Each group In source.AsList.GroupByImpl(evaluate, equals)
199                 '     Yield group
200                 Next
201
202                 ' 先进行预处理:求值然后进行排序
203                 Dim tagValues = source _
204                     .Select(Function(o) (evaluate(o), o)) _
205                     .OrderBy(Function(o) o.Item1) _
206                     .ToArray
207                 Dim means As New Average
208                 Dim members As New List(Of T)
209
210                 ' 根据分组的平均值来进行分组操作
211                 For Each x As (val#, o As T) In tagValues
212                     If means.N = 0 Then
213                         means += x.Item1
214                         members += x.Item2
215                     Else
216                         If equals(means.Average, x.Item1) Then
217                             means += x.Item1
218                             members += x.Item2
219                         Else
220                             Yield New NamedCollection(Of T)(CStr(means.Average), members)
221
222                             means = New Average({x.Item1})
223                             members = New List(Of T) From {x.Item2}
224                         End If
225                     End If
226                 Next
227
228                 If members > 0 Then
229                     Yield New NamedCollection(Of T)(CStr(means.Average), members)
230                 End If
231             Else
232                 Dim partitions = source _
233                     .SplitIterator(20000) _
234                     .AsParallel _
235                     .Select(Function(part)
236                                 Return part.AsList.GroupByImpl(evaluate, equals)
237                             End Function) _
238                     .IteratesALL _
239                     .AsList
240
241                 ' 先分割,再对name做分组
242                 Dim union = partitions.GroupByImpl(Function(part) Val(part.Name), equals)
243
244                 For Each unionGroup In union
245                     Dim name$ = unionGroup.Name
246                     Dim data = unionGroup _
247                         .Value _
248                         .Select(Function(member) member.Value) _
249                         .IteratesALL _
250                         .ToArray
251
252                     Yield New NamedCollection(Of T) With {
253                         .Name = name,
254                         .Value = data
255                     }
256                 Next
257             End If
258         End Function
259
260         <Extension>
261         Private Function GroupByImpl(Of T)(source As List(Of T), evaluate As Func(Of T, Double), equals As GenericLambda(Of Double).IEquals) As NamedCollection(Of T)()
262             Dim tmp As New With {
263                 .avg = New Average({}),
264                 .list = New List(Of T)
265             }
266             Dim groups = {
267                 tmp
268             }.AsList * 0
269
270             Do While source.Count > 0
271                 Dim x As T = source.Pop
272                 Dim value# = evaluate(x)
273                 Dim hit% = groups _
274                     .Select(Function(g)
275                                 Return g.avg.Average
276                             End Function) _
277                     .BinarySearch(value, equals)
278
279                 ' 在这里应该使用二分法查找来加快计算速度的
280                 If hit > -1 Then
281                     With groups(hit)
282                         .avg += value
283                         .list.Add(x)
284                     End With
285                 Else
286                     groups += New With {
287                         .avg = New Average({value}),
288                         .list = New List(Of T) From {x}
289                     }
290                 End If
291             Loop
292
293             Return groups _
294                 .Select(Function(tuple)
295                             Return New NamedCollection(Of T) With {
296                                 .Name = tuple.avg.Average,
297                                 .Value = tuple.list
298                             }
299                         End Function) _
300                 .OrderBy(Function(tuple) Val(tuple.Name)) _
301                 .ToArray
302         End Function
303
304         ''' <summary>
305         ''' 将一维的数据按照一定的偏移量分组输出
306         ''' </summary>
307         ''' <param name="source"></param>
308         ''' <param name="offsets"></param>
309         ''' <returns></returns>
310         ''' 
311         <MethodImpl(MethodImplOptions.AggressiveInlining)>
312         <Extension> Public Function GroupBy(Of T)(source As IEnumerable(Of T), evaluate As Func(Of T, Double), offsets#) As NamedCollection(Of T)()
313             Return source.GroupBy(evaluate, equals:=Function(a, b) Abs(a - b) <= offsets)
314         End Function
315
316         ''' <summary>
317         ''' 按照相邻的两个数值是否在offset区间内来进行简单的分组操作
318         ''' </summary>
319         ''' <typeparam name="TagObject"></typeparam>
320         ''' <param name="source"></param>
321         ''' <param name="offset"></param>
322         ''' <returns></returns>
323         <Extension>
324         Public Function Groups(Of TagObject As INumberTag)(source As IEnumerable(Of TagObject), offset As IntegerAs GroupResult(Of TagObject, Integer)()
325             Dim list As New List(Of GroupResult(Of TagObject, Integer))
326             Dim orders As TagObject() = (From x As TagObject
327                                          In source
328                                          Select x
329                                          Order By x.Tag Ascending).ToArray
330             Dim tag As TagObject = orders(Scan0)
331             Dim tmp As New List(Of TagObject) From {tag}
332
333             For Each x As TagObject In orders.Skip(1)
334                 If x.Tag - tag.Tag <= offset Then  ' 因为已经是经过排序了的,所以后面总是大于前面的
335                     tmp += x
336                 Else
337                     tag = x
338                     list += New GroupResult(Of TagObject, Integer)(tag.Tag, tmp)
339                     tmp = New List(Of TagObject) From {x}
340                 End If
341             Next
342
343             If tmp.Count > 0 Then
344                 list += New GroupResult(Of TagObject, Integer)(tag.Tag, tmp)
345             End If
346
347             Return list
348         End Function
349     End Module
350
351     Public Interface INumberTag
352         ReadOnly Property Tag As Integer
353     End Interface
354 End Namespace