Thread: 'lazy / weighted' sort algorithm

  1. #1
    Registered User
    Join Date
    May 2011
    Posts
    3

    'lazy / weighted' sort algorithm

    Not sure if this is appropriate for this mailing list, but I'm sure that there
    may be others with ideas / opinions out there. I have a list of frequency counts
    of categories where a categories count will get updated each time an item in the
    category is manipulated. The list needs is sorted slowly over an arbitrary
    period of time (possibly days) such that items at eventually appear at the head
    of the list will have been accessed the most frequently over the longest period
    of time. Newly created list entries get added to the list in such a way
    (probably towards the middle of the list?) such that existing items are not
    immediately removed from the list.

    I’ve been calling this a lazy sorted or weighted sort. Is there a ‘real’ term
    for this kind of sorting and an established algorithm? Ideas
    are solicited.

    Thanks.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Cache algorithms - Wikipedia, the free encyclopedia
    Perhaps MRU, or LRU (depending on your point of view I suppose)
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    May 2011
    Posts
    3
    yep - it's a L/M RU queue. I'm interested in getting ideas about weighting techniques where items move slowly up/down the queue & if there were any well known techniques / methods for accomplishing that.

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    The "Completely Fair Scheduler" (CFS) in the linux kernel does something like that; it maintains a red-black tree where process are picked from the left, and move rightward based on how much processor time they've used. However, this measurement is weighted by a priority formula including the "nice" value and whether the process is a "real time" process. There are some other factors, and new processes are placed into a queue with a starting value determined by the activity of the queue itself (ie, they don't necessarily go in at the front).

    So not quite the same, but similar.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    May 2011
    Posts
    3
    Thanks for the hint - I didn't consider it to be a form of a scheduler problem but it is in retrospect.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. STL Sort Algorithm
    By f1player in forum C++ Programming
    Replies: 9
    Last Post: 10-10-2008, 01:12 PM
  2. Algorithm and sort
    By grepawksed in forum C++ Programming
    Replies: 9
    Last Post: 03-27-2006, 11:23 AM
  3. Help - Weighted-Average Triangulation Algorithm
    By Geolingo in forum C++ Programming
    Replies: 0
    Last Post: 04-03-2004, 11:42 PM
  4. Please help me with this sort algorithm
    By Qui in forum C++ Programming
    Replies: 3
    Last Post: 03-11-2004, 01:33 PM
  5. Sort Algorithm ??
    By gqchynaboy in forum C++ Programming
    Replies: 1
    Last Post: 05-06-2003, 07:51 PM

Tags for this Thread