Implement RemoveAt for a BitArray

[darkangrydragon]

Hi Everyone!

Does anyone know what the most efficient technique would be for implementing a RemoveAt procedure that functions on a BitArray?

I will be working with BitArrays that have on average around 100,000 indexes and will need to perform a large number of RemoveAt operations.

My end goal is to maintain performance in my application as well as keeping the memory footprint as small as possible. The latter is what led me to BitArrays, but I am not necessarily tied to that particular data structure.

Any ideas/advice are appreciated! Thanks!

-Andrew

 

[ThatRickGuy]

The most efficient way would likely be to use a linked or dually linked list, then just alter the memory location tags on either side of the item to be removed.

But that requires creating a dual linked list class and all that hassle. It would probrably be easier to use a hash table.

-Rick

VB.Net Forum forum796 forum855 ASP.NET Forum
I believe in killer coding ninja monkeys.

 

[darkangrydragon]

Interesting idea, but the only problem I see with using linked lists (or a hash table) is that I lose the advantage of the small memory footprint of BitArrays.

 

[ThatRickGuy]

True. But if efficiency in removal is key, a linked list will give you the best performance. If small footprint is key, then using a bit array with a loop to remove items will be the best.

basicly, you're going to have to loop from a given point X (the item to be removed) to the last item, and bubble everything forward.

Another option would be a 'black list' that tracks the position of bits that have been removed. Then you can check your output against the black list before executing it. A little less efficient on the output side, but it won't have the performance hit of bubbling through the entire array.

-Rick

VB.Net Forum forum796 forum855 ASP.NET Forum
I believe in killer coding ninja monkeys.

 

[darkangrydragon]

I guess I was hoping for a "magic bullet", but it looks like either memory or performance has to give.

Based on the sets of data I will be working with, I think I need to lean more towards keeping the memory usage down.

I've been toying around with the idea of using some sort of black list as well. I think I need to analyze the problem at a more detailed level to determine how often I will need to remove bits vs. how often I read data from the array. Right now I am just theorizing, so bubbling through the array to delete a bit may be plenty fast for my purposes. I'll have to do some tests and benchmarking.

Thanks for all the good ideas, Rick!