Algorithms

Luc Pattyn wrote:

One interesting implementation has two queues, an "idle" one with empty buckets,
and a "work" one with full buckets. A producer takes an empty bucket from the idle
queue, fills it and puts it in the work queue; a consumer takes a full bucket from
the work queue, executes it, and returns the empty bucket to the idle queue.
If both queues have equal capacity, this results in a symmetric situation where a
producer gets triggered by idle queue no longer empty, and consumer gets triggered
by work queue no longer empty.

Luc Pattyn wrote:

Hope this helps.

Leslie Sanford wrote:

If you look at the members of the IList[^] interface, you get the impression that some of these operations would best be implemented using a linked list and others an array. It's as if the interface wants to have its cake and eat it, too

Leslie Sanford wrote:

I've been trying to think of a way to combine the two data structures to get the advantages of both.

Shog9 wrote:

Hashtable. Of course, it has its own disadvantages.

Leslie Sanford wrote:

In fact, I can't think of how to access the items in the hashtable by index at all.

Shog9 wrote:

A perfect hash would give you O(1) - the hash would be guaranteed to correspond to only one entry in the table. Whether or not a perfect hash is feasible depends a lot on what you're using for keys, as well as how much time is acceptable for calculating the hash.

Value someValue = hashTable[someKey];

Value someValue = hashTable[9];

Shog9 wrote:

But i was thinking more along the lines of chained hash tables[^], which are essentially an array of linked lists - this is the technique used by MFC's various CMap classes. Their performance can be very consistent but iteration tends to be rather poor unless table size and hash functions are chosen carefully.

Leslie Sanford wrote:

But just to be clear, what I meant by not knowing how to access items in a hashtable by index was that I don't know how you could treat a hashtable as an array.

public class HybridList: System.Collections.CollectionBase
{
   Hashtable _indicesTable = new Hashtable();

   public int IndexOf(object key)
   {
      if(_indicesTable.ContainsKey(key))
         return (int)_indicesTable[key];
      else
         return -1;
   }
   public int Add(object key, object val)
   {
      int index = List.Add(new DictionaryEntry(key, val));
      _indicesTable[key] = index;
      return index;
   }
   public void Remove(object key)
   {
      if(_indicesTable.ContainsKey(key))
      {
         List.RemoveAt((int)_indicesTable[key]);
         _indicesTable.Remove(key);
         int i = 0;
         foreach(DictionaryEntry entry in List)
         _indicesTable[entry.Key] = i++;
      }
   }
   public DictionaryEntry this[int index]
   {
      get { return ((DictionaryEntry)List[index]); }
   }
   public object this[object key]
   {
      get
      {
         if(_indicesTable.ContainsKey(key))
            return ((DictionaryEntry)List[(int)_indicesTable[key]]).Value;
         else
            return null;
      }
   }
   public ICollection AllKeys
   {
      get { return _indicesTable.Keys; }
   }
	
   protected override void OnClear()
   {
      base.OnClear();
      _indicesTable.Clear();
   }
}

Ray Kinsella wrote:

I occasionally end up with variations which significantly throw out the average, sometimes unfairly.