A query on java performance for string equality checking

Question

I have a very large set of string URL patterns like {http://www.imdb.com, http://www.amazon.com,...} in a list.

I am getting input URL's like this:

http://www.imdb.com/title/tt1409024/

For the purpose of my application this URL is actually formed from http://www.imdb.com, so the equality of these two should be true.

To implement this, I can extract the base URL from the input URL:

http://www.imdb.com/title/tt1409024/ => http://www.imdb.com

Now I need to compare this extracted URL with the master list of URLs and store the base URL in a database, if a match is found. So in essence, for each on of my input (base) URL's, I am looking for a match in the master list for the extracted URL, and if a match is found I am storing the input (base) URL in the database.

To implement the equality/matching logic, I have two possible solutions. Please weigh in as to which is better:

Put the master list of URL's in an array list, and use the array list contains method
Put the master list in a database, and use query to check the the input url against it

Can anyone tell me which one will be better in terms of performance?

Greg Hewgill · Accepted Answer · 2012-05-28 04:12:24Z

4

Neither of your suggestions would be appropriate. For an ArrayList, you would have to search linearly through half the list (on average) for every URL you want to check.

For a database (presumably on disk?), you would incur a potentially expensive database lookup for every query.

1000 URL patterns isn't very many. Keep the list in memory and use an appropriate data structure - a HashSet would do a good job.

answered May 28, 2012 at 4:12

Greg Hewgill

1.0m192 gold badges1.2k silver badges1.3k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

n00begon · Accepted Answer · 2012-05-28 04:19:51Z

1

If you put the url of the site into a HashSet you will get the same behaviour as your arraylist solution but it will be a constant time lookup instead of variable on the length of your list.

The database solution is probably overkill for your problem as the overhead will be more than the searching efficiency gains.

edited May 28, 2012 at 4:19

answered May 28, 2012 at 4:10

n00begon

3,5123 gold badges31 silver badges42 bronze badges

Collectives™ on Stack Overflow

A query on java performance for string equality checking

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related