Results 1 to 8 of 8

Thread: [RESOLVED] fast remove an element of an array using CopyMemory or something else

  1. #1

    Thread Starter
    Fanatic Member
    Join Date
    Sep 2010
    Location
    Italy
    Posts
    678

    Resolved [RESOLVED] fast remove an element of an array using CopyMemory or something else

    I often came across the need to remove an element from an array containing values (not strings).
    To do this, I execute a for loop that overwrites the queue from the element after the one to be deleted (to ubound ) on the one to be deleted. (then I decrease ubound by 1)
    For a big array (an more when the one to be removed is at the beginning of the array) this is slow, so I wonder if it exist a faster way to do it.
    I'm thinking about using COPYMEMORY api.
    Do you have any idea? Did you already do it or you know how to do it with COPYMEMORY ?

    using for loop:
    ......V
    01234567890

    ......V
    01234577890
    .......V
    01234578890
    ........V
    01234578990
    .........V
    01234578900
    ..........V ubound
    0123457890


    Using copymemory:
    01234567890
    .......7890
    ......*<<<<
    0123457890-



    EDIT
    Found It
    http://www.vb-helper.com/howto_delete_from_array.html

  2. #2

    Thread Starter
    Fanatic Member
    Join Date
    Sep 2010
    Location
    Italy
    Posts
    678

    Re: [RESOLVED] fast remove an element of an array using CopyMemory or something else

    source:
    http://www.vb-helper.com/howto_delete_from_array.html

    Code:
    Public Sub RemoveArrayElement_Str(AryVar() As String, ByVal _
        RemoveWhich As Long)
        '// The size of the array elements
        '// In the case of string arrays, they are
        '// simply 32 bit pointers to BSTR's.
        Dim byteLen As Byte
        
        '// String pointers are 4 bytes
        byteLen = 4
    
        '// The copymemory operation is not necessary unless
        '// we are working with an array element that is not
        '// at the end of the array
        If RemoveWhich < UBound(AryVar) Then
            '// Copy the block of string pointers starting at
            ' the position after the
            '// removed item back one spot.
            CopyMemory ByVal VarPtr(AryVar(RemoveWhich)), ByVal _
                VarPtr(AryVar(RemoveWhich + 1)), (byteLen) * _
                (UBound(AryVar) - RemoveWhich)
        End If
        
        '// If we are removing the last array element
        '// just deinitialize the array
        '// otherwise chop the array down by one.
        If UBound(AryVar) = LBound(AryVar) Then
            Erase AryVar
        Else
            ReDim Preserve AryVar(UBound(AryVar) - 1)
        End If
    End Sub

  3. #3
    PowerPoster
    Join Date
    Aug 2010
    Location
    Canada
    Posts
    2,412

    Re: [RESOLVED] fast remove an element of an array using CopyMemory or something else

    In my tests, the difference quite dramatic (loop vs. copymemory) when compiled to P-code (expected of course).

    It was less dramatic (but still much better) than when compiled to native code without any optimizations.

    When compiled to Native code with the usual optimizations, there is still a difference, but it's much smaller. I ran a million loops each, and the difference was 2.8 seconds for a VB only loop & copy, vs. 2 seconds for the API version.

  4. #4
    PowerPoster Zvoni's Avatar
    Join Date
    Sep 2012
    Location
    To the moon and then left
    Posts
    4,418

    Re: [RESOLVED] fast remove an element of an array using CopyMemory or something else

    Out of curiosity:
    Does the Array have to be sorted?
    If no, why not switch last (Ubound)-Member with the "to remove"-Member, and do the ReDim Preserve Ubound-1?
    Or instead of the ReDim Preserve keep the Ubound in a separate variable and use that variable instead of the UBound-Function

    Kinda like:
    Dim MyUbound As Long
    'UBound of Array: 32
    MyUbound=UBound(Array)

    'To remove: Array-Member 7

    Array(7)=Array(32)

    ReDim Preserve UBound(Array)-1 // MyUbound=MyUbound-1

    If it has to be sorted, send it after switching to a Quicksort. (In that case you have to use the Redim Preserve)
    Would be interested in Performance-tests
    Last edited by Zvoni; Tomorrow at 31:69 PM.
    ----------------------------------------------------------------------------------------

    One System to rule them all, One Code to find them,
    One IDE to bring them all, and to the Framework bind them,
    in the Land of Redmond, where the Windows lie
    ---------------------------------------------------------------------------------
    People call me crazy because i'm jumping out of perfectly fine airplanes.
    ---------------------------------------------------------------------------------
    Code is like a joke: If you have to explain it, it's bad

  5. #5
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    6,582

    Re: [RESOLVED] fast remove an element of an array using CopyMemory or something else

    You're assuming the data in the array is either arbitrary, or sorted.
    The data could be added to the array in a series, i.e. a list of points that make up a drawing.
    The points would have an order, i.e. one point connects to the next point in the series, but the array wouldn't be sorted by the value in the array.

    Also, a QuickSort isn't magic. There is no way moving a value from the end of a sorted array to some point in the array and then sorting it would be faster than just moving the elements down in a loop, regardless of which sort you chose. Also, if you moved a single value down to an arbitrary point in a sorted array, a Bubble sort would be faster than a QuickSort to resort the array. No testing really needed for that scenario.

    Also,

    ReDim Preserve Array(Ubound(Array)-1)

    will copy the whole array, minus one element, to another location in memory, so you end up copying the whole array rather than just a portion of it, so ends up being more work, even if you don't sort.
    Of course, the existing code is doing that anyway. If you could modify the bounds in the description of the array, rather than using ReDim Preserve that would be faster, but I guess that would fragment memory.

    If you need to do this often, then probably better to use some sort of List class, rather than an array, along the lines of your second suggestion of not using ReDim Preserve and keeping track of how much array of an existing array is being used, rather than resizing the array.
    Last edited by passel; Sep 3rd, 2019 at 06:55 AM.

  6. #6
    PowerPoster Zvoni's Avatar
    Join Date
    Sep 2012
    Location
    To the moon and then left
    Posts
    4,418

    Re: [RESOLVED] fast remove an element of an array using CopyMemory or something else

    OK, i understand your argument (especially the one with the drawing)
    Well, it really depends on the scenario the OP is fighting with.
    Otherwise: A collection is always a way to achieve what he wants (adding/removing a specific Member) without juggling Arrays
    Last edited by Zvoni; Tomorrow at 31:69 PM.
    ----------------------------------------------------------------------------------------

    One System to rule them all, One Code to find them,
    One IDE to bring them all, and to the Framework bind them,
    in the Land of Redmond, where the Windows lie
    ---------------------------------------------------------------------------------
    People call me crazy because i'm jumping out of perfectly fine airplanes.
    ---------------------------------------------------------------------------------
    Code is like a joke: If you have to explain it, it's bad

  7. #7

    Thread Starter
    Fanatic Member
    Join Date
    Sep 2010
    Location
    Italy
    Posts
    678

    Re: [RESOLVED] fast remove an element of an array using CopyMemory or something else

    Quote Originally Posted by Zvoni View Post
    Out of curiosity:
    Does the Array have to be sorted?
    If no, why not switch last (Ubound)-Member with the "to remove"-Member, and do the ReDim Preserve Ubound-1?
    Or instead of the ReDim Preserve keep the Ubound in a separate variable and use that variable instead of the UBound-Function

    Kinda like:
    Dim MyUbound As Long
    'UBound of Array: 32
    MyUbound=UBound(Array)

    'To remove: Array-Member 7

    Array(7)=Array(32)

    ReDim Preserve UBound(Array)-1 // MyUbound=MyUbound-1

    If it has to be sorted, send it after switching to a Quicksort. (In that case you have to use the Redim Preserve)
    Would be interested in Performance-tests
    Very interesting approach!
    In my case the array do not need to be sorted.
    So as you said I could simply copy (overwrite) last element to the position of the element to remove and then or use Redim preserve or keep track of the ubound (that will decrease by one)

    I was using CopyMemory that is very fast even for long arrays.

    but I tried this method and for sure in my case is the best !
    thanks for the idea !

  8. #8
    PowerPoster Zvoni's Avatar
    Join Date
    Sep 2012
    Location
    To the moon and then left
    Posts
    4,418

    Re: [RESOLVED] fast remove an element of an array using CopyMemory or something else

    Quote Originally Posted by reexre View Post
    Very interesting approach!
    In my case the array do not need to be sorted.
    So as you said I could simply copy (overwrite) last element to the position of the element to remove and then or use Redim preserve or keep track of the ubound (that will decrease by one)

    I was using CopyMemory that is very fast even for long arrays.

    but I tried this method and for sure in my case is the best !
    thanks for the idea !
    You're welcome!
    Last edited by Zvoni; Tomorrow at 31:69 PM.
    ----------------------------------------------------------------------------------------

    One System to rule them all, One Code to find them,
    One IDE to bring them all, and to the Framework bind them,
    in the Land of Redmond, where the Windows lie
    ---------------------------------------------------------------------------------
    People call me crazy because i'm jumping out of perfectly fine airplanes.
    ---------------------------------------------------------------------------------
    Code is like a joke: If you have to explain it, it's bad

Posting Permissions

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



Click Here to Expand Forum to Full Width