Solved

Self Organizing List

Posted on 2001-09-14
9
563 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
9 Comments
 
LVL 16

Accepted Solution

by:
imladris earned 35 total points
Comment Utility
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
Comment Utility
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
Comment Utility
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
 
LVL 1

Author Comment

by:nidan
Comment Utility
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
Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

 
LVL 30

Expert Comment

by:Axter
Comment Utility
>>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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
Force accepted

** Mindphaser - Community Support Moderator **
0

Featured Post

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

743 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now