6

For example, I have an object:

public class Obj{
    public int a;
    public float b;
    public String c;
}

I need to find best "Obj": largest a and then largest b and then longest c:

int bestIndex = 0;
int bestA = 0;
float bestB = 0.0f;
String bestC = "";

for(int i = 0; i < objArray.length; i++){
   Obj obj = objArray[i];
   if(obj.a > bestA || 
     (obj.a == bestA && obj.b > bestB) ||
     (obj.a == bestA && obj.b == bestB && obj.c.length() > bestC.length())){
       bestIndex = i;
       bestA = obj.a;
       bestB = obj.b;
       bestC = obj.c;
   }
}

I found it is difficult to maintain because:

  1. it needs to repeat "obj.a == bestA"
  2. it is very hard to add new condition or swap condition because it needs to rewrite whole if statements, ie : add "d" property so that "a then d then b then c":
obj.a > bestA || 
(obj.a == bestA && obj.d > bestD) ||
(obj.a == bestA && obj.d == bestD && obj.b > bestB) ||
(obj.a == bestA && obj.d == bestD && obj.b == bestB && obj.c.length() > bestC.length()))

Is there any design pattern to refactor so that "obj.a == bestA" and other equal statements would appear once only?

If possible, is there any method to rewrite the code so that the following keyword (not counting declaring bestA, bestB, bestC) would appear at most once only?

obj.a
obj.b
obj.c
bestA
bestB
bestC

or any simpler code to find the best Obj?

14
  • 13
    Important note: comparing two floats with == or != is most often a bad idea if the floats are the results of computations, because floating-point calculations result in approximate results, and even the smallest approximation might result in two floating-point numbers testing as unequal. GCC even has a standard warning option -Wfloat-equal to produce a warning whenever floats are compared for equality.
    – Stef
    Aug 2, 2023 at 12:25
  • 13
    @Stef: Floating point operations give exact results. Not necessarily the results that you wanted, but they are exact numbers. a == b is true if the numbers are the same, and false otherwise. HOWEVER with NaNs neither <, == or > is true. Which makes sorting an array of floating-point numbers including NaNs tricky.
    – gnasher729
    Aug 2, 2023 at 13:58
  • 12
    It sounds like gnasher729 is reading "floating-point calculations result in approximate results" as "floating-point calculations return values that inherently represent a range of possible numbers" (a common misconception about floating point), rather than "floating-point calculations return values that are only approximations of what the result would be if the calculation were done in exact arithmetic". I would not personally read it that way, and I would consider gnasher's statement of "Floating point operations give exact results" as misleading, even if the intended meaning may be correct. Aug 3, 2023 at 7:23
  • 1
    @gnasher729 That's a misleading statement. Computations involving floating-point numbers are likely to return different values depending on compiler flags even on the same computer and with the same compiler. This is a good reason not to use equality comparisons with floating-point numbers. Yes, a floating-point number is a specific number that you can compare to another number. But equality comparison tends to not do what the programmer intended (witness the many, many questions on this site about this). Aug 4, 2023 at 20:11
  • 2
    @JimmyJames I don't know Java very well, but I wouldn't count on it. Yes, running the same function with the same input twice should give you the same result twice. But if you turn around for a second instructions get reordered, and you're no longer getting the exact same floating-point numbers. The same line of code in different contexts can be optimized differently, and do the flatting-point computations in a different order. This happens on all platforms and all languages I've worked with (except maybe BASIC in the 1980's!). Is the Java JIT allowed to do this type of reordering too? Aug 4, 2023 at 21:54

7 Answers 7

33

Is there any design pattern

NO. design patterns are solutions on a higher level of abstraction, often language agnostic. This question, however, is about programming idioms.

Is there any method to rewrite the code

Yes.

Extract the comparison into a method of its own, for example:

public class Obj{
    public int a;
    public float b;
    public String c;
    public int compareTo(Obj otherObj){
        if(a>otherObj.a)
            return 1;
        if(a<otherObj.a)
            return -1;
        if(b>otherObj.b)
            return 1;
        if(b<otherObj.b)
            return -1;
        if(c.length()>otherObj.c.length())
            return 1;
        if(c.length()<otherObj.c.length())
            return -1;
        return 0;
    }
}

Side notes:

  • this is "air code", I did not let a compiler check this, and I am not really a Java programmer, so it surely has bugs - but I guess you get the idea.
  • You can make this an implementation of the interface Comparable<Obj>, if you like

Of course, you still need two comparisons per attribute, but not more, even when you are going to add more attributes. Moreover, the indentation level stays constant, the whole method has a clear, simple and readable structure and it will be straightforward to extend. Alternatively, one could implement this along the lines of

 int compA = a.compareTo(obj.a);
 if(compA!=0)
      return compA;
 int compB = b.compareTo(obj.b);
 if(compB!=0)
      return compB;
 // ...

using one call to compareTo instead of two comparisons with < and >.

Now, you can rewrite the loop as follows:

Obj bestObj=null;
int bestIndex=-1;  

for(int i=0;i<objArray.length;i++){
   Obj obj=objArray[i];
   if(bestObj==null || obj.compareTo(bestObj)>0) {
        bestObj=obj;
        bestIndex=i;
   }
}

This solution has a better separation of concerns, uses less helper variables and does not mask the case of an empty array by returning zero / empty strings. It will also work when a and b contain negative values.

9
  • May I suggest replacing the for loop with a sort, using your compare function? Then just pick the first (or last) object in the list. Shorter and simpler, maybe even faster if Java's standard lib has a decent sort implementation.
    – Wololo
    Aug 2, 2023 at 13:14
  • 9
    @Wololo: definitely not, for a few reasons. Using sort for finding a maximum or minimum may be only faster for very small arrays (and maybe not even then). Standard sort implementations with quick sort or merge sort require O(N*log(N)) operations, finding min or max just O(N). sort also requires an additional helper array if one does not want to mutate the original array. It also requires additional work for determining the array index. ... (1/2)
    – Doc Brown
    Aug 2, 2023 at 13:23
  • 7
    ... Moreover, I wanted to keep that part of my answer as near to the original question's code as possible, so the OP can compare the new implementation directly to the old one. (2/2)
    – Doc Brown
    Aug 2, 2023 at 13:25
  • 2
    This is the way I would do it. If speed is important, it is faster to have a function isBetter that just compares for "great than" and returns true/false
    – vals
    Aug 2, 2023 at 14:56
  • 2
    @vals your approach with isBetter would not be any faster than compareTo
    – ciamej
    Aug 2, 2023 at 17:18
27

Using the Comparator API, it is very much possible to implement the problem using very little repetition. If you don't need bestIndex, you can the use Streams to find the maximum or minimum element.

Comparator<Obj> comparator = Comparator.<Obj>comparingInt(o->o.a)
    .thenComparingDouble(o->o.b)
    .thenComparing(o->o.c);
Obj best = Arrays.stream(objArray).max(comparator).get();

If you really need the index, which is usually avoided when using Stream APIs, try this:

int bestIndex = IntStream
    .range(0, objArray.length)
    .boxed()
    .max(Comparator.comparing(i->objArray[i], comparator))
    .get();
11
  • @DocBrown Right, I added an alternative.
    – corvus_192
    Aug 2, 2023 at 16:08
  • What exactly is he assuming ? The OP says he needs the best object, not the best index, the OP's solution which he is clearly not satisfied with (and rightly so) has the bestIndex as a side effect of his implementation. corvus_192's answer is the quintessentially correct java solution.
    – user467257
    Aug 2, 2023 at 20:18
  • It's too bad there isn't a getter, instead of field access. If it were record Obj for instance, then it could be written comparingInt(Obj::a) etc. instead of lambda syntax. Aug 2, 2023 at 21:50
  • 1
    Interesting solution but do you really think that a person asking this kind of question is prepared to build such code?
    – JimmyJames
    Aug 3, 2023 at 21:08
  • 15
    @JimmyJames They certainly will never be, if no one shows them such code.
    – walen
    Aug 4, 2023 at 10:11
12

Doc Brown's guidance is very good (as usual) and I don't want to reiterate what he wrote. However, as a basic programming skill, you should understand how to reduce such a statement. As others have noted, you can avoid retesting the same conditions over and over again. I think their results are the same as what I get when I simplify but it's a little difficult to read such statements. (I'll come back to that later.)

Let's start with your original statement. I've reformatted it to make things clearer. I am not suggesting using this formatting. It's just for demonstrative purposes:

obj.a > bestA 
|| 
(
  obj.a == bestA && obj.d > bestD
) 
||
(
  obj.a == bestA && obj.d == bestD && obj.b > bestB
)
||
(
  obj.a == bestA && obj.d == bestD && obj.b == bestB && obj.c.length() > bestC.length()
)

We know that (A && B) || (A && C) is equivalent to A && (B || C). If you aren't sure about this, I suggest taking some time to think about it and convince yourself of this fact.

Using this we can remove the duplicative obj.a == bestA checks like so:

obj.a > bestA 
|| 
(
  obj.a == bestA 
  && 
  (
    (obj.d > bestD)
    ||
    (obj.d == bestD && obj.b > bestB)
    ||
    (obj.d == bestD && obj.b == bestB && obj.c.length() > bestC.length())
  )
)

OK things are a little shorter now and we can see that there's another duplicative check of obj.d == bestD that we can remove in the same way:

obj.a > bestA 
|| 
(
  obj.a == bestA 
  && 
  (
    (obj.d > bestD)
    ||
    (
      obj.d == bestD 
      && 
      (
        (obj.b > bestB)
        ||
        (obj.b == bestB && obj.c.length() > bestC.length())
      )
    )
  )
)

I may have made an error here. Statements like this are hard to read and follow. Which brings me to my final point: you shouldn't do this much logic in a single expression if you can avoid it. Either do something like Doc Brown explains in his answer or, you can at least do something along the lines of:

boolean isBetter(Foo obj) {
   if (obj.a > bestA) {
       return true;
   } else if (obj.a == bestA) {
       if (obj.d > bestD) {
           return true;
       } else if (obj.d > bestD) {
           if (obj.b > bestB) {
               return true;
           } else if (obj.b == bestB) {
               return obj.c.length() > bestC.length();
           }
       }
   }

   return false;   
}

Which is a pretty straightforward mapping of the above. I would definitely say go farther and do something like this instead:

boolean isBetter(Foo obj) {
   if (obj.a > bestA) {
       return true;
   } else if (obj.a < bestA) {
       return false;
   } else if (obj.d > bestD) {
       return true;
   } else if (obj.d < bestD) {
       return false;
   } else if (obj.b > bestB) {
       return true;
   } else if (obj.b < bestB) {
       return false;
   } else {
       return obj.c.length() > bestC.length();
   }
}

Which is similar to the compare example given by Doc Brown.

However, I still think we can do better. One way to think about this kind of thing is that you want to compare to composite types based on some order of precedence of their components. This comes up a lot. For example a date can be represented as a year, month, and a day. If the years are different, it doesn't matter what the month or day is. If the year is the same and the month is different, it doesn't matter what the day is. As such we can restructure this as:

boolean isBetter(Foo obj) {
   if (obj.a != bestA) {
       return obj.a > bestA;
   } else if (obj.d != bestD) {
       return obj.d > bestD;
   } else if (obj.b != bestB) {
       return obj.b > bestB;
   } else {
       return obj.c.length() > bestC.length();
   }
}

Lastly, on a side note, there's no reason to keep separate variables like bestA, bestB, etc. Just one variable called best will suffice.

If you want to go the Comparable route, you can use that last approach thusly:

public int compareTo(Foo other) {
   if (obj.a != other.a) {
       return obj.a - other.a;
   } else if (obj.d != other.d) { // assuming d is an integer type.
       return obj.d - other.d;
   } else if (obj.b != other.b) { // DANGER! b is a float
       return obj.b > other.b ? 1 : -1;
   } else {
       return obj.c.length() - other.c.length();
   }
}

I should note that if you have a very wide range of ints, the above approach might run into issues. For example, if you have numbers that could be in the billions and can be negative as well as positive. That is, if you ever have two numbers around Integer.MAX_VALUE apart.

Not directly related to your question, but as noted in the comments, you need to make special considerations around floats. Either make sure you will never have NaN values or consider how you want to deal with them in these comparisons.

P.S. After seeing corvus_192's answer, I must admit that it would be the next step in the progression laid out here. I'm rusty when it comes to Java and I wasn't aware of the methods. Essentially, that answer is doing the same thing as the last code example here with less boilerplate.

3
  • 1
    Your step-by-step approach is surely one possible way of approaching such a problem. My own thought process (which lead me to my answer), however, was a somewhat different. The first thing I started with was the extraction of the comparison into a separate method - to split a larger problem into two smaller ones. Then I focussed on the structure of the comparison alone. compareTo returning -1,0 or 1 is a standard idiom in C# and I guess in Java, too, with a standard interface. The implementation I suggested first is also a standard idiom for me.
    – Doc Brown
    Aug 3, 2023 at 8:03
  • 2
    @DocBrown It's a common mistake in Java to assume that compareTo will return -1, 0, or 1. However, that is an error. I would expect most developers that make that error to find that is a bad assumption when dealing with Strings, Integers or other built-in classes that implement Comparable and/or Comparators and return other values.
    – JimmyJames
    Aug 3, 2023 at 14:57
  • 1
    @DocBrown My previous response might have come off as a little snarky. I meant to be clear that your answer is absolutely correct and valid. I tend to prefer my last code example, but I would absolutely accept yours in a code review. My reason for adding an answer here was that the OP (and any other serious developer) should see right away that the original statement can be reduced. There might be reasons to not do that but it's cut-and-dried that you can.
    – JimmyJames
    Aug 3, 2023 at 20:56
3
condition = 
   Obj.a != bestA ? obj.a > bestA :
   Obj.d != bestD ? Obj.d > bestD :
   Obj.b != bestB ? obj.b > bestB :
   Obj.c.length() > bestC.length();

Some languages have “compare” functions returning less, equal, or greater. Then you write

Result = compare(obj.a, bestA)
If (Result == equal) result = compare (obj.d, bestD)

and so on. No compare operation is repeated. Quite important for string compares and comparing complex objects.

7
  • 2
    This answer has two differences relative the other answer before accointing for spawning a function. First, it requires != operator in addition to > operator, which you have not always, but often enough. Second, it we are to travel well down the list, it makes just N comparisons, not 2N comparisons, which might matter in some tight loops and/or comparing long things like things. Aug 2, 2023 at 11:53
  • @EugeneRyabtsev That was kind of intentional. For things like floating point numbers where sometimes <, == and > are all false. But everything should fall into one of the categories a > b, a != b, and then we assume a == b.
    – gnasher729
    Aug 2, 2023 at 13:55
  • Note that the precedence in nested ternaries is not always obvious, and PHP has recently started requiring parentheses to ensure that you get what you expect.
    – Barmar
    Aug 2, 2023 at 14:53
  • I would avoid ternaries except when they come in patterns like here. With that kind of pattern a ternary stretching over 100 lines is easy to read and write.
    – gnasher729
    Aug 2, 2023 at 21:49
  • @gnasher As far as I can see your proposed solution doesn't guarantee a total order for floats either (at least not in Java or any other language that has the standard float operators), so it doesn't really help there. I'd imagine that in general if < or > do not guarantee a total order then adding an equal check cannot fix correctness in the general case (but this seems non-trivial to prove). But then floats are theoretically notoriously awful for comparisons and in practice it works just fine.
    – Voo
    Aug 3, 2023 at 12:37
1

In a language that had a <=> operator and a short-circuiting || operator that works on integral types, this might be

if ((
  (obj.a <=> bestA) || 
  (obj.b <=> bestB) || 
  (obj.c.length() <=> bestC.length())
) > 0)

The <=> would return -1, 0, 1 for less, equal, and greater respectively, and the || operator would return its LHS if nonzero, otherwise its RHS. This allows "comparison chaining", in which the result of the overall comparison is the first of the individual comparison expressions to find an inequality. By requiring that inequality to be >, you get the result you want.

However, Java is not such a language. The nearest thing to <=> is the compareTo method (which is not very succinct), and || only operates on booleans (which defeats the possibility of chaining). As such, the best and most idiomatic thing you could do is to write your own compareTo, which compares the sub-elements one at a time and short-circuits explicitly, exactly as Doc Brown suggested.

2
  • 3
    Chaining is possible with Comparators. See corvus's answer. Aug 2, 2023 at 21:51
  • I’ll have to try if that can be implemented in Swift. Implementing || for Integer should be no problem.
    – gnasher729
    Aug 2, 2023 at 21:53
1

You can of course use distributivity. Your code in item 2 is equivalent to:

obj.a>bestA || (obj.a==bestA && (
obj.d>bestD || (obj.d==bestD && (
obj.b>bestB || (obj.b==bestB && (
obj.c.length()>bestC.length() )) )) ))

(But of course defining a proper comparison is far better.)

3
  • A proper comparison function might be better, but you would have the same problem since you don’t want your comparison function call a comparison function.
    – gnasher729
    Aug 2, 2023 at 22:11
  • @gnasher729 I don't understand your comment. The 'comparison' in my answer refers to a previous answer. What do your two 'comparison's refer two?
    – Pablo H
    Aug 3, 2023 at 14:26
  • 1
    This code has echoes of the well known abuse of ternary statements
    – Peter M
    Aug 4, 2023 at 13:33
1

As with most programming problems, the problem becomes vastly easier by choosing the right data model and data structures and leaning on existing algorithms than rolling your own.

Most modern mainstream programming languages already provide an algorithm for finding the maximum value in a collection, so we simply call that instead of writing our own. Typically, the only requirement this algorithm has is that our collection elements must define a total order among them.

So, all we need to do is define a total order among our Objs. And again, most modern programming languages already provide a protocol for us to implement.

Also, most modern mainstream programming languages provide some sort of product type data structure, like a tuple, which already implements the ordering protocol using a lexicographic ordering, which is exactly what we want: so, all we need is to provide an ordering key in the form of such a product type based on the state of Obj.

Here is a (runnable) example in Ruby:

Obj = Data.define(:a, :b, :c) do
  include Comparable
  def <=>(other) = ordering_key <=> other.ordering_key
  protected def ordering_key = [a, b, c.size]
end

o1 = Obj.new(1, 1, "")
o2 = Obj.new(1, 1, "9")
o3 = Obj.new(1, 1, "11")

[o1, o3, o2].max #=> #<data Obj a=1, b=1, c="11">

First, we mix the Comparable mixin into our Obj class:

This makes instances of Obj comparable to each other and defines the methods Comparable#<, Comparable#<=, Comparable#==, Comparable#>, Comparable#>=, Comparable#between?, and Comparable#clamp for us. The Comparable protocol is very simple and only requires us to define one method: <=>, the so-called spaceship operator.

At first glance, this doesn't help us much because in order to define the spaceship operator, we still need to implement all that logic. But actually, that is not true: in the implementation of the spaceship operator, we can forward the call to another object which already has the spaceship operator implemented in the way we want.

And luckily, one such object already exists: Arrays are ordered lexicographically, i.e., first by their first element, then by their second element, then their third, and so on. Which is exactly what we need: we want Obj to be ordered first by a, then by b, and then by c's length, so all we need is an Array whose first element is a, whose second element is b, and whose third element is c.size.

We could do this inline in our implementation of <=>, but instead I have chosen to provide an attribute reader named ordering_key.

Now that we have made sure that our Objs have a well-defined total ordering, we can use existing Enumerable methods such as Enumerable#max to find the maximum element in a collection.

Similarly, here is a (runnable) example in Scala:

final case class Obj(a: Int, b: Float, c: String) extends Ordered[Obj]:
  private val orderingKey = (a, b, c.size)
  override def compare(that: Obj) = 
    import Ordered.orderingToOrdered
    orderingKey compare that.orderingKey

val o1 = Obj(1, 1, "")
val o2 = Obj(1, 1, "9")
val o3 = Obj(1, 1, "11")

Seq(o1, o3, o2).max //=> Obj(1, 1.0, 11)

It works the same way, mixing in the scala.math.Ordered trait and implementing the Ordered.compare abstract method by relying on Tuple's implicit instance of Ordering, and then using Iterable.max to find the maximum of a Sequence of Objs.

And finally, this is what it looks like in Java:

import com.andrebreves.tuple.Tuple;
import com.andrebreves.tuple.Tuple3;

record Obj(int a, float b, String c) implements Comparable<Obj> {
    private Tuple3<Integer, Float, Integer> orderingKey() {
        return Tuple.of(a, b, c.length());
    }

    @Override public int compareTo(Obj o) {
        return orderingKey().compareTo(o.orderingKey());
    }
}
import java.util.stream.Stream;

var o1 = new Obj(1, 1, "");
var o2 = new Obj(1, 1, "9");
var o3 = new Obj(1, 1, "11");

var best = Stream.of(o1, o3, o2).max(Obj::compareTo);
System.out.println(best); // Optional[Obj[a=1, b=1.0, c=11]]

For some reason, I could not find a suitable tuple implementation in the Java SE JRE (seems like a weird oversight to me, considering how much stuff there is otherwise in there, but I digress), so I just randomly typed "Java Tuple" into Google and downloaded the first library I could find. There are others, all of them should work just fine.

Like with the other implementations, we define an ordering key, and then implement the Comparable interface's compareTo method by forwarding to the ordering key's implementation of compareTo. Then, we use Stream's max method to find the best Obj by satisfying max's Comparator requirement with a method reference to our compareTo method.

Technically, we don't get our "best" Obj but an Optional<Obj> because there is no guarantee that there will be a "best" object – after all, there could be no object, in which case, there won't be a "best".

We have now achieved a couple of nice properties:

  • The knowledge of how to compare itself to another object is now part of the object, not some external code.
  • By forwarding the responsibility to the tuple, the comparison code is much cleaner.
  • We make the collection responsible for finding the maximum, so we don't have to.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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