Re: Array Empty Slots

["M.Baris Demiray" <baris@labristeknoloji.com>]

[-- Attachment #1: Type: text/plain, Size: 1095 bytes --]


Chris wrote:
> Hi all,

Hi,

> Lets assume we have a very very big array with sequential integer numbers
> from 1-30000, but we have some slots that are empty.
> Which is the faster way(algorithm maybe) that we can track those empty
> slots???

A very common approach is using a linked list. Also, if you implement
a separate list for empty slots, your searches will be much faster.
OTOH, as you may guess, additional overhead will occur because of the
maintenance of the extra list.

Another option could be using a bitmap for _all_ (not only for empty
ones) slots. There are special instructions in many architectures
(like bsfl in i386) for the job "find first bit set" (hint, this is
the search keyword) and could be used inlined. I think that will be
much faster than searching a linked list.

Regards

> 
> 
> Best regards,
> Chris.

-- 
"You have to understand, most of these people are not ready to be
unplugged. And many of them are no inert, so hopelessly dependent
on the system, that they will fight to protect it."
                                                         Morpheus

[-- Attachment #2: baris.vcf --]
[-- Type: text/x-vcard, Size: 342 bytes --]

begin:vcard
fn:M.Baris Demiray
n:Demiray;M.Baris
org:Labris Teknoloji
adr:;;Teknokent Silikon Bina No:24 ODTU;Ankara;;06531;Turkey
email;internet:baris@labristeknoloji.com
title:Yazilim Gelistirme Uzmani
tel;work:+903122101490
tel;fax:+903122101492
x-mozilla-html:FALSE
url:http://www.labristeknoloji.com
version:2.1
end:vcard