java - Efficiency of the way comparator works -
i trying use comparator sort list of objects. have question how comparator works , doing in following example:
private static comparator<student> comparator() { return (student a, student b) -> { return integer.compare(complexoperation(a), complexoperation(b)); } } as can see above, there need compare , sort students according integer rank returned complexoperation() method. name suggests, heavy operation. above approach efficient? or better run through each student in list trying sort, perform complexoperation() per student , store result in field in student object. comparator an:
integer.compare(a.getrank(), b.getrank()) would both these approaches comparable or, due way comparator works (perhaps compares same object more once others hence running complexoperation() multiple times per student during compare), faster pre computation of complexoperation() result in student field?
the above called so:
collections.sort(students, comparator()); hope clear!
edit: lets say, sake of it, not possible add field student object (this toy problem more complex situation not @ liberty modify student object). still better perhaps create custom object student sitting inside field added rather doing complexoperation() right in comparator? or there way approach problem? can think of creating hashmap takes student id key , result of complexoperation() value , creates/access record within comparator?
on average, sort algorithm call complexoperation() method log2n times array of n students. if operation slow, may better off running once each student. bring order of magnitude improvement array of 1,000 students.
however, not have explicitly: make complexoperation(...) store result each student, , return cached value on subsequent requests:
private map<student,integer> cache = new hashmap<student,integer>(); private int complexoperation(student s) { // see if computed rank of student before integer res = cache.get(s); if (res != null) { // did! return stored result: return res.intvalue(); } ... // real computation here // save result future invocations cache.put(s, result); return result; } note in order approach work, student class needs implement hashcode , equals.
Comments
Post a Comment