Abo
  1. Foren
  2. Kommentare
  3. Software-Entwicklung
  4. Alle Kommentare zum Artikel
  5. › PHP7: PHP reduziert Array…

Patricia-Trie

  1. Thema

Neues Thema Ansicht wechseln


  1. Patricia-Trie

    Autor: bebbo 23.12.14 - 22:07

    Wenn man assoziative Arrays schnell und platzsparend implementieren will, bietet sich der Patricia-Trie an. Lookup in O(n).

    Für Hashmaps wird O(1) propagiert. Dabei vergessen viele, dass der Hashwert eines Strings bereits O(n) hat.

    siehe http://de.wikipedia.org/wiki/Patricia-Trie

    Bebbo

  2. Re: Patricia-Trie

    Autor: OdinX 24.12.14 - 13:05

    bebbo schrieb:
    --------------------------------------------------------------------------------
    > Wenn man assoziative Arrays schnell und platzsparend implementieren will,
    > bietet sich der Patricia-Trie an. Lookup in O(n).
    >
    > Für Hashmaps wird O(1) propagiert. Dabei vergessen viele, dass der Hashwert
    > eines Strings bereits O(n) hat.
    >
    > siehe de.wikipedia.org
    >
    > Bebbo

    Vielleicht solltest du noch der Vollständigkeit halber hinschreiben, was n denn genau ist. Normalerweise bedeutet n in diesem Kontext die Anzahl der Elemente, welche die Datenstruktur enthält. In deinem Fall meint n hingegen die Länge des zu speichernden Strings (Keys), was meistens definitiv viel kürzer ist. Ausserdem ist die reine Komplexität für grössere Datenstrukturen nicht mehr das einzig wichtige, die Minimierung der Memory-Zugriffe wird also immer wichtiger.

  3. Re: Patricia-Trie

    Autor: Bonita.M 24.12.14 - 23:34

    Du kannst davon ausgehen, dass es schneller ist den Hashwert zu bilden als durch den Baum zu springen.

Neues Thema Ansicht wechseln


Um zu kommentieren, loggen Sie sich bitte ein oder registrieren Sie sich. Zum Login

Stellenmarkt
  1. BWI GmbH, Nürnberg, München, Rheinbach
  2. Kassenärztliche Bundesvereinigung, Berlin
  3. BüchnerBarella Holding GmbH & Co. KG, Gießen
  4. BWI GmbH, verschiedene Standorte

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Top-Angebote
  1. 59€ (Vergleichspreis 70,98€)
  2. 49€ für Prime-Mitglieder (Vergleichspreis 64,98€)
  3. 59,99€ (Vergleichspreis ca. 90€)


Haben wir etwas übersehen?

E-Mail an news@golem.de


Adblock Plus: Adblock-Filterregeln können Code ausführen
Adblock Plus
Adblock-Filterregeln können Code ausführen

Unter bestimmten Voraussetzungen können Filterregeln für Adblocker mit einer neuen Funktion Javascript-Code in Webseiten einfügen. Adblock Plus will reagieren und die entsprechende Funktion wieder entfernen. Ublock Origin ist nicht betroffen.
Von Hanno Böck


    Online-Banking: In 150 Tagen verlieren die TAN-Zettel ihre Gültigkeit
    Online-Banking
    In 150 Tagen verlieren die TAN-Zettel ihre Gültigkeit

    Zum 14. September 2019 wird ein wichtiger Teil der Zahlungsdiensterichtlinie 2 für die meisten Girokonto-Kunden mit Online-Zugang umgesetzt. Die meist als indizierte TAN-Liste ausgegebenen Transaktionsnummern können dann nicht mehr genutzt werden.
    Von Andreas Sebayang

    1. Banking-App Comdirect empfiehlt, Sicherheitswarnung zu ignorieren

    Swobbee: Der Wechselakku kommt wieder
    Swobbee
    Der Wechselakku kommt wieder

    Mieten statt kaufen, wechseln statt laden: Das Berliner Startup Swobbee baut eine Infrastruktur mit Lade- und Tauschstationen für Akkus auf. Ein ähnliches Geschäftsmodell ist schon einmal gescheitert. Dieses kann jedoch aufgehen.
    Eine Analyse von Werner Pluta

    1. Elektromobilität Seoul will Zweirad-Kraftfahrzeuge und Minibusse austauschen
    2. Rechtsanspruch auf Wallboxen Wohnungswirtschaft warnt vor "Schnellschuss" bei WEG-Reform
    3. Innolith Energy Battery Schweizer Unternehmen entwickelt sehr leistungsfähigen Akku

    1. Faltbares Smartphone: Samsung sagt Start des Galaxy Fold ab
      Faltbares Smartphone
      Samsung sagt Start des Galaxy Fold ab

      Samsung steht vor einem Foldgate: Der südkoreanische Hersteller hat den Marktstart des faltbaren Smartphones Galaxy Fold vorerst abgesagt. Nachdem die Testgeräte einiger Journalisten auch ohne ihr Zutun kaputt gegangen sind, soll das Gerät noch einmal gründlich untersucht werden.

    2. Joe Armstrong: Der Erlang-Erfinder ist gestorben
      Joe Armstrong
      Der Erlang-Erfinder ist gestorben

      Der Informatiker Joe Armstrong gilt als Erfinder der Programmiersprache Erlang und war Experte für verteilte und fehlertolerante Systeme. Armstrong erlag nun den Folgen einer Lungenerkrankung.

    3. Tchap: Forscher gelingt Anmeldung im Regierungschat Frankreichs
      Tchap
      Forscher gelingt Anmeldung im Regierungschat Frankreichs

      Kurz nach dem Start ist es einem Sicherheitsforscher gelungen, sich unberechtigt bei der Whatsapp-Alternative der französischen Regierung anzumelden. Der Forscher fand weitere vermeintliche Fehler, die laut den Entwicklern der Matrix-Software aber keine sind.


    1. 21:11

    2. 12:06

    3. 11:32

    4. 11:08

    5. 12:55

    6. 11:14

    7. 10:58

    8. 16:00