|
I'm looking for an implementation or example or even just the logic for what must be an extremely common scenario:
Suppose we have N objects (where N is large). These objects are being accessed over time, but the pattern of access changes. Some are more popular at one time of the day, another i more popular at another time.
I would like to have a list of the top M (M << N) most requested objects for the last T minutes.
Keeping a log of all requests for all objects for the last T minutes is inpractical. Even keeping a list M items long in memory is stretching the friendship. It needs to be fast and efficient.
It doesn't need to be 100% accurate. Just close.
I've got something close based on rolling averages but it's not quite right. I know as soon as the answer is given I'll go 'Why didn't I think of that' but my brain is stuck, possibly because of the Adam Sandler movie I watched last night.
cheers,
Chris Maunder
CodeProject.com : C++ MVP
|
|
|
|
|
Sounds like you need a Priority Queue[^] (Wikipedia Link[^]), as used in many scheduling algorithms (process creation and much more). Each access to an object in the queue should increase the object's priority (could be a property, like a time stamp).
Or did I misunderstand your problem?
regards
modified on Sunday, June 15, 2008 11:50 AM
modified 12-Sep-18 21:01pm.
|
|
|
|
|
I don't have much experience and this is primitive and slow and it’s certainly not what you’re looking for but here are my thoughts anyway. You have N objects and you want to get the top M of N each T period. I think you would associate an integer with each object and keep them in a list or something. Each time an object is accessed you increase the integer. Each T period you sort them and get the top M instead of maintaining them in a sorted structure.
About the rolling averages, this is the first time I hear about this and I don’t understand it. Doesn’t it depend on storing the last average and calculating a new average based on the current one? It’d be great if you explain it a little. Thank you.
Eslam Afifi
|
|
|
|
|
A moving average (or rolling average) is used when you are accumulating data and you take an average of the short-term data rather than averaging all the data you accumulated. It's a way of "smoothing out" data that can fluctuate wildly when all you really want to know is the short-term trend of the data. There are various ways to approximate and weight the average of the data as it comes in rather than actually re-calculating all the data as it changes.
I've done this a lot when writing stock analysis software. Here[^] is a graph of the last six months of eBay stock values (in blue) with a "10-day moving average" (in red). See how it smooths out the data to show the short term trends?
For the original poster's application, I guess you could use a rolling average if you don't want a particular entry shooting right to the top if you suddenly start using a bunch of times but rather have it slowly drift towards the top if you continue to use it over a period of time.
If you don't like the results your rolling average is giving you, maybe you can try one of the variations like a weighted moving average or an exponential moving average. Try Wikipedia[^]for some of the theory/math.
|
|
|
|
|
Thank you for the reply. The chart of eBay is about days (the set of object) and a value for each day (the blue line) and the 10-day MA (the red line); despite I don't know how it's calculated, I can't see the relation between the average and getting the top M number of days N according to the values 
Or do I get it wrong?
Eslam Afifi
|
|
|
|
|
Eslam Afifi wrote: I think you would associate an integer with each object
This requires an entry for every object. What if I have, say, 4 billion objects?
Eslam Afifi wrote: Each T period you sort them and get the top M instead of maintaining them in a sorted structure
Unfortunately this means that your list is, by definition, always out of date (by anything between 0 and T minutes)
cheers,
Chris Maunder
CodeProject.com : C++ MVP
|
|
|
|
|
Chris Maunder wrote: This requires an entry for every object. What if I have, say, 4 billion objects?
I didn't realize that N is that big. But like I said, I don't have much experience, but I think you will keep track of how many times an object has been accessed in the past T period. I don't know about rolling average and it'd be great if you point out the relation between it and what you're trying to accomplish.
Chris Maunder wrote: Unfortunately this means that your list is, by definition, always out of date (by anything between 0 and T minutes)
Then I guess you'll keep them in a SortedList or something.
Eslam Afifi
|
|
|
|
|
Chris - there is a way that you can do this, but it's going to rely on using some technology hacks. Let's assume that each object has a unique identifier. Now, every time the object is accessed, write the id and date/time that the object has been accessed to a message queue. Next, read from the message queue and update a database server based on these values.
Periodically, prune and summarise the values in the database - so, every N minutes, you'll pick the top M objects and write a summary of this information to a table - then delete the old entries. The beauty of this approach is that you can spread the load of this processing.
|
|
|
|
|
I thought about this but I want it in-memory. The load on the database will be way too high.
cheers,
Chris Maunder
CodeProject.com : C++ MVP
|
|
|
|
|
It really depends how many objects you are talking about - if it's the billions mentioned above, then you've no chance. You would have to track every one to see if there are multiple accesses - even if 99.99999999% are only accessed once, you still have to track them.
BTW - the reason for using the messagequeue is that you can control/throttle how much throughput you want in there, so you could load data in bursts.
|
|
|
|
|
Never mind - I need to get my brain back into gear here. Basically, what you have is an optimisation problem - effectively you've got a matrix MxN, where M represents the number of objects and N represents the accesses. What you could do is create a sparse matrix, whereby you would put the value in and the time you last access time for each accessed object. Now, every so often you will want to iterate over this list and remove those objects that haven't been accessed since the last collection. At this point, you have a sparse matrix.
|
|
|
|
|
Bingo 
[Except I just thought of a way, way faster way of doing it using some stats we keep elsewhere. I know - unfair posing a problem and not telling you about the ace up my sleeve  ]
cheers,
Chris Maunder
CodeProject.com : C++ MVP
|
|
|
|
|
Chris Maunder wrote: I know - unfair posing a problem and not telling you about the ace up my sleeve
Never mind - I got to dust off some of my old optimisation skills, back from my life writing realtime optimizers.
|
|
|
|
|
Hi all, I'm new here, so if my question is not ok for this site, just delete it.
I am having a project, and actually I don't know from where to begin with it.
I'm supposed to make an mobile application(for PDA), which consists of several pages. Moving from one page to another should be done with buttons like "forward", or "back", or some kind of a menu button. Along with this mobile application, I should make a database(with merge replication options) in which images and text will be stored. Some of the mobile application's pages will be filled with the text and the images from the database.
The tools for making the mobile application and the database are respectively Visual Studio 2008(C#) and SQL Server 2005.
My knollages about C# and SQL Server are 0.
If someone is willing to tell me just where should I start from, I'll be very gratefull!
P.S. I'm not trying to ask for someone to do my project, I'm just asking for some kind of guidence.
|
|
|
|
|
new_t wrote: My knollages about C# and SQL Server are 0.
I totally respect that you're asking for help and not for someone to do the project. However, it does seem to me that if you know absolute zero about this, it sounds like you're going to need a LOT of guidance for your first ever project to be something of this complexity. Moving between forms is easy, I would imagine that depending on how many forms there are, you'd create controls to represent each form and move through them, or just create forms in the usual way ( that is, you create an instance, initialise it, and tell it to show itself ).
I'm sure there's an embedded SQL Server for PDA. SQL is not that hard, that part should be reasonably easy. The big question, based on your comments, is, do you know anything about programming at all ? i.e. are you coming from C++, or VB, or is this your first ever programming task ?
Christian Graus
Please read this if you don't understand the answer I've given you
"also I don't think "TranslateOneToTwoBillion OneHundredAndFortySevenMillion FourHundredAndEightyThreeThousand SixHundredAndFortySeven()" is a very good choice for a function name" - SpacixOne ( offering help to someone who really needed it ) ( spaces added for the benefit of people running at < 1280x1024 )
|
|
|
|
|
new_t wrote: My knollages about C# and SQL Server are 0. If someone is willing to tell me just where should I start from, I'll be very gratefull!
You don't need guidance, you need to hire a programmer.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001
modified on Sunday, June 15, 2008 9:50 AM
|
|
|
|
|
if you want to learn c# start with the basic. open this site www.homeandlearn.co.uk. maybe this could help you on your problem..
ignore this message if this doesnt help you..
|
|
|
|
|
Without information about your previous experience your question is pointless.
I give you some examples:
1. Hard experience with C++, MFC – you will need from at least 6 months to start
swimming in the deep with C#, not only to “make things barely working”.
2. Serious background with Delphi VCL and/or JAVA plus some NET experience – at least 3 months till you start creating C# reasonable code.
3. Previous experience with Oracle and PLSQL give you chances to get into the swing of the MS SQL Server for a short time.
4. No previous programming experience at all – in this case I have pity on your client. You should try your skills in the brain surgery also.
The narrow specialist in the broad sense of the word is a complete idiot in the narrow sense of the word.
modified on Monday, June 16, 2008 10:28 AM
|
|
|
|
|
hello sir,
i have got a problem that i dont understand how to solve it.
i am using c# form with a textbox . i have set localization =true and
language =urdu. my computer has arabic script installed. now when i run
my form the textbox language still is english.unless i press left+shift+ctrl. is there any way that when i run my app. the text box
will ready to accept unicode character like urdu.
when i set default language to urdu work fine .but i dont want to
change default language because it changes application default language
to urdu.
please help me .this type of project is new to me and i dont now how to
overcome this problem
thanks in advance 
modified on Sunday, June 15, 2008 9:06 AM
|
|
|
|
|
I think there's no other way to do this.. as u want to use english on other programs on your computer and for your this software u want to use urdu..
U have to manually set the default language.
|
|
|
|
|
hi
i need an article about Using MSMQ Triggers (practical). i was searched on internet and found many article about this, but all of those in Windows NT 4.0 or 2000, whereas, i need in windows xp. also i need to an artcile that Using MSMQ in Workgroup computers on the network, can anyBody help me ?
thanks.
|
|
|
|
|
I used to do it but now I completely forgot 
So, how do you include say a StackPanel in your C# Windows Application form??
Many thanks![Rose | [Rose]](https://codeproject.global.ssl.fastly.net/script/Forums/Images/rose.gif)
All generalizations are wrong, including this one!
(\ /)
(O.o)
(><)
|
|
|
|
|
Put it inside a ElementHost control.
|
|
|
|
|
jamie550 wrote: Put it inside a ElementHost control.
What, how where
Please clarify
All generalizations are wrong, including this one!
(\ /)
(O.o)
(><)
|
|
|
|
|
Put a ElementHost on your form. If it is called host, then you would do:
StackPanel s=new StackPanel();
host.Child=s;
s.Children.Add( first control you want);
s.Children.Add( second control);
etc...
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
