Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I need to create an efficient algorithm that returns unique values from an unsorted input. I don't know the length of the input.

As the function that will call this algorithm can abort the reading at any time, I think that using a well defined Iterable implementation is the right way, so I will not waste extra processing power for the uneeded input.

Today, I am using a Set to keep track of the values I've already read. But I don't know if this is the most efficient algorithm, as my input length can be huge.

The code below is my today's working algorithm:

import java.util.Iterator;
import java.util.HashSet;
import java.util.Set;
import java.util.NoSuchElementException;
import java.io.BufferedReader;
import java.io.StringReader;
import java.io.IOException;

public class UniqueValues implements Iterable<String> {
    private final Iterator<String> iterator;

    public UniqueValues(BufferedReader r) {
        this.iterator = new UniqueValuesIterator(r);
    }

    public Iterator<String> iterator() {
        return iterator;
    }

    static class UniqueValuesIterator implements Iterator<String> {
        private final BufferedReader r;

        private final Set<String> values = new HashSet<>();

        // When 'next' is null, need to get the next value
        private String next;

        public UniqueValuesIterator(BufferedReader r) {
            this.r = r;
        }

        public boolean hasNext() {
            // Good point from OldCurmudgeon
            if(next != null) return true;

            try {
                String line;
                while((line = r.readLine()) != null) {
                    if(values.add(line)) { // add() returns 'true' when it is not a duplicate value.
                        next = line;
                        return true;
                    }
                }
            } catch(IOException e) { }

            return false;
        }

        public String next() {
            if(next == null) {
                if(! hasNext() ) throw new NoSuchElementException();
            }

            final String temp = next;
            next = null;
            return temp;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    // For testing
    public static void main(String... args) {
        final StringReader r = new StringReader("value1\nvalue6\nvalue1\nvalue3\nvalue3\nvalue6\nvalue1\nvalue6");

        for(final String value : new UniqueValues(new BufferedReader(r)) ) {
            System.out.println(value);
        }

        /* Output is (order is not important):
         * 
         * line 1
         * line 6
         * line 3
         */
    }
}

Does it have any better algorithm to do this?

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

There are three significant issues I would address here...

  • Ratchet Freak is right about being concerned about the Iterator/FilteredReader... but I disagree with his suggestion. I think the problem is that your code is converting a BufferedReader in to an Iterator, and making the results unique at the same time. This is a class that is performing 2 functions... and you shoould have two classes instead. One that converts the BufferedReader to an interator, and the other that enforces uniqueness.

  • If your input data really is huge, then a Set may not be the right data structure because of it's memory footprint. I have found that custom implementations of memory-efficient structures can save a lot of space. I hesitate to recommend that you change from the Set though, it is the 'logical' choice, but, if, for example, your average String value is about 16 characters, then more than half of your memory will be in the Set overhead. I have, in the past, had reason to do similar things to you, and have written a memory-efficient class that can be seen in JDOM here (you will need to make changes to that code if you want to use it because it will need to have a mechanism for a true/false seen-it test).

  • I have a pattern I use for Iterators that is really effective, and makes the Iterator logic much simpler/readable. I'll give you an example....

First, part 1, a Reader-to-Iterator implementation:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.Reader;
import java.util.Iterator;
import java.util.NoSuchElementException;


@SuppressWarnings("javadoc")
public class ReaderLineIterator implements Iterator<String> {

    private final BufferedReader reader;
    private String nextval;

    public ReaderLineIterator(Reader reader) {
        this.reader = (reader instanceof BufferedReader) ? (BufferedReader)reader :
            new BufferedReader(reader);

        advance();

    }

    private void advance() {
        try {
            nextval = reader.readLine();
        } catch (IOException ioe) {
            throw new IllegalStateException("Unable to read from reader.", ioe);
        }
    }

    @Override
    public boolean hasNext() {
        return nextval != null;
    }

    @Override
    public String next() {
        if (nextval == null) {
            throw new NoSuchElementException();
        }
        try {
            return nextval;
        } finally {
            advance();
        }
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

}

Note how, in this class, I use a trick for the nextval, where it is advanced in the finally block of the next() call. This is a pattern I like because it makes the hasNext() method very light-weight, and it is always a step-ahead of the data.

So, that is a single-purpose class, it converts a Reader to a line-at-a-time Iterator.

Now, you need a unique Iterator... which can look something like:

import java.util.HashSet;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;


@SuppressWarnings("javadoc")
public class UniqueIterator implements Iterator<String> {

    private final Iterator<String> source;
    private String nextval = null;
    Set<String> seenit = new HashSet<String>();

    public UniqueIterator(Iterator<String> source) {
        this.source = source;
        advance();
    }

    private void advance() {
        while (source.hasNext()) {
            String nxt = source.next();
            if (seenit.add(nxt)) {
                // found a unique value....
                nextval = nxt;
                return;
            }
        }
        // no more unique values.
        nextval = null;

    }



    @Override
    public boolean hasNext() {
        return nextval != null;
    }

    @Override
    public String next() {
        if (nextval == null) {
            throw new NoSuchElementException();
        }
        try {
            return nextval;
        } finally {
            advance();
        }
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

}
share|improve this answer
    
a String tmp = nextval;advance();return tmp; us IMO much more readable than the needless try ... finally –  ratchet freak Feb 10 at 14:20
    
@ratchetfreak perhaps... it's a habit I am in, which makes it readable to me. If I recall, there was a case where I store any advance() exceptions to the next() call, and also, it's slightly faster without the temporary store... What I have above is the general pattern, on the whole, I think I will leave it unchanged. It shows a different mechanism and may be educational –  rolfl Feb 10 at 14:31
    
JIT will take care of "slightly faster" soon enough –  ratchet freak Feb 10 at 14:38
    
@ratchetfreak I am aware of what JIT can do, but, the times I have looked really hard at these problems, I have found the assembly that the JIT produces to be slightly inefficient (extra load/stores), and that was only part of my reasoning. –  rolfl Feb 10 at 14:41
add comment

you have a O(n) time algorithm using O(n) space I don't see how much better this can be without using an external data store or a RandomAccessFile

calling hasNext will advance the input several times which is not what you want. to fix test if next is already set:

public boolean hasNext() {
    try {
        if(next!=null)return true;
        String line;
        while((line = r.readLine()) != null) {
            if(values.add(line)) { // add() returns 'true' when it is not a duplicate value.
                next = line;
                return true;
            }
        }
    } catch(IOException e) { }

    return false;
}

however I believe that Iterator is not the right interface for this, instead consider using a FilteredReader

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.