dcsimg
Results 1 to 16 of 16

Thread: [RESOLVED] Can someone fix my sorting algorithm up?

  1. #1

    Thread Starter
    Member
    Join Date
    Apr 2009
    Posts
    37

    Resolved [RESOLVED] Can someone fix my sorting algorithm up?

    This is kinda complicated for me to understand

    Code:
        Dim test() As Byte = New Byte() {50, 40, 30, 10, 10}
        Dim answer() As UInteger = SortLexicoGraphicallyArrayMappedFile(test)
    The answer is the each Rotation sorted from lowest array value to highest array value.

    Code:
    Rotation 0 = 50, 40, 30, 10, 10
    Rotation 1 = 10, 50, 40, 30, 10
    Rotation 2 = 10, 10, 50, 40, 30
    Rotation 3 = 30, 10, 10, 50, 40
    Rotation 4 = 40, 30, 10, 10, 50
    When I sort this array above by hand I should get

    Code:
    Rotation 2 = 10, 10, 50, 40, 30
    Rotation 1 = 10, 50, 40, 30, 10
    Rotation 3 = 30, 10, 10, 50, 40
    Rotation 4 = 40, 30, 10, 10, 50
    Rotation 0 = 50, 40, 30, 10, 10
    So the answer should be
    Code:
    2, 1, 3, 4, 0
    I get stuck in a infinite loop and I can't put my finger on it
    My Previous question works because the data is always static here I try to move all the data around all over the place which is probably why it gets stuck I can't figure out a workaround around that.. i need to move all the data around to save cpu time later that's why I didn't pick the answer from the page below.

    How to order array in lexicographical order vb.net

    Here is my Code

    Code:
    Public Function GetRotation(Data As Byte(), rotation As UInteger) As Byte()
       'Rotation Left
        Dim rotationData As New List(Of Byte)
    
        Dim start As UInteger = Data.Length - rotation Mod Data.Length
    
        For i = 0 To Data.Length - 1
            rotationData.Add(Data((start + i) Mod (Data.Length)))
        Next
    
        Return rotationData.ToArray()
    End Function
    
       Public Function SortLexicoGraphicallyArrayMappedFile(ByRef data As Byte()) As UInteger()
            Dim OrderedRotations As New List(Of UInteger)
            Dim rotatedData As Byte()
            Dim rotation As UInteger = 0
    
    
            Dim mmF As MemoryMappedFile
            mmF = MemoryMappedFile.CreateFromFile(My.Application.Info.DirectoryPath & "\outFile", FileMode.CreateNew, "test", CLng(data.LongLength * data.LongLength))
            Dim mmVA As MemoryMappedViewAccessor
            mmVA = mmF.CreateViewAccessor(0, data.LongLength * data.LongLength)
    
            Dim pos As Long = 0
    
            For rotation = 0 To data.Length - 1
                rotatedData = GetRotation(data, rotation)
                mmVA.WriteArray(Of Byte)(pos, rotatedData, 0, rotatedData.Length)
                pos += rotatedData.Length
    
            Next
    
            For rotation = 0 To data.Length - 1
                OrderedRotations.Add(rotation)
            Next
    
            Dim eachRotation As Integer = 0
            Dim data1() As Byte
            ReDim data1(data.Length - 1)
            Dim data2() As Byte
            ReDim data2(data.Length - 1)
            Dim index As Long
            For rotation = 0 To data.Length - 1
                Dim flag As Boolean
                Do
                    flag = False
                    For eachRotation = OrderedRotations.Count - 1 To 0 Step -1
                        mmVA.ReadArray(Of Byte)((OrderedRotations(rotation) * data.Length), data1, 0, data.Length)
                        If OrderedRotations(eachRotation) = OrderedRotations(rotation) Then Continue For
                        mmVA.ReadArray(Of Byte)((OrderedRotations(eachRotation) * data.Length), data2, 0, data.Length)
    
                        For index = 0 To data.Length - 1
                            If data1(index) > data2(index) Then
                                Exit For
                            ElseIf data1(index) < data2(index) Then
                                mmVA.WriteArray(Of Byte)((OrderedRotations(eachRotation) * data.Length), data1, 0, data1.Length)
                                mmVA.WriteArray(Of Byte)((OrderedRotations(rotation) * data.Length), data2, 0, data2.Length)
    
                                Dim tmpFirst As UInteger = OrderedRotations(rotation)
                                OrderedRotations(rotation) = OrderedRotations(eachRotation)
                                OrderedRotations(eachRotation) = tmpFirst
                                flag = True
                                Exit For
                            End If
                        Next
                    Next
                Loop While flag
            Next
    
            Return OrderedRotations.ToArray()
        End Function
    This one works but it doesn't use memory mapped files well.. and I can't see the difference between them both
    Code:
    Public Function SortLexicoGraphicallyBigIntegerArray(ByRef data As Byte()) As UInteger()
        Dim OrderedRotations As New List(Of UInteger)
        Dim index As Integer = 0
        Dim data1 As Byte()
        Dim data2 As Byte()
    
        Dim rotation As UInteger = 0
        Dim eachRotation As Integer = 0
        Dim TryAgain As Boolean = False
    
        For rotation = 0 To data.Length - 1
            data1 = GetRotation(data, rotation)
            OrderedRotations.Add(rotation)
            If OrderedRotations.Count > 1 Then
                Dim flag As Boolean
                Do
                    flag = False
    
                    For eachRotation = OrderedRotations.Count - 1 To 0 Step -1
                        data1 = GetRotation(data, OrderedRotations(rotation))
                        If OrderedRotations(eachRotation) = OrderedRotations(rotation) Then Continue For
                        data2 = GetRotation(data, OrderedRotations(eachRotation))
    
                        For index = 0 To data.Length - 1
                            If data1(index) > data2(index) Then
                                Exit For
                            ElseIf data1(index) < data2(index) Then
                                Dim tmpFirst As UInteger = OrderedRotations(rotation)
                                OrderedRotations(rotation) = OrderedRotations(eachRotation)
                                OrderedRotations(eachRotation) = tmpFirst
                                flag = True
                            End If
                        Next
                    Next
                Loop While flag
            End If
        Next
    
        Return OrderedRotations.ToArray()
    End Function

  2. #2
    eXtreme Programmer .paul.'s Avatar
    Join Date
    May 2007
    Location
    Chelmsford UK
    Posts
    21,924

    Re: Can someone fix my sorting algorithm up?

    Try this...

    Code:
    Dim rotation As New Dictionary(Of Integer, Integer())
    rotation.Add(0, New Integer() {50, 40, 30, 10, 10})
    rotation.Add(1, New Integer() {10, 50, 40, 30, 10})
    rotation.Add(2, New Integer() {10, 10, 50, 40, 30})
    rotation.Add(3, New Integer() {30, 10, 10, 50, 40})
    rotation.Add(4, New Integer() {40, 30, 10, 10, 50})
    Dim list As List(Of KeyValuePair(Of Integer, Integer())) = rotation.OrderBy(Function(kvp) kvp.Value(0)) _
                                                                        .ThenBy(Function(kvp) kvp.Value(1)) _
                                                                        .ThenBy(Function(kvp) kvp.Value(2)) _
                                                                        .ThenBy(Function(kvp) kvp.Value(3)) _
                                                                        .ThenBy(Function(kvp) kvp.Value(4)).ToList
    
    MsgBox(String.Join(", ", list.Select(Function(kvp) kvp.Key.ToString).ToArray))

  3. #3

    Thread Starter
    Member
    Join Date
    Apr 2009
    Posts
    37

    Re: Can someone fix my sorting algorithm up?

    can you possibly fix mine up i use 40gb datasets can't use built in

  4. #4
    eXtreme Programmer .paul.'s Avatar
    Join Date
    May 2007
    Location
    Chelmsford UK
    Posts
    21,924

    Re: Can someone fix my sorting algorithm up?

    I've never encountered MemoryMappedFiles or worked with 40gb datasets that way. I could get it running, but i'd need the project to debug it. You'll probably find LINQ sorting to be much faster than a bubble sort, if that's what you're using, but 40gb datasets will not be sorted in milliseconds, and that's most likely what is causing the problem...

  5. #5

    Thread Starter
    Member
    Join Date
    Apr 2009
    Posts
    37

    Re: Can someone fix my sorting algorithm up?

    I cant load up 40 gb in a array my program will run out of memory thats why i need to use memory mapped files its like accessing a array from harddrive instead of the .net arrays

  6. #6
    Fanatic Member PlausiblyDamp's Avatar
    Join Date
    Dec 2016
    Location
    Newport, UK
    Posts
    888

    Re: Can someone fix my sorting algorithm up?

    Out of interest, what do these datasets look like? Are they being stored as single files or could they be stored in another format such as a database? Depending on what you are trying to do to manipulate them there might be other options than using memory mapped files and working with the data in such a direct fashion.

  7. #7

    Thread Starter
    Member
    Join Date
    Apr 2009
    Posts
    37

    Re: Can someone fix my sorting algorithm up?

    Its just 1 file thats added using a position index offset which is unsorted 200,000 bytes * 200,000 bytes. For my example I used only 25 bytes (5 rotations x 5 values in array)

  8. #8
    Frenzied Member ChrisE's Avatar
    Join Date
    Jun 2017
    Location
    Frankfurt
    Posts
    1,431

    Re: Can someone fix my sorting algorithm up?

    Hi,

    try a ConcurrentQueue<T> Class

    https://docs.microsoft.com/de-de/dot...ramework-4.7.2

    HTH
    to hunt a species to extinction is not logical !
    since 2010 the number of Tigers are rising again in 2016 - 3900 were counted. with Baby Callas it's 3901, my wife and I had 2-3 months the privilege of raising a Baby Tiger.

  9. #9

    Thread Starter
    Member
    Join Date
    Apr 2009
    Posts
    37

    Re: Can someone fix my sorting algorithm up?

    how would i use it for sorting? my sorting seems to have a pattern it does which doesn't sort all the numbers but instead after the pattern is done goes back to the original unsorted configuration like the rotations

  10. #10

    Thread Starter
    Member
    Join Date
    Apr 2009
    Posts
    37

    Re: Can someone fix my sorting algorithm up?

    Quote Originally Posted by pkedpker View Post
    how would i use it for sorting? my sorting seems to have a pattern it does which doesn't sort all the numbers but instead after the pattern is done goes back to the original unsorted configuration like the rotations
    Don't know if this is the right way to do it.. but I solved it, it seems... not tested on more different datasets but it looks alright

    Code:
    Public Function SortLexicoGraphicallyArrayMappedFile(ByRef data As Byte()) As UInteger()
        Dim OrderedRotations As New List(Of UInteger)
        Dim rotatedData As Byte()
        Dim rotation As UInteger = 0
    
    
        Dim mmF As MemoryMappedFile
        mmF = MemoryMappedFile.CreateFromFile(My.Application.Info.DirectoryPath & "\outFile296", FileMode.CreateNew, "test", CLng(data.LongLength * data.LongLength))
        Dim mmVA As MemoryMappedViewAccessor
        mmVA = mmF.CreateViewAccessor(0, data.LongLength * data.LongLength)
    
        Dim pos As Long = 0
    
        For rotation = 0 To data.Length - 1
            rotatedData = GetRotation(data, rotation)
            mmVA.WriteArray(Of Byte)(pos, rotatedData, 0, rotatedData.Length)
            pos += rotatedData.Length
    
        Next
    
        For rotation = 0 To data.Length - 1
            OrderedRotations.Add(rotation)
        Next
    
        Dim eachRotation As Integer = 0
        Dim data1() As Byte
        ReDim data1(data.Length - 1)
        Dim data2() As Byte
        ReDim data2(data.Length - 1)
        Dim index As Long
        For rotation = 0 To data.Length - 1
            Dim flag As Boolean
            Do
                flag = False
                For eachRotation = OrderedRotations.Count - 1 To 0 Step -1
                    If rotation = eachRotation Then Exit For
                    mmVA.ReadArray(Of Byte)(rotation * data.Length, data1, 0, data.Length)
                    mmVA.ReadArray(Of Byte)((eachRotation * data.Length), data2, 0, data.Length)
    
                    For index = 0 To data.Length - 1
                        If data1(index) < data2(index) Then
                            Exit For
                        ElseIf data1(index) > data2(index) Then
                            mmVA.WriteArray(Of Byte)((eachRotation * data.Length), data1, 0, data1.Length)
                            mmVA.WriteArray(Of Byte)((rotation * data.Length), data2, 0, data2.Length)
    
                            Dim tmpFirst As UInteger = OrderedRotations(eachRotation)
                            OrderedRotations(eachRotation) = OrderedRotations(rotation)
                            OrderedRotations(rotation) = tmpFirst
                            flag = True
                            Exit For
                        End If
                    Next
                Next
            Loop While flag
        Next
    
        Return OrderedRotations.ToArray()
    End Function

  11. #11
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Pointless Forest 38.517,-92.023
    Posts
    9,065

    Re: Can someone fix my sorting algorithm up?

    Is this a binary file? Are there always 5 bytes per 'Rotation'? What is the distribution of values based on byte(0)?
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  12. #12

    Thread Starter
    Member
    Join Date
    Apr 2009
    Posts
    37

    Re: Can someone fix my sorting algorithm up?

    Quote Originally Posted by dbasnett View Post
    Is this a binary file? Are there always 5 bytes per 'Rotation'? What is the distribution of values based on byte(0)?
    My real example is 200,000 bytes * 200,000 rototations of the bytes. and the values are only 1's and 0's

  13. #13
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Pointless Forest 38.517,-92.023
    Posts
    9,065

    Re: Can someone fix my sorting algorithm up?

    Quote Originally Posted by pkedpker View Post
    My real example is 200,000 bytes * 200,000 rototations of the bytes. and the values are only 1's and 0's
    I don't understand the math. How about posting a sample of the real data please.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  14. #14

    Thread Starter
    Member
    Join Date
    Apr 2009
    Posts
    37

    Re: [RESOLVED] Can someone fix my sorting algorithm up?

    Code:
    0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 ... continues up to 200,000  0's or 1's
    each rotation is take a number from the front and add it to the back until you get the original result hence 200,000 rotations 1 for every byte.

    rotation 1
    Code:
    0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 ... continues up to 200,000  0's or 1's
    rotation 2
    Code:
    0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 ... continues up to 200,000  0's or 1's
    rotation 3
    Code:
    0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 ... continues up to 200,000  0's or 1's
    and so on and so on.


    Atm my solution works.. but its way too slow at sorting it would take a month just to finish haha which it why I need something that sorts and inserts on the spot.

    can you tell me how to implement https://www.codeproject.com/Articles...and-Stabilised I can't do it since I have to scan every index before in both arrays if same values are detected
    Last edited by pkedpker; Yesterday at 10:39 PM.

  15. #15
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    4,652

    Re: [RESOLVED] Can someone fix my sorting algorithm up?

    Is it really a file of 200,000 rotations of an initial 200,000 byte array of ones and zeros?

    If that is the case, then you can hold the whole rotation "matrix" in memory easily by just creating an array twice the size (400,000 bytes) and loading the data in it twice.
    Using your first post example:
    Code:
    Rotation 0 (1st) (use this one, or the other one for rotation 0, your choice)
    |   Rotation 4
    |   |   Rotation 3
    |   |   |   Rotation 2
    |   |   |   |   Rotation 1
    |   |   |   |   |   Rotation 0 (2nd)
    |   |   |   |   |   | 
    50, 40, 30, 10, 10 ,50, 40, 30, 10, 10
                    |   |   |   |   |   |
                    |   |   |   |   |   End of Rotation 0 (2nd)  
                    |   |   |   |   End of Rotation 1
                    |   |   |   End of Rotation 2
                    |   |   End of Rotation 3
                    |   End of Rotation 4
                    End of Rotation 0 (1st)
    You then just index into that array for the starting point of whichever "rotation" you want to test.
    Since you're maintaining a list of the swapped indexes, use that list as your indexes into the array so that you never actually swap the data, only the indexes into the data.

    If you remove all the reading and writing of data to the disk, that should save you a huge amount of time, and only sorting indexes in memory also saves quite a bit of time.
    Once you have your indexes sorted, you can return that which is what it looks like you're doing. If you also need a sorted version of the file, you can write the file once, by going through the index array and writing each of the rotations out to the file in index order.
    Last edited by passel; Today at 07:01 AM.

  16. #16
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Pointless Forest 38.517,-92.023
    Posts
    9,065

    Re: [RESOLVED] Can someone fix my sorting algorithm up?

    Quote Originally Posted by pkedpker View Post
    Code:
    0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 ... continues up to 200,000  0's or 1's
    each rotation is take a number from the front and add it to the back until you get the original result hence 200,000 rotations 1 for every byte.

    rotation 1
    Code:
    0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 ... continues up to 200,000  0's or 1's
    rotation 2
    Code:
    0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 ... continues up to 200,000  0's or 1's
    rotation 3
    Code:
    0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 ... continues up to 200,000  0's or 1's
    and so on and so on.


    Atm my solution works.. but its way too slow at sorting it would take a month just to finish haha which it why I need something that sorts and inserts on the spot.

    can you tell me how to implement https://www.codeproject.com/Articles...and-Stabilised I can't do it since I have to scan every index before in both arrays if same values are detected
    Wow am I confused. In your original post it was 5 bytes, know it is some unspecified amount of bits.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Featured


Click Here to Expand Forum to Full Width