|
RepastHPC
2.3.1
|
Given an iterator and a number of elements, creates a data structure that allows efficient access to those elements. More...
#include <Random.h>
Public Member Functions | |
| RandomAccess (I beginning, int size) | |
| Constructs a RandomAccess instance for this iterator. More... | |
| I | get (int index) |
| Gets the element at the specified index. More... | |
Given an iterator and a number of elements, creates a data structure that allows efficient access to those elements.
Is only valid as long as the iterator is valid.
The basic implementation creates a vector of ordered pairs linking an integer and an iterator pointing to an element in the original iteration set. To find the nth element, the algorithm searches backwards through the list of 'landmarks', finds the highest landmark lower than n, chooses the iterator associated with that landmark, and steps forward until n is reached, adding new landmarks if appropriate. So given landmarks:
0 - pointer to element 0 100 - pointer to element 100 200 - pointer to element 200
if the request for element 438 is given, the algorithm will search backward and find landmark 200; it will then step forward, adding landmarks for 300 and 400, until element 438 is reached and returned.
Assuming that requests are evenly distributed, optimum interval for landmarks is the square root of the size of the list, and performance for the algorithm will be in log(size) time.
Note that other implementations are possible- for example, checking if enough memory would allow a completely indexed list. A long-term possibility is allowing the user to specify (for example, specify that the algorithm with lowest memory cost be used even though memory is initially available, perhaps because other routines will be filling that memory while this object is in use).
|
inline |
Constructs a RandomAccess instance for this iterator.
| beginning | |
| size |
|
inline |
Gets the element at the specified index.
| index |
1.8.17