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

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

Re: Bit packed array

Show all headers | View raw

Responding to Heiner Kücker:
>> 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.

Ach? ;)

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

Gar nicht. Denn im Prinzip kann im Code jederzeit irgendwas stehen wie

if(dataElementWidth == 637450152 && arraySize == 994637 && ...) {
  throw new JustKiddingException();
}

Will meinen, wenn Du nicht alle möglichen Kombinationen von
Eingabewerten prüfst, ist die Korrektheit "gefährdet". Da das nicht
möglich ist, muss man sich mit pragmatischeren Ansätzen bescheiden.

> Eine Überlegung ist das Formulieren einer algebraischen Spezifikation.

Das ist genau der Ansatz hinter QuickCheck. Anders als bei klassischen
Unit-Tests, die um konkrete Beispielszenarien herum gebaut sind,
formuliert man "Gesetze", die für alle möglichen Szenarien
(Kombinationen von Eingabewerten,...) gelten müssen. Statt dann aber den
kompletten Wertebereich zu durchlaufen, wie Du es versuchst, begnügt man
sich pro Testlauf mit einer überschaubaren Menge randomisiert erstellter
Szenarien. Damit hat man die Hoffnung, dass Fehler, die eine große
Teilmenge der möglichen Szenarien betreffen, in so gut wie jedem Lauf
auffallen sollten, und Fehler, die nur eine kleine Teilmenge betreffen,
wenigstens eine Chance haben, früher oder später ins Netz zu gehen.

Zusätzlich sollte man natürlich immer noch klassische Tests haben, die
Grenzfälle, typische Szenarien, etc. deterministisch prüfen. Und die
muss man halt mit einer Mischung von strukturierter Analyse, gesundem
Menschenverstand, Erfahrung und Bauchgefühl auswählen, wobei die
Dekompositionshierarchie einen unterstützen oder, wenn schlecht gewählt,
auch sabotieren kann.

Es ist ja kein Zufall, dass der oben zitierte Binder ein Ziegelstein mit
über 1000 Seiten ist - und nur eines von unzähligen Werken über
Testdesign und -strategien...

> Leider sind Spezifikation und Implementierung unterschiedliche Dinge.
> 
> Anhand der Spezifikation kann man nicht die Grenzfälle und Äquivalenzklassen
> der Implementierung erkennen.

Man will die Tests aber nicht von der Implementierung abhängig machen,
weil die eventuell beim Schreiben der Tests noch gar nicht (vollständig)
existiert, und weil sie sich wiederum jederzeit ändern kann.

> 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.

Und das Halteproblem. Und wiederum die kombinatorische Explosion auf
dieser Ebene. Und, und, und...

Nur als Scherz am Rande, weil von der Idee her verwandt: Es gab da mal
ein Tool[1], das Änderungen im Code vorgenommen hat und dann die Tests
dagegen laufen ließ - wenn die noch grün liefen, war die geänderte
Stelle nicht hinreichend abgedeckt. Nette Idee, aber die
Praxistauglichkeit...

Viele Grüße
Patrick

[1] http://jester.sourceforge.net/

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