Binary Search Method Array Java

Question

I am trying to efficiently search weather a subclass implements a method that I have the name of in a string called _szMethodName. I can get an array of all the methods that the subclass implements by doing Method[] _arrClassMethodsList = class.getMethods();. I can then compare the name of the method to the stringName of the function that I am looking for to determine weather or not the class implements that particular method. Currently I have this working in a for loop but this gets slow as the subclass grows.

For Loop implementation:

for (Method method : class.getMethods()){
       if(method.getName().equals(_szMethodName)){
          //method exists in subclass
          break;
      }
}

~~The array of methods from class.getMethods() is sorted alphabetically.~~(Only in Java >=7). I was hoping that I could leverage this by using a binary-search or some other optimization on the array instead of using the for loop. However, I have not yet been able to figure out how to implement Java's binary search function on the array. I have tried using comparator or and comparable but have not yet had success. My most recent implementation of comparator is below but has errors that I have not yet been able to resolve.

Current attempt using comparator:

Comparator<Method> c = new Comparator <Method>() {
    public int compare(Method method, String string) {
        return method.getName().compareTo(string);
    }
};

Method[] _arrClassMethodsList = class.getMethods();
int index = Arrays.binarySearch(_arrClassMethodsList, _szMethodName, c);

Any help or examples on how to get this working would be greatly appreciated. Thanks!

The Javadoc of getMethods() says the order is implementation dependent (The javadoc explicitly says "The elements in the array returned are not sorted and are not in any particular order"). I believe that in Java 7 it is alphabetical, but I believe in Java 6 it used to be definition order. So don't depend on it. — Mark Rotteveel
– Mark Rotteveel, Commented Feb 20, 2013 at 15:07

poussma · Accepted Answer · 2013-02-20 16:39:20Z

5

Why don't you use the method http://docs.oracle.com/javase/6/docs/api/java/lang/Class.html#getMethod%28java.lang.String,%20java.lang.Class...%29 to directly get the method if available and let the JVM do the job efficiently for you?

BTW, the documentation of getMethods says: "The elements in the array returned are not sorted and are not in any particular order". The binary search needs sorted data. That means you first need to sort the array.

NOTE: you should have a look to that method getMatchingAccessibleMethod that probably does what you expect.

edited Feb 20, 2013 at 16:39

answered Feb 20, 2013 at 15:06

poussma

7,3913 gold badges48 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

tehlexx Over a year ago

This will only work for public methods. For those it sounds like a reasonable way to do it.

Krejko Over a year ago

is there any way to do this without knowing the paramaters that the method takes? All I have is the string name of the method I am looking for.

Krejko Over a year ago

If I get the list of paramaters, is there any way get their classes from it in an array to pass to 'getMethod()'? One solution I am experimenting with is: Class _arrParameterClasses[]; for (Object _oParameters: _arrParameters ){ Class parameterClass = _oParameters.getClass(); _arrParameterClasses.add(parameterClass); } foundMethod = cl.getMethod(_szMethodName, _arrParameterClasses); (is there a better way to follow up a comment with a block of code?)

poussma Over a year ago

This is not that easy because of polymorphism. If you have a method sort(Collection c) and you call it with sort(new ArrayList<>()), the getMethod("sort", new Class[]{ArrayList.class}) will not return anything, but it will work if the method invocation parameters match exactly the declared arguments. see my note

Krejko · Accepted Answer · 2013-03-08 15:03:10Z

It would appear that the only real way to do this is to re-implement Binary search pulling out the method name during the search. My final implementation is below. Thanks for all the help everyone.

public final Method NOT_FOUND = null;
private Method findMethodInDelegateClassWithParameters (String _szMethodName)
{
    @SuppressWarnings("rawtypes")
    Class _cDelegateClass = m_oDelegate.getClass();

    //Get and sort array for binary search if not done, ensure methods are alphabetical before Java 7 
    if (_arrSortedMethods==null){
        _arrSortedMethods = _cDelegateClass.getMethods();   
        Arrays.sort(_arrSortedMethods, new Comparator<Method>() {
               public int compare(Method m1, Method m2) {
                   return m1.getName().compareTo(m2.getName());
               }
        });
    }

    return binarySearchForMethodNamed(_arrSortedMethods, _szMethodName);
}

public Method binarySearchForMethodNamed(Method[] _arrMethods, String _szMethodName) {
    int left = 0;
    int right = _arrMethods.length - 1;
    return binarySearchMethods(_arrMethods, _szMethodName, left, right);
    }

private Method binarySearchMethods(Method[] _arrMethods, String _szMethodName, int left, int right) {
    if (right < left) {
            return NOT_FOUND;
    }

    int mid = (left + right) >>> 1;
    String _szArrayMethodName = _arrMethods[mid].getName();
    if (_szMethodName.compareTo(_szArrayMethodName)>0) {
            return binarySearchMethods(_arrMethods, _szMethodName, mid + 1, right);
    } else if (_szMethodName.compareTo(_szArrayMethodName)<0) {
            return binarySearchMethods(_arrMethods, _szMethodName, left, mid - 1);
    } else {
            return _arrMethods[mid];
    }               
}

Collectives™ on Stack Overflow

Binary Search Method Array Java

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related