current community

your communities

more stack exchange communities

Stack Exchange
tour help
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.
up vote 2 down vote favorite 
private void merge(ArrayList<String> operations, ArrayList<LinkedHashSet<String>> setOfStrings) {
        String toMerge = operations.get(1);
        String fromMerge = operations.get(2);
        boolean enteredFirstToMerge = false;
        boolean enteredFirstForMerge = false;
        // references that points one on toMerge and the other on fromMerge
        LinkedHashSet<String> toMergeAndAfterDelete = null;
        LinkedHashSet<String> addOnFromMerge = null;
        for (LinkedHashSet<String> subSet : setOfStrings) {
        if (subSet.contains(toMerge) && subSet.contains(fromMerge))
            break;
        else {
            if (subSet.contains(toMerge) && !enteredFirstToMerge) {
            toMergeAndAfterDelete = subSet;
            enteredFirstToMerge = true;
            }
            if (subSet.contains(fromMerge) && !enteredFirstForMerge) {
            addOnFromMerge = subSet;
            enteredFirstForMerge = true;
            }
            if ((enteredFirstForMerge && enteredFirstToMerge)) {
            break;
            }
          }
        }
        /***********************************************/
        //outside Loop i call the remove on the arraylist
        //that are very expensive    
        /*************************************************/   
        if (enteredFirstForMerge && enteredFirstToMerge) {
        // first i delete from the array the linkedHashSet toMerge and
        // fromMerge and after i add a 
        // new linkedHashSet with the subSets merged
        setOfStrings.remove(toMergeAndAfterDelete);  
        setOfStrings.remove(addToMergeOnFromMerge); 
        addOnFromMerge.addAll(toMergeAndAfterDelete);
        setOfStrings.add(addOnFromMerge);
        }
}

This function takes as parameter an arrayList of operations, and an ArrayList<LinkedHashSet<String>>:

For the arrayList of operations, I always get a specific position, so I don't iterate. It is always \$O(1)\$.

For example, if I have as operation move foo bar, I have to do these steps:

  • First of all, I have to find where are located foo and bar:

    • Inside setOfStrings, I can have this situation:

          position x : {bar tree hotel}
    ...
    position y : {foo lemon coffee}

When I find them, I have to concat the foo string into bar string in this way:

            position x : {bar tree hotel foo lemon coffee}
            ...
            position y : {}

How can I improve the efficiency of this function?

share|improve this question
    
The number one problem with your code is the formatting. Fix that and you're half done. –  AJMansfield Jun 10 at 20:55
add comment

2 Answers

up vote 3 down vote accepted

  • Abstract as much as possible over type: List instead of ArrayList.

  • Use OO where appropriate: List<String> operations should clearly be some class MoveOperation(String to, String from).

  • It's not clear why you are using LinkedHashSet instead of List.

  • The algorithm is ill-defined: what happens if there are numerous foo's or bar's.

I implemented something below, but it is in functional style, so it might be hard to read. There are three implicit loops: two for the filters and one for the map. You might also notice that I never modify a collection, but always create a new one. Again, this is the functional style. In your algorithm, you can actually shoot yourself in the foot if you modify some collections at the wrong moment.

private List<List<String>> merge2(List<String> operations, List<List<String>> listOfSentences) {
    Stream<List<String>> sentencesWithTo = listOfSentences.stream()
                                           .filter(sentence -> sentence.contains(toMerge));
    Stream<List<String>> sentencesWithFrom = listOfSentences.stream()
                                             .filter(sentence -> sentence.contains(fromMerge));

    long nTo = sentencesWithTo.count();
    long nFrom = sentencesWithFrom.count();

    if (nTo == 0  || nFrom == 0) {
        return listOfSentences;
    } else if (nTo > 1 || nFrom > 1) {
        // what to do here??
    } else {
        List<String> sentenceTo = sentencesWithTo.collect(Collectors.toList()).get(0); // should only be one element ?
        List<String> sentenceFrom = sentencesWithFrom.collect(Collectors.toList()).get(0); // should only be one element ?
        Stream<List<String>> updatedSentences = listOfSentences.stream().map(sentence -> {
            if (sentence.equals(sentenceTo))
                return Stream.concat(sentenceTo.stream(), sentenceFrom.stream()).collect(Collectors.toList());
            else if (sentence.equals(sentenceFrom))
                return new ArrayList<>();
            else 
                return sentence;
        });
        return updatedSentences.collect(Collectors.toList());
    }
}
share|improve this answer
add comment
up vote 2 down vote

Another thing to point out, this code snippet does not demonstrate what you have asked:

    // first i delete from the array the linkedHashSet toMerge and
    // fromMerge and after i add a 
    // new linkedHashSet with the subSets merged
    setOfStrings.remove(toMergeAndAfterDelete);  
    setOfStrings.remove(addToMergeOnFromMerge); 
    addOnFromMerge.addAll(toMergeAndAfterDelete);
    setOfStrings.add(addOnFromMerge);

  • First of all, I have to find where are located foo and bar:

    • Inside setOfStrings, I can have this situation:

         position x : {bar tree hotel}
    ...
    position y : {foo lemon coffee}

When I find them, I have to concat the foo string into bar string in this way:

           position x : {bar tree hotel foo lemon coffee}
            ...
            position y : {}

Your code is doing more like:

position z : {bar tree hotel foo lemon coffee}

Other minor points to highlight too:

  • ArrayList<LinkedHashSet<String>> setOfStrings isn't exactly a set of Strings, more like a list of set of Strings... in other words, perhaps you can think of a better variable name.
  • Same for the other names e.g. toMerge and fromMerge, I don't think they are easily understandable when reading the code.
  • Program to interfaces, not the implementations. I.e. instead of merge(ArrayList<String> operations, ArrayList<LinkedHashSet<String>> setOfStrings) the method signature can be merge(List<String> operations, List<Set<String>> setOfStrings).
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.