• Support PF! Buy your school textbooks, materials and every day products Here!

Average number of memory accesses?

  • #1
321
20

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?
 

Answers and Replies

  • #2
.Scott
Homework Helper
2,464
861
I think we need to start by looking at part b of the previous problem.
 
  • #3
1,943
241
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.
 
  • #4
321
20
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.
 
  • #5
321
20
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 im doing fetch, 1/4 chance im doing delete, 1/4 chance im doing insert, and 1/4 chance im 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??
 
  • #6
1,943
241
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?
 
Last edited:
  • #7
321
20
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?
 
  • #8
1,943
241
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.
 

Related Threads on Average number of memory accesses?

Replies
2
Views
1K
Replies
1
Views
2K
Replies
2
Views
1K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
7
Views
731
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
7
Views
4K
  • Last Post
Replies
0
Views
5K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
2
Views
982
Top