• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Jeanne Boyarsky
  • Tim Cooke
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • Devaka Cooray
Saloon Keepers:
  • Ganesh Patekar
  • Tim Moores
  • Carey Brown
  • Stephan van Hulst
  • salvin francis
Bartenders:
  • Ron McLeod
  • Frits Walraven
  • Pete Letkeman

Creating a 'boolean equals(Object obj)' Method to compare objects in ArrayList and LinkedList  RSS feed

 
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, so I'm trying to make this method more efficient and faster. It's in the first class, DoubleLinkedList. It currently works as intended, but if a LinkedList or ArrayList has about 1,000,000 items in their Lists, it takes forever to compile.
I was wondering if there is a better way to make this method faster/efficient.
Like if there are 2 Lists, 1 List for DoubleLinkedList called list1, and 1 List for ArrayList called list2; how can I make my method more efficient if there were 1,000,000 strings in each List.
I removed some methods (set, add, remove, isEmpty) because they are not relevant here.

 
Marshal
Posts: 60879
190
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Good point: you are overriding that method, but always precede all overriding methods with the @Override annotation.
If you go to the documentation for Object, you will find seven bullet points about it. I know you can only see five, but I can see seven, one of which you are failing to implement, and I can see that without even reading the code: you haven't overridden hashCode(). The additional bullet point is that consistently returning the same result means an equals() method mustn't throw any exceptions.
You have also got some non‑object‑oriented code there. If you start using instanceof, start thinking there is something wrong. In that case, you are creating different Iterators depending on the implementation. You should look at the interface. Each of those objects should be a List, therefore each of those objects will have an implemented iterator() method. So, if the Object passed isn't instanceof List, return false, and if it is instanceof List, it has an iterator() method, so use that. Don't try creating new Iterator classes outwith the different implementations. The second line of an equals() method is one of the few places where it is actually respectable to use instanceof. The first line is of course that you should test for equality. Since you are not writing structured code, write if (obj == this) { return true; } This is one of the few places where you should use the == operator.
If something is a List, there is no guarantee that it will be a List<E>. Line 22 will cause you no end of problems. Cast your parameter to List full stop. Then iterate both Lists and look for elements which are not equal to each other.

There is a better way to do that. Make your class extend AbstractList, which already has a correctly‑implemented equals() method. Look through the details of that method, which will tell you what to do if you have any nulls in your List. This assumes you haven't been told you need to implement your own equals() method.
 
Luke Stone
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sorry for the confusion, to clear up a few things:
This is for school. We have been making these iterator classes to test with code given to us by my instructor.
We are trying to implement the instanceof in this method
We are not really overriding anything
I'm not sure what the hasCode() method is. I googled it and we have not needed to use it yet.
When you mentioned Line 22, what do you mean by "Cast your parameter to List full stop." ??
In the code my instructor has provided us, it makes an ArrayList and DoubleLinkedList in the main method like so:


*In the private field*


and then for both of the lists he uses a private method to input a string named "str" and increments the number by 1:

This just shows how many stuff is in the list when printed out.

Then in another method thats where he tests to see if they are equal in many ways. adds different things to the list and so forth.
 
Campbell Ritchie
Marshal
Posts: 60879
190
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Luke Stone wrote:Sorry for the confusion, to clear up a few things:
This is for school. We have been making these iterator classes to test with code given to us by my instructor.

Please check the instructions you were given carefully; it is usual for the Iterator to be an inner class, so you don't need separate top‑level classes. That would also allow users to create multiple Iterator objects, and that would breach this part of the contract for Iterator:-

. . . Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics. . . .

If you have multiple Iterators, it is possible for iterator1 to remove or add elements while iterator2 is iterating in which case the next element might be incorrect.

We are trying to implement the instanceof in this method

The instanceof operator is usually a sign of poor object‑oriented design. You do however usually need instanceof in the second part of an equals() method.

We are not really overriding anything

Oh yes, you are. You are overriding the equals() method. You are doing it in such a way that equals() alone will work, but any attempt to put your Lists into hash‑based collections will fail miserably. The rules for equals(), which I gave you a link to last night, tell you clearly that you must override hashCode() too.


I'm not sure what the hasCode() method is. I googled it and we have not needed to use it yet.

Beware of looking for programming advice on Google; there is some good advice and some bad advice out there, and Google doesn't know the difference. Work out from the links I gave you where the API docuementation is, and bookmark that link in your browser. When you can't understand something, ask us.

When you mentioned Line 22, what do you mean by "Cast your parameter to List full stop." ??

The equals() method must accept any kind of object as its parameter. You have eliminated everything which isn't a List in line 19, So, whatever reaches line 22 must be a List. So far, so good. But how do you know what the List contains? What if you are in a List<String> and somebody tries to test for equality against a List<Integer> or a List<Car> or a List<Foo>? I suspect you are going to get problems when you try to create your Iterator<String>. The runtime will try to cast things to Strings, which they aren't. Remember every cast is defiance to the javac tool; it means, “I know the cast will work without any problems.” Try casting to (List) not (List<E>). Or (List<?>) because you don't know what sort of element the List will contain. The <?> means you can get elements out of the List and not add elements, but that doesn't matter; you don't want to add or remove anything in an equals() method.
Or cast the List to (List<Object>) because you can be absolutley certain that whatever is in the List is an Object. You can also be absolutely certain that you can pass that Object to your current element's equals() method. Your Iterator will have to have the same type as whatever the cast is.

. . .This just shows how many stuff is in the list when printed out.

It is more than that; it is a nice simple way to fill a List with 1,000,000 different String objects.

Then in another method thats where he tests to see if they are equal in many ways. adds different things to the list and so forth.

Why are you creating head and tail nodes in the constructor? A linked list usually has exactly the same number of nodes as it has elements, so you would create your first node in the add() method.
 
Luke Stone
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

but any attempt to put your Lists into hash‑based collections will fail miserably. The rules for equals(), which I gave you a link to last night, tell you clearly that you must override hashCode() too.


I don't have a hashCode() method and my class hasn't gotten into hashmaps, sets, etc yet. Were focusing on Lists right now. So I can't override a hashCode() because I don't have one.

I get what you mean on line 22 now. I changed it.

Going back to the original question, how can I compress my code to make it run faster? Explained in my class: LinkedLists work better with Iterators and ArrayLists work better with the get() method. Is that correct? If so, how would I be able to implement it into my code?
Today I tried typing something new.
In the DoubleLinkedList class:


In the ArrayList class:


It works but it's still slow when each Lists have over 100,000 items in it. There's probably a logical error in there somewhere though. I'm not sure. I've been going at this for a few days now.
 
Luke Stone
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As for making the nodes head and tail in the constructor, I dont really know why. That's how our instructor has it done.
 
Campbell Ritchie
Marshal
Posts: 60879
190
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please ask for more explanation. If I were writing such a class, I would have the constructor make both head and tail null because a newly‑created stack has no elements at all.
 
Luke Stone
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok, can we get back to the question at hand? I need help reducing/condensing my code to make it run more efficient/faster.
If a LinkedList named Strings1 has 1,000,000 items in it and an ArrayList named Strings2 has 1,000,000 in it. How can I compare and iterate through both of them but it won't take over 10 minutes to compile?
Can we please forget about the nodes and all?
Don't mean to be rude or anything but I feel like no one is focusing on the question at hand. Or else I don't understand what you are trying to tell me. if I don't the please explain a bit more.
 
Sheriff
Posts: 12546
206
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Let's get one thing straight first: it probably doesn't take 10 minutes to compile that code. I think you meant run. Compiling doesn't involve executing the code. Running does.

When it comes to searching large collections, a linked list is notoriously slower than other data structures. According to this: http://www.bigocheatsheet.com/ , its time complexity is O(n), which means the more elements you have in it, the longer it will take to complete the search. You'll get better performance if the lists are different on one of the earlier elements. You'll get worse performance the further along the difference lies, since you'll have to compare more elements to each other. Worst case will be if both lists have the same exact elements, which means you have to traverse the entire list to determine that there are no differences.

One optimization you can make is in the case where you are comparing the list to itself. An object is always equal to itself, so you should put the check suggested earlier in your equals() method:


Other than that, I think you're pretty much stuck with that kind of poor performance.
 
Junilu Lacar
Sheriff
Posts: 12546
206
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not related to performance but design, your implementation of equals() is oddly specific.

On line 22, you cast obj to List<E>. This says that your equals() method will consider other List implementations as possibly equal() to the current implementation. This is a good thing because it adheres to the behavior defined by List.equals(). However, you still have a problem here because based on the checks you have in place, there is no guarantee that the cast to List<E> is going to be possible for all instances of List and yet that cast says exactly that. Since you're the one who programmed this, you will probably only ever test it with List instances where the cast will work. Your program correctness should not depend on proper use though. Your code should handle incompatible lists gracefully. The way it's programmed now, you'll get a ClassCastException if you pass in a List that can't be cast to List<E> at runtime.

EDIT: I just tried something similar and didn't get a cast exception, probably due to how type erasure works. Nevertheless, that code is misleading in that it leads the unwary reader into making wrong assumptions.

However, the code after that checks only for two specific implementations of List (lines 31 and 40). Failing these checks falls through to line 50, which returns true. This is absolutely the wrong thing to do and it violates the behavior defined by List.equals().
 
Campbell Ritchie
Marshal
Posts: 60879
190
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:. . . a linked list . . . its time complexity is O(n), . . . .

But along with a linear traversal of a linked list, you might have to do a linear traversal of the array list, and that also runs in O(n) complexity. So we are stuck with that sort of performance. Of course, if you use an index to traverse an array list, you are still going to be in linear time, whereas the linked list may go into O(n²) complexity.

Junilu Lacar wrote:. . . your implementation of equals() is oddly specific. . . .

That may be caused by iffy design of the other classes.
 
Junilu Lacar
Sheriff
Posts: 12546
206
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If I recall correctly and if I'm reading what you said right, it would be 2 * O(n) which is still O(n). You usually get O(n²) when there's a nested loop involved but when traversing two lists in tandem, I believe it's still O(n).
 
Campbell Ritchie
Marshal
Posts: 60879
190
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sorry if I wasn't clear. I meant if you use an index to traverse a linked list. If you traverse the linked list with its iterator, you are still in linear time. If you try this sort of thing, however, then you go into quadratic time:-If you try that with an array list, you run in linear time.
 
Junilu Lacar
Sheriff
Posts: 12546
206
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:If you try this sort of thing, however, then you go into quadratic time:-If you try that with an array list, you run in linear time.


Yes, I agree. A method like get() in a LinkedList implementation is probably going to start at the head node always and worst case will be O(n). Although it's not immediately obvious, that operation inside a for-loop like that creates a nested loop, hence the O(n²) time complexity. With an ArrayList, get(i) is pretty much O(1), so inside a loop that traverses N elements, complexity becomes O(1) * O(n) which is O(n).  (Or so I think, if I'm remembering my Big O fundamentals correctly)
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!