Разделяй и владей и дървото на рекурсията в JavaScript

Проблем

Колко доставки са разменени

Куриерската фирма обещава на всеки клиент час за доставка. Така поръчките имат обещан ред: 1, 2, 3 и така нататък. Колите обаче карат както карат, и вечерта отчетът пита: колко далеч е днешният ред на доставките от обещания?

Мярката е броят на разменените двойки: поръчка 5 е доставена преди поръчка 3, макар че 3 е обещана по-рано. Такава двойка се казва инверсия. Ако доставките са точно по обещания ред, инверсиите са 0.

Първото решение проверява всяка двойка:

function countPairs(ranks) {
  let inversions = 0;
  for (let i = 0; i < ranks.length; i++) {
    for (let j = i + 1; j < ranks.length; j++) {
      if (ranks[i] > ranks[j]) {
        inversions++;
      }
    }
  }
  return inversions;
}

const ranks = [4, 1, 7, 3, 8, 2, 6, 5];
console.log(`Инверсии: ${countPairs(ranks)}`);

Инверсии: 12

За 8 поръчки това са 28 двойки. За n поръчки са n(n − 1)/2, тоест O(n²). Фирмата прави 100 000 доставки на ден, а двойките са 4 999 950 000. Отчетът, който на теста е миг, вечер върви с минути.

Идеята

Раздели, преброй, сглоби

Подходът е разделяй и владей, като в merge sort: раздели доставките на първата и втората половина. Всяка разменена двойка е от един от три вида:

и двете поръчки са в първата половина;
и двете са във втората;
едната е в първата, другата във втората.

Първите два вида са същата задача, само че наполовина по-малка: рекурсията ги брои. Трудното е третият вид, двойките между половините. Ако проверяваш всяка, пак си на n².

Тук помага сливането. Нека двете половини вече са подредени. При сливане взимаш по-малкото от двете първи невзети числа. Когато по-малкото е отдясно, всяко невзето отляво е по-голямо от него, а е дошло по-рано, защото е от първата половина. Всяко от тях е една инверсия. Затова едно сравнение брои наведнъж колкото са невзетите отляво.

Така броенето „се качва“ на merge sort: същото делене, същото сливане и един ред повече.

Виж го

Броене при сливането

sortCount подрежда доставките на място и връща колко инверсии има в тях. Гледай последното сливане: всяко число отдясно, което слиза, брои невзетите отляво:

function sortCount(ranks) {
  if (ranks.length <= 1) {
    return 0;
  }
  const mid = Math.floor(ranks.length / 2);
  const left = ranks.slice(0, mid);
  const right = ranks.slice(mid);
  const a = sortCount(left);
  const b = sortCount(right);
  let cross = 0;
  let i = 0;
  let j = 0;
  let k = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      ranks[k++] = left[i++];
    } else {
      cross += left.length - i;
      ranks[k++] = right[j++];
    }
  }
  while (i < left.length) {
    ranks[k++] = left[i++];
  }
  while (j < right.length) {
    ranks[k++] = right[j++];
  }
  return a + b + cross;
}

Стъпка по стъпка, с думи

sortCount получава 8 поръчки в реда, в който са дошли. Числото е мястото на поръчката в обещания ред.
mid = 4: първите четири доставки [4, 1, 7, 3] и последните четири [8, 2, 6, 5]. Всяка разменена двойка е или вътре в половина, или между двете.
Всяка половина вика sortCount за себе си: брои своите двойки (a = 3, b = 4) и се връща подредена.
Сега двойките между половините. i и j сочат първото невзето число. 1 < 2: лявото слиза, без инверсия.
2 отдясно е по-малко. Всяко невзето отляво ([3, 4, 7]) е по-голямо и е дошло по-рано: left.length - i = 3 инверсии наведнъж.
Същото правило всеки път: 5 добавя 1, 6 добавя 1. cross = 5, след 7 сравнения.
Едната страна свърши. Остатъкът отива накрая без сравнение: той не добавя инверсии.
a + b + cross = 3 + 4 + 5 = 12. Проверката по двойки гледа всички 28 двойки; сливането намира същите 12 с общо 17 сравнения.

const ranks = [4, 1, 7, 3, 8, 2, 6, 5];
console.log(`Инверсии: ${sortCount(ranks)}`);
console.log(`Подредени: [${ranks.join(", ")}]`);

Инверсии: 12
Подредени: [1, 2, 3, 4, 5, 6, 7, 8]

Функцията подрежда масива, който получава. Ако ти трябва и редът на доставките, подай копие.

В JavaScript функцията може да върне и двата резултата като масив, return [merged, count], а извикващият ги взима с const [sorted, count] = …. Тук подреждането е в самия масив, за да е кодът като в другите езици.

Пробвай

Предвиди изхода

Двете половини, [2, 4, 6] и [1, 3, 5], вече са подредени, затова вътре в тях инверсии няма. Колко има между тях?

function sortCount(ranks) {
  if (ranks.length <= 1) {
    return 0;
  }
  const mid = Math.floor(ranks.length / 2);
  const left = ranks.slice(0, mid);
  const right = ranks.slice(mid);
  const a = sortCount(left);
  const b = sortCount(right);
  let cross = 0;
  let i = 0;
  let j = 0;
  let k = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      ranks[k++] = left[i++];
    } else {
      cross += left.length - i;
      ranks[k++] = right[j++];
    }
  }
  while (i < left.length) {
    ranks[k++] = left[i++];
  }
  while (j < right.length) {
    ranks[k++] = right[j++];
  }
  return a + b + cross;
}

const ranks = [2, 4, 6, 1, 3, 5];
console.log(`Инверсии: ${sortCount(ranks)}`);

Отговор

Инверсии: 3

Инверсии: 6

Инверсии: 15

Идеята

Дървото на рекурсията

Колко струва това? Нарисувай извикванията като дърво. Най-горе е извикването с всичките n поръчки. Под него са двете, които то прави, с по n/2. Под всяко от тях още две, и така до дъното.

После за всяко извикване отбележи работата му: какво прави то само, извън своите рекурсивни извиквания. Тук това е сливането: то минава всяка поръчка, която извикването е получило, веднъж.

Сега събери по нива. Най-горе работата е n. На следващото ниво са две извиквания по n/2: пак n. После четири по n/4: пак n. Нивата са колко пъти n се дели на две до 1, около log₂ n. Значи цената е нивата по работата на ниво: n · log₂ n.

Това се казва дърво на рекурсията. То е начинът да преброиш цената на всяко „разделяй и владей“: не гадаеш, а събираш ниво по ниво.

Виж го

Три дървета, три цени

Същото броене за три функции на 8 поръчки. Двоичното търсене от урока за него, написано с рекурсия. Броенето чрез сливане. И трета функция, която също дели, но лошо: първите n − 1 поръчки рекурсивно, а последната сравнява с всички преди нея.

function sortCount(ranks) {
  if (ranks.length <= 1) {
    return 0;
  }
  const mid = Math.floor(ranks.length / 2);
  const left = ranks.slice(0, mid);
  const right = ranks.slice(mid);
  const a = sortCount(left);
  const b = sortCount(right);
  let cross = 0;
  let i = 0;
  let j = 0;
  let k = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      ranks[k++] = left[i++];
    } else {
      cross += left.length - i;
      ranks[k++] = right[j++];
    }
  }
  while (i < left.length) {
    ranks[k++] = left[i++];
  }
  while (j < right.length) {
    ranks[k++] = right[j++];
  }
  return a + b + cross;
}

function find(ranks, target, lo, hi) {
  if (lo > hi) {
    return -1;
  }
  const mid = Math.floor((lo + hi) / 2);
  if (ranks[mid] === target) {
    return mid;
  }
  if (ranks[mid] < target) {
    return find(ranks, target, mid + 1, hi);
  }
  return find(ranks, target, lo, mid - 1);
}

Стъпка по стъпка, с думи

Всяка кутия е едно извикване, а числото в нея е колко поръчки получава. find поглежда средата веднъж: работа 1.
После вика себе си за ЕДНАТА половина: 8 → 4 → 2 → 1. Един клон, и всяко ниво прави 1.
4 нива × 1 = 4. Нивата са колко пъти n се дели на две до 1, около log₂ n: O(log n).
sortCount вика себе си за ДВЕТЕ половини. Сливането най-горе минава всичките 8 поръчки, двете под него 4 + 4 = 8.
На всяко ниво извикванията са два пъти повече, а поръчките на всяко са наполовина: работата на ниво остава 8. Извикванията с една поръчка само се връщат: 0.
3 нива × 8 = 24: log₂ n нива по n, O(n log n). При 100 000 поръчки това са 17 нива, не 100 000.
countSlow също дели, но лошо: първите n − 1 поръчки и последната. Рекурсията продължава с n − 1: 8 → 7 → 6 …
На всяко ниво последната поръчка се сравнява с всички преди нея: 7, 6, … 1. 8 нива, и 7 + 6 + 5 + … + 1 = 28: точно 28-те двойки, O(n²).
Цената е формата на дървото: нивата по работата на ниво. Деленето наполовина дава log n нива, отделянето по едно дава n нива. Не стига да делиш: половините трябва да са равни.

const sorted = [1, 2, 3, 4, 5, 6, 7, 8];
console.log("find:", find(sorted, 8, 0, sorted.length - 1));
const ranks = [4, 1, 7, 3, 8, 2, 6, 5];
console.log("countSlow:", countSlow(ranks, ranks.length));
console.log("sortCount:", sortCount(ranks));

find: 7
countSlow: 12
sortCount: 12

Формата на дървото решава:

Един клон, половината: log₂ n нива по малко работа. O(log n).
Два клона, половините: log₂ n нива по n. O(n log n).
Един клон, едно по-малко: n нива по n. O(n²). Това е проверката по двойки, само че написана с рекурсия.

Същото става в quick sort с лош пивот: при подреден вход пивотът отделя една цена, а другите n − 1 остават в една част. Дървото е верига от n нива, и сложността е n².

Виж го

Измери го: по двойки срещу чрез сливане

Пусни двете върху едни и същи доставки. При двойките броим проверените двойки, при сливането сравненията. По двойки при 100 000 не се пуска наистина: Bench го оценява по кривата.

Инверсии по двойки O(n²)
Инверсии чрез сливане O(n log n)

Алгоритъм	n = 10	n = 1000	n = 10 000	n = 100 000
Инверсии по двойки	45	499 500	49 995 000	≈ 4 999 500 000
Инверсии чрез сливане	21	8693	120 553	1 536 329

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

function sortCount(ranks) {
  if (ranks.length <= 1) {
    return 0;
  }
  const mid = Math.floor(ranks.length / 2);
  const left = ranks.slice(0, mid);
  const right = ranks.slice(mid);
  const a = sortCount(left);
  const b = sortCount(right);
  let cross = 0;
  let i = 0;
  let j = 0;
  let k = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      ranks[k++] = left[i++];
    } else {
      cross += left.length - i;
      ranks[k++] = right[j++];
    }
  }
  while (i < left.length) {
    ranks[k++] = left[i++];
  }
  while (j < right.length) {
    ranks[k++] = right[j++];
  }
  return a + b + cross;
}

При 1000 доставки двойките са 499 500, а сравненията 8693. При 100 000 сливането прави 1 536 329 сравнения срещу 4 999 950 000 двойки: над 3000 пъти по-малко. А инверсиите са същите, 2 504 458 463.

По-точно, за любопитните

Същите числа на твоя език. Доставките са разбъркани с малък генератор със семе, затова са еднакви при всяко пускане, на всеки език и в Bench:

let checks = 0;
let comparisons = 0;

function deliveries(n) {
  const ranks = Array.from({ length: n }, (_, k) => k + 1);
  let x = 2026;
  for (let k = n - 1; k > 0; k--) {
    x = (x * 48271) % 2147483647;
    const j = x % (k + 1);
    [ranks[k], ranks[j]] = [ranks[j], ranks[k]];
  }
  return ranks;
}

function countPairs(ranks) {
  let inversions = 0;
  for (let i = 0; i < ranks.length; i++) {
    for (let j = i + 1; j < ranks.length; j++) {
      checks++;
      if (ranks[i] > ranks[j]) {
        inversions++;
      }
    }
  }
  return inversions;
}

function sortCount(ranks) {
  if (ranks.length <= 1) {
    return 0;
  }
  const mid = Math.floor(ranks.length / 2);
  const left = ranks.slice(0, mid);
  const right = ranks.slice(mid);
  const a = sortCount(left);
  const b = sortCount(right);
  let cross = 0;
  let i = 0;
  let j = 0;
  let k = 0;
  while (i < left.length && j < right.length) {
    comparisons++;
    if (left[i] <= right[j]) {
      ranks[k++] = left[i++];
    } else {
      cross += left.length - i;
      ranks[k++] = right[j++];
    }
  }
  while (i < left.length) {
    ranks[k++] = left[i++];
  }
  while (j < right.length) {
    ranks[k++] = right[j++];
  }
  return a + b + cross;
}

for (const n of [10, 1000]) {
  checks = 0;
  const inv = countPairs(deliveries(n));
  console.log(`по двойки, n = ${n}: ${checks} проверки, ${inv} инверсии`);
}
for (const n of [10, 1000, 100000]) {
  comparisons = 0;
  const inv = sortCount(deliveries(n));
  console.log(`чрез сливане, n = ${n}: ${comparisons} сравнения, ${inv} инверсии`);
}

по двойки, n = 10: 45 проверки, 14 инверсии
по двойки, n = 1000: 499500 проверки, 249193 инверсии
чрез сливане, n = 10: 21 сравнения, 14 инверсии
чрез сливане, n = 1000: 8693 сравнения, 249193 инверсии
чрез сливане, n = 100000: 1536329 сравнения, 2504458463 инверсии

В JavaScript числото е с плаваща запетая и пази точно цели числа до 2⁵³, около 9 · 10¹⁵. 2,5-те милиарда инверсии са далеч под това. В Java и C# същият брояч трябва да е long: int стига до 2 147 483 647 и прехвърля без грешка.

Пробвай

Намери грешката

Колега е преписал функцията. За 8-те доставки от сцената тя казва 5 вместо 12:

const ranks = [4, 1, 7, 3, 8, 2, 6, 5];
console.log(`Инверсии: ${sortCount(ranks)}`);
console.log(`Подредени: [${ranks.join(", ")}]`);

Инверсии: 5
Подредени: [1, 2, 3, 4, 5, 6, 7, 8]

На кой ред е грешката?

Избери реда с грешката.

Пробвай

Попълни

Дясното число е по-малко и слиза. С колко расте cross?

function sortCount(ranks) {
  if (ranks.length <= 1) {
    return 0;
  }
  const mid = Math.floor(ranks.length / 2);
  const left = ranks.slice(0, mid);
  const right = ranks.slice(mid);
  const a = sortCount(left);
  const b = sortCount(right);
  let cross = 0;
  let i = 0;
  let j = 0;
  let k = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      ranks[k++] = left[i++];
    } else {
      cross += ;
      ranks[k++] = right[j++];
    }
  }
  while (i < left.length) {
    ranks[k++] = left[i++];
  }
  while (j < right.length) {
    ranks[k++] = right[j++];
  }
  return a + b + cross;
}

Упражнение

Отчетът за деня

Реши задачата в редактора си.

Разменени двойки. Прочети реда на доставките (обещаните номера, разделени с интервал) и отпечатай колко двойки са разменени и от колко общо. Ползвай sortCount от урока.

3 1 2 6 4 5 10 7 9 8

Разменени двойки: 8 от 45

Още задачи

Нарисувай дървото. Функция дели входа на три равни части и вика себе си за всяка, а работата ѝ извън извикванията е n. Нарисувай нивата: колко са и колко е работата на ниво? А ако частите са две, но работата на всяко извикване е n²?
Кои закъсняват най-много. За всяка поръчка преброй колко поръчки с по-голям номер са доставени преди нея. Сборът на тези числа е броят на инверсиите. Как да ги събереш по време на сливането? Подсказка: когато слиза число отдясно, за него се броят невзетите отляво.
Близо ли е до подредено. Преброй инверсиите в ред, който е почти подреден (две съседни поръчки разменени). Колко сравнения прави сливането? А insertion sort от простите сортирания върху същия вход?

По-точно

Мастър теоремата и другите езици

Дървото на рекурсията работи за всяко „разделяй и владей“. За най-честия вид има и готово правило.

По-точно, за любопитните

Мастър теоремата, като интуиция. Функция, която дели входа на b равни части, вика себе си a пъти и прави работа f(n) извън извикванията, се описва като T(n) = a · T(n/b) + f(n). Нарисувай дървото и сравни работата горе с работата на дъното:

Работата е еднаква на всяко ниво. Умножаваш по броя нива, log n. Merge sort: T(n) = 2 · T(n/2) + n, по n на ниво, O(n log n). Двоичното търсене: T(n) = T(n/2) + 1, по 1 на ниво, O(log n).
Работата намалява надолу. Горното ниво решава. T(n) = 2 · T(n/2) + n² е O(n²): долните нива са n²/2, n²/4 и така нататък, а сборът им е под още едно n².
Работата расте надолу. Листата решават. Умножението на големи числа на Карацуба е T(n) = 3 · T(n/2) + n: три половини на всяко ниво, работата расте с 3/2 на ниво, и сложността е около n^1,58 вместо n² на училищното умножение.

Лошото делене T(n) = T(n − 1) + n изобщо не е от този вид: входът не се дели на b, а намалява с едно. Там теоремата не помага, но дървото помага: n нива по около n, O(n²).

Математиката отзад е във всеки учебник по алгоритми. За работа стига картинката: колко нива и колко работа на ниво.

Колко дълбоко отива рекурсията. Стекът от извиквания е толкова висок, колкото нивата на дървото. Броенето чрез сливане е 17 нива за 100 000 поръчки и се събира навсякъде. Лошото делене е n нива.

Java, C# и JavaScript нямат лимит в брой нива, но стекът им е около 1 MB. При 100 000 вложени извиквания и той свършва, както в quick sort с лош пивот. В Python лимитът е 1000 нива, и лошото делене пада още около 1000 поръчки.

Инверсиите като мярка. Броят инверсии между две подредби е мярка колко се различават: така се сравняват класирания, например резултатите на търсачка с оценките на хора. Insertion sort прави точно толкова размествания, колкото инверсии има входът. Затова е бърз за почти подреден вход и бавен за разбъркан.

Тест

Провери се

1. Дървото на рекурсията на една функция има log₂ n нива, а на всяко ниво работата е общо n. Колко е цената?O(log n)O(n)O(n log n)

2. Функцията вика себе си веднъж, за половината от входа, и прави постоянна работа. Колко е цената?O(n log n)O(log n)O(n)

3. Функцията дели входа на първите n − 1 и последния, вика себе си за n − 1 и сравнява последния с всички останали. Колко е цената?O(n²)O(n)O(n log n)

4. При сливането дясното число е по-малко, а отляво остават 3 невзети. Колко инверсии добавя това взимане?310

5. Защо в Java и C# броят на инверсиите е long, а не int?long е по-бърз от intЗащото сливането работи само с longПри 100 000 поръчки инверсиите могат да са около 2,5 милиарда, а int стига до около 2,1 милиарда

Разделяй и владей и дървото на рекурсията

Бисквитки