What's faster in VB? Removing an element from an array or inserting one?

Question

Which is faster? someCondition has the same probability of being true as it has of being false.

Insertion:

arrayList = Array("apple", "pear","grape")
if someCondition then
    ' insert "banana" element
end if

Deletion:

arrayList = Array("apple","banana","pear","grape")
if not someCondition then
    ' remove "banana" element
end if

It looks like it depends purely on the implementation of Insert and Remove. So which, in general, is faster? I'm leaning toward insertion because I've read that one can use CopyMemory to insert without looping. Is this the same for deletion? Does anyone have an example?

Edit: This is VB6, not VB.NET. For display reasons, I have to use insert rather than append.

Answer 1

I've found an example showing that one can delete without looping as well. It looks simpler than the code to insert.

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

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

Answer 2

I'd have to guess insert, because it can always just append whereas with the delete you have to worry about holes.

But what version of vb? If you're in .Net and doing deletes or inserts, you shouldn't be using an array for this at all.

Answer 3

Both have about the same performance because both require creating a new Array. Arrays are fixed size continuous structures.

In order to maintain this on an insert a new Array must be created with an additional element. All of the existing values are copied into the array in their new position and then the inserted element is added.

In order to maintain this for a delete a new Array must be created with one less element. Then all of the existing entries except for the delete must be copied into the new array.

Both of these operations have essentially the same operations over nearly identical sizes. Performance won't be significantly different.

Answer 4

For a delete, every item after the removed item must be shifted down.

For an Insert, space must be found for the new item. If there is empty space after the array that it can annex, then this takes no time, and the only time spend is more each item after the new item up, to make room in the middle.

If there is no available space locally, a whole new array must be allocated and every item copied.

So, when considering adding or deleting to the same array position, inserting could be as fast as deleting, but it maybe much longer. Inserting won't be faster.

Answer 5

On topic but not quite an answer:

Inserting and deleting is not an application that is applicable on arrays. It goes beyond "Optimization" and into bad programming.

If this gets hidden in the bottom of a call structure and someone ends up calling it repeatedly, you could take a severe performance hit. In one case I changed an array insertion-sort to simply use a linked list and it changed runtime from 10+hours (locked the machine) to seconds/minutes).

It was populating a listbox with ip addresses. As designed and tested on a class-c address space it worked fine, but we had requirements to work on a class-b address space without failing (Could take a while, but not hours). We were tasked with the minimum possible refactor to get it to not fail.

Don't assume you know how your hack is going to be used.