Speed versus memory

I have a general question regarding c/c++ regarding what is best to optimize.

Let's say that I have a large array, say of 200.000 elements and I want to look though this array and single out certain elements and save them into another array.

I would then allocate memory for another array of 200.000 elements and then store the elements (or id numbers of these elements) that I find in this array

Code:

---

// Definition of list element
typedef struct ListStruct 
{
        long  lNum;
        short  nType;
        long  lRecNum;
        double fValue;
} LIST;

        // LIST *pList is generated earlier in the code

        long iNumberOfElem = 0;
        long *piElements = (long *)MemGet( 200001, sizeof(long), NULL );
        for( int i = 0; i < 200000; i++ )
        {
                switch( pList[i].nType )
                {
                case TYPE_1:
                case TYPE_2:
                case TYPE_3:
                        // this operation is very short
                        break;
                       
                case TYPE_4:
                        //this is the type we are looking for
                        piElements[++iNumberOfElem] = i;
                        break;
                default:
                        // Somethin else happens here
                        break;
                }
        }

---

Now another alternative is to first loop though the array and count the elements and then do the memory allocation

Code:

---

typedef struct ListStruct 
{
        long  lNum;
        short  nType;
        long  lRecNum;
        double fValue;
} LIST;

        // LIST *pList is generated earlier in the code

        long iNumberOfElem = 0;
        // Counting elements in pList array
        for( int i=0; i<200000; i++)
        {
                if( pList[i].nType == TYPE_4 )
                {
                        ++iNumberOfElem;
                }
        }
        long *piElements = (long *)MemGet( iNumberOfElem + 1, sizeof(long), NULL );
        iNumberOfElem = 0;
        for( i = 0; i < 200000; i++ )
        {
                switch( pList[i].nType )
                {
                case TYPE_1:
                case TYPE_2:
                case TYPE_3:
                        // this operation is very short
                        break;
                       
                case TYPE_4:
                        //this is the type we are looking for
                        piElements[++iNumberOfElem] = i;
                        break;
                default:
                        // Somethin else happens here
                        break;
                }
        }

---

Obviously if you would know the amount of elements in the array it would be easier to now which to choose but say in general. What would be the best to prefer?

You've already written the code. Why not try them both and see.

Quote:

---

Originally Posted by GCDEF

You've already written the code. Why not try them both and see.

---

In a smaller program it would not be any problem allocating the memory but in general what would be the best? How can you measure the memory allocation when testing the program? The speed is easier to check I suppose.

What do you mean, "measure the memory allocation". You should know how much you're allocating. As to measuring the speed, just profile the app both ways and see which is faster.

Assuming the array that you will be working with can be arbitrary you do not really know the size of it. In that case you might want to keep the memory allocation in the program to a minimum and not allocating unnecessary memory.

Of course if you had unlimited memory it would be no problem but in the cases when you don't. What should you choose?

To make it even more clear, suppose that the above code lies within a threaded section and that there are several threads working with similar problems each having their own arrays to work on.

Furthermore, there is a big chance that there are no elements at all in the arrays that they are computing.

In the first case this would mean that many of the threads would allocate memory that would not be used at all.

There is no general answer as to whether you should prefer optimizing for speed or memory usage. Obviously, how much memory you can use is limited by what your users will tolerate and their machines can handle. Also note that memory usage can significantly impact the speed of your program, so these are not separate or mutually exclusive concerns.

Either way, the computational complexity is linear... given that, I'd prefer the more correct solution of counting first. This also suggests that there is a more meaningful optimization than the one you are considering, which is using a data structure that allows for faster searching than a simple list.

I think that it depends on how many elements from the first array are expected to be copied to the second array. If we are talking about say, 200 elements (or as you mentioned, no elements), then allocating space of 200000 elements would be a waste of space. As such, counting the number of elements would make sense.

An alternative is to copy what push_back in C++'s std::vector does: allocate some small amount of space, then double the capacity should you exceed that amount.

Quote:

---

Originally Posted by Hermit

Either way, the computational complexity is linear... given that, I'd prefer the more correct solution of counting first. This also suggests that there is a more meaningful optimization than the one you are considering, which is using a data structure that allows for faster searching than a simple list.

---

QTF. When you're going to be doing a lot of searching, use a tree (for sorted data) or a hash table (for unsorted). Only use a list or array if you really *must* check every single element every time.

The doubling approach is probably the best compromise, too. Realloc the array to twice its size (or the original array size, whichever is less) whenever you need more space.

I suppose there is a reason why you can not use STL for this.

Another option is to wrap access to the array and keep counts of the number of elements of a given type which are incremented/decremented when elements are added/removed. Then when it comes time to find a given type,
you already know the required size.

What is better depends on lots of things
1. how often do you add elements vs find a type.
2. does a given elements type change
3. Are these elements allocated with new
...