Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > Effective perl function to remove one element from array?

Reply
Thread Tools

Effective perl function to remove one element from array?

 
 
josh
Guest
Posts: n/a
 
      05-30-2004
Hi all:

I am trying to find out the most efficient way to remove an element
from an array, and have the array size shrink by one.

pop, push, and splice won't work too well for me, I am trying to
remove an element that could be in any position.

Here is my current implementation (may not actually compile, just a
example)

<psuedo perl code>
# this array is purposely unsorted
@array = ['bob', 'alice', 'david', 'christy', 'edward', 'henry',
'frank'];
@array = removeFromArray ( @array, "edward" );

sub removeFromArray {
@array = $_[0];
$name = $_[1];

for ( $i = 0; $i < @$array; $i++ ) {
if ( $array[$i] eq $name ) {
unset $array[$i];
}
}
}
</psuedo perl code>

As you can see, this is not exactly the most efficient way of removing
an element as the size of my array grows. And especially when I run
this in a nested loop, say, when I want to compare two arrays and
remove the differences, it will result in a close to BigO(n^2)
efficiency.

Is there a faster, more efficient way to remove an element from an
array (and preferrably not BigO(n) )?

Will it help if I am performinig this on an already sorted array? Then
I can perhaps use some sort of binary search function to find the item
I am looking for?
 
Reply With Quote
 
 
 
 
Matt Garrish
Guest
Posts: n/a
 
      05-30-2004

"josh" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) om...
> Hi all:
>
> I am trying to find out the most efficient way to remove an element
> from an array, and have the array size shrink by one.
>
> pop, push, and splice won't work too well for me, I am trying to
> remove an element that could be in any position.
>
> Here is my current implementation (may not actually compile, just a
> example)
>
> <psuedo perl code>
> # this array is purposely unsorted
> @array = ['bob', 'alice', 'david', 'christy', 'edward', 'henry',
> 'frank'];
> @array = removeFromArray ( @array, "edward" );
>
> sub removeFromArray {
> @array = $_[0];
> $name = $_[1];
>
> for ( $i = 0; $i < @$array; $i++ ) {
> if ( $array[$i] eq $name ) {
> unset $array[$i];
> }
> }
> }
> </psuedo perl code>
>
> As you can see, this is not exactly the most efficient way of removing
> an element as the size of my array grows.


Which begs the question, why use an array when a hash would work better?

my %hash = (bob => 1, alice => 1, david => 1, christy =>1, edward => 1,
henry => 1);

delete $hash{'edward'};

It would also make removing duplicates simple because you could just assign
all the keys from your existing hashes to a new hash. And sorting would be
faster, too.

Matt


 
Reply With Quote
 
 
 
 
Jürgen Exner
Guest
Posts: n/a
 
      05-30-2004
josh wrote:
> I am trying to find out the most efficient way to remove an element
> from an array, and have the array size shrink by one.
>
> pop, push, and splice won't work too well for me, I am trying to
> remove an element that could be in any position.


I would doubt that you can hand code anything that is faster than the
build-in function splice().If there were anything faster, then chances are
that algorithm would have been used to implement splice() in the first
place.

> Here is my current implementation (may not actually compile, just a
> example)
>
> <psuedo perl code>
> # this array is purposely unsorted
> @array = ['bob', 'alice', 'david', 'christy', 'edward', 'henry',
> 'frank'];
> @array = removeFromArray ( @array, "edward" );
>
> sub removeFromArray {
> @array = $_[0];
> $name = $_[1];
>
> for ( $i = 0; $i < @$array; $i++ ) {
> if ( $array[$i] eq $name ) {
> unset $array[$i];
> }
> }
> }
> </psuedo perl code>
>
> As you can see, this is not exactly the most efficient way of removing
> an element as the size of my array grows. And especially when I run
> this in a nested loop, say, when I want to compare two arrays and
> remove the differences, it will result in a close to BigO(n^2)
> efficiency.
> Is there a faster, more efficient way to remove an element from an
> array (and preferrably not BigO(n) )?


This code screams for a better data structure. Why aren't you using a hash?
Then all you need to do is
sub removeFromHash {
delete $hash{$_[0]};
}
I would guess this should be somewhere near O(log n) (access to hash table
is not quite linear).

> Will it help if I am performinig this on an already sorted array? Then
> I can perhaps use some sort of binary search function to find the item
> I am looking for?


Well, sure, but why? I thought your problem was deleting, not finding. A
sorted array won't help you with deleting an element.
Use a proper data structure and your problem becomes trivial.

jue



 
Reply With Quote
 
John Bokma
Guest
Posts: n/a
 
      05-30-2004
Jürgen Exner wrote:

> I would guess this should be somewhere near O(log n) (access to hash table
> is not quite linear).


Access to a hash table is normally O(1). That's the whole idea behind a
hash .

--
John MexIT: http://johnbokma.com/mexit/
personal page: http://johnbokma.com/
Experienced Perl programmer available: http://castleamber.com/
 
Reply With Quote
 
Jürgen Exner
Guest
Posts: n/a
 
      05-30-2004
John Bokma wrote:
> Jürgen Exner wrote:
>
>> I would guess this should be somewhere near O(log n) (access to hash
>> table is not quite linear).


Ooopps, that should have been "not quite constant"

> Access to a hash table is normally O(1). That's the whole idea behind
> a hash .


True, but only as long as the hash is sparsely populated.
As the hash begins to fill up you will get hash conflicts and then you are
loosing O(1).

jue


 
Reply With Quote
 
Uri Guttman
Guest
Posts: n/a
 
      05-30-2004
>>>>> "JE" == Jürgen Exner <(E-Mail Removed)> writes:

JE> John Bokma wrote:
>> Jürgen Exner wrote:
>>
>>> I would guess this should be somewhere near O(log n) (access to hash
>>> table is not quite linear).


JE> Ooopps, that should have been "not quite constant"

>> Access to a hash table is normally O(1). That's the whole idea behind
>> a hash .


JE> True, but only as long as the hash is sparsely populated.
JE> As the hash begins to fill up you will get hash conflicts and then you are
JE> loosing O(1).

and perl will grow the hash as needed to keep it efficient. one of the
nice little behind the scenes things. true it is not exactly O(1) but
you can assume that for common uses. the real killer is when it grows so
large that you have to swap . then you might as well use a real db
which will be more efficient since they are designed to handle this
whereas an in ram hash is not.

uri

--
Uri Guttman ------ http://www.velocityreviews.com/forums/(E-Mail Removed) -------- http://www.stemsystems.com
--Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
Search or Offer Perl Jobs ---------------------------- http://jobs.perl.org
 
Reply With Quote
 
John Bokma
Guest
Posts: n/a
 
      05-30-2004
Jürgen Exner wrote:

> John Bokma wrote:
>
>>Jürgen Exner wrote:
>>
>>
>>>I would guess this should be somewhere near O(log n) (access to hash
>>>table is not quite linear).

>
> Ooopps, that should have been "not quite constant"
>
>>Access to a hash table is normally O(1). That's the whole idea behind
>>a hash .

>
> True, but only as long as the hash is sparsely populated.
> As the hash begins to fill up you will get hash conflicts and then you are
> loosing O(1).


Ok, you get O(k), which is still O(1) as long as k << n, which is
hopefully the case .

--
John MexIT: http://johnbokma.com/mexit/
personal page: http://johnbokma.com/
Experienced Perl programmer available: http://castleamber.com/
 
Reply With Quote
 
John Bokma
Guest
Posts: n/a
 
      05-30-2004
Uri Guttman wrote:

> and perl will grow the hash as needed to keep it efficient. one of the
> nice little behind the scenes things. true it is not exactly O(1) but


The fun part behind the big O notation is that O(k) for k << n, is still
O(1). So "not exactly O(1)" does not exists.

--
John MexIT: http://johnbokma.com/mexit/
personal page: http://johnbokma.com/
Experienced Perl programmer available: http://castleamber.com/
 
Reply With Quote
 
Tassilo v. Parseval
Guest
Posts: n/a
 
      05-30-2004
Also sprach Jürgen Exner:

> josh wrote:


>> Is there a faster, more efficient way to remove an element from an
>> array (and preferrably not BigO(n) )?

>
> This code screams for a better data structure. Why aren't you using a hash?
> Then all you need to do is
> sub removeFromHash {
> delete $hash{$_[0]};
> }
> I would guess this should be somewhere near O(log n) (access to hash table
> is not quite linear).


Hash-access is O(n) in the absolutely worst-case (for open hashing where
linear lists are used). However, the average case can be considered
constant, too, which has to do with the fact that hashes are resized
(normally their amount of buckets is doubled). So you have a complexity
of O(1 + a/2), where 'a' is the average list-length with a = m/n. 'm' is
the number of keys whereas 'n' is the number of buckets. In case of
Perl, some empirical tests suggest that 'a' is between 0.35 and 0.7.
When treating it as a random variable, I am quite sure that it will have
an expected value of 0.5. The standard deviation, I would guess, is then
probably around 0.1 or even less.

It is therefore reasonable to assume that access to Perl hashes is
constant in all but the contrived cases.

Tassilo
--
$_=q#",}])!JAPH!qq(tsuJ[{@"tnirp}3..0}_$;//::niam/s~=)]3[))_$-3(rellac(=_$({
pam{rekcahbus})(rekcah{lrePbus})(lreP{rehtonabus}) !JAPH!qq(rehtona{tsuJbus#;
$_=reverse,s+(?<=sub).+q#q!'"qq.\t$&."'!#+sexisexi ixesixeseg;y~\n~~dddd;eval
 
Reply With Quote
 
Tassilo v. Parseval
Guest
Posts: n/a
 
      05-30-2004
Also sprach John Bokma:

> Jürgen Exner wrote:


>> True, but only as long as the hash is sparsely populated.
>> As the hash begins to fill up you will get hash conflicts and then you are
>> loosing O(1).

>
> Ok, you get O(k), which is still O(1) as long as k << n, which is
> hopefully the case .


Why would that be the case? If you have O(ln(n)) and set n to 10^16,
then k is around 37. That should qualify as k << n but still, it is not
constant. It can't be constant as long as it is parametrized with n and
the function is monotonously increasing with n (log is such a function).

Tassilo
--
$_=q#",}])!JAPH!qq(tsuJ[{@"tnirp}3..0}_$;//::niam/s~=)]3[))_$-3(rellac(=_$({
pam{rekcahbus})(rekcah{lrePbus})(lreP{rehtonabus}) !JAPH!qq(rehtona{tsuJbus#;
$_=reverse,s+(?<=sub).+q#q!'"qq.\t$&."'!#+sexisexi ixesixeseg;y~\n~~dddd;eval
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to remove one structure element Leon Pollak C++ 0 03-17-2009 10:23 PM
how to Update/insert an xml element's text----> (<element>text</element>) HANM XML 2 01-29-2008 03:31 PM
Remove parent element with a child element matching a given rule patrizio.trinchini@googlemail.com XML 4 08-22-2006 11:31 AM
How to make env-vars effective on return from perl module subrtn ? Owen_Townsend Perl Misc 5 07-10-2006 02:46 PM
whereabouts of Effective Perl Xah Lee Perl Misc 1 09-21-2005 10:55 AM



Advertisments