Solved

Self Organizing List

Posted on 2001-09-14
9
576 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
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
 
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

867 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

20 Experts available now in Live!

Get 1:1 Help Now