PullMonkey Blog

31 Mar

Intersection of Array of Arrays - Ruby


Have you ever needed to retrieve the intersection of arrays in an array. Well, I did.

Let's say that you have a has and belongs to many (habtm) association between articles and tags, (I.e., a tag habtm articles and an article habtm tags). This means that tag.articles will return a list of articles that have that tag and article.tags will return the tags of the article. So if a user wants to search your blog for all articles that have 'tag1' and 'tag2', you would return all common articles.

Picture a search page with a list of check boxes, one for each tag that you have. The user can click as many tags as they want and then it is your job to find the common articles between them. The search POST contains the ids of the selected tags, like params[:tag_ids] = ["1", "3", "15"] or something. Let's go with this example.

1) The first step is to find those tags:

1
>> tags = Tag.find(params[:tag_ids])

2) Next, we want to get the articles associated with each tag, we will work with the ids:

1
2
>> tags.map(&:article_ids)
=> [[1,2,3],[2,3,4,5],[2,3,6]]

So we have our array of arrays of article ids.

3) Turn each sub array into a string like "[1,2,3]"

1
2
>> tags.map(&:article_ids).map(&:to_json)
=> ["[1, 2, 3]", "[2, 3, 4, 5]", "[2, 3, 6]"]

4) Join by the intersection symbol (&) like this:

1
2
>> tags.map(&:article_ids).map(&:to_json).join("&")
=> "[1, 2, 3]&[2, 3, 4, 5]&[2, 3, 6]"

5) Run eval() against this string:

1
2
>> eval(tags.map(&:article_ids).map(&:to_json).join("&"))
=> [2,3]

This means that the tags we selected have common articles with ids of 2 and 3.

So a one-liner would be:

1
2
>> Article.find(eval(Tag.find(params[:tag_ids]).map(&:article_ids).map(&:to_json).join("&")))
=> <returns an array of article objects>





Filed under: Home, development, ruby Tags:


2 Responses to “Intersection of Array of Arrays - Ruby”

  1. By kourge on Mar 31, 2008 | Reply

    Converting the arrays to strings using to_json, then forcing the interpreter to reevaluate them is slow.
    The faster way is:
    Tag.find(params[:tag_ids]).map(&:article_ids).inject {|x, y| x & y }

    If you’re using Ruby 1.9, it can be even shorter because inject can take a symbol for a method name:
    Tag.find(params[:tag_ids]).map(&:article_ids).inject(:"&")

  2. By charlie on Mar 31, 2008 | Reply

    @kourge - thanks a ton, that is perfect, you’re the man!

Sorry, comments for this entry are closed at this time.