How Ruby arrays behave internally when deleting an element?

Question

I am designing a game in Ruby in order to learn the language and my game needs to be in a constant cycle of deleting items from an array and adding them to another one, than deleting from the other one and readding to the first one. I want to know what happens internally when I call Array.delete(). I'd rather use a linked list for my game since deleting from and adding to a linked list is way more efficient than on an array. However, Array is the only data structure I've come accross in Ruby so far. Is it really the only one available?

edit: It's a basic shoot'em up game where the enemy ships can shoot bullets at the player. In order to avoid having to allocate a new bullet every time an enemy fires at the player, I allocate a lot of bullets before the game starts. When an enemy shoots, he picks a bullet from the list of available bullets and puts it in the list of "active" bullets. The class responsible for drawing the bullets on the screen only draws those bullets in the list of acitve bullets. When a bullet leaves the screen, it goes back to the list of available bullets. That's where all the shuffling comes from...

Answer 1

It's easy to implement a linked list in Ruby, but the one time I actually did it, performance was exactly the same as using an Array. The better algorithm in Ruby was exactly balanced by the speed of the internal C code.

Now, I wasn't trying to delete things in the middle of my Array.

For your case, I think it's safe to say if the arrays are short, then the algorithm doesn't matter and you will be fine using the built-in Array class. If the array is long, then no doubt some sort of map could be constructed whereby deleting things from the middle of the Array would not require repacking the array and its quadratic time complexity.

Really, you should first implement your game in the simple and direct way. You shouldn't stir in complexity in the beginning without even knowing what it buys, if anything. Who knows, you may even find that some other part of the game uses more time.

And should you find that indeed you are bogged down with Array deletions, the next step is to add a map or perhaps, yes, a linked list or tree implemented in Ruby. And if that isn't fast enough, with your encapsulated Ruby solution and a set of tests, you would be in a good position to write a C extension, and you would know almost exactly the benefit.

Answer 2

Use Hash. It is more efficient than Array.