Grundlagen der funktionsorientierten Programmierung mit SCHEME/QuickSort
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
<code id="4bf25ec86e452" hidden>
;-- M. Hielscher / Chr. Wagenknecht / V. Berger --
(define random-maker
(let* ((multiplier 48271)
(modulus 2147483647)
(apply-congruence
(lambda (current-seed)
(let ((candidate (modulo (* current-seed multiplier) modulus)))
(if (zero? candidate)
modulus
candidate))))
(coerce
(lambda (proposed-seed)
(if (integer? proposed-seed)
(- modulus (modulo proposed-seed modulus)) 19880214))))
(lambda (initial-seed)
(let ((seed (coerce initial-seed)))
(lambda args
(cond ((null? args)
(set! seed (apply-congruence seed))
(/ (- modulus seed) modulus))
((null? (cdr args))
(let* ((proposed-top
(ceiling (abs (car args))))
(exact-top
(if (inexact? proposed-top)
(inexact->exact proposed-top)
proposed-top))
(top
(if (zero? exact-top)
1
exact-top)))
(set! seed (apply-congruence seed))
(inexact->exact (floor (* top (/ seed modulus))))))
((eq? (cadr args) 'reset)
(set! seed (coerce (car args))))
(else
(display "random: unrecognized message")
(newline))))))))
(require-library 'sisc/libs/srfi/srfi-19)
(import srfi-19) ; stellt current-time usw. bereit
(define random (random-maker (time-nanosecond (current-time))))
(define listequal?
(lambda (ls1 ls2)
(cond
[(and (null? ls1) (null? ls2)) #t]
[(or (null? ls1) (null? ls2)) #f]
[(and (list? (car ls1)) (list? (car ls1)))
(and (listequal? (car ls1) (car ls2)) (listequal? (cdr ls1) (cdr ls2)))]
[else
(and (equal? (car ls1) (car ls2)) (listequal? (cdr ls1) (cdr ls2)))])))
(define rand 50)
(define maxbreite (- 400 (* 2 rand)))
(define maxhoehe (- 300 (* 2 rand)))
(define minmax
(lambda (ls)
(letrec
([extremsuche
(lambda (extrem ls op)
(cond
[(null? ls) extrem]
[(op extrem (car ls)) (extremsuche (car ls) (cdr ls) op)]
[else
(extremsuche extrem (cdr ls) op)]))])
(cons (extremsuche 0 ls >)
(extremsuche 0 ls <)))))
(define balken
(lambda (hoehe breite turtle)
(forward turtle breite) (left turtle 90)
(forward turtle hoehe) (left turtle 90)
(forward turtle breite) (left turtle 90)
(forward turtle hoehe) (left turtle 90)
(forward turtle breite)))
(define balkendiagramm
(lambda (ls canvas turtle)
(let* ([breite (/ maxbreite (length ls))]
[extremwerte (minmax ls)]
[min (car extremwerte)] [max (cdr extremwerte)])
(letrec
([zeichnen
(lambda (min max ls)
(if (null? ls)
'ok
(begin
(balken (* (/ (car ls) (- max min)) maxhoehe) breite turtle)
(zeichnen min max (cdr ls)))))])
(clear canvas)
(hide turtle)
(move turtle rand (+ rand (* (/ max (- max min)) maxhoehe))) (right turtle 90)
(zeichnen min max ls)))))
</code>
== Algorithmus ==
Die Zweifel an der Effizienz von MinSort unter den Sortieralgorithmen sind berechtigt.<br />
Wir betrachten deshalb den nachfolgenden Algorithmus und implementieren ihn.
'''Beschreibung:'''
* Benutze das erste Element einer (numerischen) Liste als Trennelement.
* Erzeuge zwei Teillisten, deren Elemente kleiner bzw. größer als das Trennelement sind.
* Setze dieses Verfahren für jede nichtleere Teilliste fort und
* füge die sortierten Teillisten zur Gesamtliste zusammen.
[[Datei:Hoare.jpg|miniatur|C.A.R. Hoare]]
Den so beschriebenen Sortieralgorithmus bezeichnet man als ''QuickSort'' (schnelles Sortieren). Er wurde 1962 von dem britischen Informatiker Sir '''Charles Antony Richard Hoare''' (* 11. Januar 1934) vorgestellt.
'''Beispiel:'''
<blockquote>[[Bild:QuickSort-Beispiel1.gif]]</blockquote>
'''Implementation:'''
<code id="4bf43ee409dc7">
(define zufallszahl
(lambda (min max)
(+ (random (- max min -1)) min)))
(define zufallsliste
(lambda (min max anzahl)
(if (= anzahl 0)
()
(cons (zufallszahl min max) (zufallsliste min max (- anzahl 1))))))
;Erzeuge zwei Teillisten, deren Elemente bezüglich eines Trennelementes vorsortiert sind
(define zerlegen
(lambda (el ls)
(if (null? ls)
(list () ())
(let ([tls (zerlegen el (cdr ls))])
;hier erfolgt die korrekte Einordnung des ersten Listenelements
;in die bereits vorhandene erste oder zweite Teilliste
...))))
;QuickSort
(define quicksort
(lambda (ls)
(if (null? ls)
()
(let ([tls (zerlegen (car ls) (cdr ls))])
;hier werden
;- die sortierte erste Teilliste,
;- das Trennelement (als einelementige Liste),
;- die sortierte zweite Teilliste
;zusammengesetzt
...))))
</code>
<check>
(listequal? (quicksort '(12 4 5 6 33 2 6 7 1 47)) '(1 2 4 5 6 6 7 12 33 47))
</check>
<table border="0" cellpadding="0" cellspacing="0">
<tr>
<td align="center">
'''Ungeordnete Zufallszahlen:'''
<canvas w="400" h="300"></canvas>
</td>
<td> </td>
<td align="center">
'''Geordnete Zufallszahlen:'''
<canvas w="400" h="300"></canvas>
</td>
</tr>
</table>
<eval id="4bf25ec87038c">
(define ls (zufallsliste 1 1000 100))
(balkendiagramm ls canvas1 turtle1)
(define ls-sort (quicksort ls))
(balkendiagramm ls-sort canvas2 turtle2)
</eval>
== Effizienz von QuickSort ==
=== Experimente zum Zeitaufwand ===
Wir wollen uns auf die empirische Analyse des Zeitaufwands von QuickSort beschränken und definieren dazu:
<code id="4bf26382b419d">
(define count 0)
(define quicksort-aufwand
(lambda (ls)
(letrec
([zerlege
(lambda (el ls)
(if (null? ls)
(list () ())
(let ([tls (zerlege el (cdr ls))])
(set! count (+ 1 count)) ;Zerlegen in Teillisten
(if (< (car ls) el)
(list (cons (car ls) (car tls)) (cadr tls))
(list (car tls) (cons (car ls) (cadr tls)))))))])
(if (null? ls)
()
(let ([tls (zerlege (car ls) (cdr ls))])
(set! count (+ 1 count)) ;Zusammensetzen der Teillisten
(append (quicksort-aufwand (car tls))
(list (car ls))
(quicksort-aufwand (cadr tls))))))))
(define quicksort-ausgabe
(lambda (min max anzahl)
(let ([ls (zufallsliste min max anzahl)])
(set! count 0)
(display "Ungeordnete Zufallszahlen:") (newline)
(display ls) (newline)
(display "Geordnete Zufallszahlen:") (newline)
(display (quicksort-aufwand ls)) (newline)
(display "Anzahl der Zerlegungen und Zusammensetzungen: ") (display count) (newline)
'ok)))
</code>
<eval id="4bf26382b512d">
(quicksort-ausgabe 1 1000 20)
</eval>
Die ersten Tests zeigen: QuickSort scheint deutlich effizienter als MinSort zu sein.<br />
Wir überprüfen diese Vermutung mit den bekannten Prozeduren für Mehrfachexperimente sowie den entsprechenden grafischen Darstellungen:
<code id="4bf2a0ffe0fd7">
(define quicksort-mehrfach
(lambda (min max anzahl whlg)
(letrec
([summe
(lambda (n)
(if (= n 0)
0
(begin
(set! count 0)
(quicksort-aufwand (zufallsliste min max anzahl))
(+ count (summe (- n 1))))))])
(exact->inexact (/ (summe whlg) whlg)))))
</code>
<eval id="4bf2a0ffe3eb6">
(quicksort-mehrfach 1 1000 20 100)
</eval>
<code id="4bf2a0ffe1f75">
(define experiment
(lambda (min max anzahl schrittweite whlg)
(if (< anzahl 1)
()
(append (experiment min max (- anzahl schrittweite) schrittweite whlg)
(list (quicksort-mehrfach min max anzahl whlg))))))
</code>
'''Achtung!''' In Erwartung einer besseren Laufzeit wollen wir im Vergleich zu MinSort mit höheren Wiederholraten experimentieren.
<canvas w="400" h="300"></canvas>
<eval id="4bf2a0ffe4e54">
(balkendiagramm (experiment 1 1000 200 5 50) canvas3 turtle3)
</eval>
Abschließend wollen wir die Effizienz an einer bereits sortierten Liste untersuchen. Der ''von uns implementierte'' QuickSort-Algorithmus führt dazu, dass die jeweils linke Teilliste leer bleibt. Damit werden bei gleichen Listenlängen größere Rekursionstiefen notwendig, was auch zu einem größeren Zeitaufwand führen muss.<br />
Wir untersuchen also QuickSort im ''Worst-case-Fall'':
<code id="4bf2dfa23a16a">
(define quicksort-worst-case
(lambda (min max anzahl)
(set! count 0)
(quicksort-aufwand (quicksort (zufallsliste min max anzahl)))
count))
(define experiment-worst-case
(lambda (min max anzahl schrittweite)
(if (< anzahl 1)
()
(append (experiment-worst-case min max (- anzahl schrittweite) schrittweite)
(list (quicksort-worst-case min max anzahl))))))
</code>
'''Beachte:''' Beim Experimentieren mit dem Worst-case-Fall sind keine Wiederholungen notwendig.
<canvas w="400" h="300"></canvas>
<eval id="4bf2dfa23ae8c">
(balkendiagramm (experiment-worst-case 1 1000 200 5) canvas4 turtle4)
</eval>
=== Aufgaben ===
<ol>
<li>
Belegen Sie durch eigene empirische Untersuchungen, dass für den QuickSort-Algorithmus im Mittel gilt: <math>T(n) = \mathcal{O}(n \cdot \log_2 n)</math>
</li>
<li>
Bestätigen Sie ebenfalls durch geeignete Untersuchungen, dass QuickSort im Worst-Case-Fall einem quadratischen Zeitaufwand unterliegt.
</li>
<li>
Unterbreiten Sie Vorschläge, wie der Worst-Case-Fall in der Praxis weitestgehend vermieden werden kann.
</li>
</ol>
== Zusammenfassung ==
QuickSort ist ein typisches Beispiel für ''Teile-und-herrsche-Algorithmen'' (engl.: divide and conquer):<br />
Allgemein wird ein Problem gelöst, indem man es
<ol>
<li>in Teilprobleme zerlegt (teile - divide),</li>
<li>diese Teilprobleme löst (herrsche - conquer) und</li>
<li>die Teillösungen zur Gesamtlösung zusammensetzt.</li>
</ol>
Für den Quicksort-Algorithmus lassen sich folgende Abhängigkeiten und Zeitaufwandsklassen angeben:
<table border="0" cellspace="0" cellpadding="4">
<tr valign="top">
<td rowspan="2"><b>best case: </b></td>
<td><math>T(n) = n \cdot \log_2 n</math> bzw.</td>
</tr>
<tr>
<td><math>T(n) = \mathcal{O}(n \cdot \log_2 n)</math></td>
</tr>
<tr valign="top">
<td rowspan="2"><b>average case: </b></td>
<td><math>T(n) = 2 \cdot n \cdot \ln n \approx 1.386 \cdot n \cdot \log_2 n</math> bzw.</td>
</tr>
<tr>
<td><math>T(n) = \mathcal{O}(n \cdot \log_2 n)</math></td>
</tr>
<tr valign="top">
<td rowspan="2"><b>worst case: </b></td>
<td><math>T(n) = \frac{n}{2} \cdot (n+1)</math> bzw.</td>
</tr>
<tr>
<td><math>T(n) = \mathcal{O}(n^2)</math></td>
</tr>
</table>
Im Mittel ist also QuickSort deutlich effizienter als MinSort. Im ungünstigsten Fall kann es aber ebenso ineffizient werden.<br />
Wir wollen die konkreten Funktionen zum Zeitaufwand von QuickSort vergleichend gegenüberstellen:
<code id="4bf2ee1800b49">
(define x-von 0)
(define x-bis 100)
(define y-von 0)
(define y-bis 1000)
(define log2
(lambda (x)
(/ (log x) (log 2))))
(define qs-best-case
(lambda (x)
(* x (log2 x))))
(define qs-average-case
(lambda (x)
(* 1.386 x (log2 x))))
(define qs-worst-case
(lambda (x)
(* x (+ x 1))))
</code>
<canvas w="610" h="460"></canvas>
<code id="4bf2ee1806917" hidden>
(define sqr
(lambda (x)
(* x x)))
(clear canvas5)
(define genau 6)
(define width 610)
(define height 460)
(define black
(lambda (canvas5)
(setcolor canvas5 0 0 0)))
(define red
(lambda (canvas5)
(setcolor canvas5 255 0 0)))
(define brown
(lambda (canvas5)
(setcolor canvas5 100 50 0)))
(define orange
(lambda (canvas5)
(setcolor canvas5 255 100 0)))
(define yellow
(lambda (canvas5)
(setcolor canvas5 255 200 0)))
(define green
(lambda (canvas5)
(setcolor canvas5 0 255 0)))
(define blue
(lambda (canvas5)
(setcolor canvas5 0 0 255)))
(define pink
(lambda (canvas5)
(setcolor canvas5 200 50 200)))
(define n-tes-mod
(lambda (ls anz)
(list-ref ls (modulo anz (length ls)))))
(define genaurunden
(lambda (x anz)
(let ([n 0] [erg 0])
(if (not (= x 0))
(set! n (inexact->exact (round (- anz (/ (log (abs x)) (log 10)) -0.5)))))
(set! erg (/ (round (* x (expt 10 n))) (expt 10 n)))
(if (integer? erg)
(inexact->exact erg)
(exact->inexact erg)))))
(define groessenordnung
(lambda (x)
(if (= x 0)
1
(let ([pot (/ (log (abs x)) (log 10))])
(genaurunden (expt 10 (floor pot)) genau)))))
(define min
(lambda (x y)
(if (< x y)
(if (> x 0) 0 x)
(if (> y 0) 0 y))))
(define max
(lambda (x y)
(if (> x y)
(if (< x 0) 0 x)
(if (< y 0) 0 y))))
(define ungleich-null
(lambda (x y)
(if (= x y 0) (+ y 1) y)))
(define schaubild
(lambda (fkt-list x1 x2 y1 y2 von bis koordcolor color-list)
(clear canvas5)
(setwidth canvas5 1)
(let* ([textgroesse 9]
[rand 50]
[xu (exact->inexact (min x1 x2))] [xo (exact->inexact (max x1 x2))] [xo (ungleich-null xu xo)]
[yu (exact->inexact (min y1 y2))] [yo (exact->inexact (max y1 y2))] [yo (ungleich-null yu yo)]
[spmin rand] [spmax (- width rand)] [spend (+ spmax 15)]
[zemin (- height rand)] [zemax rand] [zeend (- zemax 15)]
[s0 (+ (* (/ (- xu) (- xo xu)) (- spmax spmin)) spmin)]
[z0 (+ (* (/ (- yu) (- yo yu)) (- zemax zemin)) zemin)]
[spvon (+ (* (/ (- von xu) (- xo xu)) (- spmax spmin)) spmin)]
[spbis (+ (* (/ (- bis xu) (- xo xu)) (- spmax spmin)) spmin)]
[mx (- xo xu)] [teilerx 1] [stepx (/ (- spmax spmin) mx teilerx)] [ex mx] [faktorx 1]
[my (- yo yu)] [teilery 1] [stepy (/ (- zemin zemax) my teilery)] [ey my] [faktory 1])
(letrec
([anpassen
(lambda (m)
(if (> m 2)
(if (<= m 20)
m
(anpassen (/ m 10)))
(if (> m 2)
m
(anpassen (* m 10)))))]
[teilen
(lambda (m)
(cond
[(< m 3) 5]
[(< m 10) 2]
[else 1]))]
[x-teilen-positiv
(lambda (sx)
(if (< sx (+ spmax 1))
(begin
(line canvas5 sx z0 sx (- z0 3))
(x-teilen-positiv (+ sx stepx)))))]
[x-teilen-negativ
(lambda (sx)
(if (> sx (- spmin 1))
(begin
(line canvas5 sx z0 sx (- z0 3))
(x-teilen-negativ (- sx stepx)))))]
[y-teilen-positiv
(lambda (zy)
(if (> zy (- zemax 1))
(begin
(line canvas5 s0 zy (+ s0 3) zy)
(y-teilen-positiv (- zy stepy)))))]
[y-teilen-negativ
(lambda (zy)
(if (< zy (+ zemin 1))
(begin
(line canvas5 s0 zy (+ s0 3) zy)
(y-teilen-negativ (+ zy stepy)))))]
[faktor
(lambda (len step)
(if (<= len step)
1
(+ 1 (faktor (- len step) step))))]
[textwidth
(lambda (str)
(* textgroesse (string-length str)))]
[textout-widthcenter
(lambda (sx zy str)
(if (integer? (string->number str))
(text canvas5 (- sx (/ (textwidth str) 2))
(+ zy (/ textgroesse 2/3)) str textgroesse)
(text canvas5 (- sx (/ (textwidth str) 2) (- (/ textgroesse 2)))
(+ zy (/ textgroesse 2/3)) str textgroesse)))]
[textout-heightcenter
(lambda (sx zy str)
(if (integer? (string->number str))
(text canvas5 (- sx (textwidth str) 2)
(+ zy (/ textgroesse 2)) str textgroesse)
(text canvas5 (- sx (textwidth str) (- (/ textgroesse 2)))
(+ zy (/ textgroesse 2)) str textgroesse)))]
[x-bezeichnen-positiv
(lambda (sx e)
(if (< sx (+ spmax 1))
(begin
(textout-widthcenter sx z0 (number->string (genaurunden e genau)))
(x-bezeichnen-positiv (+ sx (* stepx faktorx)) (+ e (* ex faktorx))))))]
[x-bezeichnen-negativ
(lambda (sx e)
(if (> sx (- spmin 1))
(begin
(textout-widthcenter sx z0 (number->string (genaurunden e genau)))
(x-bezeichnen-negativ (- sx (* stepx faktorx)) (- e (* ex faktorx))))))]
[y-bezeichnen-positiv
(lambda (zy e)
(if (> zy (- zemax 1))
(begin
(textout-heightcenter s0 zy (number->string (genaurunden e genau)))
(y-bezeichnen-positiv (- zy (* stepy faktory)) (+ e (* ey faktory))))))]
[y-bezeichnen-negativ
(lambda (zy e)
(if (< zy (+ zemin 1))
(begin
(textout-heightcenter s0 zy (number->string (genaurunden e genau)))
(y-bezeichnen-negativ (+ zy (* stepy faktory)) (- e (* ey faktory))))))]
[graph-startpkt
(lambda (fkt pkt)
(let ([sx (car pkt)] [zy (cdr pkt)])
(if (< sx (+ spbis 1))
(with-failure-continuation
(lambda (error-record error-k) (graph-startpkt fkt (cons (+ sx 1) zy)))
(lambda ()
(let* ([x (+ (* (/ (- sx spmin) (- spmax spmin)) (- xo xu)) xu)] [y (fkt x)])
(if (real? y)
(begin
(set! zy (+ (* (/ (- y yu) (- yo yu)) (- zemax zemin)) zemin))
(if (> zy zemin) (set! zy zemin))
(if (< zy zemax) (set! zy zemax))
(cons sx zy))
(graph-startpkt fkt (cons (+ sx 1) zy))))))
(cons sx zy))))]
[graph-zeichnen
(lambda (fkt pkt)
(let ([sx (car pkt)] [zy (cdr pkt)])
(if (< sx (+ spbis 1))
(with-failure-continuation
(lambda (error-record error-k)
(graph-zeichnen fkt (graph-startpkt fkt (cons (+ sx 1) zy))))
(lambda ()
(let* ([sx-neu (+ sx 1)]
[x (+ (* (/ (- sx-neu spmin) (- spmax spmin)) (- xo xu)) xu)] [y (fkt x)])
(if (real? y)
(let ([zy-neu (+ (* (/ (- y yu) (- yo yu)) (- zemax zemin)) zemin)])
(if (> zy-neu zemin) (set! zy-neu zemin))
(if (< zy-neu zemax) (set! zy-neu zemax))
(if (and (< zy zemin) (> zy zemax) (< zy-neu zemin) (> zy-neu zemax))
(line canvas5 sx zy sx-neu zy-neu))
(graph-zeichnen fkt (cons sx-neu zy-neu)))
(graph-zeichnen fkt (graph-startpkt fkt (cons (+ sx 1) zy))))))))))]
[graph-list-zeichnen
(lambda (fkt-ls anz color-ls)
(if (not (null? fkt-ls))
(let ([fkt (eval (car fkt-ls))])
((eval (n-tes-mod color-ls anz)) canvas5)
(graph-zeichnen fkt (graph-startpkt fkt (cons spvon z0)))
(graph-list-zeichnen (cdr fkt-ls) (+ anz 1) color-ls))))])
(koordcolor canvas5)
(line canvas5 spmin z0 spend z0)
(line canvas5 s0 zemin s0 zeend)
(line canvas5 (- spend 6) (- z0 2) spend z0)
(line canvas5 (- spend 6) (+ z0 2) spend z0)
(line canvas5 (- spend 6) (- z0 2) (- spend 6) (+ z0 2))
(line canvas5 (- s0 2) (+ zeend 6) s0 zeend)
(line canvas5 (+ s0 2) (+ zeend 6) s0 zeend)
(line canvas5 (- s0 2) (+ zeend 6) (+ s0 2) (+ zeend 6))
(set! mx (anpassen mx)) (set! teilerx (teilen mx))
(set! stepx (/ (- spmax spmin) mx teilerx))
(set! my (anpassen my)) (set! teilery (teilen my))
(set! stepy (/ (- zemin zemax) my teilery))
(x-teilen-positiv (+ s0 stepx)) (x-teilen-negativ (- s0 stepx))
(y-teilen-positiv (- z0 stepy)) (y-teilen-negativ (+ z0 stepy))
(set! ex (/ ex mx teilerx))
(set! faktorx (faktor
(* textgroesse (string-length (number->string (genaurunden ex genau))))
stepx))
(set! ey (/ ey my teilery))
(set! faktory (faktor
textgroesse
stepy))
(if (= yu 0)
(x-bezeichnen-positiv s0 0)
(x-bezeichnen-positiv (+ s0 (* stepx faktorx)) (* ex faktorx)))
(x-bezeichnen-negativ (- s0 (* stepx faktorx)) (- (* ex faktorx)))
(if (= xu 0)
(y-bezeichnen-positiv z0 0)
(y-bezeichnen-positiv (- z0 (* stepy faktory)) (* ey faktory)))
(y-bezeichnen-negativ (+ z0 (* stepy faktory)) (- (* ey faktory)))
(if (< spvon spmin) (set! spvon spmin)) (if (> spbis spmax) (set! spbis spmax))
(graph-list-zeichnen fkt-list 0 color-list)
'ok))))
</code>
<eval id="4bf2ee180b73f">
(schaubild (list qs-best-case qs-average-case qs-worst-case) x-von x-bis y-von y-bis x-von x-bis black '(red blue green))
</eval>
== Zum Weiterarbeiten ==
=== MergeSort ===
Der Sortieralgorithmus [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/MergeSort|''MergeSort'']] ist eine effiziente Alternative zum QuickSort, da sein Zeitaufwand in allen drei Fällen (best-, average-, worst-case) <math>T(n) = \mathcal{O}(n \cdot \log_2 n)</math> beträgt. "Merge" bedeutet hier soviel wie "Zusammensetzen". Die Übersetzung mit "Sortieren durch Mischen" ist eher irreführend.
'''Beschreibung:'''
* Teile eine (numerische) Liste in zwei etwa gleich große Teillisten.
* Führe diese Teilung bei jeder Teillisten solange fort, bis nur noch einelementige Teillisten bestehen bleiben.
* Setze diese Teillisten in der richtigen Reihenfolge zur sortierten Gesamtliste zusammen.
Implementieren Sie diesen Algorithmus.<br />
Zur [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/MergeSort|Problemlösung]].