c++: Random access to Dynamic Array

Question

Following is my scenario:

I am making use of a large 2D dynamic array to store elements with following attributes:

int
vector

Now, the array elements are accessed randomly. As a result, time access to elements greatly varies.

I want time access to elements to be small as well as constant for all the accessions.

Is dynamic array best suitable for my scenario?

I tries using unordered_map of boost but it seems that unordered map takes more time to access elements as compared to dynamic array.

Please give suggestions:

Code:

Code:

for( counter1=0; counter1< sizeof(chunk1); ++counter1)
{
   //code lines skipped
    IndexEntries &data=IndexTable[chunk1[counter1]][chunk1[counter1+1]];
    DoubleTableEntries &GetValue=NewDoubleTable[NextState_chunk1][data.index]; 
    NextState_chunk1= GetValue.Next_State;
    ++Bcount;
    buffer[ Bcount]=NextState_chunk1;
    ++counter1;

    //  Code lines skipped
}

Here NewDoubleTable is the 2d Array from which I am accessing randomly elements.

By what are you accessing? Do you search for some int? Do you index the 2D array? Please give an example declaration and access. — user395760
– user395760, Commented Apr 30, 2014 at 4:48
@delnan I specify particular indexes to access the element.I have added the code. — Xara
– Xara, Commented Apr 30, 2014 at 4:51
If your indices are random, then your performance is always going to be poor, unfortunately. — kec
– kec, Commented Apr 30, 2014 at 4:59
As a result, time access to elements greatly varies. Is this assumption verified by a profiling session? Afaik you might have performance issues (and guessing is not the way to find them) but as long as no profile support it, you have none in this area. — Samuel
– Samuel, Commented Apr 30, 2014 at 5:11
As user3521733 stated, if your indices are random, for large size arrays, your performance is going to be poor due to a potentially large number of cache misses — Alex Brooks
– Alex Brooks, Commented Apr 30, 2014 at 5:34

cmaster - reinstate monica · Accepted Answer · 2014-04-30 05:07:04Z

1

There is nothing that can beat an array access in terms of speed, all the higher level containers like unordered_map<> add additional work. When you can use a plain array or vector<>, that is always the fastest you can get.

You need unordered_map<> only if you have a sparsely populated keyspace which prohibits use of a plain array/vector due to space considerations. In that case, the unordered_map<> can translate the keys in the sparse keyspace to a hash index into the tightly populated hash table, which in turn is nothing more or less than an array.

answered Apr 30, 2014 at 5:07

cmaster - reinstate monica

41.1k9 gold badges69 silver badges110 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Rakib · Accepted Answer · 2014-04-30 04:46:15Z

1

For random access, nothing can beat array (dynamic or not). Only this data structure provides O(1) access time on an average because the it uses consecutive memory.

answered Apr 30, 2014 at 4:46

Rakib

7,6137 gold badges34 silver badges46 bronze badges

Collectives™ on Stack Overflow

c++: Random access to Dynamic Array

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related