how fast is the observer pattern?
hi,
let磗 say i have a graph with thousands of edges existing.
Now i delete some of them, but i do not remember, which ones are deleted.
Deleting should mean in this case i mark them as deleted, by setting a specific flag of the edge object to true.
If i, lets say "push a button" then i want all edges to switch back to the state of being not deleted.
If i realize it using Observer and Observable, and i call update(), how fast is this? I think it must be O(n) - with n being the number of Observers, since all observers must be run through, like a link list. But i can be wrong, and it might be much faster?
Does anybody know about that?
Thanks a lot for your explanation in advance!
Message was edited by:
Cinimood
[781 byte] By [
Cinimooda] at [2007-10-3 7:55:17]
i have just seen in the source code that it uses an Vector implementation, and therefore it is really O(n)Is there an mechanism to get it much faster than O(n)?Best way would be of course "thread like" but it might be too expensive.
If you're going to touch every element once, then, yes, it is O(n). However, if all you're doing is flipping a boolean, then this will be quite fast.
If, after testing and measuring, you determine it to be too slow, you could try to get fancier. You might have one varialbe that has three states--all deleted, none deleted, and some deleted. Setting all deleted or all undeleted is then O(1). Any subsequent operations that involve individual items now must incur the additional overhead of checking the master state, and then, if it's "some", check the state of the individual item in question.
You could take this a step further, and break the elements down into blocks of 100 or 1000 or whatever, with masters for each block. That would allow you to have O(1) on some of the blocks, but O(m) overall, where m is the number of blocks.
But seriously, do measure before complicating things this way, and consider how often "undelete all" will occur in practice.
> Best way would be of course "thread like" No idea what you mean here.> but it> might be too expensive.Or here.
> If i realize it using Observer and Observable, and i
> call update(), how fast is this? I think it must be
> O(n) - with n being the number of Observers, since
> all observers must be run through, like a link list.
> But i can be wrong, and it might be much faster?
There is no way it could be faster than O(n). You can't touch every element without touching every element. And O(n) is plenty fast. How many observers could you possibly have? 5, 100, 10000? Even if it's the last, it's highly unlikely to have any impact on the performance of your code. Do you have any idea how long it takes to iterate over a Vector with 10000 elements? It's on the order of milliseconds or at most 10's of milliseconds on any contemporary hardware.
You are wasting your time. You should start writing some code and once you learn what causes performance problems (or the lack thereof) you can start trying to optimize things.
"Premature optimization is the root of all evil"
maybe, http://www.javaworld.com/cgi-bin/mailto/x_java.cgi
> maybe,> http://www.javaworld.com/cgi-bin/mailto/x_java.cgiIs that an example of premature optimization?
tried to provide the all-in-one print page :) http://www.javaworld.com/javaworld/jw-06-1998/jw-06-undoredo.html
> let磗 say i have a graph with thousands of edges
> existing.
> Now i delete some of them, but i do not remember,
> which ones are deleted.
> Deleting should mean in this case i mark them as
> deleted, by setting a specific flag of the edge
> object to true.
>
> If i, lets say "push a button" then i want all edges
> to switch back to the state of being not deleted.
Walking through the full graph will obviously take O(n), since you need to visit every edge.
The quickest option is obviously to do remember which ones are deleted: If you delete 10 edges from a 10,000 edges graph, and store these deleted edges in a separate list, you only need to visit those 10 to undelete them.
But I agree with the previous poster who said that this might not be necessary, for a few thousand nodes the overhead of visiting them all may be hardly noticable.
Do the simple version first, and do the optimization only if required. It's quite likely that other parts of your application will be more in need of optimization than this one.
