Paolo:
Thanks for your recommendations. I just followed the comment in the code.
These are the tests (attached).
best regards
Juan C. Olivares
using System;
using System.Collections.Generic;
using System.Runtime.InteropServices;
class Test
{
public static void Main (string [] args)
{
// Check
if (args.Length < 1)
{
Console.WriteLine ("Specify original list size");
return;
}
int max = Int32.Parse (args [0]);
// Create original list
List <int> numbers = new List <int> ();
// Fill list
Random rand = new Random ();
for (int i = 1; i <= max; i++)
numbers.Add (rand.Next (1, 1000000000));
int pivot = numbers [numbers.Count / 2];
// Create predicate
Predicate <int> predicate = delegate (int number) { return number < pivot; };
List <int> results1 = null;
List <int> results2 = null;
List <int> results3 = null;
List <int> results4 = null;
List <int> results5 = null;
List <int> results6 = null;
// Sort using old method
DateTime dt1 = DateTime.Now;
for (int i = 1; i <= 10; i++)
results1 = Find1 (numbers, predicate);
DateTime dt2 = DateTime.Now;
// Sort using stackalloc bool
DateTime dt3 = DateTime.Now;
for (int i = 1; i <= 10; i++)
results2 = (max < 100000) ? Find2 (numbers, predicate) : new List <int> ();
DateTime dt4 = DateTime.Now;
// Sort using stackalloc bit
DateTime dt5 = DateTime.Now;
for (int i = 1; i <= 10; i++)
results3 = (max < 100000) ? Find3 (numbers, predicate) : new List <int> ();
DateTime dt6 = DateTime.Now;
// Sort using bool array
DateTime dt7 = DateTime.Now;
for (int i = 1; i <= 10; i++)
results4 = Find4 (numbers, predicate);
DateTime dt8 = DateTime.Now;
// Sort using bit array
DateTime dt9 = DateTime.Now;
for (int i = 1; i <= 10; i++)
results5 = Find5 (numbers, predicate);
DateTime dt10 = DateTime.Now;
// Sort using heap bit
DateTime dt11 = DateTime.Now;
for (int i = 1; i <= 10; i++)
results6 = Find6 (numbers, predicate);
DateTime dt12 = DateTime.Now;
Console.WriteLine ("Old method: {0}: found {1} elements", dt2 - dt1, results1.Count);
Console.WriteLine ("stackalloc bool method: {0}: found {1} elements", dt4 - dt3, results2.Count);
Console.WriteLine ("stackalloc bit method: {0}: found {1} elements", dt6 - dt5, results3.Count);
Console.WriteLine ("bool array method: {0}: found {1} elements", dt8 - dt7, results4.Count);
Console.WriteLine ("bit array method: {0}: found {1} elements", dt10 - dt9, results5.Count);
Console.WriteLine ("heap bit method: {0}: found {1} elements", dt12 - dt11, results6.Count);
}
private static List <int> Find1 (List <int> numbers, Predicate <int> predicate)
{
List <int> results = new List <int> ();
foreach (int number in numbers)
if (predicate (number))
results.Add (number);
return results;
}
private static List <int> Find2 (List <int> numbers, Predicate <int> predicate)
{
unsafe
{
bool *bools = stackalloc bool [numbers.Count];
bool *ptr = bools;
int found = 0;
foreach (int number in numbers)
{
if (predicate (number))
{
(*ptr) = true;
found++;
}
ptr++;
}
List <int> results = new List <int> (found);
for (int i = 0; i < numbers.Count; i++)
if (bools [i])
results.Add (numbers [i]);
return results;
}
}
private static List <int> Find3 (List <int> numbers, Predicate <int> predicate)
{
unsafe
{
uint *bits = stackalloc uint [(numbers.Count / 32) + 1];
uint *ptr = bits;
int found = 0;
uint bitmask = 0x80000000;
foreach (int number in numbers)
{
if (predicate (number))
{
(*ptr) = (*ptr) | bitmask;
found++;
}
bitmask = bitmask >> 1;
if (bitmask == 0)
{
ptr++;
bitmask = 0x80000000;
}
}
List <int> results = new List <int> (found);
bitmask = 0x80000000;
ptr = bits;
for (int i = 0; i < numbers.Count; i++)
{
if (((*ptr) & bitmask) == bitmask)
results.Add (numbers [i]);
bitmask = bitmask >> 1;
if (bitmask == 0)
{
ptr++;
bitmask = 0x80000000;
}
}
return results;
}
}
private static List <int> Find3b (List <int> numbers, Predicate <int> predicate)
{
unsafe
{
uint *bits = stackalloc uint [(numbers.Count / 32) + 1];
uint *ptr = bits;
int found = 0;
uint bitmask = 0x80000000;
foreach (int number in numbers)
{
if (predicate (number))
{
(*ptr) = (*ptr) | bitmask;
found++;
}
bitmask = bitmask >> 1;
if (bitmask == 0)
{
ptr++;
bitmask = 0x80000000;
}
}
int [] results = new int [found];
bitmask = 0x80000000;
ptr = bits;
int j = 0;
for (int i = 0; i < numbers.Count && j < found; i++)
{
if (((*ptr) & bitmask) == bitmask)
results [j++] = numbers [i];
bitmask = bitmask >> 1;
if (bitmask == 0)
{
ptr++;
bitmask = 0x80000000;
}
}
return new List <int> (results, found);
}
}
private static List <int> Find4 (List <int> numbers, Predicate <int> predicate)
{
unsafe
{
bool [] bools = new bool [numbers.Count];
int found = 0;
int indice = 0;
foreach (int number in numbers)
{
if (predicate (number))
{
bools [indice] = true;
found++;
}
indice++;
}
List <int> results = new List <int> (found);
for (int i = 0; i < numbers.Count; i++)
if (bools [i])
results.Add (numbers [i]);
return results;
}
}
private static List <int> Find5 (List <int> numbers, Predicate <int> predicate)
{
uint [] bits = new uint [numbers.Count / 32 + 1];
int bitindex = 0;
uint bitmask = 0x80000000;
int found = 0;
for (int i = 0; i < numbers.Count; i++)
{
if (predicate (numbers [i]))
{
bits [bitindex] = bits [bitindex] | bitmask;
found++;
}
bitmask = bitmask >> 1;
if (bitmask == 0)
{
bitindex++;
bitmask = 0x80000000;
}
}
List <int> results = new List <int> (found);
bitindex = 0;
bitmask = 0x80000000;
for (int i = 0; i < numbers.Count; i++)
{
if ((bits [bitindex] & bitmask) == bitmask)
results.Add (numbers [i]);
bitmask = bitmask >> 1;
if (bitmask == 0)
{
bitindex++;
bitmask = 0x80000000;
}
}
return results;
}
private static List <int> Find6 (List <int> numbers, Predicate <int> predicate)
{
unsafe
{
uint *bits = (uint*) Marshal.AllocHGlobal ((numbers.Count / 8) + 4);
uint *ptr = bits;
int found = 0;
uint bitmask = 0x80000000;
(*ptr) = 0;
foreach (int number in numbers)
{
if (predicate (number))
{
(*ptr) = (*ptr) | bitmask;
found++;
}
bitmask = bitmask >> 1;
if (bitmask == 0)
{
ptr++;
(*ptr) = 0;
bitmask = 0x80000000;
}
}
List <int> results = new List <int> (found);
bitmask = 0x80000000;
ptr = bits;
for (int i = 0; i < numbers.Count; i++)
{
if (((*ptr) & bitmask) == bitmask)
results.Add (numbers [i]);
bitmask = bitmask >> 1;
if (bitmask == 0)
{
ptr++;
bitmask = 0x80000000;
}
}
Marshal.FreeHGlobal ((IntPtr) bits);
return results;
}
}
}
_______________________________________________
Mono-list maillist - [email protected]
http://lists.ximian.com/mailman/listinfo/mono-list
