Solved

Self Organizing List

Posted on 2001-09-14
9
659 Views
Last Modified: 2012-06-27
I have an assignment where I need to read data from a file, and use it to grow a self-organizing list with 4 of the following methods:
Front: If an item is not already present in the list, put it at the front, else ignore it.
Rear: If an item is not already present in the list, put it at the rear, else ignore it.
Move-to-front: If an item is already present in the list, move it to the front, else add it to the rear.
Transpose: If an item is already present in the list, interchange it with the item immediately before it, else add it to the rear..
Count: If an item is already present in the list, order list items by the frequency with which they have occurred, most frequent first, else add it to the rear.
Order: Maintain the list in ascending (numeric or alphabetical) order.

What I did was derive a class from std::list and then I implemented the first 4 of these insertion methods.  What I don't understand is the following:  Everytime I call Front, Rear, Move-to-front, and then Transpose to insert a new item, Rear will never have any effect on the list because Front will have already placed the item at the front of the list.  Or if I implemented all 6 methods, the last method called would be order which would cancel the effects of the other 5 methods.  It seems like a self organizing list should only use 1 of these methods, or maybe a combination of 2 or 3 of them.  Either that or I am misunderstanding everything.
0
Comment
Question by:nidan
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
9 Comments
 
LVL 16

Accepted Solution

by:
imladris earned 35 total points
ID: 6483666
Yes, I agree. The first line reads "WITH 4 of the following methods". I would assume that means they have to be available. Which is used, would depend on some selection by the user of the list, perhaps in the constructor.
0
 
LVL 1

Author Comment

by:nidan
ID: 6485106
Here are the actual instructions which I don't understand:

Using the STL for list, add any four of the above six insertion methods, each corresponding to one of the methods above.  
Build a self-organizing list with the first 1000 numbers in Numbers and then insert TestNumbers into it.  Repeat for 2000, 4000, 8000, and 16000 numbers. ( Numbers and TestNumbers are data files which I have already ).

Then I have to explain what the theoretical complexity of each of the implemented methods is and why, and what the empirical complexity of each method is.

I don't need any code for this.  I want to know if you think I should create all 5 lists with a combination of the 4 methods:

while ( cin >> number )
{
    mylist.front(number);
    mylist.rear(number);
    mylist.movetofront(number);
    mylist.transpose(number);
}

or if I should use the standard list class to create the first list, and then use different methods to create the other 4 and then compare results.  Or should I create the 5 lists using the same method?  
0
 
LVL 49

Expert Comment

by:DanRollins
ID: 6485191
Stand back from the problem and it make a little more sense...

Some random data comes in to your program and you put it into a list.  Later you begin to access that data, and it turns out that some of the random elements are accessed more often than others.  So it would be convenient/expedient if those often-used data items were closer to the front of the list.

Or in another light, as more an more copies of a particular datum come in, you don't want to insert duplicates, you just want to increase a counter.  Then you want to reorganize so that the items with the highest count appear earlier in the list.

So really, you just need one insertion fn -- it places the item at the end of list or, if it is already in the list, it just bumps the count for that item and optionally moves it closer to the front of the list.

Because this is classwork, your prof wants you to write several insert functions and discuss them.  In real life, you would only use one at a time.

Front: Badly named -- call this fn UpdateOnly.  You would use this for a pre-built list.  Not an insert fn at all.

Rear: Call this fn AddNewOrUpdate.  It can be called for random items while you are building the list.

Move-to-front: Irrelevant excercise -- You would use this if you had a gut-feeling that the new item would eventually have a high count.  I'd call it ForcedInsertToFront.

Transpose: Irrelevant excercise -- I guess it could be used as a helper fn for the case when you happen to know that adding this datum would normally force a reorganization.  And to avoid that, you postpone the full reorg by moving it forward one notch immediately.  It will be closer to where you eventually want it to be.  I'd call it UpdateAndBumpForward

Count: Who thinks of these names?  This should be called AddNewOrUpdateAndForceReorder.  Like AddNewOrUpdate, this would be called while building the list.  However, it forces a reorganization with each new irem.  By using this, you ensure that the list is always in order, but performance would suck.  I'd use this fn every 10 or 100 inserts (or never; just call Order periodically).

Order: Not an insert operator - a helper fn.  It is called by AddNewOrUpdateAndForceReorder.

I hope that helps.

-- Dan
0
[Live Webinar] The Cloud Skills Gap

As Cloud technologies come of age, business leaders grapple with the impact it has on their team's skills and the gap associated with the use of a cloud platform.

Join experts from 451 Research and Concerto Cloud Services on July 27th where we will examine fact and fiction.

 
LVL 1

Author Comment

by:nidan
ID: 6485927
I agree with what you're saying, but my dilemna is the instructions which say using the STL for list, add any four of the above 6 insertion methods, and build a self organizing list...  I have implemented 4 of the insertion methods.  How do I use these methods to create the lists?  Do I use all 4 of them together to add an item?  
insert(item)
{
mylist.front(item);
mylist.rear(item);
mylist.movetofront(item);
mylist.transpose(item);
}
Or do I use a different insertion method for every different list? Or should I use the same insertion method for every list?  The experiment is to create several kinds of self - organizing lists and compare their performance to the original list.  I am unsure of what the original list is.

0
 
LVL 30

Expert Comment

by:Axter
ID: 6495629
>>How do I use these methods to create the lists?  Do I
>>use all 4 of them together to add an item?  

No, you would not use all 4 together.
Each insertion method has it's own function, and depending on the calling functions's requirements, will depend on which function is called.

For example, if you had a function that took 10 names from a user's input, and the function had to put the names in a list, and then sort the list, you could make the function put all names that begin with letters A-M use the mylist.front() function, and all names that begin with letters N-Z use the mylist.rear() function.

This is not the greatest example in the world, but it might point you in the right direction.
0
 
LVL 2

Expert Comment

by:triso
ID: 6502623
Hi,

I'm probably too late to help you with your work, but I think this will shed light on your problem.  You should create six list classes, each a subclass of std::list, that have different implementations of insert ().

Then you create six empty lists and put the same data into each list. You could do this with a method called insert_all ():

void insert_all (integer item)
{
   bobby.insert (item);
   peter.insert (item)
   greg.insert (item);
   cindy.insert (item);
   jan.insert (item);
   marsha.insert (item);
}




0
 
LVL 11

Expert Comment

by:griessh
ID: 6868104
I think you forgot this question. I will ask Community Support to close it unless you finalize it within 7 days. Unless there is objection or further activity,  I will suggest to accept "imladris, DanRollins. Axter" comment(s) as an answer.

If you think your question was not answered at all, you can post a request in Community support (please include this link) to refund your points.
The link to the Community Support area is: http://www.experts-exchange.com/commspt

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!
======
Werner
0
 
LVL 5

Expert Comment

by:Netminder
ID: 6891068
Force-accepted by
Netminder
CS Moderator

DanRollins: points for you at http://experts-exchange.com/jsp/qShow.jsp?ta=cplusprog&qid=20280730
Axter: points for you at http://experts-exchange.com/jsp/qShow.jsp?ta=cplusprog&qid=20280731
0
 
LVL 6

Expert Comment

by:Mindphaser
ID: 6996994
Force accepted

** Mindphaser - Community Support Moderator **
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

623 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question