Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (522)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (590)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: 1 ... 3 4 [5]
  ignore  |  Print  
  ArrayList vs LinkedList  (Read 14721 times)
0 Members and 1 Guest are viewing this topic.
Offline Best Username Ever

Junior Devvie





« Reply #120 - Posted 2012-08-26 02:46:15 »

Let me revise that. -- Any size data collection that requires FIFO behavior can use a circular buffer. Anything requiring LIFO behavior can use an ArrayList, Vector, etc. Specific types of computations requiring ordered data (and can't be rewritten without that requirement) will typically require specific data structures that aren't helpful to implement using an ArrayList instead of a normal array. Things that are not ordered for the sake of computations can be left unordered until they need to be presented to the user. -- I forgot stacks.

And I mean ordered as in the context of bags vs. ArrayLists. I meant to say "ordered as in maintaining relative orders even after arbitrary insertions and removes like in the List interface." I'll concede that other data structures like heaps, trees, spatial data structures, and even things like hash tables have an order, but it would not help to maintain a List to implement these things. Give me a few examples if you don't mind. Every example that might have more than a hundred elements that I can imagine can be re-engineered without that requirement. My experience and imagination tells me that Lists are only useful/convenient when dealing with user interfaces.

While we're talking about what Java collections could have done... STL containers in C++ have an erase method that takes an iterator as a parameter.
Offline princec

« JGO Spiffy Duke »


Medals: 421
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #121 - Posted 2012-08-26 11:23:56 »

The bugs I used to be plagued by happened several years ago and the precise nature of the problems I had are now lost in the mists of time. It was largely to do with things mysteriously not getting ticked when I was expecting them to be, or things getting ticked before the thing that had spawned them was ticked causing some odd behaviours related to my assumption that they'd always be ticked in a particular order. However I do remember making a note to myself about it. Always use Lists, never Bags, when dealing with game entities. Mostly everything else was ok with bags - particles, sprites, etc. - especially particles and sprites actually as these tend to come and go very very frequently compared to anything else.

Cas Smiley

Offline Best Username Ever

Junior Devvie





« Reply #122 - Posted 2012-08-26 18:02:27 »

Sounds like a bug in your Iterator or for loop, especially if objects are getting skipped entirely. If I add objects in the middle of a game loop, then I either make sure it doesn't break anything or wait until the next update cycle to acknowledge new objects. Also, unless you need a specific order instead of just consistent ordering, you can still maintain relative order inside a multiple-stage update cycle. Specific ordering might include things like updating platform game entities in order from left to right, executing update functions on objects in a FIFO manner, or pulling game entities from a priority queue to determine update order. All of those things are easiest to accomplish using a different data structure or by sorting the elements of the bag at the start of an update cycle. If consistent ordering is good enough, just wait to the last time you loop through each element to take them out. The order won't change if you don't remove anything. Plus, if you start from the beginning assuming the opposite, then you won't have a problem if you change to a non-list-based data structure.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #123 - Posted 2012-08-26 19:41:10 »

To be a weenie...I can't think of a hashing situation that would have any meaningful ordering...assuming the hash generation isn't awful.
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #124 - Posted 2012-08-26 19:53:22 »

To be a weenie...I can't think of a hashing situation that would have any meaningful ordering...assuming the hash generation isn't awful.

I can think of a few. The most useful is where you can use the hashing order to generate a more optimal iteration order.

I used Morton order to generate hashes for minecraft chunks in Tectonicus. The actual iteration order is unimportant (from a correctness point of view), but using morton order gives a much higher cache hit rate for the various geometry caches as it churns through the collection.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Roquen
« Reply #125 - Posted 2012-08-26 20:04:33 »

Hashing is not equal to many-to-one or one-to-one mappings.
Offline DrewLols

Senior Devvie


Medals: 3
Projects: 1


Noob going through metamorphosis...


« Reply #126 - Posted 2012-08-27 02:03:48 »

Uhhhhh...  Don't suppose there's a safe way to remove an element from a Bag while iterating through it, is there?  I want to use Bag, but it seems that there is no iterator method.

Did you know that 90% of statistics are wrong?
Offline jonjava
« Reply #127 - Posted 2012-08-27 02:15:19 »

@DrewLols Huh If you're doing it in a for loop just remove the item at the current index and decrement i by 1.

Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #128 - Posted 2012-08-27 02:55:09 »

You could also iterate in reverse order, removing current wouldn't shift any elements.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline kaffiene
« Reply #129 - Posted 2012-08-27 04:54:45 »

Looked into Bag.  Looks nice, but it isn't a generic class.  Weird...   Shocked

It's pretty easy to make it generic.  I did so and implemented Collection and Iterable as well (the latter for use in for each loops)
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline kaffiene
« Reply #130 - Posted 2012-08-27 04:58:27 »

Uhhhhh...  Don't suppose there's a safe way to remove an element from a Bag while iterating through it, is there?  I want to use Bag, but it seems that there is no iterator method.

Oh yeah: I implemented that also.
Offline DrewLols

Senior Devvie


Medals: 3
Projects: 1


Noob going through metamorphosis...


« Reply #131 - Posted 2012-08-27 14:41:02 »

@DrewLols Huh If you're doing it in a for loop just remove the item at the current index and decrement i by 1.

Well, yeah, but that would force the removal to happen within the loop rather than an object in a loop.  I've allowed objects contained in a level to be responsible for their own removal in a few cases.  I guess I could flag the item to be removed and then remove it in the loop.  Least then the removal would be safe.

Quote
It's pretty easy to make it generic.  I did so and implemented Collection and Iterable as well (the latter for use in for each loops)

Yeah, I made mine generic as well.  Apparently, though, for each loops are blasphemous (thank you spell checker).

Did you know that 90% of statistics are wrong?
Offline Best Username Ever

Junior Devvie





« Reply #132 - Posted 2012-08-29 00:18:23 »

Uhhhhh...  Don't suppose there's a safe way to remove an element from a Bag while iterating through it, is there?  I want to use Bag, but it seems that there is no iterator method.

There is. Use the exact same removal process and adjust the index value back to the index of the gap the removal made before it got filled in with a new value. You can implement an Iterator based loop and remove them the same way as you would a LinkedList or HashSet. Here's the example I used in my Shared Code topic

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
for(Iterator<Goomba> itr = bag.iterator(); itr.hasNext(); )
{
  Goomba g = itr.next();
  if(g.isSquished() || g.isOffScreen())
  {
     itr.remove();
     g.dispose();
     continue;
  }
  g.step();
  Object o = g.checkCollision();
  if(o == mario)
  {
    mario.damage();
  }
  else
  {
    g.reverse();
    g.step();
  }
}
Offline sproingie

JGO Kernel


Medals: 202



« Reply #133 - Posted 2012-08-29 00:38:00 »

Turns out Apache Commons collections has a Bag interface.  And it's *weird*.
http://commons.apache.org/collections/apidocs/org/apache/commons/collections/Bag.html#add%28java.lang.Object%29

But hey the trunk version of commons-collections uses generics.  Welcome to 2004, Apache!
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 835
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #134 - Posted 2012-08-29 01:01:05 »

Theirs is a frequency table / histogram.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline kaffiene
« Reply #135 - Posted 2012-08-29 01:44:51 »

Theirs is a frequency table / histogram.
So... it implements "buckets"?  Values or value ranges with an associated count?  If so - very definitely not the same thing as the JGO Bag =)
Offline Best Username Ever

Junior Devvie





« Reply #136 - Posted 2012-08-29 03:48:13 »

It's actually not weird at all. A bag is also called a "multiset". It's like a set because it stores objects with its own internal organization and has no guarantee on the order of elements returned by an iterator. It differs from a set because it lets you store multiple copies of each object. Adding an object increases the count and removing one decreases it. You could implement something like this so that internally a bag stores multiple copies of each object and keeps one reference for each one; Or, you could implement a bag such that it stored one reference to each instance of an object and an integer counter to keep track of each additional insertion of the same object.

Like I explained in my "tutorial" on the subject, bags/multisets can also be implemented similarly to a map. You could almost do the same thing using a Map, but it would require a lot of extra work on the user's end. (Get a value, add one, put the new value back in for adding objects. And getting a value, subtracting one, removing a key-value pair if zero, putting the new value back in otherwise. It requires a lot of extra work and is a lot easier to implement as a separate class.) If you take a look at the Apache Commons implementations, they include a HashBag and a TreeBag, which are analogous to HashSets and TreeSets and HashMaps and TreeMaps. That's why I tried to be precise and say "Array Backed Bag." Kappa's post did not reference that fact.

An array based bag functions the same way, but there are trade offs.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
String s12 = "12", s23 = "23", s1 = "1", s3 = "3";
Bag<String> bag1 = new MyArrayBag<String>(2);
Bag<String> bag2 = new HashBag<String>(2);
Bag<String> bag;

String a = s12 + s3, b = s1 + s23;
bag1.add(a);
bag1.add(b);
bag2.add(a);
bag2.add(b);


// Array backed bag

for(String s : bag1)
{
  System.out.println(s.equals(a) || s.equals(b));
  System.out.println("a: " + (s == a) + " b: " + (s == b));
  System.out.println();
}

// Possible outputs
// true
// a: true b: false
//
// true
// a: false b: true
// === OR ===
// true
// a: false b: true
//
// true
// a: true b: false


// Map/Set like bag

for(String s : bag2)
{
  System.out.println(s.equals(a) || s.equals(b));
  System.out.println("a: " + (s == a) + " b: " + (s == b));
  System.out.println();
}

// Possible outputs
// true
// a: true b: false
//
// true
// a: true b: false
// === OR ===
// true
// a: false b: true
//
// true
// a: false b: true


The Apache implementation uses the .equals method of your class to detect duplicates, like Java collections do. It considers objects identical if equals returns true. It doesn't define buckets/ranges, but you could accomplish something like that if you wrote equals a certain way. Mine and Kappa's implementations do not use .equals. (All three sources implement a bag that either violates the Collections interface or could not implement it without doing so.) The array based version is usually more useful in game programming, especially if you only keep one copy or don't override equals.

You might use array based bags in your game loop or as generic containers as an alternative to ArrayLists or HashSets. You might use a HashBag to keep count of stackable items in a player's inventory, calling add(obj) or add(obj, count) for every item picked up and remove(obj) for every item used.

The array based version will have faster adds and removes. It can provide O(n) based contains(obj) and count(obj) function while other implementations could provide O(1) or O(log n) time. The array based implementations will take less space if you keep one copy or only a few copies, but the others will take less space if you have many duplicates.
Pages: 1 ... 3 4 [5]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

trollwarrior1 (27 views)
2014-11-22 12:13:56

xFryIx (69 views)
2014-11-13 12:34:49

digdugdiggy (48 views)
2014-11-12 21:11:50

digdugdiggy (42 views)
2014-11-12 21:10:15

digdugdiggy (36 views)
2014-11-12 21:09:33

kovacsa (60 views)
2014-11-07 19:57:14

TehJavaDev (64 views)
2014-11-03 22:04:50

BurntPizza (62 views)
2014-11-03 18:54:52

moogie (77 views)
2014-11-03 06:22:04

CopyableCougar4 (77 views)
2014-11-01 23:36:41
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!