Feedback

C# - Filtern mit dem Blacklist - Whitelist Verfahren

Veröffentlicht von am 6/25/2007
(3 Bewertungen)
Mit dieser Klasse können Listen mit Hilfe der Black and Whitelist gefiltert werden.

Dank IList können z.B. List<String> Objekte oder Arrays übergeben werden.
Die Listenelemente müssen sich als Key für ein Dictionary eignen, das ist bei String immer der Fall.

Danke an herbivore für das das Feintuning.
using System.Collections.Generic;

namespace Filter
{
    internal class BlackWhite<T>
    {
        private Dictionary<T, bool> black = new Dictionary<T, bool>();
        private Dictionary<T, bool> white = new Dictionary<T, bool>();

        public BlackWhite(IList<T> black, IList<T> white)
        {
            foreach (T t in black) {
               this.black [t] = true;
            }
            foreach (T t in white) {
               this.white [t] = true;
            }
        }

        public List<T> GetGoodList(IList<T> inputList)
        {
            List<T> goodList = new List<T>();

            foreach (T t in inputList)
            {
                if (white.ContainsKey(t) || !black.ContainsKey(t)) {
                    goodList.Add(t);
                }
            }
            return goodList;
        }
    }
}

4 Kommentare zum Snippet

Jan Welker schrieb am 1/17/2010:
Der Code könte dadurch vereinfacht werden, dass auf die Umwandlung in ein Dictionary<T, bool> verzichtet wird, weil IList<T> bereits über eine Contains-Methode verfügt. Damit können black und white als IList<T> deklariert werden und können im Konstruktor direkt zugewiesen werden. Damit erspart man sich die unbenötigten bool-Werte des Dictionarys. Dadurch entfallen weiter die Foreach-Schleifen im Konstruktor, die zudem fehleranfällig sind, weil in den übergebenen IList-Colletions identische Einträge vorhanden sein können, die Key-Werte in einem Dictionary aber eindeutig sein müssen. In GetGoodList ist dann beim Schleifendurchlauf lediglich der Methodenaufruf "white.ContainsKey(t)" durch "white.Contains(t)" zu ersetzen.
Die Funktionalität lässt sich auch etwas anders implementieren (Beispiel in VB:

Friend Class BlackWhiteEx(Of T)
Private _black As New HashSet(Of T)
Private _white As New HashSet(Of T)

Public Sub New(black As IList(Of T), white As IList(Of T))
Me._black.UnionWith(black.AsEnumerable)
Me._white.UnionWith(white.AsEnumerable)
End Sub

Public Function GetGoodList(inputList As IList(Of T)) As List(Of T)
Dim goodList As New List(Of T)
Dim htResult As New HashSet(Of T), htWhite As New HashSet(of T)
htWhite.UnionWith(_white.AsEnumerable)
htResult.UnionWith(inputList.AsEnumerable)
htWhite.IntersectWith(inputList.AsEnumerable)
htResult.ExceptWith(_black.AsEnumerable)
htResult.UnionWith(htWhite.AsEnumerable)
goodList = htResult.ToList
Return goodList
End Function
End Class

Der Unterschied: In der zurückgegebenen "GoodList" sind alle mehrfach enthaltenen Einträge der Ausgangsliste bis auf einen entfernt, d. h. die Ergebnisliste enthält keine doppelten oder mehrfachen Werte mehr.
FormFollowsFunction schrieb am 9/16/2019:
Ich verwende für Blacklist/Whitelist Stack() (https://docs.microsoft.com/en-us/dotnet/api/system.collections.stack?view=netframework-4.8), die Methode ist rasend schnell, und stellt die nötigen Eigenschaften Contains und Equals bereit, mehr braucht es nicht.
KISS (https://de.wikipedia.org/wiki/KISS-Prinzip).
Koopakiller schrieb am 9/17/2019:
Es ist sicher von der persönliches Vorliebe abhängig, aber ich würde hierfür kein Stack benutzen. Stack hat klassischerweiße keine Contains-Methode und ein ganz bestimmtes Verhalten (eben Push und Pop). Siehe https://de.wikipedia.org/wiki/Stapelspeicher
Dass Stack<T> in .NET auch Contains implementiert ist etwas untypisch, auch wenn es dadurch erst hierfür verwendbar wird.

Was die Laufzeit von Contains angeht, so ist Stack<T> nicht besser als List<T>, siehe den Code:
https://referencesource.microsoft.com/#System/compmod/system/collections/generic/stack.cs,c5371bef044c6ab6,references
und
https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,cf7f4095e4de7646
Beide benutzen den selben Algorithmus der in O(n) liegt.

Wenn man etwas schnelleres haben will, so sind HashMaps ein erster Ansatz. Oder eben alles weitere was auch Datenbanken nutzen. Letzten Endes ist das aber auch stark von den zu suchenden Daten abhängig.
Wenn man beispielsweise prüfen will ob eine E-Mail-Adresse geblockt ist, dann sucht man auch nicht nach allen Lokalteilen sofern die ganze Domain bereits geblockt wurde
FormFollowsFunction schrieb am 9/25/2019:
(editiert)
"HashMaps" war mir bis jetzt völlig unbekannt, danke für die Info.
edit:
Ich denke, meine erinnerung hat mir einen Streich gespielt und ich meinte von vorherein HashMaps.
Habe gestern einen Benchmark-Test gemacht und rasend schnell trifft nur auf HashMaps zu, Stack(Of T) ist etwas schneller als List(Of T).
Bei 10000000 Einträgen (Random().Next.ToString) ergibt sich in etwa so ein Bild:
List : 400000 Ticks
Stack : 350000 Ticks
HashMap : < 10 (!) Ticks
 

Logge dich ein, um hier zu kommentieren!