Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (109)
games submitted by our members
Games in WIP (537)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: 1 [2]
  ignore  |  Print  
  Java Data structures  (Read 23699 times)
0 Members and 1 Guest are viewing this topic.
Offline Gudradain
« Reply #30 - Posted 2012-07-31 23:26:10 »

Can someone please explain the differenct between a Vector and a ArrayList in java? I've never used a Vector.

Well the difference is that Vector has some synchronization. To understand it correctly you have to understand the 5 level of synchronization for object and method

1. Immutable : The object can't be modified once created. This is the most safe level. No matter how many thread access this object you won't run into any problem
2. Thread-safe : The object contain enough internal synchronization (synchronized method) to be used without worry by multiple threads.
3. Conditionnaly thread-safe : Same as thread-safe except that under some circonstances, you will need to provide external synchronization (outside of that object)
4. Thread-Compatible : Can be use in multi-threaded environment but it is up to the programmer to do the synchronization
5. Thread-hostile : Can't be use in multi-threaded envrionment (Ex.: Thread.stop() - That method was deprecated because it releases the lock when it is called. Hence it could leave an object into an invalid state)

Vector are Conditionnally thread-safe. That means that most of the time you don't need to provide external synchronization but in some case you might. One of that example is when iterating over the Vector and modifying it.
Collection.getSynchronizedCollection() - (or something like that) are also conditionnally thread-safe : meaning that you have to provide external synchronization for some operation.
ArrayList is thread compatible : meaning that if you want to use it in a multi-threaded environment you have to provide all the synchronization

There are no magic solution to synchronization, except for the human brain Smiley
Offline OttoMeier

Senior Member


Medals: 4
Projects: 1



« Reply #31 - Posted 2012-07-31 23:28:57 »

Collections.synchronizedList(new ArrayList())
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 757
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #32 - Posted 2012-08-01 01:20:46 »

Some people really don't understand the concept of a wiki... Cranky

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Gudradain
« Reply #33 - Posted 2012-08-01 02:30:08 »

lol Smiley
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 757
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #34 - Posted 2012-08-01 14:28:50 »

lol Smiley
Please consider moving content into the wiki article.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #35 - Posted 2012-08-01 14:38:26 »

The created concurrency page should not indicate that synchronization is required for thread-safety...that's so 80s.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 757
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #36 - Posted 2012-08-01 14:48:52 »

The created concurrency page should not indicate that synchronization is required for thread-safety...that's so 80s.
It's a wiki, correct it when it is added.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #37 - Posted 2012-08-01 20:01:21 »

Don't be afraid to edit. We'll try not to slaughter anyone Smiley

Offline ra4king

JGO Kernel


Medals: 342
Projects: 2
Exp: 5 years


I'm the King!


« Reply #38 - Posted 2012-08-02 01:21:16 »

I disagree with the "General Advice", always use the most specific type that you can so you can have access to all possible methods. If you are planning to switch out types later, you are doing something wrong. Smiley

Offline sproingie

JGO Kernel


Medals: 202



« Reply #39 - Posted 2012-08-02 01:26:34 »

If you are planning to switch out types later, you are doing something wrong. Smiley

I can't believe how full of nonsense that is.  I can't even begin to respond to it.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 757
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #40 - Posted 2012-08-02 01:33:45 »

I can't believe how full of nonsense that is.  I can't even begin to respond to it.
I had the same, so I let somebody else bite the bullet. Thx!

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline ra4king

JGO Kernel


Medals: 342
Projects: 2
Exp: 5 years


I'm the King!


« Reply #41 - Posted 2012-08-02 01:38:04 »

Sad Why would you use List<TYPE> instead of ArrayList<TYPE>? When would you ever need to switch to a different List implementation (unless you didn't understand what you were doing)?

Offline sproingie

JGO Kernel


Medals: 202



« Reply #42 - Posted 2012-08-02 01:46:29 »

http://en.wikipedia.org/wiki/Polymorphism_%28computer_science%29

One practical application I have of it is 2d arrays where I switch between packed and sparse implementatios. 
Some pseudo-ish-code:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
interface Layer<T> {
   T get(int x, int y);
   void set(int x, int y, T val);
}

class ArrayLayer<T> implements Layer<T> {
   ArrayList<T> store;
   public T get(int x, int y) { return store.get(x + y*width); }
   public void set(int x, int y, T val) { store.set(x + y*width, val); }
}

class MapLayer<T> implements Layer<T> {
   Map<Pair<Int,Int>, T> store;
   public T get(int x, int y) { return store.get(new Pair(x,y)); }
   public void set(int x, int y, T val) { store.put(new Pair(x,y), val); }
}

class Display {
  List<Layer<Tile>> layers;
  public Display(int width, int height) {
     layers.add(new ArrayLayer<Tile>(width,height));  // tiles
    layers.add(new MapLayer<Tile>(width,height));    // cursor
 }
}


(the real thing is scala so it's a lot less ugly ... though I manage to add plenty of ugliness in other ways)
Offline UprightPath
« Reply #43 - Posted 2012-08-02 01:58:43 »

Sad Why would you use List<TYPE> instead of ArrayList<TYPE>? When would you ever need to switch to a different List implementation (unless you didn't understand what you were doing)?

Because one of the geniuses here abouts might implement a version of one of the others that actually works better? Like a LinkedList backed by a Node object pool or something that'll take some of the pain (Extra time to create/manage the nodes) out of using them, or implement whatever else might be required to make a 'good' Java LinkedList implementation. I mean it still bothers me that something backed with an array, that has to copy to grow as well as shift indexes is better than LinkedList for regular insertions and the like. Raw. >.>

Offline ra4king

JGO Kernel


Medals: 342
Projects: 2
Exp: 5 years


I'm the King!


« Reply #44 - Posted 2012-08-02 03:06:26 »

Ah, seems I was misunderstood then. If you intentionally need to use different List implementations, I understand. But if all your code uses is ArrayList, then using List as the field type makes my eyes bleed.

My question has nothing to do with polymorphism really. It's more style-oriented.

Offline Gudradain
« Reply #45 - Posted 2012-08-02 03:22:03 »

I mean it still bothers me that something backed with an array, that has to copy to grow as well as shift indexes is better than LinkedList for regular insertions and the like. Raw. >.>

Well it bother me too when I just finished my class on datastructure but since I learn how to live with it... Creating a lot of object is not free and you need more operation in linked list to add a new element.

Well you might consider using a LinkedArrayList : You get the best of the two world. Here is a quick example

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
public class ArrayList {
   
   private int[] list = new int[10];
   private int size = 0;
   
   public void add(int n){
      if(size < list.length-1){
         list[size] = n;
         size++;
      }else{
         int[] newlist = new int[list.length*2];
         for(int i=0; i<list.length; i++){
            newlist[i] = list[i];
         }
         list = newlist;
         list[size] = n;
      }
   }

}


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  
public class LinkedArrayList {
   
   private class Node {
      Node next;
      Node previous;
      int[] array = new int[1000];
      int size = 0;
     
      public Node(Node previous){
         this.previous = previous;
      }
     
      public boolean isFull(){
         return size > array.length;
      }
     
      public void add(int n){
         array[size] = n;
      }
   }
   
   private Node head;
   private Node tail;
   private int size = 0;
   
   public void add(int n){
      if(size == 0){
         head = new Node(null);
         tail = head;
         tail.add(n);
         size++;
      }else{
         if(tail.isFull()){
            Node newnode = new Node(tail);
            tail.next = newnode;
            tail = newnode;
            tail.add(n);
            size++;
         }else{
            tail.add(n);
            size++;
         }
      }
   }

}


You can test a lot of insertions with that :

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  
public class Test {
   
   public static void main(String [] args){
      long begin;
      long end;
      long delta;
     
      begin = System.nanoTime();
      ArrayList arrayList = new ArrayList();
      for(int i=0; i<100000000; i++){
         arrayList.add(i);
      }
      end = System.nanoTime();
      delta = end-begin;
      System.out.println("--- ArrayList ---");
      System.out.println("Time elapsed in nano : " + delta);
      System.out.println("Time elapse in milli : " + delta/(1000*1000));
      System.out.println();
     
      begin = System.nanoTime();
      LinkedArrayList linkedArrayList = new LinkedArrayList();
      for(int i=0; i<100000000; i++){
         linkedArrayList.add(i);
      }
      end = System.nanoTime();
      delta = end-begin;
      System.out.println("--- LinkedArrayList ---");
      System.out.println("Time elapsed in nano : " + delta);
      System.out.println("Time elapse in milli : " + delta/(1000*1000));
      System.out.println();
     
   }

}


Here are my results running it :

1  
2  
3  
4  
5  
6  
7  
--- ArrayList ---
Time elapsed in nano : 708601408
Time elapse in milli : 708

--- LinkedArrayList ---
Time elapsed in nano : 362729744
Time elapse in milli : 362


You would probably get even more benefits with insertion since in the ArrayList you have to move every objects back one spot while in the LinkedArrayList you only have to move the object in one Node Smiley
Offline UprightPath
« Reply #46 - Posted 2012-08-02 03:31:55 »

Yep, Datastructures: Where the information doesn't really matter and the numbers are made up.

Ahem, that's really why I suggested this Wiki chunk. Because Data Structure classes tend to spend so much time beating you over the head about the BigO stuff, and how LinkedLists are good in these situations and this other is good in those situations. Then you get out into the real world and find out "Welp, because of the way the API implemented these, you'll be using ArrayList pretty much exclusively".


As an aside, you'd still need to implement a proper Iterator for that system that meets the requirements of being an implementer of the List API. Which is more of what I'm talking about.

Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #47 - Posted 2012-08-02 10:13:57 »

It is pretty much intresting to have had a look into languages like scheme, which build up entirely on linked Lists. That means iterating on such a list is very fun... you need to do it with recursion btw, because there aren't any loops.
Take a look, guys, you will find it ugly in the beginning, if you wrote Java and other imperative language before. But I actually think the concept of that language is pretty good.

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Roquen
« Reply #48 - Posted 2012-08-02 10:37:57 »

Like ra4king I disagree with the general advice, but on different grounds.  The notion of using the most basic 'type' which fits a given need is something I pretty much never do.  The idea behind this is the sound thought of hiding of implementation details.  Given the strengths of refactoring this is slightly less important that it once was, but that's not really my point.  You're much more effective at hiding implementation details by not giving the world outside of the subsystem in question ANY notion of how it's implemented.  This is achieved by hiding the field(s) in question from the outside world and providing the required methods to access/modify the contained set.  An added bonus of going this route is that it's much more backend compiler friendly.
Offline Icecore

Senior Member


Medals: 5



« Reply #49 - Posted 2012-08-02 13:41:21 »

Add wiki vector ^^
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


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

Removed wiki vector.  Tongue

Added some basic info on multi-threaded collections. I'm sure someone else could add some more info on some of the other concurrent.* collections but I haven't used them much.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 757
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #51 - Posted 2012-08-02 14:11:37 »

Like ra4king I disagree with the general advice, but on different grounds. 
[snip]
You're much more effective at hiding implementation details by not giving the world outside of the subsystem in question ANY notion of how it's implemented.  This is achieved by hiding the field(s) in question from the outside world and providing the required methods to access/modify the contained set.
[snip]
Polymorphism and accessibility are two distinct subjects. You should pretty much always make fields private, and keep the type of the field as generic as possible, for the functionality required.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #52 - Posted 2012-08-02 14:21:14 »

Sure, but that's not really the topic at hand.  The point is protection against changes in implementation.  If a field is private, then there's no reason not to state its concrete type.  Not doing so (in general) causes more work for the backend compiler, which it may not be able to perform.  For instance declaring a reference to an interface (should always be able to for private however), the backend may not be able to infer a base class and therefore require a dynamic lookup for each method call.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 757
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #53 - Posted 2012-08-02 14:35:03 »

Polymorphism, accessibility and performance are three distinct subjects.
If you take all three into account, you can never give any 'general advice'.

IMHO the 'general advice' part was offtopic in this wiki entry in the first place, so we might have to move that to a different wiki entry that takes into account some context on the matter.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #54 - Posted 2012-08-02 17:03:52 »

Yes, have links to related topics would make much more sense.
Offline sproingie

JGO Kernel


Medals: 202



« Reply #55 - Posted 2012-08-02 18:32:57 »

Time to try adding WikiLinks to the SMF wiki, Riven? Wink
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 757
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #56 - Posted 2012-08-02 18:41:27 »

Time to try adding WikiLinks to the SMF wiki, Riven? Wink
Nuh-uh!

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #57 - Posted 2013-03-29 13:22:54 »

Added a reference section with a sole entry of a link to an applet that shows how some data structures work step-by-step.

BTW: Why not add LaTeX support?  Smiley
Pages: 1 [2]
  ignore  |  Print  
 
 

 

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

The first screenshot will be displayed as a thumbnail.

CogWheelz (17 views)
2014-08-01 22:53:16

CogWheelz (15 views)
2014-08-01 22:51:43

CopyableCougar4 (20 views)
2014-08-01 19:37:19

CogWheelz (19 views)
2014-07-30 21:08:39

Riven (27 views)
2014-07-29 18:09:19

Riven (16 views)
2014-07-29 18:08:52

Dwinin (14 views)
2014-07-29 10:59:34

E.R. Fleming (42 views)
2014-07-29 03:07:13

E.R. Fleming (13 views)
2014-07-29 03:06:25

pw (44 views)
2014-07-24 01:59:36
Resources for WIP games
by CogWheelz
2014-08-01 18:20:17

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

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

List of Learning Resources
by SilverTiger
2014-07-31 18:26:06

List of Learning Resources
by SilverTiger
2014-07-31 13:54:12

HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22
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!