koobas.hobune.stream
Data structure to efficently manage a queue of objects
I need To find and remove objects in the middle of a queue of objects. I suppose that list, arraylist, stack and queue implemented in .net 2.0 are useless. Should I implement an other data structure by myself? And which should I use? Aren't there any third party libraries?
Because first it will run a linear search and I think that, called each frame with more than 100 of objects in the list, will probably slow down the game. The problem is that I'm having heavy lags on android devices and the game is really simple!
If you need to remove arbitrary values from the middle of the list, you won't get better than O(n)... are you sure this is what's causing your performance bottleneck?
As tanoshimi said, you should profile your code. .NET's List class should do everything you need and I doubt it is causing your performance problems.
There's no room for "probably" in program$$anonymous$$g. You should get the data! :)
With an unordered collection there is no faster way than iterating through the whole thing and compare with the token.
Now, I said unordered which means if you use an ordered queue/list/array/else then you have some algorithm getting to the point faster using a binary search, then the point moves to the choice of sorting algorithm. BUT, Bill already did that for you so you can use list.Sort and that is it.
Once ordered, you can use a binary search that will increase your performance. Using an integer for comparison as opposed to string will also improve.
"There is no faster way than iterating through the whole thing and compare with the token.". Well we have dictionary don't we?
You were right. I've compared the two data structures and the .NET implementation seems to be the quickest. 4,5 10^-6 seconds(Custom LinkedList) vs 1.9 10^-6 seconds.However now I think that my problem is due to rendering. Thank you all :) this was my implementation.
class CustomLinkedListNode<T>
{
public T item;
public CustomLinkedListNode<T> previous;
public CustomLinkedListNode<T> next;
public void Remove()
{
previous.next = next;
next.previous = previous;
}
#region Constructors
public CustomLinkedListNode(T item)
{
this.item = item;
}
public CustomLinkedListNode() { }
#endregion
}
class CustomLinkedList<T>
{
private int N;
private CustomLinkedListNode<T> pre;
private CustomLinkedListNode<T> post;
private Dictionary<T, CustomLinkedListNode<T>> searchDic;
public CustomLinkedList()
{
searchDic = new Dictionary<T, CustomLinkedListNode<T>>();
pre = new CustomLinkedListNode<T>();
post = new CustomLinkedListNode<T>();
pre.next = post;
post.previous = pre;
}
public bool isEmpty() { return N == 0; }
public int Count
{
get
{
return N;
}
}
public void Remove(T item)
{
CustomLinkedListNode<T> nodeToRemove = searchDic[item];
searchDic.Remove(item);
nodeToRemove.Remove();
N--;
}
public void Add(T item)
{
CustomLinkedListNode<T> last = post.previous;
CustomLinkedListNode<T> newNode = new CustomLinkedListNode<T>();
newNode.item = item;
newNode.next = post;
newNode.previous = last;
post.previous = newNode;
last.next = newNode;
searchDic.Add(item, newNode);
N++;
}
}
If you have programming experience you can write it yourself according to your needs. Here is an idea. Write a double linked list which will hold your objects(Which has extra node class to hold objects). When you add to the queue, add to the linked list and also hold a dictionary for fast search of node to delete. So the code will be like:
// Actually a double linked list
public class LinkedList<T>{
LinkedListNode<T> head;
LinkedListNode<T> tail;
Dictionary<T,LinkedListNode<T>> searchDic;
void Remove(T item){
var nodeToRemove = searchDic[item];
searchDic.Remove(item);
nodeToRemove.Remove();
}
void Add(T item){
var newNode = new LinkedListNode(item);
tail.next = newNode;
tail = newNode;
searchDic.Add(item, newNode);
}
}
public class LinkedListNode<T>{
void Remove(); // This basically binds the next and previous
#region Constructors
// Insert Constructors here
#endregion
}
Note that it doesn't have to be generic. I don't guarantee it will work or you have what it takes to make it work. Also code is not completed and you should complete it as an exercise. If this works it means you can add, search and delete in constant time. One point I did oversee is you should first check if element exists in dictionary or you will get exceptions. You can use TryGetValue().
Why would you implement an already existing data structures? THis will never go as fast as the .NET linked list: http://msdn.microsoft.com/en-us/library/he2s3bh7%28v=vs.110%29.aspx
Of course he should use built-in data structures if it suits his needs. But overloading these are not possible and he may need other functionality from the data structure. For example .Net linked list takes linear time to remove an object http://msdn.microsoft.com/en-us/library/k87xw3hb(v=vs.110).aspx . This is because they assume there will be duplicates in the list. But if you won't have duplicates you can have a dictionary for fast search and make the remove constant time. That is why I prefer writing my own data structures.
By the way, if you implement it correctly, your data structures will be slower than built-in data structures only by trivial amount (trivial as in time to make 2-3 extra function calls).
I haven't duplicates and I think this solution can be useful. However fafase why do you think it will be slower?
It is highly unlikely that a user may match the performance of .NET implementation. They know what they are doing at $$anonymous$$icrosoft and that is why they are doing it. Now, in some cases, you could get some good result by stripping off additional commands, most likely security and exception check. But then your code is less safe. So fast or safe? If you have no duplicate, then you could try Dictionary. Bets is to compare Dictionary against SortedList. First should be faster though but you could also improve by overriding the GetHashCode method of the type you use as key.
