Register for your free account! | Forgot your password?

Go Back   elitepvpers > MMORPGs > Conquer Online 2 > CO2 Programming
You last visited: Today at 13:05

  • Please register to post and access all features, it's quick, easy and FREE!

Advertisement



[Intermediate] Competing against Microsofts ArrayList

Discussion on [Intermediate] Competing against Microsofts ArrayList within the CO2 Programming forum part of the Conquer Online 2 category.

Reply
 
Old   #1
 
InfamousNoone's Avatar
 
elite*gold: 20
Join Date: Jan 2008
Posts: 2,012
Received Thanks: 2,881
[Intermediate] Competing against Microsofts ArrayList

Performance status:

(Attempting to add 1,000,000 Elements)
Flexible: 156ms
List: 234ms
Improvement Speed: 40-50%

(Attempting to remove 1,000 Elements)
Flexible: 16ms
List: 7907ms
Improvement Speed: 99.998%

(Attempting to clear 1,000,000 Elements)
Flexible: 0ms (Less than 1ms)
List: 16ms


Ups / Downs
Collection speed improved (up)
Remove speed improved (up)
Removing re-arranged the array (down)
Supports multi-threaded operations (up)
Potentially 'wasted' memory (down)

Coded in Managed C++ by Infamous

Code:
	public ref class FlexibleArray
	{
		private:
			array<Object^>^ Elements;
			int Count;
			bool Synchronized;
		public:
			FlexibleArray(int Capacity)
			FlexibleArray()
			void Add(Object^ Value)
			void Remove(Object^ Value)
                        void Clear()
			int IndexOf(Object^ Value)
			bool Contains(Object^ Value)
			array<Object^>^ GetElements(int& Length)
	};
Code:
// Constructors
FlexibleArray(int Capacity)
{
        // Allocate elements using their estimated capacity
	Elements = gcnew array<Object^>(Capacity);
	Count = 0;
	Synchronized = true;
}
FlexibleArray()
{
        // Allocate elements using a default size of 36
	Elements = gcnew array<Object^>(36);
	Count = 0;
	Synchronized = true;
}
Code:
void Add(Object^ Value)
{
	while (!Synchronized)
		Sleep(1);
	Synchronized = false;
        // Resize the array if needed
	if (Count == Elements->Length)
	{
		array<Object^>^ nObj = gcnew array<Object^>(GetPrime(Elements->Length * 2));
                // Get prime returns the next prime number after the param
		Array::Copy(Elements, nObj, Count);
		Elements = nObj;
	}
	Elements[Count] = Value;
	Count++;
	Synchronized = true;
}
Code:
void Remove(Object^ Value)
{
	while (!Synchronized)
		Sleep(1);
	Synchronized = false;
	int Slot = 0;
	bool Found = false;
	int hashCode = Value->GetHashCode();
        // Find the elements index
	for each(Object^ tmp in Elements)
	{
		if (tmp->GetHashCode() == hashCode)
		{
			Found = true;
			break;
		}
		Slot++;
	}
	if (Found)
	{
		Count--;
		Elements[Slot] = Elements[Count];
                // Move the last element to the element's place
                // that we no longer need
		Elements[Count] = nullptr;
                // nullify the last element because its now in the index of the
                // element that we're removing
	}
	Synchronized = true;
}
Code:
// Clear the collection
void Clear()
{
	while (!Synchronized)
		Sleep(1);
	Synchronized = false;
	for (int i = 0; i < Count; i++)
	{
		Elements[i] = nullptr;
	}
	Count = 0;
	Synchronized = true;
}
Code:
// Pretty much a copy/paste from "Remove"
int IndexOf(Object^ Value)
{
	while (!Synchronized)
		Sleep(1);
	Synchronized = false;
	int Slot = 0;
	int hashCode = Value->GetHashCode();
	for each(Object^ tmp in Elements)
	{
		if (tmp->GetHashCode() == hashCode)
		{
			Synchronized = true;	
			return Slot;
		}
		Slot++;
	}
	Synchronized = true;
	return -1;
}
bool Contains(Object^ Value)
{
	return (IndexOf(Value) > -1);
}
Code:
// Lastly, beable to retrieve our block of data
array<Object^>^ GetElements(int& Length)
{
	Length = Count;
	return Elements;
}
Attached Files
File Type: rar ManagedCLibrary.rar (16.2 KB, 4 views)
InfamousNoone is offline  
Thanks
3 Users
Old 08/28/2008, 03:23   #2
 
elite*gold: 0
Join Date: Aug 2007
Posts: 49
Received Thanks: 12
What does the ^ modifier do? I don't know anything about C# but it looks to be used just like a pointer to me...

Anyways, some comments:

The clear function could be O(1) since you don't really need to set the items to null, do you?

Also I'm surprised at how slow the ArrayList remove is... your implementation is O(N) in the size of the list.. from a complexity analysis that's pretty much as slow as it gets. I assume the Arraylist one is O(N) as well (average 2n while yours is n/2, but in complexity analysis constants don't matter). Also, it seems that you're trying to use a hash of sorts to do the comparison? But then it requires the object to implement a GetHashCode() function? Why not just overload the equality operator?

Oh and is it really synchronized? In practice you probably won't have any problems but in theory assignment isn't atomic. To truly synchronize you should ask the OS for a semaphore of some kind.
flowerpot! is offline  
Old 08/28/2008, 03:26   #3
 
elite*gold: 0
Join Date: Feb 2008
Posts: 1,590
Received Thanks: 154
Quote:
Originally Posted by flowerpot! View Post
What does the ^ modifier do? I don't know anything about C# but it looks to be used just like a pointer to me...

Anyways, some comments:

The clear function could be O(1) since you don't really need to set the items to null, do you?

Also I'm surprised at how slow the ArrayList remove is... your implementation is O(N) in the size of the list.. from a complexity analysis that's pretty much as slow as it gets. I assume the Arraylist one is O(N) as well (average 2n while yours is n/2, but in complexity analysis constants don't matter). Also, it seems that you're trying to use a hash of sorts to do the comparison? But then it requires the object to implement a GetHashCode() function? Why not just overload the equality operator?

Oh and is it really synchronized? In practice you probably won't have any problems but in theory assignment isn't atomic. To truly synchronize you should ask the OS for a semaphore of some kind.
Just one thing.. this is Managed C++ not C#, both still .NET...
tao4229 is offline  
Old 08/28/2008, 17:45   #4
 
InfamousNoone's Avatar
 
elite*gold: 20
Join Date: Jan 2008
Posts: 2,012
Received Thanks: 2,881
Quote:
Originally Posted by flowerpot! View Post
What does the ^ modifier do? I don't know anything about C# but it looks to be used just like a pointer to me...

It's used as a pointer in managed C++ to represent a 'pointer' to a managed object.

Anyways, some comments:

The clear function could be O(1) since you don't really need to set the items to null, do you?

Also I'm surprised at how slow the ArrayList remove is... your implementation is O(N) in the size of the list.. from a complexity analysis that's pretty much as slow as it gets. I assume the Arraylist one is O(N) as well (average 2n while yours is n/2, but in complexity analysis constants don't matter). Also, it seems that you're trying to use a hash of sorts to do the comparison? But then it requires the object to implement a GetHashCode() function? Why not just overload the equality operator?

System::Object (the root of everything in the .NET Framework) implements a default GetHashCode() function tat can be overridden by default, so and object/class/struct will be fine

Oh and is it really synchronized? In practice you probably won't have any problems but in theory assignment isn't atomic. To truly synchronize you should ask the OS for a semaphore of some kind.
Fanks for your input, I'm going to compete against their Random soon probably (amazingly their Random is faster than 'rand() and srand()').
InfamousNoone is offline  
Reply


Similar Threads Similar Threads
[Intermediate]Server basics
05/28/2020 - CO2 Programming - 31 Replies
Hello elitepvpers members! In this topic, i will try to explain the basics of creating a conquer online private server from 'scratch' :} Before reading this i would suggest that you have to read these threads: http://www.elitepvpers.com/forum/co2-pserver-discu ssions-questions/177002-ask-yourself-before-you-st art-trying-make-server.html http://www.elitepvpers.com/forum/co2-programming/1 59269-intermediate-c-asyncsockets-server.html
[Intermediate] - C# AsyncSockets(Server)
11/07/2010 - CO2 Programming - 16 Replies
Hello everyone! In this tutorial I will teach you how to do simple ServerSocket and ClientSocket implementation using Asynchronous Sockets (non blocking, doesn't wait for data & doesn't freeze the current thread) Requirement(s) - Microsoft Visual C# 2008 Express Edition - .NET Framework 3.5 (I'm not sure wether this comes with the above program or not.) I will be using that program on all my C# tutorials so get ready to download it. :D I'll start off with Async ServerSocket; I'll...
[Tips][Intermediate]Making A UCE
07/07/2009 - Grand Chase Philippines - 11 Replies
How To Make A UCE Requirement : At least Intemediate Hacking Brains ;) Content Page: (Note that you could just press "Ctrl + F" to enable the "Find" function if you want to quickly move to a specific steps.) A_1) Updates of tutorial B_2) Programmes required



All times are GMT +1. The time now is 13:05.


Powered by vBulletin®
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
SEO by vBSEO ©2011, Crawlability, Inc.
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

Support | Contact Us | FAQ | Advertising | Privacy Policy | Terms of Service | Abuse
Copyright ©2022 elitepvpers All Rights Reserved.