performance - Algorithm: Selecting common elements of a collection -
i had write following algorithm:
given group of tags, , group of blog posts, blog post may contain zero-to-many tags, return tags common posts.
this comparison being done in-memory - accessing either collection does not cause trip across network (ie., database, etc).
also, tags collection not have reference blogposts contain it. blogposts have collection of tags contain.
below implementation. performs fine, i'm curious if there better way implement it.
my implementation in actionscript, i'm curious more algorithim perspective, examples in language fine. (but if don't know language, may ask clarify aspects)
any examples of improvements received.
private function getcommontags(blogposts:vector.<blogpost>):vector.<tag> { var commontags:vector.<tag> = new vector.<tag>(); if (!blogposts || blogposts.length == 0) return commontags; var blogpost:blogpost = blogposts[0]; if (!blogpost.tags || blogpost.tags.length == 0) return commontags; commontags = vector.<tag>(blogposts[0].tags); each (var blogpost:blogpost in blogposts) { if (!blogpost.tags || blogpost.tags.length == 0 || commontags.length == 0) // updated fix bug mentioned below // optomized exit - there no common tags return new vector.<tag>(); each (var tag:tag in commontags) { if (!blogpost.containstagid(tag.id)) { commontags.splice(commontags.indexof(tag),1); } } } return commontags; }
well, need efficient algorithm computing intersection of 2 sets because can repeatedly invoke algorithm more 2 sets.
a quick algorithm add items of first set hash table , iterate through second set checking hash table see if present; if add list of items returned in intersection.
Comments
Post a Comment