BinarySearch des dichtesten Elementes in C#

BinarySearch des dichtesten Elementes in C#
Frank Dzaebel, erstellt am: 21.3.2006, zuletzt geändert: 10.4.2006
Kategorie: Implementation, .NET-Version: 2.0

Eine .NET 2.0 Dictionary.ContainsKey-Methode kommt etwa einer O(1)-Komplexität nahe und ist zum Suchen also eine der performantesten Möglichkeiten. In diesem Fall wird ein Element gesucht, das am dichtesten an dem zu suchenden Element liegt. Hier ist eine SortedList eine Möglichkeit, bei der man durch die Sortierung eine Binärsuche [SortedList.ContainsKey] ausführen kann und somit eine Performance von etwa O(log n) erreicht.

Zu überdenken wäre auch die Möglichkeit eines SortedDictionary's, welches eine Abruf-Komplexität von O(log n) hat. Unsortierte Daten werden vom SortedDictionary schneller hinzugefügt und entfernt: O(log n) im Gegensatz zu O(n) bei der SortedList. Wenn die Liste in einem Vorgang mit sortierten Daten gefüllt wird, ist die SortedList schneller als das SortedDictionary.

In folgendem Beispiel wird diese Binärsuche aber manuell codiert, um das dichteste Element zu bekommen. Eine Alternative wäre auch ein zweiter Hashtable, aber das wird nicht berücksichtigt.

using System;
using System.Collections.Generic;
using System.Windows.Forms;

namespace BinarySearchTest
{
  public partial class Form1 : Form
  {
    public Form1()
    {
      InitializeComponent();
    }
    Properties.Settings Props = Properties.Settings.Default;

    private void Form1_Load(object sender,EventArgs e)
    {
      Personen personen = new Personen();
      personen.Add(36,new Person("Gustav","Gans"));
      personen.Add(40,new Person("Dagobert","Duck"));
      personen.Add(45,new Person("Tick","Duck"));
      personen.Add(35,new Person("Donald","Duck"));
      int d = personen.NearestKey(42);
      MessageBox.Show(d.ToString() + personen[d].ToString()); //Ergebnis: 40[Name:Dagobert Duck]
    }
  }

  class Person
  {
    public Person(string vorname,string nachname)
    {
      Vorname = vorname; Nachname = nachname;
    }
    public string Vorname;
    public string Nachname;
    public override string ToString()
    {
      return "[Name:" + Vorname + " " + Nachname + "]";
    }
  }

  class Personen : SortedList<int,Person>
  {
    /// <summary>Sucht (binär) in der Liste und gibt den Person-Key zurück, 
    /// dessen Key am dichtesten an 'key' liegt.</summary>
    /// <returns>-1, bei leerer Liste, sonst den (dichtesten) key</returns>
    public int NearestKey(int key)
    {
      int links = 0,mitte,rechts = Keys.Count - 1;
      if (this == null || Keys.Count == 0)
        return -1;

      do
      {
        mitte = (links + rechts) / 2;
        if (Keys[mitte] == key) return Keys[mitte];
        else
          if (Keys[mitte] > key)
          {
            rechts = mitte - 1;
            if (links > rechts)  return nearest(key,rechts);
          }
          else
          {
            links = mitte + 1;
            if (links > rechts)  return nearest(key,links);
          }
      } while (true);
    }
    
    private int nearest(int key,int idx)
    {
      if (idx < 0) idx = 0;
      if (idx >= Keys.Count - 1) idx = Keys.Count - 1; 
      int diff2,diff1 = key - Keys[idx];
      if (diff1 > 0)
      {
        if (idx == Keys.Count - 1) return Keys[idx];
        diff2 = Math.Abs(key - Keys[idx + 1]);
      }
      else
      {
        if (idx == 0) return Keys[idx];
        diff2 = Math.Abs(key - Keys[idx - 1]);
      }
      return Math.Abs(diff1) <= diff2 ? Keys[idx] : Keys[idx + 1];
    }
  }
}