Re: Remove from a collection

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance


"Schmidt" <sss@xxxxxxxxx> wrote in message
news:%23%23jgdxa2GHA.1040@xxxxxxxxxxxxxxxxxxxxxxx

"Dmitriy Antonov" <antonovdima@xxxxxxxxxxxxxxxxxxxxxxxx> schrieb im
Newsbeitrag news:uGfkjla2GHA.4924@xxxxxxxxxxxxxxxxxxxxxxx

I just can guess that the reason for such difference is that,
when removing from the end, Collection physically shrinks/de-
allocates its underlying array (maybe after difference between
allocated and actually used memory becomes significant) but
doesn't do it, when removing the first element.
The main-reason is, that the last element first has to be found,
inside the (linked) collection-list, before it's removed.
The time needed for memory-deallocation should be the same
in both cases.
In a "RemoveFirst-Loop" your measured time is the sum of the
deallocation-time.
In a "RemoveLast-Loop" you will measure the same dealloc-time
+ the time(s) needed, to iterate over the list to the appropr. last item.

The VB-Collection behaves not perfect in this regard, because
it can do better as one can measure during the Adds.
Here it "knows" (stores) the last added item and jumps directly
there if the next item has to be added to the end of the list.

Olaf



I measured Adding to the end and to the beginning and they are almost the
same. This is why I thought that Collection knows its last element and
didn't think that it wouldn't use its "knowledge" for the task of removing
the last element. But it's perfect explanation of the exponential grows,
when removing from the end, and significant difference between two methods.

As to my guess as for de-allocation (which is probably wrong after your
explanation), I thought that it wouldn't shrink array on the way of removing
from the beginning but would do it if removed from the opposite direction.
Something like the following simplified pseudocode:

Fix links
If the item, which was just removed, was the last one then
check ratio used items/unused items
if ratio >=50%
allocate smaller array
copy data from bigger array to smaller one
de-allocate bigger array
end if
end if

Someone may think why it would behave in such inconsistent way. But the same
question could be asked, why it adds to the end by directly going to that
end, but fails to do it, while removing.

Dmitriy.



.

Relevant Pages

  • Re: Remove from a collection
    ... allocates its underlying array (maybe after difference between ... allocated and actually used memory becomes significant) but ... when removing the first element. ... In a "RemoveFirst-Loop" your measured time is the sum of the ...
    (microsoft.public.vb.general.discussion)
  • Re: Weird $_POST behavior when trying to unset elements
    ... "array_remove" PHP FUNCTION IS MADE PART OF CORE IN THE FUTURE ... Remove a specific element from the array. ... removing the wrong element when you remove something by the value, ... AFTER JAVA Vector.removeElementAt ...
    (comp.lang.php)
  • Releasing memory (continuation)
    ... UDTs array would be the fastest). ... - Removing in reversed key order ... Release time in collection test seems to be spent 1/2 navigating thru the ... collection, 1/2 releasing memory. ...
    (microsoft.public.vb.general.discussion)
  • Re: Weird $_POST behavior when trying to unset elements
    ... Remove a specific element from the array. ... removing the wrong element when you remove something by the value, ... I have no trouble telling which element you ... I think the real problem here is actually that wrong elements are ...
    (comp.lang.php)
  • Re: Weird $_POST behavior when trying to unset elements
    ... "array_remove" PHP FUNCTION IS MADE PART OF CORE IN THE FUTURE ... Remove a specific element from the array. ... removing the wrong element when you remove something by the value, ... AFTER JAVA Vector.removeElementAt ...
    (comp.lang.php)