Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > de.comp.lang.java > #13214

Re: Bit packed array

Show all headers | View raw

> Am Donnerstag, 4. Oktober 2018 12:07:43 UTC+2 schrieb Patrick Roemer:
> > Responding to Heiner Kücker:
> > "The number of input and output combinations for trivial programs is
> > surprisingly large. It is astronomical for typical programs and beyond
> > comprehension for typical systems. [...] Clearly, we can never test all
> > inputs, states, or outputs."
> > Robert V. Binder, Testing Object-Oriented Systems
> > §3.3: The Limits of Testing
> > 
> > Das ist sehr gründlich gedacht, aber effektiv hast Du damit ja gar keine
> > Tests, weil niemand sie je (komplett) laufen lassen wird. Unit Tests
> > sollten eigentlich sogar nach jeder in sich abgeschlossenen
> > Code-Änderung automatisiert durchlaufen; das kannst Du mit diesem Ansatz
> > komplett knicken.
> > 
> > Üblicherweise wählt man für Unit Tests Szenarien mit (Kombinationen von)
> > Extremen oder besonders hervorgehobenen Elementen aus dem erlaubten
> > Bereich der Eingabewerte (hier etwa: 0, 1, Integer.SIZE,...) und einige
> > mehr oder minder zufällige Werte, die pars pro toto für die sonstige
> > Bandbreite stehen. Ergänzen kann man das durch randomisierte Tests a la
> > QuickCheck[1]. Da gibt es wohl auch diverse Java-Ports; keine Ahnung,
> > wie es sich damit arbeitet.
> > Viele Grüße
> > Patrick
> > 
> > [1] http://www.cse.chalmers.se/~rjmh/QuickCheck/manual.html

Ich habe die Tests für die arraycopy-Methoden des Bit-Packed-Array noch laufen und die dauern schon ziemlich lange.

Wie könnte man die Anzahl der ausgeführten Testfälle verringern, ohne die Korrektheit zu gefährden?

Eine Überlegung ist das Formulieren einer algebraischen Spezifikation.


Diese Zeile bedeutet nichts bzw. ich weiss es nicht:

	array[length]

Es gibt eine Variable length, für diese gilt:

	int length; length >= 0 && length <= Integer.MAX_INT

Es gibt eine Variable index, für diese gilt:

	int index; index >= 0 && index < length

Ein einzelner Wert aus der Anzahl length Werte wird geschrieben als:

	array[index]

Eventuell bekommt die erste Zeile dadurch doch irgendwie einen Sinn.

Nun die Methode arraycopy aus java.lang.System:

	public static native void arraycopy(
		Object src,
		int srcPos,
		Object dest,
		int destPos,
		int length);

Zur Vereinfachung sage ich mal:

src == dest == this

Dann ist die Signatur:

	public void arraycopy(
		int srcPos,
		int destPos,
		int length);

Es gibt einen Zustand /Inhalt des Arrays vor dem Ausführen der Methode arracopy und einen Zustand /Inhalt des Arrays danach.

Das Array nach dem Ausführen der Methode arraycopy nenne ich:

	array'

(Habe ich irgendwo schon mal gesehen)

Die Invariante wäre dann:


	                if (index >= destPos && index < destPos + Parameter length): array[index - (destPos - srcPos)]
	array'[index] =
	                else: array[index]

'Parameter length' bedeutet Parameter der Methode zur Unterscheidung von der Länge des Arrays.

Man könnte nun naiv über einen Wertebereich

		int Array length; length >= 0 && length <= Integer.MAX_INT

		array[index] >= Typ.MIN_VALUE && array[index] <= Typ.MAX_VALUE

laufen.

Das ist ganz schön viel.

Leider sind Spezifikation und Implementierung unterschiedliche Dinge.

Anhand der Spezifikation kann man nicht die Grenzfälle und Äquivalenzklassen der Implementierung erkennen.

Die Implementierung könnte einfach eine Tabelle/Map mit Zuordnung der Parameter und des vorherigen Zustandes zum Ergebniszustand sein (wahrscheinlich ist dies nicht die Implementierung, weil der Speicherbedarf ganz schön groß wäre).
Dann müßte man jede Kombination aus Parametern und Vorherzustand testen.

Also benötigt man scheinbar so etwas wie Code-Abdeckung.

Bekanntermaßen reicht Code-Abdeckung nicht aus, man muss auch Zweig-Abdeckung, Pfad-Abdeckung und Daten-Abdeckung beachten.

Hätte man also ein Tool, welches programmatisch die Abdeckung der einzelnen Code-Teile: Statements, Expressions, Bedingungen, Verzweigungen, Wiederholungen, Methoden-Aufrufe je Parametern und Vorherzustand des Arrays aufzeichnet, könnte man in einer Zuordnungs-Tabelle von Parametern und Vorherzuständen zu getesten Code-Teilen, die Parameter und Vorherzustände, die bestimmte Code-Teile redundant testen, finden.

Um darin ein System zu finden, benötigt man Intelligenz, hier droht also der Gödel.

Für einen wiederholten Test könnte man die redundant testenden Parameter und Vorherzustände aussparen.

Aber nach einer Änderung des Codes würde die vorherige Zuordnungstabelle nicht mehr gelten und das ganze müsste wiederholt werden.

Deshalb komme ich zu dem Schluß, dass die Anwendung einer solchen Einsparungsmethode ohne Intelligenz (Gödel) mindestens genauso aufwändig wie der sture Test wäre.

Wenn man aber Intelligenz anwendet, kann man sich irren und dadurch Fehler übersehen.

Eine Alternative wäre noch, dass während des Tests die Code-/Zweig-/Pfad-/Daten-Abdeckung geprüft wird und bei ausreichender Abdeckung abgebrochen wird.
Vor dem Abbrechen wären aber sicher jede Menge redundante Tests ausgeführt worden.

> Schöne Grüße
> Heiner

Back to de.comp.lang.java | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Bit packed array Heiner Kücker <mail@heinerkuecker.de> - 2018-09-22 19:33 -0700
  Re: Bit packed array Patrick Roemer <sangamon@netcologne.de> - 2018-10-01 09:46 +0200
    Re: Bit packed array Patrick Roemer <sangamon@netcologne.de> - 2018-10-02 10:21 +0200
    Re: Bit packed array Heiner Kücker <mail@heinerkuecker.de> - 2018-10-03 22:05 -0700
      Re: Bit packed array Patrick Roemer <sangamon@netcologne.de> - 2018-10-04 12:07 +0200
        Re: Bit packed array Heiner Kücker <mail@heinerkuecker.de> - 2018-10-04 03:34 -0700
          Re: Bit packed array Heiner Kücker <mail@heinerkuecker.de> - 2018-10-09 23:10 -0700
            Re: Bit packed array Patrick Roemer <sangamon@netcologne.de> - 2018-10-10 16:50 +0200
              Re: Bit packed array Joerg Meier <joergmmeier@arcor.de> - 2018-10-10 20:15 +0200
                Re: Bit packed array Heiner Kücker <mail@heinerkuecker.de> - 2018-10-10 23:17 -0700
                Mutation Testing (was: Bit packed array) Patrick Roemer <sangamon@netcologne.de> - 2018-10-12 12:12 +0200
              Re: Bit packed array Heiner Kücker <mail@heinerkuecker.de> - 2018-10-10 23:23 -0700

csiph-web