Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (757)
Games in Android Showcase (229)
games submitted by our members
Games in WIP (844)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Specialized Data Structure  (Read 5764 times)
0 Members and 1 Guest are viewing this topic.
Offline IronclawsBt

Junior Devvie


Medals: 1



« Posted 2011-03-03 15:36:57 »

I want to use a data structure with a very specific behavior. The general idea is that it acts as an array, but the objects have a permanent location. For example, if three objects were added, they may be assigned the indexes 0, 1, and 2. If object 1 is then removed, the other two objects can still be found at 0 and 2. Once an index is empty, a new object can be reassigned to that index (this is not required though).

The performance requirements are O(1) amortized insert, O(1) delete, O(1) find (by index), and iteration should be O(n) in the number of elements (with a constant factor at least as good as a linked list, preferably closer to array iteration). Most of these requirements would be taken care of by a hash map with carefully chosen keys, but the iteration cost would still be dependent on the capacity, not the actual number of elements.

I am going to use this to keep track of game entities with unique ID's. I believe I have come up with a solution, and I am currently working out the details in the implementation (that is where the devil is after all). Before I invest to much more time in this, I wanted to see if anyone else has already solved this problem.

It's not what you know, it's what other people think you know.
Just hope you don't get quizzed on it.
Game engine design tutorials
Offline Captain Awesome

Junior Devvie


Medals: 2


Hi


« Reply #1 - Posted 2011-03-03 15:53:17 »

Just use a normal array. When you wish to delete an object, just do array[index] = null;
I don't think it goes much faster than that Smiley
Offline IronclawsBt

Junior Devvie


Medals: 1



« Reply #2 - Posted 2011-03-03 16:02:36 »

Just use a normal array. When you wish to delete an object, just do array[index] = null;
I don't think it goes much faster than that Smiley

There are two problems with that, one easily fixed and the second one is what I am working on. The first problem is that leaving null elements will eventually lead to a lot of wasted space. The fix for that is pretty simple though. When an element is removed add that index to a list of empty elements. When a new element is added grab one of the empty elements first.

The hard part is the iteration problem. If there are a lot of empty elements, you are wasting time iterating over those. I am probably over engineering this, but I love clever algorithms so working on this is fun for me, if not completely necessary.

It's not what you know, it's what other people think you know.
Just hope you don't get quizzed on it.
Game engine design tutorials
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline lhkbob

JGO Knight


Medals: 32



« Reply #3 - Posted 2011-03-03 16:13:56 »

To solve the space issue, you need a map. This is what it was designed for. If you want better iteration performance than what the map gives you, consider wrapping two data structures.  You could manage a map for the random access operations and a list or bag for the iteration.

Offline ryanm

Senior Devvie


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #4 - Posted 2011-03-03 16:25:36 »

Sounds like what you want can be solved by a doubly-linked list whose nodes are stored in an array, plus a stack to keep track of empty array locations.
Offline IronclawsBt

Junior Devvie


Medals: 1



« Reply #5 - Posted 2011-03-03 16:29:17 »

To solve the space issue, you need a map. This is what it was designed for. If you want better iteration performance than what the map gives you, consider wrapping two data structures.  You could manage a map for the random access operations and a list or bag for the iteration.

That would probably be a workable solution. To remove items from the bag quickly, you need to know what index they are at. The map would essentially translate the permanent index to the local index in the bag. Find, add, and remove would need to go through one layer of indirection and iteration would be at array speeds. Because iteration is generally more performance critical, it would make sense to sacrifice the small speed hit to the other operations to maximize that.

It's not what you know, it's what other people think you know.
Just hope you don't get quizzed on it.
Game engine design tutorials
Offline IronclawsBt

Junior Devvie


Medals: 1



« Reply #6 - Posted 2011-03-03 18:12:37 »

A wrote up a rough implementation of the map + bag design. It has no error checking which is critical to maintaining a consistent state, but it does work for the initial tests I ran. I am tentatively calling it a shelf as elements you place in it stay where they are even if you remove other elements (a better name is welcome). Once I get this a bit more polished I will post it in the shared code section.
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  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
import java.util.Arrays;
import java.util.Iterator;

/**
 *
 * @author Eric
 */

public class Shelf<E> implements Iterable<E>
{
    private E[] items;
    private int[] map;
    private int size;
    private Node next;

    /**
     * Create a shelf with the default capacity.
     */

    public Shelf()
    {
        this(10);
    }

    /**
     * Create a shelf with the provided initial capacity.
     * @param capacity initial capacity.
     */

    public Shelf(int capacity)
    {
        if(capacity < 0)
            throw new IllegalArgumentException(
                    "Initial capacity must be positive");
        items = (E[])new Object[capacity];
        map = new int[capacity];
    }

    /**
     * Add an element in the first open slot.
     * @param e item to be added.
     * @return the index where the item can be found.
     */

    public int add(E e)
    {
        int index;
        if(next == null) // no empty slots in map
        {
            index = size;
            ensureCapacity(index + 1);
        }
        else // at least one empty slot in map
        {
            index = next.index;
            next = next.next;
        }
        map[index] = size;
        items[size] = e;
        size++;
        return index;
    }

    /**
     * Removes the item with the given index.
     * @param index
     * @return
     */

    public E remove(int index)
    {
        next = new Node(index, next);
        index = map[index];
        E item = items[index];
        size--;
        items[index] = items[size];
        items[size] = null;
        return item;
    }

    /**
     * Finds the item with the given index.
     * @param index
     * @return
     */

    public E find(int index)
    {
        return items[map[index]];
    }

    /**
     * Returns an iterator over the stored elements.
     * @return
     */

    @Override
    public Iterator<E> iterator()
    {
        return new ShelfIterator(items, size);
    }

    /**
     * Ensures that the shelf has a given capacity.
     * @param capacity
     */

    public void ensureCapacity(int capacity)
    {
        if(items.length < capacity)
        {
            int newCapacity = Math.max(capacity, (items.length * 3) / 2);
            items = Arrays.copyOf(items, newCapacity);
            map = Arrays.copyOf(map, newCapacity);
        }
    }
   
    private class Node
    {
        private int index;
        private Node next;

        private Node(int index, Node next)
        {
            this.index = index;
            this.next = next;
        }
    }

    private class ShelfIterator implements Iterator<E>
    {
        private int i = 0;
        private int size;
        private E[] items;

        private ShelfIterator(E[] items, int size)
        {
            this.items = items;
            this.size = size;
        }

        @Override
        public boolean hasNext()
        {
            return i < size;
        }

        @Override
        public E next()
        {
            return items[i++];
        }

        @Override
        public void remove()
        {
            throw new UnsupportedOperationException(
                    "Items cannot be removed during iteration.");
        }
    }
}

It's not what you know, it's what other people think you know.
Just hope you don't get quizzed on it.
Game engine design tutorials
Offline krasse
« Reply #7 - Posted 2011-03-03 20:28:11 »

How about the LinkedHashMap?

It is very good for iteration. It can also keep track of the latest object inserted if you want that as well.

Offline pjt33

« JGO Spiffy Duke »


Medals: 40
Projects: 4
Exp: 7 years



« Reply #8 - Posted 2011-03-03 22:31:25 »

Is there a reason that you need to use indices to identify the objects rather than just their references?
Offline IronclawsBt

Junior Devvie


Medals: 1



« Reply #9 - Posted 2011-03-03 22:51:41 »

Is there a reason that you need to use indices to identify the objects rather than just their references?

At the moment no, but it does have its uses. If you want to save then load your game state, using the references would get a bit tricky.

It's not what you know, it's what other people think you know.
Just hope you don't get quizzed on it.
Game engine design tutorials
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline pjt33

« JGO Spiffy Duke »


Medals: 40
Projects: 4
Exp: 7 years



« Reply #10 - Posted 2011-03-04 07:07:27 »

Is there a reason that you need to use indices to identify the objects rather than just their references?

At the moment no, but it does have its uses. If you want to save then load your game state, using the references would get a bit tricky.
Not if you make your classes serialisable. And if you use the references then you can do what you want with a linked list of weak references, and avoid having to reimplement GC.
Offline tberthel
« Reply #11 - Posted 2011-03-04 07:44:33 »

According to your time complexity requirements ryanm gave you the correct answer.  In general linked list is the answer to the time complexity needs.  While insertions and deletions are very fast with a linked list you will often realize that an array is fine.

Offline adon_y_coya

Senior Newbie





« Reply #12 - Posted 2011-03-04 14:18:33 »

I want to use a data structure with a very specific behavior. The general idea is that it acts as an array, but the objects have a permanent location. For example, if three objects were added, they may be assigned the indexes 0, 1, and 2. If object 1 is then removed, the other two objects can still be found at 0 and 2. Once an index is empty, a new object can be reassigned to that index (this is not required though).

The performance requirements are O(1) amortized insert, O(1) delete, O(1) find (by index), and iteration should be O(n) in the number of elements (with a constant factor at least as good as a linked list, preferably closer to array iteration). Most of these requirements would be taken care of by a hash map with carefully chosen keys, but the iteration cost would still be dependent on the capacity, not the actual number of elements.

A double linked list, with two forward and two backward links: one for *any* next/previous element and one for next/previous *non-null* element if the element is non-null (else it could refer to the *null* previous/next).
If you need to fast refer to *any* elements by index, then have also an array pointing to them as well.
The tricky part on those links would be to update them when null becomes non-null and vice versa (although that's when the array can come handy as well, by sequentially scanning forward and backward from updated location/index).
Offline IronclawsBt

Junior Devvie


Medals: 1



« Reply #13 - Posted 2011-03-04 14:46:09 »

The LinkedHashSet achieves what I needed. I forgot that that was included in the collections framework. The performance may not have the best constants, but unless that ends up being a problem, no reason not to use it.

It's not what you know, it's what other people think you know.
Just hope you don't get quizzed on it.
Game engine design tutorials
Pages: [1]
  ignore  |  Print  
 
 

 
EgonOlsen (79 views)
2018-06-10 19:43:48

EgonOlsen (59 views)
2018-06-10 19:43:44

EgonOlsen (78 views)
2018-06-10 19:43:20

DesertCoockie (261 views)
2018-05-13 18:23:11

nelsongames (160 views)
2018-04-24 18:15:36

nelsongames (158 views)
2018-04-24 18:14:32

ivj94 (901 views)
2018-03-24 14:47:39

ivj94 (162 views)
2018-03-24 14:46:31

ivj94 (813 views)
2018-03-24 14:43:53

Solater (177 views)
2018-03-17 05:04:08
Java Gaming Resources
by philfrei
2017-12-05 19:38:37

Java Gaming Resources
by philfrei
2017-12-05 19:37:39

Java Gaming Resources
by philfrei
2017-12-05 19:36:10

Java Gaming Resources
by philfrei
2017-12-05 19:33:10

List of Learning Resources
by elect
2017-03-13 14:05:44

List of Learning Resources
by elect
2017-03-13 14:04:45

SF/X Libraries
by philfrei
2017-03-02 08:45:19

SF/X Libraries
by philfrei
2017-03-02 08:44:05
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!