Unique List (List + Dictionary?)

  • Thread starter Thread starter Sin Jeong-hun
  • Start date Start date
S

Sin Jeong-hun

For example, I want to extract unique words from some text. Using
List<string> to store the extracted words in the following way will be
inefficient
List<String> words;
foreach(String word in text)
{
if(words.Contains(word)==false) words.Add(word);
}
because, according to the documentation, the Contains is an O(n)
operation.
I was looking for something like a UniqueList but I couldn't. Up until
now, I was using something like
Dictionary<String, object> words;
object dummy = null;
foreach(String word in text)
{
words[word]=dummy;
}
This works but using unnecessary "dummy" object makes the code look
dirty. What would be the best way to achieve what I'm trying to do?
Thanks.
 
Sin said:
For example, I want to extract unique words from some text. Using
List<string> to store the extracted words in the following way will be
inefficient
[...] I was using something like
Dictionary<String, object> words;
object dummy = null;
foreach(String word in text)
{
words[word]=dummy;
}
This works but using unnecessary "dummy" object makes the code look
dirty. What would be the best way to achieve what I'm trying to do?
Click to expand...

Sounds like you want the HashSet<T> class.
 
For example, I want to extract unique words from some text. Using
List<string> to store the extracted words in the following way will be
inefficient
List<String> words;
foreach(String word in text)
{
if(words.Contains(word)==false) words.Add(word);
}
because, according to the documentation, the Contains is an O(n)
operation.
I was looking for something like a UniqueList but I couldn't. Up until
now, I was using something like
Dictionary<String, object> words;
object dummy = null;
foreach(String word in text)
{
words[word]=dummy;
}
This works but using unnecessary "dummy" object makes the code look
dirty. What would be the best way to achieve what I'm trying to do?
Thanks.
Click to expand...

If you are using framework 3.5 or later, you can use a HashSet<string>.
The hash set automatically ignores duplicates, so you can just add all
the strings to it and at the end it will only contain one of each:

HashSet<string> words = new HashSet<string>();
foreach (string word in text) {
words.Add(word);
}

You can also use the Distinct extension method to create a distinct
result. This gives simpler code, but has slightly more overhead:

List<string> words = text.Distinct().ToList();

For earlier versions of the framework the dictionary is the best option.
However, you can use a smaller data type than an Object reference, and
one that is not a reference type (as the garbage collector has to scan
all references each run), like a Dictionary<string, byte>.
 
Göran Andersson said:
If you are using framework 3.5 or later, you can use a HashSet<string>.
The hash set automatically ignores duplicates, so you can just add all
the strings to it and at the end it will only contain one of each:

HashSet<string> words = new HashSet<string>();
foreach (string word in text) {
words.Add(word);
}
Click to expand...

The above can be replaced with:

HashSet<string> words = new HashSet<string>(text);

…where in both examples, of course, whatever "text" is, it's declared to
be IEnumerable said:
You can also use the Distinct extension method to create a distinct
result. This gives simpler code, but has slightly more overhead:

List<string> words = text.Distinct().ToList();
Click to expand...

The extension method only works in a situation when you could pass the
object directly to the HashSet constructor, and just using the HashSet
constructor is simpler than the above (and results in an object that
continues to have the "set" semantics desired).
For earlier versions of the framework the dictionary is the best option.
However, you can use a smaller data type than an Object reference, and
one that is not a reference type (as the garbage collector has to scan
all references each run), like a Dictionary<string, byte>.
Click to expand...

Seems like a premature optimization to me. The generational GC in .NET
will minimize whatever nominal overhead there is in managing the
dictionary (since it still has to scan the key, which has data locality
with the value, the bulk of the overhead involved is in the memory i/o
cost which is incurred regardless). As far as the data type being
smaller, I doubt there will be any difference between using "object" and
"byte", because the value is stored inside a managed struct with other
data elements, the size of which is likely aligned to at least 32-bit size.

Pete
 
For example, I want to extract unique words from some text. Using
List<string>  to store the extracted words in the following way will be
inefficient
List<String>  words;
foreach(String word in text)
{
    if(words.Contains(word)==false) words.Add(word);
}
because, according to the documentation, the Contains is an O(n)
operation.
I was looking for something like a UniqueList but I couldn't. Up until
now, I was using something like
Dictionary<String, object>  words;
object dummy = null;
foreach(String word in text)
{
     words[word]=dummy;
}
This works but using unnecessary "dummy" object makes the code look
dirty. What would be the best way to achieve what I'm trying to do?
Thanks.
Click to expand...

If you are using framework 3.5 or later, you can use a HashSet<string>.
The hash set automatically ignores duplicates, so you can just add all
the strings to it and at the end it will only contain one of each:

   HashSet<string> words = new HashSet<string>();
   foreach (string word in text) {
     words.Add(word);
   }

You can also use the Distinct extension method to create a distinct
result. This gives simpler code, but has slightly more overhead:

   List<string> words = text.Distinct().ToList();

For earlier versions of the framework the dictionary is the best option.
However, you can use a smaller data type than an Object reference, and
one that is not a reference type (as the garbage collector has to scan
all references each run), like a Dictionary<string, byte>.
Click to expand...


When I read the OP's question, I was also thinking that HashSet is
what s/he was looking for. But on 2nd thought, I am wondering how
different is HashSet from a List or Dictionary in terms of
performance. HashSet does save us from one or two lines comparing if
the next item is already in the collection, but how is HashSet
implemented? In its implementation, doesn't it still need to compare
if the next item is already in the set? Other than saving us a couple
of lines of code, does HashSet really improve the performance?
 
csharper said:
When I read the OP's question, I was also thinking that HashSet is
what s/he was looking for. But on 2nd thought, I am wondering how
different is HashSet from a List or Dictionary in terms of
performance. HashSet does save us from one or two lines comparing if
the next item is already in the collection, but how is HashSet
implemented? In its implementation, doesn't it still need to compare
if the next item is already in the set? Other than saving us a couple
of lines of code, does HashSet really improve the performance?
Click to expand...

Yes, because the way a HashSet stores its items speeds up searches
enormously in comparison with the way a List operates. With a List, a
search has to examine the existing items one by one. With a HashSet, the
search uses arithmetic to compute where the item will be located if it's
already a member, and checks that location directly. See
http://www.vcskicks.com/hashset.php for a sample performance comparison.
 
When I read the OP's question, I was also thinking that HashSet is
what s/he was looking for. But on 2nd thought, I am wondering how
different is HashSet from a List or Dictionary in terms of
performance. HashSet does save us from one or two lines comparing if
the next item is already in the collection, but how is HashSet
implemented? In its implementation, doesn't it still need to compare
if the next item is already in the set? Other than saving us a couple
of lines of code, does HashSet really improve the performance?
Click to expand...

The name HashSet somewhat implies that it uses a hash table.

Meaning that lookup is a O(1) operation.

So performance of HashSet would be similar to Dictionary
and much better than List which is O(n) for lookup.

List is better for indexing.

Arne
 
Arne said:
And if .Split(' ') is added to both, then they will both
compile.
Click to expand...

They compile fine as long as "text" already implements IEnumerable<string>.

There was nothing in the original post to suggest it didn't, as you seem
to be assuming (in fact, the original post strongly suggests it
_does_…the OP didn't show any declaration of "text", but it is already
being used as an enumerable type in the OP).

Pete
 
The above can be replaced with:

HashSet<string> words = new HashSet<string>(text);
Click to expand...

Good point.
…where in both examples, of course, whatever "text" is, it's declared to


The extension method only works in a situation when you could pass the
object directly to the HashSet constructor, and just using the HashSet
constructor is simpler than the above (and results in an object that
continues to have the "set" semantics desired).
Click to expand...

Yes, supposing that the set is the desired result. If you just want a
list as the result, there is no specific advantage of going the way over
a set.
Seems like a premature optimization to me. The generational GC in .NET
will minimize whatever nominal overhead there is in managing the
dictionary (since it still has to scan the key, which has data locality
with the value, the bulk of the overhead involved is in the memory i/o
cost which is incurred regardless). As far as the data type being
smaller, I doubt there will be any difference between using "object" and
"byte", because the value is stored inside a managed struct with other
data elements, the size of which is likely aligned to at least 32-bit size.
Click to expand...

The implementation seems to have changed in the latest framework... The
keys and values used to be stored in separate arrays, which would
definitely make the value array smaller with a smaller data type.
 
Göran Andersson said:
[...]
The extension method only works in a situation when you could pass the
object directly to the HashSet constructor, and just using the HashSet
constructor is simpler than the above (and results in an object that
continues to have the "set" semantics desired).
Click to expand...

Yes, supposing that the set is the desired result. If you just want a
list as the result, there is no specific advantage of going the way over
a set.
Click to expand...

Yes, but under what scenario would the list be the desired result? It
seems contrary to the original problem requirement. In general, the
HashSet<T> will offer all the same operations that a List<T> would,
including enumeration.

I could see maybe wanting the data sorted, in which case having it in a
list would be useful. But in that case, one could easily check for
uniqueness _and_ sort at the same time using, for example,
[QUOTE="SortedList said:
[...] As far as the data type being
smaller, I doubt there will be any difference between using "object" and
"byte", because the value is stored inside a managed struct with other
data elements, the size of which is likely aligned to at least 32-bit
size.
Click to expand...

The implementation seems to have changed in the latest framework... The
keys and values used to be stored in separate arrays, which would
definitely make the value array smaller with a smaller data type.[/QUOTE]

The 2.0 CLR has the same implementation as the current one. If there
was ever an implementation that stored the values in standalone array,
it would be the 1.1 CLR which hasn't been in common use for many years.

Pete
 
Back
Top