Skip to main content
added 280 characters in body
Source Link
slepic
  • 5.5k
  • 2
  • 9
  • 27

Avoid repeated calls to Contains() on a list. Each individual call has linear time complexity in size of the collection. This is usually a red flag that a set (HashSet) should be used instead.

This alone will reduce the time complexity of CensorWord from O(b) to O(1). And thus reducing time complexity of CensorText from O(b×(b+n)) to O(b×n). Where b is size of blacklist and n is size of input.

But in fact we could have done the same using a list like you do. Just don't call CensorWord from CensorText. You already know the word is coming from blacklist and so there is no need to check if blacklist indeed contains a word coming from blacklist. Just censor the word and trust that it is coming from blacklist.

Using a regex for a simple replace is probably overkill.

I can imagine that you might have a very long list of banned words while the input text may contain only few words. Using an algorithm with complexity that depends on size of blacklist may not be the best option. Instead, you can read the input text word by word, checking if each of them is on blacklist and censor them in place if they are. In this case, you will need the set for blacklist because you cannot avoid calling Contains() on the blacklist. Such implementation would be O(n) where n is size of input text.

Additionally, using a set gives us the benefit that blacklist automatically cannot contain duplicates. When using list you risk duplicates being present in blacklist or you would check it explicitly again with O(b) complexity for each individual word added to the blacklist.

Avoid repeated calls to Contains() on a list. Each individual call has linear time complexity in size of the collection. This is usually a red flag that a set (HashSet) should be used instead.

This alone will reduce the time complexity of CensorWord from O(b) to O(1). And thus reducing time complexity of CensorText from O(b×(b+n)) to O(b×n). Where b is size of blacklist and n is size of input.

But in fact we could have done the same using a list like you do. Just don't call CensorWord from CensorText. You already know the word is coming from blacklist and so there is no need to check if blacklist indeed contains a word coming from blacklist. Just censor the word and trust that it is coming from blacklist.

Using a regex for a simple replace is probably overkill.

I can imagine that you might have a very long list of banned words while the input text may contain only few words. Using an algorithm with complexity that depends on size of blacklist may not be the best option. Instead, you can read the input text word by word, checking if each of them is on blacklist and censor them in place if they are. In this case, you will need the set for blacklist because you cannot avoid calling Contains() on the blacklist. Such implementation would be O(n) where n is size of input text.

Avoid repeated calls to Contains() on a list. Each individual call has linear time complexity in size of the collection. This is usually a red flag that a set (HashSet) should be used instead.

This alone will reduce the time complexity of CensorWord from O(b) to O(1). And thus reducing time complexity of CensorText from O(b×(b+n)) to O(b×n). Where b is size of blacklist and n is size of input.

But in fact we could have done the same using a list like you do. Just don't call CensorWord from CensorText. You already know the word is coming from blacklist and so there is no need to check if blacklist indeed contains a word coming from blacklist. Just censor the word and trust that it is coming from blacklist.

Using a regex for a simple replace is probably overkill.

I can imagine that you might have a very long list of banned words while the input text may contain only few words. Using an algorithm with complexity that depends on size of blacklist may not be the best option. Instead, you can read the input text word by word, checking if each of them is on blacklist and censor them in place if they are. In this case, you will need the set for blacklist because you cannot avoid calling Contains() on the blacklist. Such implementation would be O(n) where n is size of input text.

Additionally, using a set gives us the benefit that blacklist automatically cannot contain duplicates. When using list you risk duplicates being present in blacklist or you would check it explicitly again with O(b) complexity for each individual word added to the blacklist.

deleted 1 character in body
Source Link
slepic
  • 5.5k
  • 2
  • 9
  • 27

Avoid repeated calls to Contains() on a list. Each individual call has linear time complexity in size of the collection. This is usually a red flag that a set (HashSet) should be used instead.

This alone will reduce the time complexity of CensorWord from O(b) to O(1). And thus reducing time complexity of CensorText from O(b² + b×nb×(b+n)) to O(b×n). Where b is size of blacklist and n is size of input.

But in fact we could have done the same using a list like you do. Just don't call CensorWord from CensorText. You already know the word is coming from blacklist and so there is no need to check if blacklist indeed contains a word coming from blacklist. Just censor the word and trust that it is coming from blacklist.

Using a regex for a simple replace is probably overkill.

I can imagine that you might have a very long list of banned words while the input text may contain only few words. Using an algorithm with complexity that depends on size of blacklist may not be the best option. Instead, you can read the input text word by word, checking if each of them is on blacklist and censor them in place if they are. In this case, you will need the set for blacklist because you cannot avoid calling Contains() on the blacklist. Such implementation would be O(n) where n is size of input text.

Avoid repeated calls to Contains() on a list. Each individual call has linear time complexity in size of the collection. This is usually a red flag that a set (HashSet) should be used instead.

This alone will reduce the time complexity of CensorWord from O(b) to O(1). And thus reducing time complexity of CensorText from O(b² + b×n) to O(b×n). Where b is size of blacklist and n is size of input.

But in fact we could have done the same using a list like you do. Just don't call CensorWord from CensorText. You already know the word is coming from blacklist and so there is no need to check if blacklist indeed contains a word coming from blacklist. Just censor the word and trust that it is coming from blacklist.

Using a regex for a simple replace is probably overkill.

I can imagine that you might have a very long list of banned words while the input text may contain only few words. Using an algorithm with complexity that depends on size of blacklist may not be the best option. Instead, you can read the input text word by word, checking if each of them is on blacklist and censor them in place if they are. In this case, you will need the set for blacklist because you cannot avoid calling Contains() on the blacklist. Such implementation would be O(n) where n is size of input text.

Avoid repeated calls to Contains() on a list. Each individual call has linear time complexity in size of the collection. This is usually a red flag that a set (HashSet) should be used instead.

This alone will reduce the time complexity of CensorWord from O(b) to O(1). And thus reducing time complexity of CensorText from O(b×(b+n)) to O(b×n). Where b is size of blacklist and n is size of input.

But in fact we could have done the same using a list like you do. Just don't call CensorWord from CensorText. You already know the word is coming from blacklist and so there is no need to check if blacklist indeed contains a word coming from blacklist. Just censor the word and trust that it is coming from blacklist.

Using a regex for a simple replace is probably overkill.

I can imagine that you might have a very long list of banned words while the input text may contain only few words. Using an algorithm with complexity that depends on size of blacklist may not be the best option. Instead, you can read the input text word by word, checking if each of them is on blacklist and censor them in place if they are. In this case, you will need the set for blacklist because you cannot avoid calling Contains() on the blacklist. Such implementation would be O(n) where n is size of input text.

added 45 characters in body
Source Link
slepic
  • 5.5k
  • 2
  • 9
  • 27

Avoid repeated calls to Contains() on a list. Each individual call has linear time complexity in size of the collection. This is usually a red flag that a set (HashSet) should be used instead.

This alone will reduce the time complexity of CensorWordCensorWord from O(n)O(b) to O(1)O(1). And thus reducing time complexity of CensorTextCensorText from O(n^2)O(b² + b×n) to O(n)O(b×n). Where nb is size of blacklist and n is size of input.

But in fact we could have done the same using a list like you do. Just don't call CensorWordCensorWord from CensorTextCensorText. You already know the word is coming from blacklist and so there is no need to check if blacklist indeed contains a word coming from blacklist. Just censor the word and trust that it is coming from blacklist.

Using a regex for a simple replace is probably overkill.

I can imagine that you might have a very long list of banned words while the input text may contain only few words. Using an algorithm with complexity that depends on size of blacklist rather then size of input text may not be the best option in such case. Instead, you can read the input text word by word, checking if each of them is on blacklist and censor them in place if they are. In this case, you will need the set for blacklist because you cannot avoid calling Contains()Contains() on the blacklist. Such implementation would be O(m)O(n) where mn is numbersize of words in input text.

Avoid repeated calls to Contains() on a list. Each individual call has linear time complexity in size of the collection. This is usually a red flag that a set (HashSet) should be used instead.

This alone will reduce the time complexity of CensorWord from O(n) to O(1). And thus reducing time complexity of CensorText from O(n^2) to O(n). Where n is size of blacklist.

But in fact we could have done the same using a list like you do. Just don't call CensorWord from CensorText. You already know the word is coming from blacklist and so there is no need to check if blacklist indeed contains a word coming from blacklist. Just censor the word and trust that it is coming from blacklist.

Using a regex for a simple replace is probably overkill.

I can imagine that you might have a very long list of banned words while the input text may contain only few words. Using an algorithm with complexity that depends on size of blacklist rather then size of input text may not be the best option in such case. Instead, you can read the input text word by word, checking if each of them is on blacklist and censor them in place if they are. In this case, you will need the set for blacklist because you cannot avoid calling Contains() on the blacklist. Such implementation would be O(m) where m is number of words in input text.

Avoid repeated calls to Contains() on a list. Each individual call has linear time complexity in size of the collection. This is usually a red flag that a set (HashSet) should be used instead.

This alone will reduce the time complexity of CensorWord from O(b) to O(1). And thus reducing time complexity of CensorText from O(b² + b×n) to O(b×n). Where b is size of blacklist and n is size of input.

But in fact we could have done the same using a list like you do. Just don't call CensorWord from CensorText. You already know the word is coming from blacklist and so there is no need to check if blacklist indeed contains a word coming from blacklist. Just censor the word and trust that it is coming from blacklist.

Using a regex for a simple replace is probably overkill.

I can imagine that you might have a very long list of banned words while the input text may contain only few words. Using an algorithm with complexity that depends on size of blacklist may not be the best option. Instead, you can read the input text word by word, checking if each of them is on blacklist and censor them in place if they are. In this case, you will need the set for blacklist because you cannot avoid calling Contains() on the blacklist. Such implementation would be O(n) where n is size of input text.

added 60 characters in body
Source Link
slepic
  • 5.5k
  • 2
  • 9
  • 27
Loading
Source Link
slepic
  • 5.5k
  • 2
  • 9
  • 27
Loading