Collections and Arrays

yes but that copies ALL of the items in the collection.. I only want to copy a few of them.. A range of items in the collection so to speak

hi,
you can use Addrange and getrange to do that ...
here is some code:

ArrayList a = new ArrayList();
ArrayList b = new ArrayList();

b.Add(31); //add elemnts to a
b.Add(32);
b.Add(33);
b.Add(34);
b.Add(35);
b.Add(36);
b.Add(37);

a.AddRange(b.GetRange (2,3)); //add 3 elements from b to a

for (int i = 0;i<a.Count;i++)   //a contain 33,34,35
      MessageBox.Show(a[i].ToString());

what are you guys doing??? I said a COLLECTION not an ArrayList.

A COLLECTION does NOT support the GetRange method.

Because collection doesn't have something similar to Array.Copy(...),

you could use CopyTo to copy ALL elements of collection into an existing Array and after
copy a section of that Array to another Array using Array.Copy(source,start, destination,count).
 

Sir,
can i ask what kind of of Collection are you using? there are many in C#

does not matter the collection in this case.. What I am looking for is a way to copy a specificied number of objects from a collection. That's not easy and I know it's not available in .NET that is why I am here..

I don't care if it's done in managed or unmanaged code..

The reason why Array.Copy functions exist is that you don't have to loop the array in order to copy it, there are faster ways.

For a general collection the ONLY way to access each member is to enumerate them, i.e.. a foreach loop. Even the internal implementation would have to make some loop of some kind and apart from lists and other sequences it isn't obvious exactly how you would want to loop them.

Do you want to traverse a tree in prefix, infix or postfix order?

Do you want to traverse a graph in breadth first or depth first order?

And since any internal implementation would have to be implemented by a foreach loop anyway and there are so many options to choose on exaclty how you want to iterate them, it is just as well to skip it and rather export a foreach mechanism to the end user so that he can choose how he or she wants to iterate the elements by himself or herself.

So the short answer is: No, there is no way, you have to loop through the elements. This is usually trivial to do though once you know the context where you want to do it.

Alf

Salte,

I agree for the most part, it is trivial do loop a collection but it is SLOW to loop it. I am looking for a way to get a range of items in a collection with speed. I am sure there is a way to do it using the Windows API, I just don't know the calls.

Any ideas?

What do you mean by "slow" here?

Let's say I implement a list class.

class ListNode {
internal ListNode next;
internal object data;
}

class List : IEnumerable {
internal ListNode first;
internal ListNode last;

...blah blah blah various functions...

    ListEnumerator GetEnumerator()
    {
        return new ListEnumerator(first);
    }
};

class ListEnumerator : IEnumerator {
   private ListNode cur;
   private ListNode list;

   internal ListEnumerator(ListNode f) { list = f; cur = null; }

   public virtual bool MoveNext()
   {
        if (cur == null)
           cur = list;
        else
           cur = cur.next;
       return cur != null;
   }

    public virtual object Current()
    { return cur.data; }

    public virtual void Reset()
    { cur = null; }
}

Now you might think it is "slow" to use the enumerator but it is actually just as fast or slow as it would be to loop through the ListNode objects by yourself:

ListNode p = first;
while (p != null) {
     ...access p.data....
     p = p.next;
}

but this is only barely faster and actually after the CLI code has been compiled by the JIT compiler it might actually result in exactly the same machine code.

So, no, it isn't necessarily any slower than doing it "directly" and note that there is no faster way to walk through a list - it is an inherent property of a list that you have to walk through the list node by node.

The same consideration is for other collections.

The only exception is arrays or similar array-like data st        ListNode c = cur;
        if (c != null) {
           cur = c.next;
           return c.data;
       }
      return null;
ructures such as stringbuilder's strings (which actually are char[]  - i.e. array of char). For these the hardware often offer special instructions which can run through the array faster than you can do it in a loop.

Hope this answers your question.

Alf

Salte,

Well in my experience I can copy 5000 items from one array to another in less than 1 second but when I loop through 5000 items in a collection using the enumerator, it takes about 5-10 seconds depending...

I am looking to reduce the time to the less than a second deal

What kind of collection are we talking about here? Usually enumreators are made so that they can find the element as fast as possible but what is "fast as possible" depends very much upon the data structure. For example if you have a tree structure I would imagine a looping through a range of the data structure IS much slower than just traversing the tree and doing short-cuts by dropping subtrees you know are without interest.

If you are in a current node in a tree and want to find the "next" node in order this is a rather complicated run, especially if you don't have a parent pointer in the tree node but even with a parent node the "next" node is found by a fairly tricky algorithm.

1. If the current node has a right subtree then it has nodes that is larger than itself in a subtree and so you find the smallest such value. This is found going down the right subtree and then follow the chain of left subtrees until you find a node without left subtrees. This is the next node.

2. If the current node has no right subtree then it is the largest value in its own subtree (with itself as root) and you have to check the parent node.

3a. If the current node is in the right subtree of the parent then it is the largest node in the paren't subtree as well so you move up the tree until you find a parent where the current node is in the left subtree and not the right. If you hit the root node and all pointers are the right subtree then the node was the largest node in the tree and you are done.

3b. If you find a node where the current node is in the left subtree then that node is the next node since that is the next value.

Something like this in C# code.

Node next(Node C)
{
     if (C.right != null) {
           C = C.right;
           while (C.left != null)
               C = C.left;
           return C;
     }
     Node P = C.parent;
     while (P != null && P.right == C) {
          C = P;
          P = P.parent;
     }
     // either P == null and we're done, return null
     // or P != null and P.right != C so P.left must equal C and so P is the next node.
    return P;
}

As you can see this is quite complicated and you might call it slow but it is as fast as you can get for a binary tree. Your problem isn't that it is slow, your problem is that you have either chosen the wrong type of collection or that you are trying to use the collection in a way it wasn't meant to be used.

If you could explain in more detail what type of collection you are using and what you are trying to do with it and why you want it to be that type of collection, maybe we can help.

Hope this explains.

Alf

ok then...

The collection is an EventLogEntryCollection

I have about 5 of them in an ArrayList object.

and I am using it to populate a dynamic listview and I need to get the items out of the Collections and into an EventLogEntry[] array

Okay... Every collection I looked through (lists, sorted lists, array lists, Queues, hashtables, etc) has a copyTo or ToArray Function.  By implementing ICollection you will have a CopyTo function, so even if you have your own home grown collection you still have that function.

hence.... this code works.  I have a collection (a queue, and I only want to copy 3 elements from it)


                  Queue q = new Queue();

                  for(int x = 0; x<10; x++)
                        q.Enqueue(x);

                  object[] o = new object[3];

                  Array.Copy(q.ToArray(),4,o,0,3);      



// display results

                  for(int y = 0; y<o.Length; y++)
                        Console.WriteLine(((int) o[y]).ToString());

_TAD_

I am not seeing this in the same way...

If I inherit from ICollection or IList, I do not get a ToArray Function???

Let me see if I get this right.

You have an array list containing 5 EventLogEntryCollection objects?

If so I suspect the reason for it being slow is due to the EventLogEntryCollection object being slow. This object is probably implemented through some form of list or array or perhaps even worse by doing RPC call to get each element. However, I would assume that the CopyTo function would be fast.... try this...

int k = 0;

foreach (EventLogEntryCollection ec in ArrayListOfEventLogEntryCollections)
    k += ec.Count;
EventLogEntry [] arr = new EventLogEntry[k];
k = 0;
foreach(EventLogEntryCollection ec in ArrayListOfEventLogEntryCollections) {
    ec.CopyTo(arr, k);
    k += ec.Count;
}
Ok, we loop twice, as I said, if you keep the count you can avoid that first loop.

The second loop should go as fast as it can go.

This is using CopyTo which people already at the first posting adviced you to do ;)

If you want to copy a range then that range is either:

1. Based on index (see below) or

2. Based on contents.

If it is 2 then you HAVE TO loop through each individual element of the collections, there's no way around it and presumably the enumerator for that collection is as fast as it can when looping through the elements.

If it is 1, then I can help you. Let's say you want to copy C elements starting from index S instead of all of them as the above loops do. Also, assume you want to copy them into an array starting from index V. V must have room for the elements copied.

int k = 0;
foreach (EventLogEntryCollection ec in TheArrayList) {
     k += ec.Count;

I could have made a break out of the loop when k >= S + C but there's no point since there's only 5 elements in the array list.

int j = S + C;
if (k < S)
    return -1; // no events before S

if (k < j) {
   j = k;
   C = j - S;
}
// check that the destination array has room for C entries after V i.e. V + C <= arr.Length;
if (V + C > arr.Length) {
    // arr isn't big enough, throw some argument exception or something.
}

k = 0;
int copied = 0;

foreach (EventLogEntryCollection ec in TheArrayList) {
    int u = k + ec.Count;
    // if    S <= k < S + C  then we must copy some elements.
    // specifically if S <= k  <= u < S + C then we copy the whole collection to the array:
    // if S <= k < S + C < u then we only copy part of the collection.
    // we may also have the situation that k < S < u <= S + C if so we also copy part of the collection.
    if (u < S) { // haven't started copy yet.
         // do nothing
    } else if (k < S) { // k < S <= u
        if (u < S + C) {
               // k < S <= u < S + C we need to copy from S to u - 1.
               // since ec is based on k so all index values in ec is relative to k.
               int to_copy = u - S;
              CopyTo(ec, S - k, arr, V, to_copy);
              V += to_copy;
              C -= to_copy;
              copied += to_copy;
              S = u;
        } else {
              // k < S <= S + C <= u, Thus the whole copying is within this segment of ec.
             CopyTo(ec,S-k,arr,V,C);
             break;
        }
    } else if (u < S + C)  { // S <= k < u < S + C, copy the whole segment to array.
        ec.CopyTo(arr,V);
        V += u - k;
        C -= u - k;
        S = u;
    } else { // S <= k < S + C <= u, copy from k to S + C.
       ec.CopyTo(arr,V);
        break;
    }
    return copied + C;
}

The CopyTo function needs to be written:

int CopyTo(EventLogEntryCollection ec, int start, EventLogEntry [] dest, int start2, int count)
{
    EventLogEntry[] temp = new EventLogEntry[ec.Count];
    ec.CopyTo(temp,0);
    return Array.Copy(temp,start,dest,start2,count);
}

Unfortunately, there's no CopyTo that only copies a range.

If you need to filter the elements based on contents there really is no other way other than either 1. loop through each element in the collection or 2. Use CopyTo to copy the elements to an array and then continue from there.

Hope this is of help.

Alf

Err.. the I... whatever are interfaces.... you do not INHERIT them... they a class cannot inherit from an interface. Only interfaces can inherit from interfaces.

What you think is inheritance is C#'s way of saying that a given class promises to IMPLEMENT the interface. I.e. you can specify an interface that contain a ToArray function but then YOU must write that function. The interface doesn't have any code you can use.

Alf

To clarify, any class that implements ICollection needs a function called CopyTo()

when implementing the ICOllection you also have a "Count" property as well as a IsSyncrhronized and SyncRoot Properties.

take a gander at this snippet


// I'm using an event log entry object
EventLogEntry e;
                  
//create an array of Icomponent Objects
IComponent[] c = new IComponent[10];

//create an array of generic objects
object[] obj = new object[10];

//copy eventlog entry array to Icomponent array en mass
e.Container.Components.CopyTo(c,0);

// copy eventlog entry data objects to generic object array
e.Data.CopyTo(obj,0);


and if you don't want to create a specific array of type IComponent, just declare it as a generic object array and then cast it as an IComponent when you use it.

e.Container.Components.CopyTo(o,0);
Console.WriteLine(((IComponent)obj[0]).ToString());

Sorry for the delay.. had to deal with work :(

I do like the idea's but what I am seeing with both Salte's and _TAD_'s code is that you guys are doing what I am trying to avoid: Using the copyTo function of the collection which copies all of the elements to an array. This is the slow part that I am trying to get around by using some other method to copy a specific number of items from the collection.

Salte,
I am using method #1 (by index) to try and make this copy work so we are good.

Orbital,
   There in might lay your problem.  You must remember that Microsoft has optimized all of its code to be the most efficient.  The only way that may be faster is to use pointers and pointer arithmetic.  But then you aren't really copying the array, you are only referencing portions of another array.  If that base array changes, then the array your are using gets all hosed up as well.




Here is a thought... Although I haven't tried it yet, so the theory may be better than the application.


Suppose you have an array of 10,000 elements, and you want roughly 1,000 of those elements.

What about multi-threading the copy process?


have one thread only copy the first 100 element to array1, have a second thread copy elements 101 to 200 to array2, etc, etc.

Then at the end you simply merge the arrays.


I'll have to run a few trials and see if the straight CopyTo function (for 1,000 elements) is faster than a multi-threaded app each copying 100 elements.  

_TAD_,

it might work but keep this in mind.. I am displaying the record not too soon after they are copied.. so if the multithreaded approach is not faster then it will do me no good.

NOW, using pointer types and pointer arithmetic sounds like a plan.. My biggest problem is that I am not as proficient in pointer usage as I would like to be.. So if anyone has any samples of how I might accomplish my task using the pointer types then by all means...

Ok, yes, we use the CopyTo which copies the whole array. There is no other version available.

The only OTHER alternative is to loop through the set using enumerator. Normally an enumerator is written to work as fast as possible. I agree though that the collection support in C# is far from perfect.

int CopyTo(EventLogEntryCollection ec, int start1, EventLogEntry [] dest, int start2, int count)
{
    int x = 0;
    int y = start2;
    foreach (EventLogEntry e in ec) {
       if (x >= start1) {
           dest[y++] = e;
           if (--count == 0)
                     break;
       }
       ++x;
    }
    return y - start2;
}

Perhaps add some more index checking, for example I don't test if start2 + count >= dest.Length etc.

Note that I only walk through the initial part of the collection, when I have copied count elements I break.

I must start from beginning though and simply just count x up to start1 before I can do any copying. There's no way around that unless you know the internal details of the collection in question. I don't know how an EventLogEntryCollection is implemented.

Also, even an internal CopyTo function must scan through the elements in a manner similar to the one I use here, there's no way around that. This is frequently an inherent limitation with the collection itself - such as a list.

Alf

alas, this is just way to slow for me to handle... I guess I will just have to find another way.

I am still intrested int he pointer types version

I might just look into that and see