Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

RE: Removing certain elements from an array

by BlaisePascal (Monk)
on Aug 24, 2000 at 23:00 UTC ( [id://29503]=note: print w/replies, xml ) Need Help??


in reply to Removing certain elements from an array

This may work as well...
@hugearray = ( ... ); @toremove = ( ... ); # remove from @hugearray elements indexed in @toremove @hugearray[@toremove] = ("RemoveMe") x @toremove; push @hugearray, "SentinelFlag"; for (my $_;;) { $_ = shift @hugearray; last if $_ eq "SentinelFlag"; next if $_ eq "RemoveMe"; push @hugearray, $temp; }
This works by flagging the elements you want to delete, then using @hugearray as a circular shift register, shift-pushing each element in the array in turn, until it gets back to the beginning. As it goes, it doesn't push back in the elements to be deleted.

How does it fare efficiency-wise? This routine touches each data element once, and likely does at most a single implicit array-copy. I think it is probably an O(n+m) operation (n=@hugearray, m=@toremove). The splice solution is O(m log m + m*O(splice(n)). Since perl arrays are not linked lists, I think splice is an O(n) operation, meaning that the splice solutions are O(m log m + m*n). Which is faster? My guess would be the shift-register, but I don't know.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://29503]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others imbibing at the Monastery: (6)
As of 2024-03-28 14:13 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found