How can I optimize two similar methods?

Question

Java 7 doesn't support lambda expressions. How can I optimize two similar methods 'GetMinOfList' and 'GetMaxOfList'?

package com.example;

import java.util.ArrayList;
import java.util.List;

public class MinMax<T extends Comparable<T>> {

    private List<T> lst = null;
    public MinMax(List<T> com)
    {
        this.lst = com;
    }

    public Pair<T, T> GetMinMaxOfList()
    {
        return GetMinMaxOfList(this.lst);
    }

    private Pair<T, T> GetMinMaxOfList(List<T> list)
    {
        if(list == null || list.size() == 1)
            return null;
        //Pair<T, T>  minMax = new Pair<T, T>();
        T min, max;
        if(list.size() == 2)
        {
            if(list.get(0).compareTo(list.get(1)) < 0)
            {
                min = list.get(0);
                max = list.get(1);
                return new Pair<T,T>(min, max);
            }
        }
        //T sentry = list.get(0);
        min = GetMinOfList(list);
        max = GetMaxOfList(list);
        return new Pair<T, T>(min, max);
    }

    private T GetMinOfList(List<T> littleList)
    {
        T sentry = littleList.get(0);
        if(littleList.size() == 1)
            return sentry;

        List<T> nextLittle = new ArrayList<T>(1);
        for(T t: littleList)
        {
            if(t.compareTo(sentry) < 0)
                nextLittle.add(t);
        }
        if(nextLittle.size() == 0)
            return sentry;
        return GetMinOfList(nextLittle);
    }

    private T GetMaxOfList(List<T> lagerList)
    {
        T sentry = lagerList.get(0);
        if(lagerList.size() == 1)
            return sentry;

        List<T> nextLarge = new ArrayList<T>(1);
        for(T t: lagerList)
        {
            if(t.compareTo(sentry) > 0)
                nextLarge.add(t);
        }
        if(nextLarge.size() == 0)
            return sentry;
        return GetMaxOfList(nextLarge);
    }
}

What do you mean by *optimize*: better performance or less code? — Luiggi Mendoza, Sep 26 '13 at 03:31
Wow . . . I never though I'd see a O(n^2) recursive min or max function . . . — Aurand, Sep 26 '13 at 03:36
possible duplicate of [best way for get min and max value from a list of Comparables in java](http://stackoverflow.com/questions/369383/best-way-for-get-min-and-max-value-from-a-list-of-comparables-in-java) — TheKojuEffect, Sep 26 '13 at 03:38
@Aurand Never done an interview before? I've seen `O(n^3)` array reverse algorithms from interview candidates. — Brian, Sep 26 '13 at 03:39

James · Answer 1 · 2013-09-26T03:40:04.143

4

Less code? You can replace those methods with these:

 min = Collections.min(list); 
 max = Collections.max(list);

Though that assumes T implements Comparable. As Luiggi Mendoza points out: you can also implement a comparator and use it via the other form of min/max, if it doesn't:

 min = Collections.min(list, comparator); 
 max = Collections.max(list, comparator);

edited Sep 26 '13 at 03:40

answered Sep 26 '13 at 03:36

James

8,512
1
26
28

Probably you need to implement an anonymous `Comparator` as well. Still, this is the lesser code that accomplish the task. – Luiggi Mendoza Sep 26 '13 at 03:38

TheKojuEffect · Answer 2 · 2013-09-26T04:41:32.017

1

Java provide Collections.min(Comparables) and Collections.max(Comparables) which you can implement as follows.

private Pair<T, T> GetMinMaxOfList(List<T> list) {

        return new Pair<T, T>(getMinOfList(list), getMaxOfList(list));
}


private T getMinOfList(List<T> list) {
      return Collections.min(list)
}


private T getMaxOfList(List<T> list) {
      return Collections.max(list)
}

edited Sep 26 '13 at 04:41

answered Sep 26 '13 at 03:37

TheKojuEffect

20,103
19
89
125

score 1 · Answer 3 · answered Sep 26 '13 at 03:39

I Think your use of Recursion is not very efficient. This type of recursion and use up alot of stack memory. Also every iteration will trigger an additional ArrayList creation. Try simply looping through the given list and setting a local variable if the next element is greater than / less than depending on which function you're in

private T GetMaxOfList(List<T> littleList){
    T smallest = null;
    for(T element : littleList){
        if(smallest == null){
            smallest = element;
        } else if (smallest.compareTo(element) > 0) {
            smallest = element;
        }
    }
    return smallest
}

and vice versa.

How can I optimize two similar methods?

3 Answers3