Speicherbedarf eines Strings? (als Byteangabe oder über andere Datentypen)

e86

Gibt es eine standardisierte Angabe für den Speicherbedarf eines Strings? Ich benötige die Angabe in Byte oder irgendetwas ähnlichem.

Meine ersten Anlaufstellen waren:

IEEE 754 (leider nur für Gleitkommawerte)
diverese Vorlesungsskripte von Universitäten (u.a. auch unsere eigene)
http://www.galileocomputing.de/openbook/javainsel6/ (da wir mit Java arbeiten)

Es gab auch mal die Information, dass ein String eine Menge von char-Variablen ist. Nur aus wievielen und mit welcher Bytegröße?

Grüße

MrBurns

http://de.wikipedia.org/wiki/Zeichenkodierung

Bashar

e86 schrieb:

Gibt es eine standardisierte Angabe für den Speicherbedarf eines Strings? Ich benötige die Angabe in Byte oder irgendetwas ähnlichem.

Das hängt davon ab, wie der String repräsentiert ist. In C sind Strings üblicherweise char-Arrays, die durch 0 terminiert sind. Der Speicherbedarf ist folglich strlen(str) + 1 Bytes.
In Java sieht das schon schwerer aus, da Strings Objekte mit undurchsichtiger interner Struktur sind. Man kann auf jeden Fall sagen, dass jedes Zeichen des Strings ein char ist und somit (wegen Unicode) 2 Bytes verbraucht, aber irgendwo muss auch noch die Länge gespeichert werden und vielleicht noch einiges mehr, das weiß man nicht so ohne weiteres.

e86

Ich habe das hier nicht direkt als Programm zu bearbeiten, sondern rein formell. Es geht um Algorithmen und Datenstrukturen. (Uni, Informatik)

Mein Problem ist einfach: Gibt es überhaupt eine standardisierte Angabe einer Speicherlänge bei Strings? Welche Sprache wäre da erstmal egal.

Ein weiterführender Link aus deiner Angabe, MrBurns, zeigt den ISO 8859. Dort ist die ASCII-Tabelle aufgelistet und da wird jedes Zeichen mit 8 Bit kodiert. Also wären es nicht 2 Byte, sondern nur noch 1 Byte pro char?

UPDATE: Sehe gerade, dass es noch Unicode gibt. Also müsste man zwischen UNICODE und UTF-8 noch unterscheiden?

Grüße

Es kommt ja darauf an, wie die einzelnen Zeichen gespeichert werden. Sprich: Latin1, Latin9, UTF-8, UTF-16, UTF-32 ... Und bei jedem Zeichensatz belegt jeder einzelne Buchstabe entsprechend anders viele Bytes als bei einem anderen Zeichensatz. Bei manchen Unicode-Derivaten können sogar einzelne zeichen unterschiedlich viele Bytes belegen. Eine allgemeingültige Aussage kann es daher imho nicht geben. Höchstens eine pro Sprache.

e86

Zweifle langsam daran, dass ich die Aufgabe richtig bearbeite. Wir haben hier eine "einfaches verkettete Liste" aus Wörtern (also Strings). Und davor sollen wir (formell?) den Speicherbedarf berechnen. Es gibt hingegen keine Angabe für eine Sprache oder ein Sprachsystem (Latin, UTF...)

Gregor

Es gibt da eigentlich keinen Standard. Java macht diesbezüglich auch keine genauen Zusicherungen. Du kannst in Java allerdings eine Untergrenze abschätzen:

Du hast in Java mindestens:

1. Eine Referenz auf den String: 4 Byte (bei einer 32-Bit JVM)
2. 8 Byte Overhead für jedes Objekt.

...und wenn der String intern als char-Array abgespeichert wird, was relativ wahrscheinlich ist:

3. nochmal 8 Byte Overhead.
4. Die Referenz auf das char-Array: 4 Byte (bei einer 32-Bit JVM)
5. eine int-Variable, in der die Länge des Arrays steht: 4 Byte
6. 2 Byte für jedes Zeichen des Strings. (ein char hat 16 Bit)

Ein String "Hallo" hat in Java also vermutlich eine Größe von etwa 38 Byte. ...In C++ kommst Du vermutlich mit 6 Byte oder so aus.

Ich bin mir aber nicht sicher, ob das interne char-Array immer minimal ist. Es könnte auch sein, dass in einem String-Objekt ein Anfangs- und Endindex für das Array gespeichert wird und das eigentliche Array auch länger sein kann. Soetwas könnte dann Sinn machen, wenn man häufig Substrings braucht. Diesbezüglich würde ich Dir empfehlen, einfach mal in den Quellcode von java.lang.String zu gucken.

...aber das ganze ist in Java sogar noch komplizierter:

Nicht jeder String ist in Java auch gleich ein neuer String. Angenommen, Du hast soetwas:

public class A
{
   private String a = "Hallo";
}

public class B
{
   public String b = "Hallo";
}

In dem Fall erkennt Java, dass es zwei identische Strings sind. Entsprechend wird nur einer erzeugt: Strings sind in Java schließlich immutable, können also nicht verändert werden. Zumindest hast Du in diesem Fall nur ein einziges String-Objekt mit 2 Referenzen auf dieses Objekt. Du kannst allerdings auch zwei gleiche Strings haben, die nicht durch das selbe Objekt representiert werden: Zum Beispiel, wenn Du in dem Code da oben etwas wie "new String("Hallo");" geschrieben hättest.

Also letztendlich gilt: In Java kannst Du die Größe eines Strings praktisch nicht berechnen. Es wird da auch Unterschiede zwischen unterschiedlichen JVMs geben.

e86

Danke für den ausführlichen Beitrag.

Du gehst von einem Array aus. Nur bin ich mir grad nicht so sicher, ob dass nicht nur für Arrays gilt und "einfach verkettete Listen" anders behandelt werden? Laut unseren Skripten wird da unterschieden. Andererseits könnte es ja auch sein, dass Java da nicht unterscheidet (unterscheiden kann) und man verkettete Listen nur in Form von Arrays implementieren kann.

Bashar

e86 schrieb:

Zweifle langsam daran, dass ich die Aufgabe richtig bearbeite. Wir haben hier eine "einfaches verkettete Liste" aus Wörtern (also Strings). Und davor sollen wir (formell?) den Speicherbedarf berechnen. Es gibt hingegen keine Angabe für eine Sprache oder ein Sprachsystem (Latin, UTF...)

Kannst du mal bitte den Aufgabentext zitieren?

e86

Ja, gern.

1. (6 Punkte) Verkettete Listen: Gegeben sei eine einfach verkettete leere Liste zum Speichern von Strings mit einem Zeiger auf das erste Listenelement. Fügen Sie nacheinander die folgenden Elemente in diese Liste ein: Elbe Spree Pleiße Aue Elster Parthe

b.) (2 Punkte) Wie viel zusätzlicher Speicherplatz wird bei dieser Art von
Speicherung benötigt? Rechnen Sie auch den konkreten zusätzlichen Platz für die
obige Liste aus, inklusive des Zeigers auf die Liste selbst.

Gregor

e86 schrieb:

Danke für den ausführlichen Beitrag.

Du gehst von einem Array aus. Nur bin ich mir grad nicht so sicher, ob dass nicht nur für Arrays gilt und "einfach verkettete Listen" anders behandelt werden? Laut unseren Skripten wird da unterschieden. Andererseits könnte es ja auch sein, dass Java da nicht unterscheidet (unterscheiden kann) und man verkettete Listen nur in Form von Arrays implementieren kann.

Du hast doch eine Liste von Strings und nicht einen String, der aus einer Liste besteht? Oder habe ich das falsch verstanden? Natürlich kann man Strings auch über Listen implementieren. Und natürlich kann man Listen auch in Java implementieren (siehe z.B. java.util.LinkedList). Ich habe eher das angegeben, was ich in der Referenzimplementierung vermute. Ich glaube nicht, dass Strings in Java über eine Liste implementiert sind. Das würde alleine deshalb schon keinen Sinn machen, weil Strings immutable sind. Listen haben aber gerade dann einen Vorteil, wenn man damit in der Art arbeitet, dass man hier mal etwas ausschneidet oder da mal etwas dazwischensteckt oder ähnliches macht.

Gregor

e86 schrieb:

b.) (2 Punkte) Wie viel zusätzlicher Speicherplatz wird bei dieser Art von
Speicherung benötigt? Rechnen Sie auch den konkreten zusätzlichen Platz für die
obige Liste aus, inklusive des Zeigers auf die Liste selbst.

Der Trick liegt hier vermutlich im Wort "zusätzlich". Was ist die Alternative, mit der man da vergleichen soll?

e86

Alternative? Meinst du eine andere Vorgehensweise in einer anderen Sprache oder ähnlichem? Die Problematik mit den Zeigern habe ich erstmal herausgelassen, da ich mich erstmal um die Strings an sich kümmern wollte. Aber solangsam denke ich, sind die Zeiger sehr wichtig und müssen mit rein. (und können nicht erst am Ende "dazuaddiert" werden.)

Gregor

e86 schrieb:

Alternative? Meinst du eine andere Vorgehensweise in einer anderen Sprache oder ähnlichem? Die Problematik mit den Zeigern habe ich erstmal herausgelassen, da ich mich erstmal um die Strings an sich kümmern wollte. Aber solangsam denke ich, sind die Zeiger sehr wichtig und müssen mit rein. (und können nicht erst am Ende "dazuaddiert" werden.)

Du wirst Dich gar nicht um die Strings kümmern müssen. Wenn sie nach dem zusätzlichen Speicherplatz fragen, dann ist die Ausgangssituation definitiv so, dass die Strings schon existieren und nicht für den _zusätzlichen_ Speicherbedarf relevant sind. Es geht letztendlich nur um die Liste.

Vermutlich sollst Du da mal zeigen, dass Du weißt, wie so eine Liste aufgebaut ist. Was wird wo in einer Liste referenziert usw..

Th

Ich glaube, du hast die Aufgabe etwas mißverstanden.
Ich denke gemeint ist, daß du den zusätzlichen Speicherbedarf für die Linked-List angeben sollst, d.h. dass jedes Element der Liste einen Zeiger auf das nächste Element verwalten muß. (im Gegensatz zu einem Array)

Th schrieb:

Ich glaube, du hast die Aufgabe etwas mißverstanden.
Ich denke gemeint ist, daß du den zusätzlichen Speicherbedarf für die Linked-List angeben sollst, d.h. dass jedes Element der Liste einen Zeiger auf das nächste Element verwalten muß. (im Gegensatz zu einem Array)

selbst dann ist die aufgabe schlecht formuliert. ist es nun ein:

struct list_entry
{
  struct list_entry *next;
  char *string;
};

oder ein

struct list_entry
{
  struct list_entry *next;
  char string[MAX];
};

?
und ausserdem ist nirgends erwähnt, wie breit ein pointer ist.

Bei fehlenden Angaben bitte selbst eine Annahme treffen und diese aufschreiben.

Blue-Tiger

mies gemachte aufgabe schrieb:

Th schrieb:

Ich glaube, du hast die Aufgabe etwas mißverstanden.
Ich denke gemeint ist, daß du den zusätzlichen Speicherbedarf für die Linked-List angeben sollst, d.h. dass jedes Element der Liste einen Zeiger auf das nächste Element verwalten muß. (im Gegensatz zu einem Array)

selbst dann ist die aufgabe schlecht formuliert. ist es nun ein:
struct list_entry
{
  struct list_entry *next;
  char *string;
};
oder ein
struct list_entry
{
  struct list_entry *next;
  char string[MAX];
};
?
und ausserdem ist nirgends erwähnt, wie breit ein pointer ist.

Ich find die Aufgabe eindeutig formuliert: da wir von Java reden, wird dir der gesunde Menschenverstand sagen, dass ein Listenelement aus einer Referenz zum naechsten Element sowie einer Referenz auf den String besteht (und weil das nach einer Einfuehrungs-Vorlesung klingt, wirds vermutlich keine Rolle spielen dass jedes Element zusaetzlich noch 16 Bytes benoetigt).
Und wie Breit eine Referenz ist, spielt auch keine Rolle, weil er die Groesse ja in sizeof(Reference) angeben kann.

Zeus

Sind die Aufagben aus der Theoretische Informatik? Wenn ja dann will dein Prof evtl. sowas sehen

String speichern in Array:
Speicherbedarf: O(N+1)

String in eine Liste:
Speicherbedarf: O(NP+2) bei SingleLinked
O(N2P+2) bei DoubleLinked

Th

Den Speicherbedarf mit Hilfe der O-Notation zu beschreiben, macht absolut keinen Sinn.
Und wie groß der Speicherbedarf für einen Zeiger ist, ist auch (für diese Frage) irrelevant, nur daß er eben pro Listenelement benötigt wird.