Average number of memory accesses?

[Rijad Hadzic]

Homework Statement

The Unsorted-Optimized array structure is used to store a data set.
Calculate its density if:

Each of the client's nodes contains 200 bytes of information and there
are 1,000,000 nodes in the data set.

(This was the previous problem, the problem I'm doing is based on it though, :)

Give the average number of memory accesses of the Unsorted-
Optimized array structure whose data set is described in part (b) of
the previous exercise:
a) Assuming all operations on the data set are equally probable.


answer choices:

375,008
750,002
70,022
50,002

Homework Equations

The Attempt at a Solution

So I know the operations are: insert, fetch, update, and delete.

I'm just lost on where to even start on this problem. Could someone please give me a hint?

 

[.Scott]

I think we need to start by looking at part b of the previous problem.

 

[willem2]

You just need to calculate the average number of an insert, delete, fetch and update, and then compute the average of those 4 numbers.
It shouldn't be too hard if you know how these operations work. I think you use Data Structures and Algorithms using Java by William McAllister. In that case it should be clearly explained.

There is a bit of a problem however. In an Unsorted-Optimized optimized array, the most frequently accessed node references should slowly move to the start of the array, and this should make searching faster, but you can't really tell how much faster without knowing if there are any nodes that are accessed much more than others. If you ignore this, you can get one of the answers in the list, but if you don't I wouldn't know what the average is.

 

[Rijad Hadzic]

I think we need to start by looking at part b of the previous problem.

Part B of the previous problem is in my OP it just doesn't say part B. All of the relevant info is there.

 

[Rijad Hadzic]

You just need to calculate the average number of an insert, delete, fetch and update, and then compute the average of those 4 numbers.
It shouldn't be too hard if you know how these operations work. I think you use Data Structures and Algorithms using Java by William McAllister. In that case it should be clearly explained.

There is a bit of a problem however. In an Unsorted-Optimized optimized array, the most frequently accessed node references should slowly move to the start of the array, and this should make searching faster, but you can't really tell how much faster without knowing if there are any nodes that are accessed much more than others. If you ignore this, you can get one of the answers in the list, but if you don't I wouldn't know what the average is.

Yes I am using Data Structures and Algorithms using Java by William McAllister. I actually do not like this book lol.
I still don't think I'm getting it.

So there are 1,000,000 nodes in the data set.

So there is a 1/4 chance I am doing fetch, 1/4 chance I am doing delete, 1/4 chance I am doing insert, and 1/4 chance I am doing update

for fetch and delete it is using a sequential search, so n/2 and n/2 for delete and fetch

but how do I know what it is for insert and update? it seems to me like those two arent memory accesses?

What I did so far:

n/2 = 500,000, which I divided by 4 since there is a 1/4th chance of it happening for fetch
so 125000
the same will happen to delete so I add 125000+125000 = 250000

I divide this by 4 since there is 4 operations, and get 62500 which is obviously not an answer.

How do I find the number of memory accesses for update and insert? and is my logic correct so far in how I'm calculating it??

 

[willem2]

How do I find the number of memory accesses for update and insert? and is my logic correct so far in how I'm calculating it??

When you search for a node, you have to check half the nodes on average. Does checking a node take a single access?
If you want to update something, you want to change it, so you have to know where it is.
what does insert do? Do you have to do something with the entire array?

 

[Rijad Hadzic]

When you search for a node, you have to check half the nodes on average. Does checking a node take a single access?
If you want to update something, you want to change it, so you have to know where it is.
what does insert do? Do you have to do something with the entire array?

>Does checking a node take a single access?

Hmm this is a weird question. Nodes have multiple fields, but to check a node it only requires one access, correct? Because you are checking the node with a key or numeric mode, is why I think it requires only one access. Am I wrong in this thinking?

 

[willem2]

Hmm this is a weird question. Nodes have multiple fields, but to check a node it only requires one access, correct? Because you are checking the node with a key or numeric mode, is why I think it requires only one access. Am I wrong in this thinking?

There are the nodes themselves, and there is an array of pointers to them. You will have to access both.