Niedzielna „kata”, lekki trening z klawiaturą

W nawiązaniu do poprzedniego posta, chciałbym podzielić się przebiegiem takiego ćwiczenia. Wyobraźmy sobie bardzo prostą sytuację z dowolnej gry. Mamy zestaw graczy i będziemy w chcieli którymś momencie dopasować ich na podstawie zebranych przez nich punktów. Dla uproszczenia powiedzmy więc, że mamy nieuporządkowaną tablicę samych ilości punktów. Co by nie komplikować powiedzmy, że interesuje nas najniższa różnica punktów pomiędzy dowolnymi z graczy z puli.

Dla podsumowania, dane wejściowe to tablica liczb naturalnych (zero dozwolone, mniejsze lub równe 999) a dane wyjściowe to pojedyncza liczba całkowita, co najmniej zero, która reprezentuje badaną najmniejszą różnicę. Wybrałem na te potrzeby język JavaScript, jako, że wydaje mi się najprostszy w obsłudze, bo od biedy można testować nawet w konsoli przeglądarki. Ot, lenistwo.
Zważając na fakt, że sesje kata zalecane są z użyciem metodyki Test Driven Development, do swojego pakietu ćwiczeniowego dorzucam bibliotekę qUnit. Tym razem dlatego, że mieści się w dwóch plikach, używa się łatwo a składnia jest bardzo podobna do innych standardowych narzędzi.

Tworzę więc podstawowy dokument i dołączam wszystkie niezbędne pliki, w tym wspomnianą przed momentem bibliotekę.

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width">
  <title>QUnit Example</title>
  <link rel="stylesheet" href="qunit/qunit.css">
</head>
<body>


<div id="qunit"></div>




<div id="qunit-fixture"></div>


  <script src="qunit/qunit.js"></script>
  <script src="test.js"></script>
  <script src="../solution.js"></script>
</body>
</html>

Następnie, jak przystało na porządnego obywatela, tworzę testy pod opisany scenariusz.

// No players
var testData0 = [];
var expectedResult0 = false;

QUnit.test("Two players", function( assert ) {
  assert.ok( shortestDifference(testData0) === expectedResult0, "Wrong!" );
});

Na pierwszy strzał upewniam się jaki jest rezultat jeżeli dane wejściowe są puste.

// Just two players
var testData1 = [7,3];
var expectedResult1 = 4;

QUnit.test("Two players", function( assert ) {
  assert.ok( shortestDifference(testData1) === expectedResult1, "Wrong!" );
});

Kolejny test obsługuje sytuację, gdy mamy jedynie dwóch graczy. Wiadomo więc, że wynik to różnica między nimi. Zadaniem tego typu testów jest zapewnienie, że nasz program działa niezależnie od tego jakie dane dostaje na wejściu.

// Many players
var testData2 = [7,3,12,6,11,14,5,2,4,7,5,6];
var expectedResult2 = 1;

QUnit.test("Many players", function( assert ) {
  assert.ok( shortestDifference(testData2) === expectedResult2, "Wrong!" );
});

// Lots of players
var testData3 = [40,154,25,10,106,136,175,178,46,145,103,169,178,22,46,178,76,73,25,25,157,49,31,160,196,34,13,82,124,112,52,88,115,7,67,139,193,166,196,118,166,40,52,184,184,106,151,172,175,181,79,127,43,1,160,145,25,82,64,169,142,166,19,16,88,58,175,91,127,58,127,124,190,7,163,31,73,85,13,160,178,1,31,46,169,73,64,4,82,154,70,52,112,109,43,52,196,160,172];
var expectedResult3 = 3;

QUnit.test("Lots of players", function( assert ) {
  assert.ok( shortestDifference(testData3) === expectedResult3, "Wrong!" );
});

// Almost equal players
// Many players
var testData4 = [3,2,3,4,3,2,1,2,1,3,4];
var expectedResult4 = 0;

QUnit.test("Many players", function( assert ) {
  assert.ok( shortestDifference(testData4) === expectedResult4, "Wrong!" );
});

Podstawowy zestaw jaki przyszedł mi na szybko do głowy zamykają trzy testy, które zawierają dużo danych lub sporo bliskich sobie wartości. Taki rodzaj testów powinien zachęcać do myślenia o optymalnym rozwiązaniu!
Ruszajmy więc, odpalam dokument z testami i oczywiście oblewam wszystkie możliwe.

shortest_differences_1

To chyba nie jest zaskoczenie, nie zacząłem nawet jeszcze pisać rozwiązania. 🙂
Tworzę więc odpowiednią funkcję i nadaje jej domyślne zachowanie.

function shortestDifference(valuesArray)
{
	return false;
}

To powinno częściowo pomóc, a efekt jest następujący.

shortest_differences_2
Pierwszy test zdany. Uff! Tak właśnie wygląda TDD w praktyce. Rozwijamy kod i zdajemy kolejne testy.
Rozwiązania tego problemu wydaje się bardzo proste, piszę więc kod, który porównuje ze sobą wszystkie możliwe wartości i ustala najniższą różnicę.

function shortestDifference(valuesArray)
{
	var shortest = false;
	for(var i=0; i<valuesArray.length; i++){
		for(var j=0; j<valuesArray.length; j++){
			if(i == j)
				continue;
			
			var difference = Math.abs(valuesArray[i] - valuesArray[j]);

			if(shortest === false || difference < parseInt(shortest))
				shortest = difference;
		}
	}
	return shortest;
}

Odświeżam dokument z raportami z testów i jest dużo lepiej…
shortest_differences_3

Wszystkie testy zadowolone, znaczy, że algorytm działa. Nie jest on jednak idealny, mam nadzieję, że Ty również wiesz dlaczego. Ta zagnieżdżona pętla przy większych zbiorach danych będzie powodowała spadek wydajności, ponieważ w obecnej konfiguracji musimy wykonać N*N kroków, czyli sporo.
Po chwili namysłu mam inne rozwiązanie. Wykorzystuję wbudowane w JavaScript sortowanie, dzięki temu będę mógł przeglądać uporządkowane dane w jednym przebiegu, porównując ze sobą kolejne pary. Najniższa z nich będzie rozwiązaniem!
To nie zdziała cudów, ale z pewnością poprawi wydajność tego algorytmu. Spójrzmy na nową wersję metody shortestDifference.

function shortestDifference(valuesArray)
{
	valuesArray.sort();

	var shortest = false;
	for(var i=1; i<valuesArray.length; i++){
		var difference = Math.abs(valuesArray[i] - valuesArray[i-1]);

		if(shortest === false || difference < parseInt(shortest))
			shortest = difference;
	}
	return shortest;
}

Jest nawet przyjaźniejsza dla oka, sprawdźmy więc czy nie narobiła szkód. Otwieram więc ponownie dokument z testami qUnit i sprawdzam. W dalszym ciągu wszystkie zestawy widnieją jako zdane. Oznacza to sukces i przy okazji ulepszenie pomysłu! Cel ćwiczenia osiągnięty.
Jeżeli spodobało Ci się to, co się tutaj dzieje, może zechcesz porównać wydajność dwóch wersji rozwiązania i podzielić wnioskami? A może masz pomysł na jeszcze lepsze i prostsze rozwiązanie tego problemu? Podziel się koniecznie!

p.s. Poszczególne kroki i zmiany w kodzie możesz podejrzeć na repozytorium. W razie pytań zapraszam do kontaktu!