...
In-memory Data Structure | Pros | Cons | Comments |
---|---|---|---|
doubly linked list | + least amount of processing during fetch (probably not significant relative to overall processing required) | - iteration requires traversing next links | |
convert to array on fetch | + allows for fast access by position to loaded items | ||
convert to hash on fetch | + allows for fast fast access by proxy URI to loaded items | - iteration requires traversing next links | I anticipate the need to have direct access by proxy URI more than positional. |
Limit Testing
Test descriptions:
- array_create - use Array fill method to add array items with values from 0 to max_items
- array_move - use Array insert(to, delete_at(from)) to move an item from the end of the filled array to the beginning (worst case scenario)
- list_create - create a list header data structure and list item data structures with sample real world data using items[i]=item_info to add each item to the items array
- list_move - use Array insert(to,delete_at(from)) to move an item from the end of the filled array to the beginning AND update prev and next links
Environment for testing:
- RAM: 16 G (approximately 4.5 G is allocated to other running programs prior to running tests)
- Processor: 2.3 GHz quad core
Target production system:
- 2-8 G
- Processor: 2.3 GHz dual core
Test code:
...
Use Cases:
Use Case: Fetch the first N items in the list and display to user; Fetch next N and display; Fetch prev N and display; Fetch page X and display
...
example value types | Comments | |||||
---|---|---|---|---|---|---|
key | description of value | doubly linked | doubly linked + order | array | hash | |
first | pointer to first item in list | URI of first proxy | URI of first proxy | URI of first proxy | URI of first proxy | |
last | pointer to last item in list | URI of last proxy | URI of last proxy | URI of last proxy | URI of last proxy | |
count | count of all items in list | X | last.index | last.index | last.index | Count for full list is available for array and hash when order index is stored in triplestore. |
first_loaded | pointer to first item in loaded range of items | item | item | array[0] | URI of first loaded proxy | |
current | pointer to current item | item | item | int cpos | URI of current proxy |
|
last_loaded | pointer to last item in loaded range of items | item | item | array[size of array] | URI of last loaded proxy | |
count_loaded | count of items in currently loaded range | X | =position of last - position of first | size of array | size of hash | |
resume_next_token | pointer to item after last_loaded | URI of proxy | URI of proxy | URI of proxy | URI of proxy | |
resume_prev_token | pointer to item just before first_loaded | URI of proxy | URI of proxy | URI of proxy | URI of proxy | |
loaded_items | pointer to loaded items | use first_loaded | use first_loaded | array | hash |
List Item Info Structure
Each item's info is stored in a hash. It holds information about the individual item. The loaded items as a group are in-memory using one of four possible grouping methods: doubly linked lists, doubly linked lists + order index, array, or hash with proxy URI as the key.
...