If the ennemies are generated randomly, and if you are sure they are the bottleneck of the FPS, you could generate them dynamically as the character progresses through the world.
Otherwise, you can divide your world in multiples rects the size of the screen, and link each ennemy to the "screen" to which it belongs. Ennemies are then woke up when the actual screen approaches the rect of the ennemy, allowing you to double-loop over a domain with side size 600 times smaller approximately.
(well I wrote "ennemies" but of course this applies to any element that is more or less static with respect to the map)