Anspruchsvoll Aufgabe
-
Randomisiert klappts in O(n) mit einer Hashtabelle. Deterministisch glaube ich nicht, dass es ohne weitere Annahmen in linearer Zeit geht, weshalb ich sehr gespannt auf SeppJs Versuch bin.
-
-
So man ganz auf doof würde mir auf Anhieb diese Lösung einfallen:
Zutaten:
1 Hash-Map mit Wort als Key und Häufigkeit als Value (Einfügen und Abfragen in O(1)).
1 beliebige Liste, Vektor, etc. in der du die 3 häufigsten Wörter und deren Häufigkeit speicherst (Komplexität der Datenstruktur egal, da die Größe eh durch die 3 Wörter nach oben beschränkt ist ihre Kompexität dadurch konstant, also O(1) wird).Vorgehen:
Wörter-Liste durchlaufen, und für jedes Wort:
- Value in Hash-Map für das Wort um 1 inkrementieren.
- nach dem inkrementieren die bisherige Häufigkeit des Wortes aus Hash-Map auslesen und Liste der 3 häufigsten Wörter aktualisieren (ist aktuelles Wort häufiger, als eines der 3 in der Liste, dann ersetzen).Am Ende die 3-Wörter-Liste ausgeben.
Laufzeit des Algorithmus ist O(n): Jedes der n Wörter wird einmal durchlaufen und im Schleifenkörper werden nur Operationen mit konstantem Aufwand durchgeführt (Hash-Map-Zugriffe und 3 Listen-Elemente prüfen).
Oder auch: n * (O(1) + O(3)) = n * O(1) = O(n)... oder hab ich hier was übersehen?
Gruss,
Finnegan
-
volkard schrieb:
Kannstes denn in O(3*n) packen? Dann mach das erstmal. SeppJ zeigt Dir dann, wie man es als O(n) verkauft.
Ich denke nicht dass man da was verkaufen muss, O(4671647467824671421 * n) ist exakt gleich O(n) da beide Funktions-Mengen identisch sind - es ist lediglich ein anderer Repräsentant derselben Klasse angegeben.
Finnegan
-
Finnegan schrieb:
Laufzeit des Algorithmus ist O(n): Jedes der n Wörter wird einmal durchlaufen und im Schleifenkörper werden nur Operationen mit konstantem Aufwand durchgeführt (Hash-Map-Zugriffe und 3 Listen-Elemente prüfen).
Oder auch: n * (O(1) + O(3)) = n * O(1) = O(n)... oder hab ich hier was übersehen?
Ich lese Deinen Code, finde die Hashfunktion, und bastele eine Wörterliste, wo alle Wörter den gleichen Hashwert haben und schau mal, ob der Hashtable-Zugriff noch O(1) hat.
-
volkard schrieb:
Ich lese Deinen Code, finde die Hashfunktion, und bastele eine Wörterliste, wo alle Wörter den gleichen Hashwert haben und schau mal, ob der Hashtable-Zugriff noch O(1) hat.
Ja, das ist ein Argument. Allerdings ist soweit ich sehe nicht genau definiert, ob die O(n) auch für den Worst Case eingehalten werden sollen - lediglich dass es "in O(n) laufen soll".
Ich kontere einfach mal und zähle stattdessen in einem wahnwitzig großen Array, das ich direkt über die Integer-Repräsentation des Wortes adressieren kann :p
... oder ich implementiere den Algorithmus als Funktion der man bitteschön als zweites Argument eine für die Wortliste perfekte Hashfunktion zu übergeben hat (sehe keine Einschränkung, die das verbietet) :p
Genug gescherzt, es gibt möglicherweise eine pfiffigere Lösung, ich habe auch nur das vorgeschlagen, was mit als erstes eingefallen ist, und das im mittleren Fall die Laufzeit-Grenzen einhält.
Finnegan
-
Finnegan schrieb:
Ich kontere einfach mal und zähle stattdessen in einem wahnwitzig großen Array, das ich direkt über die Integer-Repräsentation des Wortes adressieren kann :p
Vorher die Zähler mit Nullen Initialisieren O(wahnwitz), schnell zählen O(n), und nachher die drei größten Zahlen finden O(wahnwitz).
-
volkard schrieb:
Finnegan schrieb:
Ich kontere einfach mal und zähle stattdessen in einem wahnwitzig großen Array, das ich direkt über die Integer-Repräsentation des Wortes adressieren kann :p
Vorher die Zähler mit Nullen Initialisieren O(wahnwitz), schnell zählen O(n), und nachher die drei größten Zahlen finden O(wahnwitz).
Ja! Aber wahnwitz ist konstant (abhängig von zuvor in O(n) ermittelte maximale Länge eines Wortes) :p ... zumindest konstant in Bezug auf unser n.
=> O(wahnwitz) + O(n) = O(n)
Finnegan
P.S.: Das Ganze zeigt allerdings, dass diese theoretischen Komplexitätsbetrachtungen im praktischen Einsatz mit vorsicht zu genießen sind. Auch ein O(1)-Algorithmus kann 100 Jahre benötigen. Wenn ich den dann auf 1 Stunde drücke dann ist das für den praktischen Einsatz sehr relevant, aber immer noch O(1)
-
Finnegan schrieb:
Ja! Aber wahnwitz ist konstant (abhängig von zuvor in O(n) ermittelte maximale Länge eines Wortes) :p ... zumindest konstant in Bezug auf unser n.
Nö. Den Worst Case gibt man ja nie mit einer einzelnen Instanz an, denn eine einzelne Instanz hat konstante Größe und lässt sich somit für jedes beliebige Problem in konstanter Zeit lösen. Stattdessen gibt man eine Instanzfamilie an. In diesem Fall gibt man z.B. entsprechend deiner Hashfunktion n Wörter der Länge >= n mit demselben Hashwert an, um deine Aussage zu widerlegen.
-
Dann definiert man halt das Problem und folglich die Lösung nur für Wörter mit einer gewissen maximal Länge.
Alles Definitionssache.
-
m.e. schrieb:
Finnegan schrieb:
Ja! Aber wahnwitz ist konstant (abhängig von zuvor in O(n) ermittelte maximale Länge eines Wortes) :p ... zumindest konstant in Bezug auf unser n.
Nö. Den Worst Case gibt man ja nie mit einer einzelnen Instanz an, denn eine einzelne Instanz hat konstante Größe und lässt sich somit für jedes beliebige Problem in konstanter Zeit lösen. Stattdessen gibt man eine Instanzfamilie an. In diesem Fall gibt man z.B. entsprechend deiner Hashfunktion n Wörter der Länge >= n mit demselben Hashwert an, um deine Aussage zu widerlegen.
Ja, das stimmt. Ich habe wahnwitz mit meiner Formulierung gewissermassen abhängig von der Eingabe gemacht. Ich formuliere es mal ein wenig anders:
Sei wahnwitz eine endliche Konstante, die groß genug für alle Wörter der zu lösenden Problemklasse gewählt ist.
Besser?
Finnegan
-
Um mal wieder etwas Konstruktives beizutragen: Es geht nicht schneller als Theta(n log n) (im selben Modell wie "Sortieren geht nicht schneller als Theta(n log n)), weil unser Problem schwerer ist als das Element Distinctness Problem. Also ist Sortieren, was SeppJ zu Recht aus praktischer Sicht nicht mag, theoretisch optimal für den Worst Case.
-
Ich dachte auch an nee Hashtabelle. Aber erstens ist die unsortiert. Ich muesste dann den String als Key speichern und als value die Anzahl. Wenn der String schon existiert und muesste ich den value auslesen und den value dann um 1 erhöhen. Nächstes Problem wie lese ich alle keys aus. In einer Hashtable sind ja viele keys nur rubbish.
Selbst wenn ich dann eine HashDatenstruktur mit String -> Anzahl habe, frage ich mich wie ich in O(n) die 3 häufigsten Strings bekomme.
-
Matze16 schrieb:
Aber erstens ist die unsortiert.
Ja...?
Ich muesste dann den String als Key speichern und als value die Anzahl. Wenn der String schon existiert und muesste ich den value auslesen und den value dann um 1 erhöhen.
Ja...? Trivial zu schreiben, da der operator[] von std::unordered_map beim nicht vorhandensein den value value-initialized, der somit 0 ist und man einfach map[key]++ schreiben kann.
Nächstes Problem wie lese ich alle keys aus.
Schleife?
In einer Hashtable sind ja viele keys nur rubbish.
Nein...?
Selbst wenn ich dann eine HashDatenstruktur mit String -> Anzahl habe, frage ich mich wie ich in O(n) die 3 häufigsten Strings bekomme.
Schleife?
Nur mal so aus Neugier: Für was genau bewirbst du dich?
-
Matze16 schrieb:
Ich dachte auch an nee Hashtabelle. Aber erstens ist die unsortiert. Ich muesste dann den String als Key speichern und als value die Anzahl. Wenn der String schon existiert und muesste ich den value auslesen und den value dann um 1 erhöhen. Nächstes Problem wie lese ich alle keys aus. In einer Hashtable sind ja viele keys nur rubbish.
Selbst wenn ich dann eine HashDatenstruktur mit String -> Anzahl habe, frage ich mich wie ich in O(n) die 3 häufigsten Strings bekomme.
Du scheinst Probleme damit zu haben, Informationen aus ner Hashtabelle wieder auszulesen. Wenn du std::unordered_map benutzt, dann schau dir mal z.B. http://www.cplusplus.com/reference/unordered_map/unordered_map/begin/ an.
-
Die Aufgabe kommt von Evernote.
Zitat: Implement this function as you would for a production/commercial system
-
Matze16 schrieb:
Ich dachte auch an nee Hashtabelle. Aber erstens ist die unsortiert. Ich muesste dann den String als Key speichern und als value die Anzahl. Wenn der String schon existiert und muesste ich den value auslesen und den value dann um 1 erhöhen. Nächstes Problem wie lese ich alle keys aus. In einer Hashtable sind ja viele keys nur rubbish.
Selbst wenn ich dann eine HashDatenstruktur mit String -> Anzahl habe, frage ich mich wie ich in O(n) die 3 häufigsten Strings bekomme.
Schau dir mal meine erste Antwort an. Du aktualisierst die Liste (oder die einzelnen Variablen) mit deinen 3 häufigsten Strings direkt nach jedem erhöhen der Anzahl in der Hash-Map: niedrigere Häufigkeiten fallen raus und werden durch höhere ersetzt.
Alternativ kannst du die Hash-Map auch im Anschluss 3 mal durchlaufen und dabei jeweils das größte Element suchen, das kleiner ist als das gefundene des letzten Durchlaufs (O(4 * n) ist schließlich immer noch O(n)).Zumindest die std::unordered_map lässt sich in O(n) iterieren. Soweit ich weiss haben die Elemente intern einen Zeiger auf das nachfolgende Element, so dass man nicht immer alle Buckets durchlaufen muss.
Finnegan
P.S.:
m.e. schrieb:
Um mal wieder etwas Konstruktives beizutragen: Es geht nicht schneller als Theta(n log n) (im selben Modell wie "Sortieren geht nicht schneller als Theta(n log n)), weil unser Problem schwerer ist als das Element Distinctness Problem. Also ist Sortieren, was SeppJ zu Recht aus praktischer Sicht nicht mag, theoretisch optimal für den Worst Case.
Das ist ein schönes Argument, falls der Vorwurf kommt, dass die Hash-Map-Variante im Worst Case nicht mehr O(n) ist ... es mag zwar für den Worst Case besser gehen, aber immer noch nicht in O(n).
-
Wie kann ich überhaupt prüfen ob der Key schon existiert ? Jedenfalls hab ich keine exisit Funktion gesehen?
Würde der value dann einfach überschrieben ?
-
Matze16 schrieb:
Wie kann ich überhaupt prüfen ob der Key schon existiert ? Jedenfalls hab ich keine exisit Funktion gesehen?
Es gibt eine count() Funktion.
Würde der value dann einfach überschrieben ?
Ja. Siehe die Dokumentation zu operator[].
-
Finnegan schrieb:
Alternativ kannst du die Hash-Map auch im Anschluss 3 mal durchlaufen und dabei jeweils das größte Element suchen, das kleiner ist als das gefundene des letzten Durchlaufs (O(4 * n) ist schließlich immer noch O(n)).
Das funktioniert nicht, falls es mehrere Elemente gibt, die am häufigsten vorkommen. Es ist trotzdem kein Problem, die drei häufigsten Elemente in einem Durchlauf zu finden, so wie Insertion Sort, nur dass man nur die größten drei Elemente speichert.