Wykonujemy proste ćwiczenie z dwiema tablicami zawierającymi liczby oraz ich kwadraty, w dowolnej kolejności. Poznajemy trzy sposoby na sprawdzenie, czy te tablice są prawidłowe tj. jedna pasuje do drugiej.
Jeden sposób jest prosty, ale wymaga sortowania, drugi bardziej zawiły i wymaga znajomości metod tablicowych, zaś trzeci to popularne podejście „frequency counter”, którego znajomość opłaci nam się w przyszłości.
W zasadzie trudno o opisowy tytuł dla tego ćwiczenia. Piszemy funkcję, która pobiera dwie tablice. Chodzi o to, że w jednej tablicy znajdują się, w dowolnej kolejności, pewne liczby. W drugiej tablicy znajdują się, w dowolnej kolejności, kwadraty tych liczb.
Poniższy przykład ilustruje co chcemy osiągnąć:
function compareArrays(arr1, arr2) {
return;
}
console.log(compareArrays([1,2,3], [1,4,9]));
//ma zwracać trueW takim przypadku mamy dostać wartość prawdziwą. Pozwalamy jednak użytkownikowi, aby te wartości były w dowolnej kolejności. Poniższy przykład również ma zwrócić true:
console.log(compareArrays([3,2,1], [4,9,1]));
//ma zwracać trueMało tego – pozwalamy na dowolną ilość liczb. Poniższy przykład również ma zwrócić true:
console.log(compareArrays([3,3,2,1], [4,9,1,9]));
//ma zwracać trueMamy liczbę 3 dwa razy w pierwszej tablicy, zaś w drugiej liczbę 9 (jej kwadrat) też dwa razy. To jest istota tego ćwiczenia.
Podejście pierwsze – posortuj
Bardzo łatwe podejście do problemu, polegające na posortowaniu obu tablic.
function compareArrays(arr1, arr2) {
arr1.sort((a,b)=>a-b);
arr2.sort((a,b)=>a-b);
console.log(arr1);
console.log(arr2);
}
compareArrays([3,3,2,1], [4,9,1,9]);
//[1, 2, 3, 3]
//[1, 4, 9, 9]Jak widać problem mamy już prawie rozwiązany. Teraz musimy przejść po tablicach, po ich indeksach, i sprawdzić, czy element o danym indeksie w jednej tablicy to kwadrat elementu o tym samym indeksie w drugim.
Do przechodzenia po indeksach tablic mamy pętle for…in (łatwo zapamiętać – in jak INdeks…):
function compareArrays(arr1, arr2) {
arr1.sort((a,b)=>a-b);
arr2.sort((a,b)=>a-b);
for(let idx in arr1) {
if(arr2[idx] !== arr1[idx] ** 2)
return false;
return true;
}
}
console.log(compareArrays([3,3,2,1], [4,9,1,9]));
//trueCzyli tak – przechodzimy po indeksach arr1 (albo arr2, bez różnicy) i sprawdzamy czy w arr2 pod danym indeksem jest element z arr1 pod takim samym indeksem do kwadratu.
Jeżeli nie ma – false. Jeżeli pętla się skończy – true.
Brakuje tylko sprawdzenia, czy tablice są jednakowej długości. Bo jeżeli są różne, to już na początku wiemy, że trzeba zwrócić false:
function compareArrays(arr1, arr2) {
if(arr1.length !== arr2.length)
return false;
arr1.sort((a,b)=>a-b);
arr2.sort((a,b)=>a-b);
for(let idx in arr1) {
if(arr2[idx] !== arr1[idx] ** 2)
return false;
return true;
}
}
console.log(compareArrays([1,2,3], [1,4,9]));
//true
console.log(compareArrays([1,2], [1,4,9]));
//falseGotowe. Możemy to sobie na spokojnie przeanalizować albo przejść do bardziej zaawansowanych przykładów.
Podejście naiwne z pomocą metod tablicowych
To podejście jest z jednej strony „naiwne” (proste), z drugiej wymaga od nas pewnej znajomości metod tablicowych.
Na samym początku odrzucamy tablice o różnej długości:
function compareArrays(arr1, arr2) {
if(arr1.length !== arr2.length)
return false;
}Teraz przechodzimy po tablicy 1 w pętli for. Kod poniżej to tylko demonstracja, bo robimy to krok po kroku:
function compareArrays(arr1, arr2) {
if(arr1.length !== arr2.length)
return false;
for(let i = 0; i < arr1.length; i++) {
let foundIdx = arr2.indexOf(arr1[i] ** 2);
}
}Czyli bierzemy element o danym indeksie z arr1, podnosimy go (wartość pod tym indeksem) do kwadratu i za pomocą funkcji indexOf szukamy tego indeksu w tablicy arr2.
Metoda indexOf może zwrócić -1, jeżeli w drugiej tablicy nie znajdzie elementu (z tablicy 1 podniesionego do kwadratu):
function compareArrays(arr1, arr2) {
if(arr1.length !== arr2.length)
return false;
for(let i = 0; i < arr1.length; i++) {
let foundIdx = arr2.indexOf(arr1[i] ** 2);
if(foundIdx === -1)
return false;
}
}Wtedy wiemy, że skoro w tablicy 2 nie ma elementu z tablicy 1 podniesionego do kwadratu, to mamy false.
Teraz tylko usuwamy element o danym indeksie z tablicy 2, jak już został „wykorzystany”:
function compareArrays(arr1, arr2) {
if(arr1.length !== arr2.length)
return false;
for(let i = 0; i < arr1.length; i++) {
let foundIdx = arr2.indexOf(arr1[i] ** 2);
if(foundIdx === -1)
return false;
arr2.splice(foundIdx, 1);
}
return true;
}
console.log(compareArrays([1,2,3], [1,4,9]));
//true
console.log(compareArrays([1,2,4], [1,4,9]));
//falseMożemy to sobie przeanalizować na spokojnie. Oto nasz algorytm:
- Jeżeli różna długość tablic na początku – fałsz
- Przechodzimy w pętli for po indeksach tablicy 1
- Wartość elementu z tablicy 1 podnosimy do kwadratu i sprawdzamy pod jakim indeksem znajduje się w tablicy 2
- Jeżeli się nie znajduje (indexOf zwraca -1) to zwracamy fałsz
- Po upewnieniu się, że element o wartości podniesionej do kwadratu się w drugiej tablicy znajduje i zapisaniu jego indeksu usuwamy ten element z drugiej tablicy, już jest „wykorzystany”
- Na koniec – zwracamy prawdę.
Uwaga – to podejście jest dużo gorsze, niż podejście pierwsze. Nie dość, że wymaga dobrej znajomości wbudowanych, czasami osobliwych funkcji tablicowych (jak splice) i jest mało czytelne, to jeszcze jest mało wydajne.
Operacje zmiany w tablicach są kosztowne. W przykładzie pierwszym dokonujemy dwóch takich zmian (posortowanie tablicy 1 i 2). W przykładzie drugim dokonujemy zmiany tablicy (usunięcia elementu arr2) wewnątrz pętli, co z punktu widzenia złożoności algorytmu jest jeszcze gorsze.
Frequency counter – sposób najlepszy
Chyba najlepsze podejście. Zacznijmy od tego, że chcemy napisać funkcję, która podlicza ilość wystąpień elementów w naszych tablicach:
function compareArrays(arr1, arr2) {
if(arr1.length !== arr2.length)
return false;
let counter1 = {};
let counter2 = {};
for(let val of arr1)
counter1[val] = (counter1[val] || 0) + 1;
for(let val of arr2)
counter2[val] = (counter2[val] || 0) + 1;
console.log(counter1);
console.log(counter2);
}
compareArrays([1,2,3], [1,4,9]);
//{1: 1, 2: 1, 3: 1}
//{1: 1, 4: 1, 9: 1}Tworzymy dwa obiekty, będące licznikami ile razy dana wartość występuje w obu tablicach.
Teraz musimy:
- Przejść po kluczach licznika pierwszego
- Sprawdzić czy w liczniku drugim jest klucz, który jest podniesieniem do kwadratu tego z pierwszego, np. klucz w pierwszym 2, sprawdź czy drugi licznik ma klucz 4
- Sprawdzić, czy klucz z licznika pierwszego i jego odpowiednik podniesiony do kwadratu mają taką samą wartość (czyli 2:1 w pierwszym liczniku odpowiada 4:1 w drugim).
Wygląda to tak:
function compareArrays(arr1, arr2) {
if(arr1.length !== arr2.length)
return false;
let counter1 = {};
let counter2 = {};
for(let val of arr1)
counter1[val] = (counter1[val] || 0) + 1;
for(let val of arr2)
counter2[val] = (counter2[val] || 0) + 1;
for(let key in counter1) {
if(!(key ** 2 in counter2))
return false;
if(counter2[key**2] !== counter1[key])
return false;
}
return true;
}
console.log(compareArrays([1,2,3], [1,4,9]));
//trueMożemy to sobie na spokojnie przeanalizować. Nie jest to tak prosty algorytm jak przykład 1, ale zdecydowanie łatwiejszy (moim zdaniem) niż przykład 2.
W dodatku optymalny. Nie modyfikujemy tablic, pętle są, ale nie są zagnieżdżone (w przypadku złożoności algorytmów pętla po pętli to jak jedna pętla, zaś pętla w pętli – cała złożoność podniesiona do kwadratu).
Myślę, że tyle sposobów wystarczy.
