Welche Art von Algorithmus erfordert einen Satz?

Bei meinen ersten Programmierkursen wurde mir gesagt, ich solle ein Set verwenden, wenn ich Dinge wie das Entfernen von Duplikaten von etwas tun muss. Beispiel: Um alle Duplikate aus einem Vektor zu entfernen, durchlaufen Sie diesen Vektor und fügen Sie jedes Element einer Menge hinzu. Dann bleiben eindeutige Vorkommen übrig. Ich könnte dies jedoch auch tun, indem ich jedes Element einem anderen Vektor hinzufüge und überprüfe, ob das Element bereits vorhanden ist. Ich gehe davon aus, dass es je nach verwendeter Sprache zu Leistungsunterschieden kommen kann. Aber gibt es einen Grund, ein anderes Set zu verwenden?

Grundsätzlich gilt: Welche Arten von Algorithmen erfordern einen Satz und sollten nicht mit einem anderen Containertyp durchgeführt werden?

Sie fragen speziell nach Mengen, aber ich denke, Ihre Frage bezieht sich auf ein größeres Konzept: Abstraktion. Sie haben absolut Recht, dass Sie dazu einen Vektor verwenden können (wenn Sie Java verwenden, verwenden Sie stattdessen ArrayList). Aber warum sollten Sie dort aufhören? Wofür brauchst du den Vektor? Sie können dies alles mit Arrays tun.

Wann immer Sie ein Element zum Array hinzufügen müssen, können Sie einfach jedes Element durchlaufen und wenn es nicht vorhanden ist, fügen Sie es am Ende hinzu. Tatsächlich müssen Sie jedoch zuerst prüfen, ob im Array Platz ist. Wenn dies nicht der Fall ist, müssen Sie ein neues Array erstellen, das größer ist, und alle vorhandenen Elemente aus dem alten Array in das neue Array kopieren. Anschließend können Sie das neue Element hinzufügen. Natürlich müssen Sie auch jeden Verweis auf das alte Array aktualisieren, um auf das neue zu verweisen. Hast du das alles erledigt? Groß! Was wollten wir nun wieder erreichen?

Oder Sie können stattdessen eine Set-Instanz verwenden und einfach aufrufen add(). Der Grund, warum Mengen existieren, ist, dass sie eine Abstraktion sind, die für viele häufig auftretende Probleme nützlich ist. Angenommen, Sie möchten Elemente verfolgen und reagieren, wenn ein neues hinzugefügt wird. Sie rufen add()einen Satz auf und er gibt zurück trueoder falsebasiert darauf, ob der Satz geändert wurde. Sie könnten das alles von Hand mit Primitiven schreiben, aber warum?

Es kann tatsächlich vorkommen, dass Sie eine Liste haben und Duplikate entfernen möchten. Der von Ihnen vorgeschlagene Algorithmus ist im Grunde der langsamste Weg, dies zu tun. Es gibt einige gängige schnellere Möglichkeiten: Bucketing oder Sortieren. Sie können sie auch einem Satz hinzufügen, der einen dieser Algorithmen implementiert.

Zu Beginn Ihrer Karriere / Ausbildung liegt der Schwerpunkt darauf, diese Algorithmen zu entwickeln und zu verstehen, und es ist wichtig, dies zu tun. Aber das ist nicht das, was professionelle Entwickler normalerweise tun. Sie verwenden diese Ansätze, um viel interessantere Dinge zu bauen, und die Verwendung vorgefertigter und zuverlässiger Implementierungen spart Schiffsladungen Zeit.

Ich gehe davon aus, dass es je nach verwendeter Sprache zu Leistungsunterschieden kommen kann. Aber gibt es einen Grund, ein anderes Set zu verwenden?

Oh ja, (aber es ist keine Leistung.)

Verwenden Sie ein Set, wenn Sie eines verwenden können, da Sie zusätzlichen Code schreiben müssen, wenn Sie es nicht verwenden. Die Verwendung eines Sets erleichtert das Lesen Ihrer Arbeit. All diese Tests auf Eindeutigkeitslogik sind an einem anderen Ort versteckt, an dem Sie nicht darüber nachdenken müssen. Es befindet sich an einem Ort, der bereits getestet wurde, und Sie können darauf vertrauen, dass es funktioniert.

Schreiben Sie dazu Ihren eigenen Code und Sie müssen sich darum kümmern. Bleh. Wer will das schon?

Grundsätzlich gilt: Welche Arten von Algorithmen erfordern einen Satz und sollten nicht mit einem anderen Containertyp durchgeführt werden?

Es gibt keinen Algorithmus, der "mit keinem anderen Containertyp durchgeführt werden sollte". Es gibt einfach Algorithmen, die Mengen nutzen können. Es ist schön, wenn Sie keinen zusätzlichen Code schreiben müssen.

Jetzt ist diesbezüglich nichts Besonderes an set. Sie sollten immer die Kollektion verwenden, die Ihren Anforderungen am besten entspricht. In Java habe ich festgestellt, dass dieses Bild hilfreich ist, um diese Entscheidung zu treffen. Sie werden feststellen, dass es drei verschiedene Arten von Sets gibt.

Und wie @germi zu Recht betont, wird Ihr Code für andere leichter lesbar, wenn Sie die richtige Sammlung für den Job verwenden.

Ich könnte dies jedoch auch tun, indem ich jedes Element einem anderen Vektor hinzufüge und überprüfe, ob das Element bereits vorhanden ist.

Wenn Sie dies tun, implementieren Sie die Semantik eines Satzes über der Vektordatenstruktur. Sie schreiben zusätzlichen Code (der Fehler enthalten kann), und das Ergebnis ist extrem langsam, wenn Sie viele Einträge haben.

Warum sollten Sie dies über die Verwendung einer vorhandenen, getesteten, effizienten Set-Implementierung tun?

Software-Entitäten, die reale Entitäten darstellen, sind häufig logische Mengen. Stellen Sie sich zum Beispiel ein Auto vor. Autos haben eindeutige Kennungen und eine Gruppe von Autos bildet einen Satz. Der festgelegte Begriff dient als Einschränkung für die Sammlung von Fahrzeugen, die ein Programm möglicherweise kennt, und die Einschränkung von Datenwerten ist sehr wertvoll.

Außerdem haben Mengen eine sehr gut definierte Algebra. Wenn Sie einen Satz Autos von George und einen Satz von Alice haben, dann ist die Gewerkschaft eindeutig der Satz von George und Alice, auch wenn George und Alice beide dasselbe Auto besitzen. Die Algorithmen, die Mengen verwenden sollten, sind solche, bei denen die Logik der beteiligten Entitäten Mengenmerkmale aufweist. Das stellt sich als ziemlich häufig heraus.

Eine andere Frage ist, wie Mengen implementiert werden und wie die Eindeutigkeitsbeschränkung garantiert wird. Man hofft, eine geeignete Implementierung für die Mengenlogik finden zu können, die Duplikate eliminiert, da Mengen für die Logik so grundlegend sind, aber selbst wenn Sie die Implementierung selbst durchführen, ist die Eindeutigkeitsgarantie für das Einfügen eines Elements in eine Menge und wesentlich Sie sollten nicht "prüfen, ob das Element bereits vorhanden ist".

Abgesehen von den Leistungsmerkmalen (die sehr wichtig sind und nicht so einfach zu verwerfen sind), sind Sets als abstrakte Sammlung sehr wichtig.

Könnten Sie das Set-Verhalten (Ignorieren der Leistung) mit einem Array emulieren? Ja absolut! Bei jedem Einfügen können Sie überprüfen, ob sich das Element bereits im Array befindet, und das Element dann nur hinzufügen, wenn es noch nicht gefunden wurde. Aber das müssen Sie sich bewusst bewusst machen und sich jedes Mal daran erinnern, wenn Sie es in Ihr Array-Psuedo-Set einfügen. Oh, was ist das? Sie haben einmal direkt eingefügt, ohne vorher nach Duplikaten zu suchen. Welp, Ihr Array hat seine Invariante gebrochen (dass alle Elemente eindeutig sind und dass keine Duplikate vorhanden sind).

Was würden Sie tun, um das zu umgehen? Sie würden einen neuen Datentyp erstellen, ihn aufrufen (z. B. PsuedoSet), der ein internes Array umschließt und eine insertOperation öffentlich verfügbar macht , wodurch die Eindeutigkeit von Elementen erzwungen wird. Da auf das umschlossene Array nur über diese öffentliche insertAPI zugegriffen werden kann, stellen Sie sicher, dass keine Duplikate entstehen können. Fügen Sie jetzt etwas Hashing hinzu, um die Leistung der containsÜberprüfungen zu verbessern , und früher oder später werden Sie feststellen, dass Sie eine vollständige Implementierung implementiert haben Set.

Ich würde auch mit einer Erklärung antworten und die Frage beantworten:

Bei meinen ersten Programmierkursen wurde mir gesagt, ich solle ein Array verwenden, wenn ich beispielsweise mehrere geordnete Elemente von etwas speichern muss. ZB: um eine Sammlung von Namen von Mitarbeitern zu speichern. Ich könnte dies jedoch auch tun, indem ich Rohspeicher zuordne und den Wert der Speicheradresse einstelle, der durch den Startzeiger + einen gewissen Offset angegeben wird.

Könnten Sie einen Rohzeiger und feste Offsets verwenden, um ein Array nachzuahmen? Ja absolut! Bei jedem Einfügen können Sie überprüfen, ob der Offset nicht vom Ende des zugewiesenen Speichers abweicht, mit dem Sie arbeiten. Aber das müssen Sie sich bewusst bewusst machen und sich jedes Mal daran erinnern, wenn Sie es in Ihr Pseudo-Array einfügen. Oh was ist das, du hast einmal direkt eingefügt, ohne vorher den Offset zu überprüfen? Welp, es gibt einen Segmentierungsfehler mit Ihrem Namen!

Was würden Sie tun, um das zu umgehen? Sie würden einen neuen Datentyp erstellen, ihn aufrufen (z. B. PsuedoArray), der einen Zeiger und eine Größe umschließt und eine insertOperation öffentlich verfügbar macht, wodurch erzwungen wird, dass der Offset die Größe nicht überschreitet. Da auf die umschlossenen Daten nur über diese öffentliche insertAPI zugegriffen werden kann, stellen Sie sicher, dass keine Pufferüberläufe auftreten können. Fügen Sie nun einige weitere praktische Funktionen hinzu (Größenänderung des Arrays, Löschen von Elementen usw.), und früher oder später werden Sie feststellen, dass Sie eine vollständige Implementierung implementiert haben Array.

Es gibt alle Arten von satzbasierten Algorithmen, insbesondere dort, wo Sie Schnittpunkte und Vereinigungen von Mengen ausführen müssen und das Ergebnis eine Menge sein muss.

Set-basierte Algorithmen werden häufig in verschiedenen Pfadfindungsalgorithmen usw. verwendet.

Eine Einführung in die Mengenlehre finden Sie unter folgendem Link: http://people.umass.edu/partee/NZ_2006/Set%20Theory%20Basics.pdf

Wenn Sie eine Set-Semantik benötigen, verwenden Sie ein Set. Es wird Fehler aufgrund falscher Duplikate vermeiden, weil Sie irgendwann vergessen haben, den Vektor / die Liste zu beschneiden, und es wird schneller sein, als Sie es tun können, indem Sie Ihren Vektor / Ihre Liste ständig beschneiden.

Ich finde Standard-Set-Container selbst meistens nutzlos und bevorzuge es, nur Arrays zu verwenden, aber ich mache es auf eine andere Art und Weise.

Um festgelegte Schnittpunkte zu berechnen, durchlaufe ich das erste Array und markiere Elemente mit einem einzelnen Bit. Dann iteriere ich durch das zweite Array und suche nach markierten Elementen. Voila, setzen Sie den Schnittpunkt in linearer Zeit mit weitaus weniger Arbeit und Speicher als eine Hash-Tabelle, z. B. sind Vereinigungen und Unterschiede mit dieser Methode gleichermaßen einfach anzuwenden. Es hilft, dass sich meine Codebasis eher um das Indizieren von Elementen als um das Duplizieren dreht (ich dupliziere Indizes zu Elementen, nicht zu den Daten der Elemente selbst) und muss selten sortiert werden, aber ich habe seit Jahren keine festgelegte Datenstruktur mehr verwendet ein Ergebnis.

Ich habe auch einen bösen C-Code, den ich benutze, selbst wenn die Elemente für solche Zwecke kein Datenfeld bieten. Dabei wird der Speicher der Elemente selbst verwendet, indem das höchstwertige Bit (das ich nie verwende) zum Markieren von durchquerten Elementen gesetzt wird. Das ist ziemlich grob, tun Sie das nicht, es sei denn, Sie arbeiten wirklich in der Nähe der Baugruppe, sondern wollten nur erwähnen, wie es auch in Fällen anwendbar sein kann, in denen Elemente kein für die Durchquerung spezifisches Feld bereitstellen, wenn Sie dies garantieren können Bestimmte Bits werden niemals verwendet. Auf meinem dinky i7 kann es in weniger als einer Sekunde einen festgelegten Schnittpunkt zwischen 200 Millionen Elementen (etwa 2,4 GB Daten) berechnen. Versuchen Sie, einen festgelegten Schnittpunkt zwischen zwei std::setInstanzen zu erstellen, die jeweils hundert Millionen Elemente gleichzeitig enthalten. kommt nicht einmal nahe.

Davon abgesehen ...

Ich könnte dies jedoch auch tun, indem ich jedes Element einem anderen Vektor hinzufüge und überprüfe, ob das Element bereits vorhanden ist.

Diese Überprüfung, ob ein Element bereits im neuen Vektor vorhanden ist, ist im Allgemeinen eine lineare Zeitoperation, die den gesetzten Schnittpunkt selbst zu einer quadratischen Operation macht (explosiver Arbeitsaufwand, je größer die Eingabegröße ist). Ich empfehle die oben beschriebene Technik, wenn Sie nur einfache alte Vektoren oder Arrays verwenden möchten und dies auf eine Weise tun möchten, die sich wunderbar skalieren lässt.

Grundsätzlich gilt: Welche Arten von Algorithmen erfordern einen Satz und sollten nicht mit einem anderen Containertyp durchgeführt werden?

Keine, wenn Sie meine voreingenommene Meinung fragen, wenn Sie auf Containerebene darüber sprechen (wie in einer Datenstruktur, die speziell implementiert wurde, um Set-Operationen effizient bereitzustellen), aber es gibt viele, die Set-Logik auf konzeptioneller Ebene erfordern. Nehmen wir zum Beispiel an, Sie möchten die Kreaturen in einer Spielwelt finden, die sowohl fliegen als auch schwimmen können, und Sie haben fliegende Kreaturen in einem Satz (unabhängig davon, ob Sie tatsächlich einen Set-Container verwenden oder nicht) und solche, die in einem anderen schwimmen können . In diesem Fall möchten Sie einen festgelegten Schnittpunkt. Wenn Sie Kreaturen wollen, die entweder fliegen können oder magisch sind, verwenden Sie eine festgelegte Vereinigung. Natürlich benötigen Sie keinen Set-Container, um dies zu implementieren, und die optimalste Implementierung benötigt oder möchte im Allgemeinen keinen Container, der speziell als Set konzipiert wurde.

Tangente losgehen

In Ordnung, ich habe einige nette Fragen von JimmyJames zu diesem festgelegten Kreuzungsansatz bekommen. Es weicht ein bisschen vom Thema ab, aber na ja, ich bin daran interessiert, dass mehr Leute diesen grundlegenden aufdringlichen Ansatz verwenden, um Schnittpunkte festzulegen, damit sie nicht ganze Hilfsstrukturen wie ausgeglichene Binärbäume und Hash-Tabellen nur zum Zweck von Set-Operationen erstellen. Wie bereits erwähnt, besteht die Grundvoraussetzung darin, dass die Listen flache Kopierelemente sind, so dass sie indizieren oder auf ein gemeinsam genutztes Element verweisen, das durch den Durchlauf durch die erste unsortierte Liste oder das erste unsortierte Array oder was auch immer "markiert" werden kann, um dann das zweite aufzunehmen Durchlaufen Sie die zweite Liste.

Dies kann jedoch praktisch sogar in einem Multithreading-Kontext erreicht werden, ohne die Elemente zu berühren, vorausgesetzt, dass:

1. Die beiden Aggregate enthalten Indizes zu den Elementen.
2. Der Bereich der Indizes ist nicht zu groß (sagen wir [0, 2 ^ 26], nicht Milliarden oder mehr) und ist ziemlich dicht besetzt.

Dies ermöglicht es uns, ein paralleles Array (nur ein Bit pro Element) zum Setzen von Operationen zu verwenden. Diagramm:

Die Thread-Synchronisation muss nur vorhanden sein, wenn ein paralleles Bit-Array aus dem Pool abgerufen und wieder an den Pool freigegeben wird (implizit, wenn der Gültigkeitsbereich verlassen wird). Die tatsächlichen zwei Schleifen zum Ausführen der Set-Operation müssen keine Thread-Synchronisierungen beinhalten. Wir müssen nicht einmal einen parallelen Bitpool verwenden, wenn der Thread die Bits nur lokal zuweisen und freigeben kann, aber der Bitpool kann nützlich sein, um das Muster in Codebasen zu verallgemeinern, die zu dieser Art von Datendarstellung passen, auf die häufig auf zentrale Elemente verwiesen wird nach Index, damit sich nicht jeder Thread um eine effiziente Speicherverwaltung kümmern muss. Paradebeispiele für meinen Bereich sind Entitätskomponentensysteme und indizierte Netzdarstellungen. Beide benötigen häufig festgelegte Schnittpunkte und beziehen sich in der Regel auf alles, was zentral gespeichert ist (Komponenten und Entitäten in ECS und Scheitelpunkte, Kanten,

Wenn die Indizes nicht dicht besetzt und dünn gestreut sind, gilt dies immer noch für eine vernünftig spärliche Implementierung des parallelen Bit / Booleschen Arrays, wie eines, das nur Speicher in 512-Bit-Blöcken speichert (64 Bytes pro nicht gerolltem Knoten, der 512 zusammenhängende Indizes darstellt ) und überspringt die Zuweisung vollständig leerer zusammenhängender Blöcke. Möglicherweise verwenden Sie so etwas bereits, wenn Ihre zentralen Datenstrukturen nur spärlich von den Elementen selbst belegt sind.

... eine ähnliche Idee für ein Sparse-Bitset als paralleles Bit-Array. Diese Strukturen eignen sich auch für die Unveränderlichkeit, da es einfach ist, klobige Blöcke flach zu kopieren, die nicht tief kopiert werden müssen, um eine neue unveränderliche Kopie zu erstellen.

Wiederum können mit diesem Ansatz auf einer sehr durchschnittlichen Maschine festgelegte Schnittpunkte zwischen Hunderten von Millionen von Elementen in weniger als einer Sekunde erstellt werden, und das innerhalb eines einzelnen Threads.

Dies kann auch in weniger als der Hälfte der Zeit erfolgen, wenn der Client keine Liste von Elementen für die resultierende Schnittmenge benötigt, z. B. wenn er nur eine gewisse Logik auf die in beiden Listen gefundenen Elemente anwenden möchte und an diesem Punkt nur übergeben kann Ein Funktionszeiger oder Funktor oder Delegat oder was auch immer, der zurückgerufen werden soll, um Bereiche von Elementen zu verarbeiten, die sich überschneiden. Etwas in diesem Sinne:

// 'func' receives a range of indices to
// process.
set_intersection(func):
{
    parallel_bits = bit_pool.acquire()

    // Mark the indices found in the first list.
    for each index in list1:
        parallel_bits[index] = 1

    // Look for the first element in the second list 
    // that intersects.
    first = -1
    for each index in list2:
    {
         if parallel_bits[index] == 1:
         {
              first = index
              break
         }
    }

    // Look for elements that don't intersect in the second
    // list to call func for each range of elements that do
    // intersect.
    for each index in list2 starting from first:
    {
        if parallel_bits[index] != 1:
        {
             func(first, index)
             first = index
        }
    }
    If first != list2.num-1:
        func(first, list2.num)
}

... oder so ähnlich. Der teuerste Teil des Pseudocodes im ersten Diagramm befindet sich intersection.append(index)in der zweiten Schleife, und dies gilt auch für std::vectorim Voraus auf die Größe der kleineren Liste reservierte.

Was ist, wenn ich alles tief kopiere?

Nun, hör auf damit! Wenn Sie Schnittpunkte festlegen müssen, bedeutet dies, dass Sie Daten duplizieren, mit denen Schnittpunkte erstellt werden sollen. Möglicherweise sind selbst Ihre kleinsten Objekte nicht kleiner als ein 32-Bit-Index. Es ist sehr gut möglich, den Adressierungsbereich Ihrer Elemente auf 2 ^ 32 (2 ^ 32 Elemente, nicht 2 ^ 32 Bytes) zu reduzieren, es sei denn, Sie benötigen tatsächlich mehr als ~ 4,3 Milliarden instanziierte Elemente. Zu diesem Zeitpunkt ist eine völlig andere Lösung erforderlich ( und das verwendet definitiv keine festgelegten Container im Speicher).

Schlüsselübereinstimmungen

Wie wäre es mit Fällen, in denen wir Set-Operationen ausführen müssen, bei denen die Elemente nicht identisch sind, aber übereinstimmende Schlüssel haben könnten? In diesem Fall die gleiche Idee wie oben. Wir müssen nur jeden eindeutigen Schlüssel einem Index zuordnen. Wenn der Schlüssel beispielsweise eine Zeichenfolge ist, können internierte Zeichenfolgen genau das tun. In diesen Fällen ist eine schöne Datenstruktur wie ein Trie oder eine Hash-Tabelle erforderlich, um Zeichenfolgenschlüssel 32-Bit-Indizes zuzuordnen. Wir benötigen solche Strukturen jedoch nicht, um die festgelegten Operationen für die resultierenden 32-Bit-Indizes auszuführen.

Eine ganze Reihe sehr billiger und unkomplizierter algorithmischer Lösungen und Datenstrukturen eröffnen sich auf diese Weise, wenn wir mit Indizes für Elemente in einem sehr vernünftigen Bereich arbeiten können, nicht im gesamten Adressierungsbereich der Maschine, und es sich daher oft mehr als lohnt, dies zu sein in der Lage, einen eindeutigen Index für jeden eindeutigen Schlüssel zu erhalten.

Ich liebe Indizes!

Ich liebe Indizes genauso wie Pizza und Bier. Als ich 20 Jahre alt war, habe ich mich wirklich mit C ++ beschäftigt und angefangen, alle Arten von vollständig standardkonformen Datenstrukturen zu entwerfen (einschließlich der Tricks, die erforderlich sind, um einen Füll-Ctor zur Kompilierungszeit von einem Range-Ctor zu unterscheiden). Rückblickend war das eine große Zeitverschwendung.

Wenn Sie Ihre Datenbank darauf konzentrieren, Elemente zentral in Arrays zu speichern und zu indizieren, anstatt sie fragmentiert und möglicherweise über den gesamten adressierbaren Bereich des Computers zu speichern, können Sie am Ende eine Welt voller algorithmischer und Datenstrukturmöglichkeiten erkunden Entwerfen von Containern und Algorithmen, die sich um einfache alte intoder alte drehen int32_t. Und ich fand das Endergebnis so viel effizienter und einfacher zu warten, dass ich nicht ständig Elemente von einer Datenstruktur zu einer anderen zu einer anderen zu einer anderen übertrug.

Einige Anwendungsbeispiele, bei denen Sie einfach davon ausgehen können, dass ein eindeutiger Wert von Teinen eindeutigen Index hat und Instanzen in einem zentralen Array vorhanden sind:

Multithread-Radix-Sortierungen, die gut mit vorzeichenlosen Ganzzahlen für Indizes funktionieren . Ich habe tatsächlich eine Multithread-Radix-Sortierung, die ungefähr 1/10 der Zeit benötigt, um hundert Millionen Elemente als Intels eigene parallele Sortierung zu sortieren, und Intels ist bereits viermal schneller als std::sortbei so großen Eingaben. Natürlich ist Intel viel flexibler, da es sich um eine vergleichsbasierte Sortierung handelt und die Dinge lexikografisch sortieren kann, sodass Äpfel mit Orangen verglichen werden. Aber hier brauche ich oft nur Orangen, wie ich einen Radix-Sortierdurchlauf machen könnte, um cachefreundliche Speicherzugriffsmuster zu erzielen oder Duplikate schnell herauszufiltern.

Möglichkeit, verknüpfte Strukturen wie verknüpfte Listen, Bäume, Diagramme, separate Verkettungs-Hash-Tabellen usw. ohne Heap-Zuweisungen pro Knoten zu erstellen . Wir können die Knoten einfach in großen Mengen parallel zu den Elementen zuordnen und sie mit Indizes verknüpfen. Die Knoten selbst werden einfach zu einem 32-Bit-Index für den nächsten Knoten und in einem großen Array gespeichert, wie folgt:

Freundlich für die Parallelverarbeitung. Oft sind verknüpfte Strukturen für die parallele Verarbeitung nicht so geeignet, da es zumindest umständlich ist, Parallelität beim Durchlaufen von Bäumen oder verknüpften Listen zu erreichen, anstatt beispielsweise nur eine parallele for-Schleife durch ein Array durchzuführen. Mit der Index- / Zentralarray-Darstellung können wir immer zu diesem Zentralarray gehen und alles in klobigen parallelen Schleifen verarbeiten. Wir haben immer das zentrale Array aller Elemente, die wir auf diese Weise verarbeiten können, auch wenn wir nur einige verarbeiten möchten (an diesem Punkt können Sie die durch eine radixsortierte Liste indizierten Elemente für den cachefreundlichen Zugriff über das zentrale Array verarbeiten).

Kann jedem Element im laufenden Betrieb Daten in konstanter Zeit zuordnen . Wie im Fall des obigen parallelen Arrays von Bits können wir parallele Daten einfach und äußerst kostengünstig Elementen zuordnen, um sie beispielsweise vorübergehend zu verarbeiten. Dies hat Anwendungsfälle, die über temporäre Daten hinausgehen. Beispielsweise möchte ein Netzsystem Benutzern ermöglichen, so viele UV-Karten an ein Netz anzuhängen, wie sie möchten. In einem solchen Fall können wir nicht einfach mithilfe eines AoS-Ansatzes fest codieren, wie viele UV-Karten sich in jedem einzelnen Scheitelpunkt und jeder einzelnen Fläche befinden. Wir müssen in der Lage sein, solche Daten im laufenden Betrieb zuzuordnen, und parallele Arrays sind dort praktisch und viel billiger als jeder hochentwickelte assoziative Container, selbst Hash-Tabellen.

Parallele Arrays sind natürlich verpönt, weil sie fehleranfällig sind, parallele Arrays miteinander synchron zu halten. Wenn wir beispielsweise ein Element am Index 7 aus dem Array "root" entfernen, müssen wir dies auch für die "Kinder" tun. In den meisten Sprachen ist es jedoch einfach genug, dieses Konzept auf einen Universalcontainer zu verallgemeinern, sodass die schwierige Logik, parallele Arrays miteinander synchron zu halten, nur an einer Stelle in der gesamten Codebasis vorhanden sein muss, und ein solcher paralleler Array-Container kann Verwenden Sie die obige Implementierung des Sparse-Arrays, um zu vermeiden, dass viel Speicherplatz für zusammenhängende freie Speicherplätze im Array verschwendet wird, die beim nachfolgenden Einfügen zurückgefordert werden sollen.

Weitere Ausarbeitung: Sparse Bitset Tree

In Ordnung, ich bekam die Bitte, noch etwas auszuarbeiten, was ich für sarkastisch halte, aber ich werde es trotzdem tun, weil es so viel Spaß macht! Wenn Menschen diese Idee auf ganz neue Ebenen bringen möchten, ist es möglich, festgelegte Schnittpunkte auszuführen, ohne N + M-Elemente linear zu durchlaufen. Dies ist meine ultimative Datenstruktur, die ich seit Ewigkeiten verwende und im Grunde genommen Modelle set<int>:

Der Grund, warum es Set-Schnittpunkte ausführen kann, ohne jedes Element in beiden Listen zu untersuchen, liegt darin, dass ein einzelnes Set-Bit an der Wurzel der Hierarchie anzeigen kann, dass beispielsweise eine Million zusammenhängender Elemente in der Menge belegt sind. Wenn wir nur ein Bit untersuchen, können wir erkennen, dass sich N Indizes im Bereich [first,first+N)in der Menge befinden, wobei N eine sehr große Zahl sein könnte.

Ich benutze dies tatsächlich als Schleifenoptimierer, wenn ich belegte Indizes durchquere, weil beispielsweise 8 Millionen Indizes in der Menge belegt sind. Normalerweise müssten wir in diesem Fall auf 8 Millionen Ganzzahlen im Speicher zugreifen. Mit diesem kann es möglicherweise nur einige Bits untersuchen und Indexbereiche von belegten Indizes zum Durchlaufen erstellen. Darüber hinaus sind die Indexbereiche in sortierter Reihenfolge angeordnet, was einen sehr cachefreundlichen sequentiellen Zugriff ermöglicht, anstatt beispielsweise ein unsortiertes Array von Indizes zu durchlaufen, die für den Zugriff auf die ursprünglichen Elementdaten verwendet werden. Natürlich ist diese Technik in extrem spärlichen Fällen schlechter, wobei das Worst-Case-Szenario darin besteht, dass jeder einzelne Index eine gerade Zahl ist (oder jeder ungerade). In diesem Fall gibt es überhaupt keine zusammenhängenden Regionen. Aber zumindest in meinen Anwendungsfällen

Um zu überprüfen, ob eine Menge mit n Elementen ein anderes Element enthält, benötigt X normalerweise eine konstante Zeit. Um zu überprüfen, ob ein Array mit n Elementen ein anderes Element enthält, benötigt X normalerweise O (n) Zeit. Das ist schlecht, aber wenn Sie die Duplikate aus n Elementen entfernen möchten, dauert es plötzlich O (n) in der Zeit anstelle von O (n ^ 2); 100.000 Gegenstände bringen Ihren Computer in die Knie.

Und Sie fragen nach weiteren Gründen? "Abgesehen von den Dreharbeiten, haben Sie den Abend genossen, Mrs. Lincoln?"