7 replies to this topic

[AtoZ]

I need to make an array of dynamic data so I don't know how big it will be until the programs running, how can I do this?

[zoranh]

I'll give you couple of ideas:

1. Using Generic List
You can use System.Collections.Generic.List<T> generic class to add as many elements as you like. In this case, you cannot access random element by its position in time less than O(n) steps.

2. Using ArrayList
You can use System.Collections.ArrayList class but it only accepts objects. Hence, if you intend using it for value types then bear on mind the boxing/unboxing overhead.

3. Using Array
Create fixed-size strong type array of required type. Keep track of allocated capacity of the array (property Length) and used capacity of the array (in a separate variable). New elements are inserted at position of that separate variable. Once it reaches beyond of allocated size of the array, double the size of the array by using generic Resize method. Here's the code:

double[] a = new double[2];

int used = 0;


for (int i = 0; i < 10; i++)

{

    if (used == a.Length - 1)

    {

        Array.Resize<double>(ref a, 2 * a.Length);

        Console.WriteLine("Resized to {0} elements.", a.Length);

    }

    a[used++] = Math.PI * i;

}


for (int i = 0; i < used; i++)

    Console.WriteLine("array[{0}] = {1}", i, a[i]);

4. Exotics
Use strong typed dictionary which maps Int32 to desired type (e.g. Double if you intend storing Double values). Then insert elements where key is the item's position in the simulated array and value is the value stored in the array, like this:

Dictionary<int, double> d = new Dictionary<int, double>();


for (int i = 0; i < 10; i++)

    d.Add(d.Count, Math.PI * i);


for (int i = 0; i < d.Count; i++)

    Console.WriteLine("array[{0}] = {1}", i, d[i]);

[zoranh]

Just for fun, I've measured time required to append an element to each of the structures named above:

Array      24 nsec/element

List       25 nsec/element

ArrayList  58 nsec/element

Dictionary 83 nsec/element

And here's the source code for the test bench application:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Collections;


namespace TestApp

{

    class Program

    {


        delegate void Tester(Int64 elementsCount);


        static void Main(string[] args)

        {


            Int64 elementsCount = 100000;  // Modify this to select maximum size of the structure

            Int64 iterationsCount = 1000;  // Larger the value, more precise the answer is

            Tester[] functions = new Tester[] 

            {

                TestList,

                TestArrayList,

                TestArray,

                TestDictionary

            };


            for (int i = 0; i < functions.Length; i++)

            {


                DateTime start = DateTime.Now;

                for (int j = 0; j < iterationsCount; j++)

                    functions[i](elementsCount);

                DateTime end = DateTime.Now;


                double msec = end.Subtract(start).TotalMilliseconds;


                double nsec = msec * 1000000 / elementsCount / iterationsCount;


                Console.WriteLine("{0}\t{1} nsec/element", functions[i].Method.Name.Substring(4), Math.Round(nsec));


            }


        }


        static void TestList(Int64 elementsCount)

        {


            List<double> l = new List<double>();


            for (Int64 i = 0; i < elementsCount; i++)

                l.Add(Math.PI * i);


        }


        static void TestArrayList(Int64 elementsCount)

        {


            ArrayList al = new ArrayList();


            for (Int64 i = 0; i < elementsCount; i++)

                al.Add(Math.PI * i);


        }


        static void TestArray(Int64 elementsCount)

        {

        

            double[] a = new double[2];

            int used = 0;


            for (Int64 i = 0; i < elementsCount; i++)

            {

                if (used == a.Length - 1)

                    Array.Resize<double>(ref a, 2 * a.Length);

                a[used++] = Math.PI * i;

            }


        }


        static void TestDictionary(Int64 elementsCount)

        {


            Dictionary<Int64, double> d = new Dictionary<long, double>();


            for (int i = 0; i < elementsCount; i++)

                d.Add(d.Count, Math.PI * i);


        }


    }

}

[vinyl]

I like to use method #1 from above, then if you must end up with an array, you can use the CopyTo method of lists once you have your list complete.

[zoranh]

vinyl said:

I like to use method #1 from above, then if you must end up with an array, you can use the CopyTo method of lists once you have your list complete.

Me too.

If I have to code a method that returns an array of values, whatever, it happens that it's unknown in advance how many elements the array will return. For example, a method that lists all text files in a directory that have word "something" in their content. Then I'd simply build a List<string>, adding file names to it as it proves that the file satisfies the condition. Then return statement looks like this: return list.ToArray().

In addition, I don't like to return lists from methods. Maybe because of my C/C++ roots.

Method #3 is for real time programming only and even then for very large structures. I mean when you need to pass on megabytes of data in blink of an eye, that's the solution. Otherwise, not worth an effort (and bugs). I've used this method a lot in socketing servers and in cases when lot of data are being processed in a stream of bytes. No built-in .NET collection can help you in such case, but only a plain old array.

[brightmatter]

Yep, I use #1

However, the question is how to use array not list so if you are done adding elements, use the *.toArray<[your object type or primitive]>()

Edited by brightmatter, 09 July 2010 - 04:54 PM.
incomplete thought

[gokuajmes]

This is what you want:
1.Make a array of Undefined size.
2.Fill them with data
3.Get the Size of the Array ?
that is not possible man.you should either restrict array but its Item count or Limit the array by its size.
But if this is possible ,let me know the solution too

[zoranh]

gokuajmes said:

This is what you want:
1.Make a array of Undefined size.
2.Fill them with data
3.Get the Size of the Array ?
that is not possible man.you should either restrict array but its Item count or Limit the array by its size.
But if this is possible ,let me know the solution too

It IS possible, and that is solution #3. You just keep track of allocated and used size of the array. Once the two meet, reallocate the array to twice the size.

It is easy to prove that appending an element to such an array has asymptotic complexity O(1), which equals to simple fixed-size array case. Suppose that you have appended n elements to an empty reallocable array, initially having size 1. Then average number of copies of single element is this:

k = log2(n), implying: 2^(k-1) < n <= 2^k

avg.copies = sum(2^i, i = 0, 1, ... , k-1) / n

           = (2^k - 1) / n 

           = O(1 / n * 2 ^ log2(n)) 

           = O(1)

Hence, reallocable array has asymptotic complexity O(1) to add an element, which equals asymptotic complexity of adding an element to an end of the list. This is demonstrated by the experiment above, where appending to list required 25 nanoseconds per element and appending to array 24 nanoseconds per element. Also note that reading an element from a random position inside list has complexity O(n) while the same operation for reallocable array has complexity O(1).