Page 1 of 1

How sometimes what you require, is a different algorithm. Rate Topic: -----

#1 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2216
  • View blog
  • Posts: 9,352
  • Joined: 29-May 08

Posted 16 March 2013 - 12:36 AM

How sometimes what you require, is a different algorithm.


Let's say we have a balance binary tree and we want to yield (iterate) all the nodes in order.
Interface IBalancedTreeNode(Of T)
  ReadOnly Property Value As T
  Property Left As IBalancedTreeNode(Of T)
  Property Righ As IBalancedTreeNode(Of T)
End Interface



Let's take the simple recursive approach
<Extension>
Public Iterator YieldNode(Of T)( node As IBalancedTreeNode(Of T)) As IEnumerable(Of IBalancedTreeNode(Of T))
  IF node Is Nothing Then Exit Function
  For Each node In node.Left.YieldNodes
    Yield node
  Next
  Yield node
  For Each node In node.Righ.YieldNodes
    Yield node
  Next
End Function



Really simple to follow arithmetically , but has the issue that you are repeatedly yielding the same node(s).




A Solution would be that have some way of passing as parameter "the yield" when you do the recursion

Imaginary VB.net
extension public iterator function YieldNodes(of T)
  ( node As IBalancedTreeNode(Of T)
  ) As IEnumerable(Of IBalancedTreeNode(Of T))
  return _YieldNodes(of T)( node, ThisMethod.Yielder )
end function

extension private iterator function
  _YieldNodes (Of T)(Node As IBalancedTreeNode(of T),
            ByRef yielder As Yield(Of
                                      IEnumerable(Of IBalancedTreeNode(Of T))
                                  )
                    ) As IEnumerable(Of IBalancedTreeNode(of T))
  If node Is Nothing Then Exit Function
  If node.Left IsNot Nothing Then node.YieldNodes( yielder )
  Yielder.Yield node
  If node.Righ IsNot Nothing Then Node.YieldNodes( yielder )
end function



Now the yield algorithm is Linear, but I have yet to find a way to implement this design.

So this means a change of algorithm to fit in with restrictions of the language.




<Extension>
  Iterator Function YieldNodes(Of T)
    ( Current As IBalancedTreeNode(Of T)
    ) As IEnumerable(Of IBalancedTreeNode(Of T))

    If Current IsNot Nothing Then Exit Function
    Dim TheStack As New Stack(Of BalancedTreeNode(Of T) )
 
   Do

      While Current IsNot Nothing
        TheStack.Put( Current )
        Current = Current.Left
      End While

      If TheStack.Count > 0 Then
        Dim Popped = TheStack.Pop
        Yield Popped
        Current = Popped.Righ
      End If

    Loop Until (Current Is Nothing) AndAlso (TheStack.Count = 0)

  End Function



Slightly more complex algorithm to understand, but has the advantage of linearizing the yielding of nodes.




Conclusion

Think about how the programming language can effect the implementation of your algorithm.
Also think how the implementation can effect the running time of the algorithm.

Is This A Good Question/Topic? 0
  • +

Page 1 of 1