• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

remove specific object from ArrayList

 
Ranch Hand
Posts: 57
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I created a list (ArrayList) of Objects which differ from each other by x,y coordinates on a grid. I have these Objects moving around randomly, so the coordinates change, but no object in the List can have the same coordinates. These coordinates are stored and updated within the objects. Is there a way to remove one specific Object from the ArrayList based on finding/identifying the object by it's specific coordinate?

In other words, if I want to remove the object that is currently occupying 2,3 (x.y) is this possible?
 
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
No there is no way that I know of except iterating one by one.

Use a java.util.LinkedHashMap instead of an Array and have the key be your (x,y).

 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
sorry I posted to the wrong thread above answer is still valid
 
Ranch Hand
Posts: 98
Oracle Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
try remove() first and then set() them
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ray Anderson wrote:try remove() first and then set() them



Hi Ray,

Remove still iterates and it isn't really efficient.

ArrayList.remove code:



Worst, it has to relocate the tail of the array by moving stuff around in memory everytime:

ArrayList.fastRemove:



On top of that, he would still have to define an equals() method where he would check Object equality based on (x,y).

LinkedHashMap is much more efficient. He could still easily shuffle his order randomly.
 
Marshal
Posts: 79061
375
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That depends on the size of the collection. The code to move objects in a Map would require removal of the old pair, recording the V at that location and then putting the old V with the new location as a K. That might make the linked list ineffective; rather than retaining insertion order, you would be iterating from least recently moved to most recently moved. So maybe an ordinary Map would be better than a linked Map.
As you say, AJC, the method with a List runs in linear time and the method with a Map runs in amortised constant time, so if you have large collections it would run much faster. The last time I delved into ArrayList it used System#arraycopy to move parts of the array. I don't know how fast arraycopy is, but I suspect it is faster than iterating the array. So the simple remove() method runs in linear time. I see from your code that it still uses arraycopy.

So you have the conflicting demands of performance v ease of writing the code. If you have a small collection (<100 elements) you won't notice any performance differences.

But a Map has another advantage. Unlike a List, which implicitly permits duplicates, a Map does not permit two Vs with the same K. If you use a Map you can easily enforce the prohibition on two objects occupying the same location. You would need to decide what to do if you do seem to have two locations the same: do you displace the old V?
 
Campbell Ritchie
Marshal
Posts: 79061
375
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
To find an object in a List you usually use its equals() method, so you might consider overriding equals() to make two objects the same if their locations are the same. In the case with a Map, you only need to get the equals() method in the Location class working for the Map to work. Another advantage for a Map.
Remember that you must override hashCode whenever you override equals() and hash maps use hash codes for all Ks.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
SORRY, I think I made a mistake. Update coming...


Hi Campbell,

Even with only one single element in the Collection LinkedHashMap is faster than ArrayList:

Output of the benchmark (I ran it several times):



Source code for the benchmark:
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sorry, I made a mistake forgetting to re-initialize the timer.

Here are the updated results:




 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

A.J. Côté wrote:Even with only one single element in the Collection LinkedHashMap is faster than ArrayList:


Unsurprising. For the reasons Campbell has already given.

However, depending on the range of values, and "density" of coordinates you're dealing with, there are other possibilities, including a "2-dimensional" array, which will give you close to O(1) performance for all operations, but may waste an awful lot of space (but possibly not ridiculous, since any "row" in a 2-D array can be null).
There is also BitSet - a much underused class, IMO - that would also give you similar performance, but has similar problems to an array and would be restricted to a 32768 x 32768 grid. It could handle rectangular grids of larger sizes though.

I suspect that LHM (actually, any sort of HashMap) is probably the best compromise for you though. Just thought you might be interested in other alternatives.

Space - Order - Speed -- pick any two. :-)

Winston
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I believe the following benchmark is much closer to the use case the original poster was asking about in his game and LinkedHashMap always win.

Feel free to comment.

output:


Object to put into the Collection:


The benchmark:


 
Campbell Ritchie
Marshal
Posts: 79061
375
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You have put a lot of work into that

I didn't say there would be no difference; I said you would not notice it in a small collection … and then found all sorts of other reasons why a Map is better. As Winston said, you are always going to win with constant time over linear time.
 
Ted Schrey
Ranch Hand
Posts: 57
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I like the Map idea, and have used HashMaps, but don't see how to make int coordinates as key. Would I have to convert it to a String that "looks like" the actual coordinates?
 
Sheriff
Posts: 67745
173
Mac Mac OS X IntelliJ IDE jQuery TypeScript Java iOS
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Suggestion: create a class that models the coordinates and use it as the key.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ted Schrey wrote:I like the Map idea, and have used HashMaps, but don't see how to make int coordinates as key. Would I have to convert it to a String that "looks like" the actual coordinates?



Here you go:




Output:





 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
public int hashCode() {
return x*37/y; // use anything based on x y....
}

not a good idea ;-) divide by zero when y == 0;

this should be better ;-)))

public int hashCode() {
return (x*37)+(y*13);
}
 
Campbell Ritchie
Marshal
Posts: 79061
375
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
AJC: please read this, which you find on the contents page of this forum:-

We're all here to learn, so when responding to others, please focus on helping them discover their own solutions, instead of simply providing answers.

I think that providing a whole class without allowing OP to work it out for himself reduces the learning opportunity. Please don't be annoyed but I have pulled rank and removed the code. The old version is cached behind the scenes.
 
Campbell Ritchie
Marshal
Posts: 79061
375
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Why on earth they didn't introduce the Objects class fifteen years earlier?
Better way still to write a hash code method.
 
Campbell Ritchie
Marshal
Posts: 79061
375
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I see the hash method uses the unoverridden hash code for an array, so you might require a different technique for classes which have arrays as fields.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Why on earth they didn't introduce the Objects class fifteen years earlier?
Better way still to write a hash code method.



Hi Campbell,

To answer your question, fifteen years earlier, Java was slow enough so we didn't feel the need to make it any slower. Objects.hash(x, y) is 60 times slower than the method I suggested.

No Objects, Computed: 1.0E8 hashes in 219 mili-seconds
With Objects, Computed: 1.0E8 hashes in 13285 mili-seconds

>
 
Campbell Ritchie
Marshal
Posts: 79061
375
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

A.J. Côté wrote: . . . fifteen years earlier, Java was slow enough so we didn't feel the need to make it any slower. . . .



It is easy enough to write a correct hash code method when you are dealing with two ints. In think most people now use 31 throughout as their prime multiplier, so you getBut once you get onto more complicated things, particularly with longs and doubles …You are now in the realms of complicated‑looking code, which thereby becomes error‑prone. Any errors outweigh faster code.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

It is easy enough to write a correct hash code method when you are dealing with two ints. In think most people now use 31 throughout as their prime multiplier, so you get.



Well, x*37+y*13 seems to consistently produce less collisions than x*31+y:

hashCodeTest 100.0 hashes 0 collisions
hashCodeTest2 100.0 hashes 0 collisions

hashCodeTest 10000.0 hashes 5481 collisions
hashCodeTest2 10000.0 hashes 6831 collisions

hashCodeTest 1000000.0 hashes 950481 collisions
hashCodeTest2 1000000.0 hashes 968031 collisions

hashCodeTest 1.0E8 hashes 99500481 collisions
hashCodeTest2 1.0E8 hashes 99680031 collisions

>
 
Ranch Hand
Posts: 47
1
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Well, x*37+y*13 seems to consistently produce less collisions than x*31+y:


That is because you use "j" to generate hash by and j is in the range from 0 to nbOfHashes. So the range of the hashes generated is also limited by 31 * nbOfHashes or 37 * nbOfHashes. Intuitively in the smaller range you get more collisions.

For proper test "j" should be evenly distributed in the whole int range, I believe

P.S. I dare to add that if I remember correctly, the idea with 31 is mentioned by Joshua Bloch in his "Effective Java". Though I personally will prefer 37 because 31 is 2^5-1 and I do not want to wander whether this can lead to some special consequences (e.g. with hashmap having sizes of 2^n usually) or not.
 
Campbell Ritchie
Marshal
Posts: 79061
375
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
RG welcome to the Ranch

I think this discussion of hash codes is getting too difficult for the “beginning” forum, so I shall move it.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rodion Gork wrote:

Well, x*37+y*13 seems to consistently produce less collisions than x*31+y:


That is because you use "j" to generate hash by and j is in the range from 0 to nbOfHashes. So the range of the hashes generated is also limited by 31 * nbOfHashes or 37 * nbOfHashes. Intuitively in the smaller range you get more collisions.



That was brilliant! Are you a mathematician?

I can't find a single collision using: x*9973+y*3067

1) x*37+y*13
2) x*31+y
3) x*9973+y*3067

hashCodeTest 100.0 hashes 0 collisions
hashCodeTest2 100.0 hashes 0 collisions
hashCodeTest3 100.0 hashes 0 collisions

hashCodeTest 400.0 hashes 0 collisions
hashCodeTest2 400.0 hashes 0 collisions
hashCodeTest3 400.0 hashes 0 collisions

hashCodeTest 1600.0 hashes 81 collisions
hashCodeTest2 1600.0 hashes 351 collisions
hashCodeTest3 1600.0 hashes 0 collisions

hashCodeTest 6400.0 hashes 2881 collisions
hashCodeTest2 6400.0 hashes 3871 collisions
hashCodeTest3 6400.0 hashes 0 collisions

hashCodeTest 25600.0 hashes 18081 collisions
hashCodeTest2 25600.0 hashes 20511 collisions
hashCodeTest3 25600.0 hashes 0 collisions

hashCodeTest 102400.0 hashes 86881 collisions
hashCodeTest2 102400.0 hashes 92191 collisions
hashCodeTest3 102400.0 hashes 0 collisions

hashCodeTest 409600.0 hashes 378081 collisions
hashCodeTest2 409600.0 hashes 389151 collisions
hashCodeTest3 409600.0 hashes 0 collisions

hashCodeTest 1638400.0 hashes 1574881 collisions
hashCodeTest2 1638400.0 hashes 1597471 collisions
hashCodeTest3 1638400.0 hashes 0 collisions

hashCodeTest 6553600.0 hashes 6426081 collisions
hashCodeTest2 6553600.0 hashes 6471711 collisions
hashCodeTest3 6553600.0 hashes 0 collisions

hashCodeTest 2.62144E7 hashes 25958881 collisions
hashCodeTest2 2.62144E7 hashes 26050591 collisions
hashCodeTest3 2.62144E7 hashes 0 collisions

hashCodeTest 1.048576E8 hashes 104346081 collisions
hashCodeTest2 1.048576E8 hashes 104529951 collisions

Exception: java.lang.OutOfMemoryError thrown from the UncaughtExceptionHandler in thread "main"
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Then again, same results with: x*9973+y; unable to detect a collision.

So I would use x*9973+y to avoid the expensive second multiplication in: x*9973+y*3067

Also, as a side note, Object.hash(x,y) generates exactly as many collisions as x*31+y.
 
Rodion Gork
Ranch Hand
Posts: 47
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

That was brilliant! Are you a mathematician?


Oh no, surely it is not about me - I was almost kicked out from school and later from university for sucking at math

Meanwhile I slightly modified your original test so that it makes hashes of more evenly distributed values:
http://ideone.com/soJIdp

See, the results are like this:

hashCodeTest 100.0 hashes 0 collisions
hashCodeTest2 100.0 hashes 0 collisions

hashCodeTest 10000.0 hashes 0 collisions
hashCodeTest2 10000.0 hashes 0 collisions

hashCodeTest 1000000.0 hashes 134 collisions
hashCodeTest2 1000000.0 hashes 114 collisions


(running it several times we can see that either of the tests can win, just as in good black jack game)
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rodion Gork wrote:

That was brilliant! Are you a mathematician?


Oh no, surely it is not about me -



Hi Rodion,

I am serious, it was brillant and it was you.

(running it several times we can see that either of the tests can win, just as in good black jack game)
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rodion Gork wrote:

That was brilliant! Are you a mathematician?


Oh no, surely it is not about me - I was almost kicked out from school and later from university for sucking at math

Meanwhile I slightly modified your original test so that it makes hashes of more evenly distributed values:
http://ideone.com/soJIdp



Reformulating the use case is unacceptable.

The OP was talking about fit in memory coordinates, like; in real life use cases.

P,S, I have already done exactly the same as you did but I didn't post results here because of not overflowing the thread concerns.

Keep on the good work!
 
Campbell Ritchie
Marshal
Posts: 79061
375
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That simply shows how one cannot predict from the algorithm used for hashing how it will be used.When writing a hash method all you can do is try to get the widest possible distribution of values, remembering that differences in the right bits are usuallyheavier than differences in the left bits.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:That simply shows how one cannot predict from the algorithm used for hashing how it will be used.When writing a hash method all you can do is try to get the widest possible distribution of values, remembering that differences in the right bits are usuallyheavier than differences in the left bits.



Exactly! write your hashCode() method in order to be efficient with your use case.

P.S. nothing beats good old testing ;-)
 
Campbell Ritchie
Marshal
Posts: 79061
375
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That depends on your knowing the use cases before you write the method.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:That depends on your knowing the use cases before you write the method.



Exactly, here the goal is to provide an efficient hashCode() method for a coordinate(x,y) object that will contain real life coordinates in a grid starting at 0,0

I assumed that the grid should fit in memory so will never range from (0,Integer.MAX_VALUE, 0,Integer.MAX_VALUE) but more likely be like:

1920 × 1080
2560 x 1440
100000 x 100000
1000000 x 1000000

x*31+y would be fine for Integer.MAX_VALUE x Integer.MAX_VALUE but we have found that x*9973+y is way much more efficient for our real life use case.


 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

A.J. Côté wrote:Then again, same results with: x*9973+y; unable to detect a collision.
So I would use x*9973+y to avoid the expensive second multiplication


I hate to say but this sounds like micro-optimization to me; but if you're really interested in shaving nanoseconds, then my suggestion would be to use a Mersenne prime like 31, only bigger, because then the "multiplication" can be done with shifts, eg:
(x << 17) - x + y   == (x * 131071) + y (well, nearly)
How many collisions do you get with that?

However, if you really want to delve into hashcode functions, I'd suggest looking somewhere like here, because there are all sorts of other tricks to help prevent collisions, like combining shifts and the wonderful XOR operator (^), and plenty of geeks who have forgotten more than you or I will ever know about this stuff.

Good luck.

Winston
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:

A.J. Côté wrote:Then again, same results with: x*9973+y; unable to detect a collision.
So I would use x*9973+y to avoid the expensive second multiplication


I hate to say but this sounds like micro-optimization to me; but if you're really interested in shaving nanoseconds, then my suggestion would be to use a Mersenne prime like 31, only bigger, because then the "multiplication" can be done with shifts, eg:
(x << 17) - x + y   == (x * 131071) + y (well, nearly)
How many collisions do you get with that?



Unable to detect a collision.

Objects.hash(x,y), Computed: 1.0E8 hashes in 11761 mili-seconds
x*9973+y, Computed: 1.0E8 hashes in 97 mili-seconds
(x << 17) - x + y, Computed: 1.0E8 hashes in 76 mili-seconds
 
Campbell Ritchie
Marshal
Posts: 79061
375
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What is going to happen when you put those location objects into a 128‑capacity map as “K”s?
 
Sheriff
Posts: 22780
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:


1) The method is doubleToLongBits.
2) The the cast isn't redundant. All of these operators produce longs since at least one argument is a long.

Anyway, you've missed some updates:
- Java 7 added Objects.hashCode(Object) which does exactly the same as your ternary expression (well, you probably knew about that one).
- Java 8 added static hashCode methods on all primitive wrapper types.

So your code a bit more readable:
 
Rob Spoor
Sheriff
Posts: 22780
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Also, if a class like Coordinate is to be used as a map key, make sure it's immutable. Making all fields final is a good first step.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rob Spoor wrote:Also, if a class like Coordinate is to be used as a map key, make sure it's immutable. Making all fields final is a good first step.



Keep in mind the OP use case; he wants to shuffle the coordinate around. If coordinate had final final fields, he would be much more costly to change the coordinate because he would have to create a new object every time thus offsetting the gains because of the load on the garbage collector.

More details: I assumed the OP has a set of objects much smaller than the grid capacity and he wants to move them randomly around, similarly to what is done in a video game.
reply
    Bookmark Topic Watch Topic
  • New Topic