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. AKDB, Regensburg
  2. Bertrandt Services GmbH, Friedrichshafen
  3. BWI GmbH, Rheinbach
  4. Vodafone GmbH, Düsseldorf, Eschborn

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Top-Angebote
  1. (u. a. Microsoft Surface Pro i5/256GB/8GB für 829,00€, Acer Aspire ab 299,00€)
  2. 114,99€
  3. (u. a. GTA 5 für 12,99€, Landwirtschafts-Simulator 19 für 27,99€, Battlefield V für 32,99€)
  4. 849,00€ (Bestpreis!)


Haben wir etwas übersehen?

E-Mail an news@golem.de


Kontist, N26, Holvi: Neue Banking-Apps machen gute Angebote für Freelancer
Kontist, N26, Holvi
Neue Banking-Apps machen gute Angebote für Freelancer

Ein mobiles und dazu noch kostenloses Geschäftskonto für Freiberufler versprechen Startups wie Kontist, N26 oder Holvi. Doch sind die Newcomer eine Alternative zu den Freelancer-Konten der großen Filialbanken? Ja, sind sie - mit einer kleinen Einschränkung.
Von Björn König


    Mordhau angespielt: Die mit dem Schwertknauf zuschlagen
    Mordhau angespielt
    Die mit dem Schwertknauf zuschlagen

    Ein herausfordernd-komplexes Kampfsystem, trotzdem schnelle Action mit Anleihen bei Chivalry und For Honor: Das vom Entwicklerstudio Triternion produzierte Mordhau schickt Spieler in mittelalterlich anmutende Multiplayergefechte mit klirrenden Schwertern und hohem Spaßfaktor.
    Von Peter Steinlechner

    1. Bus Simulator angespielt Zwischen Bodenschwelle und Haltestelle
    2. Bright Memory angespielt Brachialer PC-Shooter aus China

    e.Go Life: Ein Auto, das lächelt
    e.Go Life
    Ein Auto, das lächelt

    Das Auto ist zwar klein, bringt aber sogar gestandene Rennfahrer ins Schwärmen: Das Aachener Unternehmen e.Go Mobile hat seine ersten Elektroautos ausgeliefert. In einer Probefahrt erweist sich der Kleinwagen als sehr dynamisch.
    Ein Bericht von Werner Pluta

    1. Eon-Studie Netzausbau kostet maximal 400 Euro pro Elektroauto
    2. EZ-Pod Renault-Miniauto soll Stadtverkehr in Kolonne fahren
    3. Elektromobilität EnBW will weitere 2.000 Schnellladepunkte errichten

    1. Karlsdorf-Neuthard: Telekom überbaut Glasfaser der Gemeinde mit Vectoring
      Karlsdorf-Neuthard
      Telekom überbaut Glasfaser der Gemeinde mit Vectoring

      Die Telekom wollte in einer Gemeinde keine Glasfaser ausbauen. Als Karlsdorf-Neuthard selbst ein Netz verlegte, wurde mit Vectoring überbaut. Die Gemeinde musste aufhören.

    2. Glücksspiel: Nintendo schaltet zwei Mobile Games in Belgien ab
      Glücksspiel
      Nintendo schaltet zwei Mobile Games in Belgien ab

      Fire Emblem Heroes und Animal Crossing Pocket Camp haben demnächst ein paar Spieler weniger: Nintendo will die beiden Mobile Games in Belgien vollständig vom Markt nehmen.

    3. Entwicklung: Github will Behebung von Sicherheitslücken vereinfachen
      Entwicklung
      Github will Behebung von Sicherheitslücken vereinfachen

      Die Funktion zur Sicherheitswarnung von Github wird so erweitert, dass die Plattform auch direkt die Patches zum Einpflegen bereitstellt. Entwickler können Lücken und deren Lösung zudem in geschlossenen Gruppen betreuen.


    1. 19:15

    2. 19:00

    3. 18:45

    4. 18:26

    5. 18:10

    6. 17:48

    7. 16:27

    8. 15:30