Assoziatives, mehrdimensionales Array sortieren

[Rolf B]

Hallo 1unitedpower,

ich bin durchaus für Zeilenarrays und finde Spaltenarrays ebenfalls nur für spezielle Anwendungsfälle geeignet, aber hier hast Du Dich vergallopiert, meine ich:

Wenn n die Anzahl der Datensätze ist, und m die Anzahl der Felder in einem Datensatz, dann hat ein direkter Lesezugriff die Komplexitätsklasse O(1) in einem Zeilenarray, in einem Spaltenarray aber O(m)

In einem Array aus Zeilenarrays habe ich beim Zugriff auf t Werte einer Zeile einen Arrayzugriff um das Zeilenarray aus dem Haupt-Array zu holen, und dann t Array-Zugriffe für die Felder. Insgesamt t+1 Arrayzugriffe, das ist O(t). Wenn ich n Zeilen verarbeite, habe ich n Zugriffe für die Zeilenarrays und n*t Zugriffe für die Werte, also n(t+1) Arrayzugriffe. Das ist O(nt). Auch, wenn ich das Hauptarray mit foreach verarbeite, ist jeder foreach-Schritt ein Zeilenzugriff. Zwar schneller, aber trotzdem ein Zugriff. Es bleibt O(nt).

In Array aus Spaltenarrays habe ich je Feld einen Zugriff auf den Spaltenkopf und einen für den Zeileneintrag, also 2t, aber trotzdem O(t). Wenn ich n Zeilen verarbeite und die Spaltenköpfe cache, habe ich t Zugriffe für's cachen und n*t Zugriffe für die Werte, also (n+1)t Arrayzugriffe. Ohne Cache hätte ich 2nt Arrayzugriffe. Das ist aber immer noch O(nt).

D.h. für eine einzelne Zeile bin ich in beiden Fällen O(t) und für n Zeilen in beiden Fällen O(nt). In der Komplexitätsklasse ergibt sich kein Unterschied.

In der realen Laufzeit dürfte es sich aber schon unterscheiden. Wenn ich die Zeilen per Key abrufen muss und kein foreach verwenden kann, hat das Spaltenarray mit gecachten Spaltenköpfen ggf. einen kleinen Vorteil. Wenn es darum geht, auf einer einzigen Spalte zu aggregieren oder zu sortieren, dürfte das Spaltenarray ebenfalls von Vorteil sein. Nicht in der Größenordnung, aber in absoluter Laufzeit.

Unter dem Strich glaube ich aber trotzdem an die Vorteile des Zeilenarrays. Wenn ich eine Zeile an eine Funktion als Parameter übergeben will, ist das bei Zeilenarrays deutlich einfacher. Wenn ich eine neue Zeile aus einer Funktion zurückbekomme (z.B. $mysqli->fetch_assoc()), ist sie an ein Zeilenarray deutlich leichter anzuhängen.

Rolf