String vs List to check if a country is part of a continent

Question

I simply need to check if a country is part of a particular continent (only one). The continent has around 50 countries. The list is constant and must be initialized at the time of creation. Which one of the solutions below is a better approach from performance point of view?

1. Having all the counties in a single string and doing simple String.contains()

   String countryList = "country1 country2";
   boolean isPartOfContinent = countryList.contains("country1");
   

2. Creating a List and using contains method

   List<String> countryList  = Arrays.asList("country1 ", "country2");
   boolean isPartOfContinent = countryList.contains("country1");
   

I realise the use case is pretty trivial to hamper performance. I feel that List is an overkill for simple stuff like this, whereas my colleague thinks Strings are "meh!" and Java programmers should stick to Lists. What would you use if you had to do this?

The number of countries won't change and is constant so maintainability and performance over a range of countries shouldn't be considered.

To summarise my question: is the use of a comparatively complex data structure than String justifiable when the requirement is so trivial?

Answer 1

String countryList = "country1 country2";
boolean isPartOfContinent = countryList.contains("country1");

This is vulnerable to usage like

String countryList = "country1 country2";
boolean isPartOfContinent = countryList.contains("count");

Which will happily give a true result.

Even the better version

String countryList = " country1 modifier country2 ";
boolean isPartOfContinent = countryList.contains(" country2 ");

Still isn't perfect. Perhaps

String countryList = ":country1:modifier country2:";
boolean isPartOfContinent = countryList.contains(":country2:");

has covered all the bases. Of course, maybe the others will work at first, since you might not have any input countries that match incorrectly.

I would go with a Set, as it better describes the data. You don't have a String of countries; you have a Set of countries on which you want to check membership. If search performance is an issue, use a SortedSet to allow a quick binary search or a constant time HashSet. Even a good string search is going to have to search through about half the string to do the contains. If all countries in the world are equally likely, you'll have a miss about 75% of the time.

Assuming there are \$n\$ countries with an average length of \$m\$, then your string will be about \$nm\$ characters long. Even a good string search will have to check almost all of them if there isn't a match, so \$\Omega(nm)\$ characters in the worst case.

Meanwhile, a binary search on a balanced tree is \$\Omega(\log n)\$ comparisons and each string comparison will tend to require less than \$m\$ character comparisons. Call it \$\Omega(m\log n)\$ character comparisons. Obviously \$\log n\$ is better than \$n\$.

All that said, performance is unlikely to be a big issue. Either should return in a tiny fraction of a second. Unless you are doing hundreds of thousands of these in a program run, you probably won't even notice any difference.

I'd use either a List or a Set because they will more reliably return correct results. I wouldn't use a String because it is harder to set it up so that it works properly. To reinforce my point, note there was a bug in my original post which required an edit to fix.

Answer 2

Option 1 is sloppy. By that logic, Guinea is a country in Oceania. The end-of-string delimiters are an important part of the data and cannot be discarded like that.

Moreover, option 2 has a chance of being faster: if the first few characters fail to match, it can skip to the next item.

However, I would say that neither implementation is recommended. Better solutions include

3. A simple data structure that allows searching in O(log n) time:

   String[] countries = new String[] { "Countries", "in", "lexicographical", "order" };
   boolean isPartOfContinent = (0 <= Arrays.binarySearch(countries, "Country1"));
   

4. A more complicated data structure that can perform lookups in constant time.

   Set<String> countries = new HashSet<String>(Arrays.asList(…));
   boolean isPartOfContinent = countries.contains("Country1");
   

Considering options 3 and 4 are not any harder to write than options 1 and 2, you might as well choose the better-performing options.

Answer 3

The thing here is that a string would not do the job. I'm not sure why you would use the wrong data structure for the job. It's not simpler, it's wrong.

The problem you face can be phrased as is this item in this collection in which case use a List or Set, or what is the value(continent) that matches this key(country) in which case use a Dictionary.

In contrast, with the string alternative asks this question: Does this sequence of characters exist somewhere in this larger sequence of characters. Which doesn't answer your question.

For example: Assume we have a 100 country names, say 10 characters long. With a list or dictionary, we have a collection with 100 items - pretty simple right? With a string, how many sequences do we have?

1,000,000! Of which only 0.01% match the semantics we are after, leaving 99.99% if matched would return an unexpected result.

Answer 4

List. Although I'm not a Java programmer specifically, I can tell you that the documentation for almost all major languages defines a list as someone like this:

List: a collection of items, stored in separate elements of the same data structure. Should be used for related but distinct items.

Countries fit this definition pretty well: related but distinct. Many documentation documents also give countries as an example of list usage.

Lastly, as others have mentioned, .contains() matches the pattern in strings, but the elements in lists. Therefore, lists are a more robust data structure for this application.

Answer 5

If it is a list of countries, then it is a list.

Also helps against:

String listOfCountries = "ukraine denmark"
//As in united kingdom, i'm not sure there are other examples, but perhaps there are countries that are substrings of other countries north ireland, (old) zealand, and others
if(listOfCountries.contains("uk"){ 
    nuke();
}

Answer 6

General

Nearly everybody has some concerns about using String as the favorite datastructure in this use case. I will try to sum up these concerns and have a look at WHY these concerns occur and WHEN they are valid or invalid.

Quotes

NPSF3000 says:

The thing here is that a string would not do the job. I'm not sure why you would use the wrong data structure for the job. It's not simpler, it's wrong.

ArtOfCode says:

Countries fit this definition (he means the "List" definition) pretty well: related but distinct.

Brythan says:

This is vulnerable (the Usage of a String)

furthermore

I would go with a Set, as it better describes the data. You don't have a String of countries; you have a Set of countries [...].

200_success says:

Option 1 is sloppy. By that logic, Guinea is a country in Oceania.

What's this all about?

My view on this is: There is a lot of confusion about adressing the correct level of abstraction. I have two glasses to put on. The "language mechanical/technical" and the "semantic".

If we talk about datastructures that support speed then we are on a technical level. If we talk about a disjunct set of countries we face the semantic level.

Technically using a String would do the job for some situations and maybe these are the only situations the use case describes.

Semantically you have a subject. Because the semantic is not modeled into an equivalent datastructure. Nearly every answer provided adresses this. The semantic of your String is not "a set of countries". It's "a concatenation of country names". As some answers pointed out the "vulnerability" of this approach. The reason for this vulnerability is exactly the datastructure that does not match the semantic.

After all this may be not a problem if you intentionally use a structure that deviates from the semantic to improve performance. But you have to know that any deviation from the real structure goes with drawbacks. You get redundancy, vulnerability, inextensibility, unmaintainability and all the stuff that code quality decreases. These drawbacks may be jusified to the goal you want to achieve.

BUT: This does not release you from the responsibility to provide the "correct" datastructure representation of the semantic as other algorithms maybe want to work on it. You should always provide a sufficient correct model of the part of the reality the use case needs. After that you can think about mapping it to a datastructure that may have drawbacks but the algorithms will work under certain metrics.

So my core statement is:

Beside ANY performance subjects I do not want to adress: The String will technically do the job for ONE use case. But you have to expect drawbacks in OTHER use cases as the datastructure representation does not match reality as use cases came from reality. It is a distorted model of the reality and this is expected to be acceptable for a small area but error prone for other areas.

Metaphor

Think about a chair and a desk. You may have the idea to omit the chair in your model because you can also sit on the desk AND you have al lot of space left to put other things there. So why use a chair anyway? Technically you could put everything on a table. Semantically a table is not meant for that because both and a chair may have properties that are not that obvious but the algorithms want to work on it. One person may sit on the table, two or three will certainly break it. One person may sit on the table for an hour but not for a whole day. You will have drawbacks if you use objects in a way that they are not made for. So the concatenated names of countries.

Suggestion

Not that surprising: I would go for the "Set of Countries". But if you think the perfmormance can be better with another datastructure you should map the correct representation to the datastructure that provides more performance WITHOUT touching the model that represents reality best as you do not want other algorithms to take the burden of the drawbacks.