Flor1an

Ist die Frage wie die Arrays bei PHP intern gelöst sind.

Soweit ich weiß sind PHP Arrays intern als Hash Table gelöst, da dauert die Suche nach dem Index dann auch O(log n), heißt am Ende kommst du auf n*log n raus ...

Mister Ad

Chriz

Hm es wird doch wohl etwas mit den Integer-Werten auf sich haben nehme ich an .. macht gerade keinen Sinn, aber vielleicht multipliziert man zunächst alle Werte des ersten Arrays und schaut so, ob im zweiten Array eine Division ohne Rest möglich ist. Macht bei kleinen oder sehr vielen Zahlen allerdings einen ziemlichen Aufwand, genau ist es erstmal auch nicht. Ist die (verkettete) Binärdarstellung relevant?

__________________
"Nuschel ich?" - "Was?"

Flor1an

Die Frage ist erstmal unter welchen Umständen wir arbeiten, sind PHP Arrays gemeint mit deren Hash Table implementierung in C? Was genau soll die Laufzeit sein, Anzahl der PHP Funktionsaufrufe oder Anzahl der echten Operationen/Vergleiche.

mermshaus

Die Lösung, die ich im Kopf hatte, ist die von hts.
Die Frage war nicht speziell auf PHP bezogen.

Bei der Frage, wie lange der Lookup in einer Hashtabelle dauert und wie Programmiersprachen das lösen, hörte es bei mir aber zugegebenermaßen auch auf.

Wikipedia sagt:

- http://de.wikipedia.org/wiki/Hashtab...mplexit.C3.A4t

*schulterzuck*

Müsste mich da definitiv weiter einlesen, um es erklären zu können. Mein Halbwissen ist mehr als gefährlich.

Ein Bekannter hat die Frage kürzlich in einem C-Kurs bearbeitet. Ich weiß nicht genau, ob es da auch um eine praktische Umsetzung ging oder nur um die "theoretische" Lösung. (Hashmaps in C möchte ich glaube ich nicht selbst erstellen.)

Mein spontaner Vorschlag war es, die größte Zahl aus beiden Arrays zu suchen, so viele Speicherstellen zu reservieren und zu "nullen" und dann die Idee von hts anzuwenden. Nur eben nicht mit einer Datenstruktur, sondern direkt mit den entsprechenden Positionen im Speicher. Das ist natürlich unglaublich ineffizient, sollte aber theoretisch in linearer Zeit ablaufen.

Ich nehme an, das ließe sich dann erheblich sparsamer als Baumstruktur anordnen. Wenn ich einen -- sagen wir -- 4 Byte langen Integer byteweise in einem 4 Ebenen tiefen Baum anordne, muss ich pro Ebene und Zweig 256 Einträge reservieren, aber nur noch diejenigen Zweige setzen, deren entsprechende Byteabfolge in der Eingabe auftaucht.

Da ich Speicherstellen direkt anspringen kann, wäre der Lookup für jede Zahl immer maximal vier Schritte.

Die Lösung dürfte noch immer massiven Overhead an Speicherverbrauch haben, aber nicht mehr massiven.

Das war jetzt das gefährliche Halbwissen, btw.

__________________
Blog | Buch | Kaloa

fab

Die PHP Arrays sind allerdings keine Hashtables in dem Sinne sondern Hashmaps ohne Kollisionen, damit sollte der Lookup tatsächlich genau in O(1) sein, ebenso wie bei "echten" Arrays (entspricht dem Vorschlag mit Speicherpositionen).

Aber auch bei mir: Wie genau Hashmaps in C realisiert sind weiß ich nicht also gefährliches Halbwissen Teil II

__________________
PHP Blog + Library
CSS Effects + Tools

Flor1an

Ja bei sowas ist es halt wichtig zu wissen wie die genannten Arrays funktionieren, wenn du wirklich "echte" Arrays hast die nen numerischen Index besitzen dann mag das eher funktionieren.

@hts: Du darfst die nächste Frage stellen.

Hash maps/tables sind eigentlich nicht so kompliziert. Es wird halt eine Hashfunktion auf den Key ausgeführt, dadurch kommt eben ein Integerwert heraus. Dieser Stellt dann die position da wo der Wert zum entsprechenden Key steht. Die Sache ist eben immer die größte der Hashtabelle, angenommen ich wähle eine mit 100 Werten, dann kann ich aber nicht 101 Elemente eindeutig abbilden und somit gibt es bei einem Hash zwei zugehörige Werte. Mehrere Einträge pro Hash können zum Beispiel durch eine verkettete Liste gespeichert werden. Heißt beim Lookup in der Hashtabelle wird zuerst der Hash des gesuchten Keys erzeugt, dann wird in der Tabelle an dieser Position nachgeschaut, angenommen es gibt dort mehrere Werte müssen diese eben einzeln durchlaufen werden. Eine ganz einfache Hashfunktion auf numerische Keys wäre einfach der modulo Operator. Für eine Hashtabelle mit 100 Werten wird dann einfach "Key modulo 100" genommen und somit ergibt sich der Hashwert.

fab

Danke für die Aufklärung, da hatte ich ein Brett vorm Kopf. Natürlich sind dann auch bei PHP Arrays Kollisionen möglich...

__________________
PHP Blog + Library
CSS Effects + Tools

Flor1an

Keine Ahnung wie genau Arrays implementiert sind in PHP kann ich dir nicht sagen, ist ja auch egal

Chriz

OK neuer Versuch:

Googlen zählt nicht.

__________________
"Nuschel ich?" - "Was?"

eagle275

da deine Reihe ziemlich kurz ist ....

8 bleibt als Lösung, da ja 6 falsch ist (dann wäre jeder Rechenschritt die Division durch 2 gewesen) ... bleibt nur die Frage, woher wissen die anderen Beteiligten ob ihre Rechnung gerade die Division ist oder doch die Subtraktion ...

1) 16 : 2 = 8
2) 8 - 4 = 4
3) 28 : 2 = 14
4) 12 - 4 = 8

__________________
"Irren ist männlich", sprach der Igel und stieg von der Drahtbürste