1

I have 2D static array with a size of 256 X 256.

Array[256][256]

Each Array element is storing two integer values.

Now, the issue is that the program in which I am using this array has to be time efficient. But I have noticed that those elements like Array[1][40], Array[34][67] and Array[80][80], they take less time as compared to Array[150][256], Array[140][192]. Thus, the index values greater than 100 takes more time as compared to other.

Is there any other data structure which can help me to achieve constant time access to the value but also takes less time to access

Code:

for( counter1=0; counter1< sizeof(chunk1); ++counter1)
{

    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
}

The values of chunk1[counter1] and chunk1[counter1+1] ranges from 0-255. Where chunk1[counter1] and chunk1[counter1+1] is array of random unsigned characters.

Marius Bancila
  • 16,053
  • 9
  • 49
  • 91
Xara
  • 8,748
  • 16
  • 52
  • 82
  • 3
    How do you figure indices greater than 100 take more time to access? – Ben Apr 28 '14 at 08:24
  • @Ben I used chrono time library to measure time. In a for loop, in which I am accessing these elements, I put the timer in the start and end of loop to measure time. – Xara Apr 28 '14 at 08:26
  • An array should be perfect for this. The only effects you could be seeing are due to cache behaviour, this is impossible to determine without seeing your code (it's access pattern dependant). Or you could have a bug in your timing tests. What kind of times are we talking, mS, uS? – Joe Apr 28 '14 at 08:26
  • 1
    Do repeated access to the same element with an index higher than 100 show the same number? If not (successive accesses are faster), then it could be that your data is not cached. – tillaert Apr 28 '14 at 08:26
  • @Joe I am using chrono high resolution timer . Using uS – Xara Apr 28 '14 at 08:27
  • Without code it's hard to tell for sure what's going on. If you're not able to post some, try looking at this previous question on SO - http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array or http://stackoverflow.com/questions/13612046/cache-miss-rate-of-array – Joe Apr 28 '14 at 08:28
  • What about using std::array if you're coding in C++ ? http://www.cplusplus.com/reference/array/array/ – Jaffa Apr 28 '14 at 08:33
  • As suggested in previous comments, cache-ing could be a considerable consideration. In C/C++ (at least with older compilers), it was often better to try and walk through memory linearly. Try to write code such that the last index varies fastest. – ilent2 Apr 28 '14 at 08:38
  • I don't know if this is a typo. If you declared your array as Array[256][256], you shouldn't be accessing Array[150][256]. The index range is 0..255. – cup Apr 28 '14 at 08:52
  • I would like to know what you are trying to achieve with a 2d array. If it is doable or if it's mappable to a 1d array I would suggest you go for it. Since, for this 2d array u are accessing the row first then the column e.g, Array[1][2], hence it is likely to take more time than a O(1) lookup (for a fixed length 1d array). Try mapping it to a 1d array and compare your lookup/access time. – Syed Mauze Rehan Apr 28 '14 at 08:58
  • Moreover, you can go for a Hashmap (for each value in your 2d array>>> hash it), use this hash to access the value u want >>> constant access time. – Syed Mauze Rehan Apr 28 '14 at 09:05
  • @Joe I have added a small portion of code. Please suggest something to improve speed. – Xara Apr 28 '14 at 14:57
  • @ilent2 Can you please explain it in detail esp this line "Try to write code such that the last index varies fastest." – Xara Apr 28 '14 at 17:22
  • @Zara This Wikipedia page might be useful (http://en.wikipedia.org/wiki/Row-major_order), in C its the last index that should be in the inner most loop, if you were to switch to something like FORTRAN you would want the first index to be varied in the inner most loop. If you need random array (memory) access though, then this isn't much help. – ilent2 Apr 29 '14 at 01:53
  • @ilent2 I have to do random access to the dynamic array. Is there any way to reduce time of access in random accesses? – Xara Apr 29 '14 at 06:42

0 Answers0