áá ááĽá! á¨á˝ááá áľááá ááĽááľá áľáŠá¨áľ á áááŁááá˘
áá° á°ááá á¨ááἠááłáá˝ áľááᣠá¨áá ááá áááľáá ââáĽáŹ á¨áá°áĽ á áá˝ááᢠá ááá áŚáł áĽá á áá áááá. á¨áľáá˝ áĽá á áá SQLite áĽáľá¨ áááá á´áŤáłáł áľá¨áľ áĽá á¨á°ááŤáŠ á¨áá¨á ááśá˝ á áᢠáá á¨áá¨á ááą áĽáá´áľ áĽáá°áá°áŤ á¨ááŤáĽáŤáŠ áĽááľ á˝ááá˝ áĽáť á áᢠáá áŤá á áĽááľ áá¤áśá˝ áĽááłá ááá¨áľ "howdoesarelationaldatabasework" á áá áá áĽáŤáľáá áááá áá˝ááᢠá¨áá á á áá áĽááá á˝ááá˝ á áá áá¸á. á¨á áἠááááš á áá á´áááááá˝ (BigDataᣠNoSQL ááá JavaScript) áĽá¨ááá á¨áá áĽáá´áľ áĽáá°áá አá¨ááááš á°á¨á᪠áĽáá á˝ááá˝á áŤáááá˘
á°ááá á¨áá¨á ááśá˝ á áŁá áŤá¨á áĽá á áŁá á á°ááş áá¸á á¨áŠáá¨áá˛á˛ áŽááśá˝áŁ á¨áááá áá¨ááśá˝ áĽá áá˝ááá˝ áá áááĽáŤáŤáľ?
áĽáá° ááá˘áŁ áŤáááŁáá ááá áá áá áĽá áááᢠáĽá á¨ááἠááłáὠᨠ40 áááłáľ á áá áĽá á áá á¨áá, ááááŤáľ ááá áááŁá. á á¨áĽááą á¨áá áááŁá¸áá áĽááá á áĽáááł áĽáá áłáĽáá˝ á áľááá ááá¨áłáľ áŁáááľ á ááłáľ á ááśáá˝ á¨ááá አá°ááłáľ á áłáááŤááᢠá°ááá á¨ááἠááłáá˝ áĽááą ááááŤáąá á áŁá á áľá°áłá˝ á áá áĽá áĽáá°áá áĽá á áá á ááá á˝áá°-ááłáŚá˝ áá á¨á°áá°á¨á°. á¨ááἠááłáá ááá¨áłáľ ááááľ áŤááľáŁ ááá áá áá°áá á°á áááľ ááľáĽ ááááŁáľ áá ááá áááŁá á¨ááááľáŁ á áá á˝áá áá°á°áľ á ááĽááľá˘
á¨áá á˝áá áááľ ááá˝ á˘áááᣠá¨áá á˝áá ááá á¨ááἠááłáá áĽáá´áľ áĽáá°áá áá áá¨áłáľ á áá°áá. áľááá á áĽ.á¤.á . ááá á¨áááááľ áĽáŤá áĽá áá°á¨áłá áĽáŤááá˝á áĽáá´áľ áĽáá°áá˝á á áľááľáá ááá á ááĽááľ ááŠáľ; á áá áá፠áá á á˝áá ááá¨áąáľ áá˝áá. ááá áŤááĽááľ áĽá¸áá ááá áá áá, á¨áá¨áá áĽáááťáá.
áĽáá° áľáá° áááŽá˝ á¨áá ááľáĽáľáĽááľ (BigO) áŁá á ááłááľ á¨áŽáááá°á áłáááľ áá°á¨áłá áááá˝ áĽáááŤááᢠá ááłááśáťá˝á áá áá á áá°-ááłáĽ áĽáá°ááľá á á áááá ááá áá áŤá áĽáą á áá¨á ááą ááľáĽ áŤááľá ááľáĽáľáĽ áááŽá˝ áá¨áłáľ á áá˝ááᢠáá áľáá áááľ áľááá áá á á°áŠáŤáá á áľááá áá áĽáŹ á¨ááľá á: á¨ááἠááł áĽáá´áľ áĽáá°áá°áŤ SQL áá áá . á á á áľá°áááááᢠáá á¨áłá á¨ááἠááł á˝áá°-ááłáŚá˝áľááá á á áááš áá¨á¨áť áá á¨á˝áá áľá áá áĽá¨á°á°á¨á áĽááłá ááłáĽ á áááľ á˘
áá áĽá áľáá° áááŽá˝á áĽá á¨ááἠá ááááŽá˝á á¨ááŤáŤáľáľ á¨á á áĽá á´áááŤá á˝áá áľááá áĽáąá áááá ἠáááá ááá°áąá˘ á ááłááľ á˝áá°-ááłáŚá˝ ááá¨áłáľ á áľá¸á᪠ááá áá˝áá; áĽááąá áááá áĽá á ááá á á ááá ááłáĄá ááááľ áá˝ááá˘
á ááŤá¨áá˝á á¨á áá áĽáááľ ááá ᣠáá á˝áá á 3 áááá˝ á°á¨ááá á˘
- áá á°á-á°á¨á áĽá á¨áá°á-á°á¨á á¨ááἠááł áááá˝ á á ááá áĽááł
- á¨áĽáŤá ááťáťáŤ áá°áľ á á ááá áĽááł
- á¨ááĽááľ áĽá á¨ááľ áááł á áľá°áłá°á á á ááá áĽááł
áá° áá°á¨áłá áááŽá˝ á°áááľ
á¨áááłáľ á ááľ (á áááᲠá áŠá ᣠá áŠá ...)ᣠááá˘áá˝ áŽáľ á¨ááŤá°áááŁá¸áá á¨ááááá˝ áĽááľ á áľááá ááá áá á¨áŁá¸áᢠá¨ááᨠáŽáááá°áŽáťá¸áá á˛áአáĽá áá᪠ááŁá¨á áľáááá˝á áľáá° áááŤá¸áá áĽá áłáł á ááááŤá¸áá áŤáá áá áá˘
á áá ááá ááľáĽáŁ á¨ááἠááłáá ááá¨áłáľ á áľááá áľááá á¨áĽááá á˝áá°-ááłáŚá˝ ááľáĽ á ááłááśášá á áľáłááłá˝áááᢠá áá°-ááłáĄáá á áľá°áááááᢠá¨ááἠááł áá¨á á áá.
áŚ(1) vs O(n2)
á á áá ááᣠáĽá ááá˘áá˝ áľá áľáá° áááŽá˝ á¨áá ááľáĽáľáĽááľ ááľ á¨áá¸áá... áĽá áľááá áá¸á!
ááá áá á¨áĽá áłáł áá áľáľááá (áşá á áááŤá) ááá á ááá°á¨ááśá˝ áĽá¨áłááá á¨áá áá á á˝áá° ááłáĽ áá¨áłáľ á áŁá á áľááá ááááᢠáĽá áĽááľá áĽáá°ááááąáľ, á¨ááἠááłáá˝ áááąáá áááłáá˝ áááá á ááŁá¸á! ááĽáĄá ááá¨áłáľ á¨ááŤáľáááá á áá áá áĽáá˛áŤáłáá á áá°áááᢠáá á áá áá ááŞá áá°á¨áľ áŤá°á¨á á¨áááťá¸áľ á˝áá°-ááłáĽ áĽááľáá¨áł áá¨áłáá (áá áá á¨á°áá á¨á° áááťá¸áľ).
á˝áá°-ááłáĽ
á¨á áááŞáá á¨áá ááľáĽáľáĽááľ áá°áá°á á¨ááἠáá á á áááŞááá ááá°áá á áá áŤá á áá áĽáá°áááľáľ ááá¨áľ áá á áá. áá áá ááľáĽáľáĽááľ ááááá áľáá O á¨ááłáĽ ááľ áĽáá áááá áá ááááľ áĽá á áá á¨ááá áá ááľ á¨á°áá°á á¨ááĽá áľ áĽááľ áá áŤá á áŚááŹá˝áá˝ áĽáá°ááŤáľáááá á¨áááá˝ á°ááŁá áá ááá˘
áááłá "áá á áááŞáá ááľáĽáľáĽááľ O(á ááłááľ_á°ááŁá()) á áá" áĽáŹ áľááá áľáá° ááá á¨á°áá°á áá á áŤáá ááἠáááľáŤáľ á ááłááľ_á°ááŁá(a_certain_amount_of_data) áľáŤáá˝á ááááá áááľ ááá˘
áľááá ááłá á¨ááἠáá á á áá°áá**á áá áá፠** á¨ááἠáá á á áá¨áá á¨ááááá˝ áĽááľ áĽáá´áľ áĽáá°áá¨áá. á¨áá ááľáĽáľáĽááľ áľáááá á¨ááááá˝ áĽááľ á áá°áĽá, ááá áá á¨ááľáá¸á፠ááá áááááľ áĽáŠ ááááľ áá.
á áá ááŤá ááľáĽ áá°ááŤáŠ á¨á áááŞáá á¨áá ááľáĽáľáĽ ááááśá˝ á¨ááĽá áľ ááἠáá á áá á˛áááá á¨ááááá˝á áĽááľ áá¨áľ áá˝ááᢠáĽááąá áááłá¨áľ áááŞáá ááá á°á áááŠá˘ á áá á áááá á¨ááἠáá á á ááĽáᾠᨠ1 áá° 1 á˘ááŽá áá¨ááŤá. áĽá áá¨áľ áĽáá˝ááá:
- áŚ(1) ááá á¨ááŤááἠááľáĽáľáĽááľ áá áá áááŤá (á áá áá፠áá ááľáĽáľáĽááľ á°áĽá á áá áŤá)á˘
- O(ááááĽ(n)) á á˘ááŽáá˝ á ááá á áá¨áá á˘áá áá á°á ááá˘.
- á áŁá á áľá¸ááŞá á˝áá - áŚ(n2)ᣠá¨ááááá˝ áĽááľ á ááĽááľ á¨ááŤáľáá áľ.
- áááš áááľ ááľáĽáľáŚá˝ áá á ááĽááľ áá¨ááŤá.
ááłááá˝
á áľáá˝ á¨ááἠáá á á O(1) áĽá O(n2) ááŤá¨á áŤáá ááŠááľ áĽáá áᣠá¨ááŁá á áá°ááᢠáááłáᣠ2000 á¤ááááśá˝á áááľáŹáľ á¨ááŤáľá˝á áľáá° ááá á áá áĽáá áá˘
- á¨O(1) áľáá° ááá 1 ááá áŤáľá¨ááááłá
- ᨠO(log(n)) áľáá° ááá 7 áľáŤáá˝á áŤáľá¨áááá
- á¨O(n) áľáá° ááá 2 áľáŤáá˝á áŤáľááŁááá
- á¨O(n*log(n)) áľáá° ááá 14 áľáŤáá˝á áŤáľááŁááá
- á¨O(n2) áľáá° ááá 4 áľáŤáá˝á áŤáľá¨ááááłá
á O(1) áĽá O(n2) ááŤá¨á áŤáá ááŠááľ áľáá
áááľáá (4áááŽá áŚááŹá˝ááľ) áá á˘á á 2 áá´ áłáŁáá
ᣠáá
á áá áĽáť áá á ááá
á áĽáá áľááá á¨áááᢠá áĽáááĽ, áááá ááááŁá áŞáŤáá˝ ááááŁá á áá˝áá
áĽáá°á°ááááŠáľáŁ á¨áá°á áá á áŤáá áá¨á áá á˛á°áŤ áá á á˝áá° ááłáĽ ááá á ááá á áľááá ááᢠá áá áá á áááŞáá 1 ááĽá¨ áááŽá˝á ááŤááľ áŤáá áľ (áá á ááłáłá¤á áŤá áŤá á á áá°áá)
- á¨O(1) áľáá° ááá 1 ááá áŤáľá¨ááááłá
- ᨠO(log(n)) áľáá° ááá 14 áľáŤáá˝á áŤáľá¨áááá
- á¨O(n) áľáá° ááá 1 áľáŤáá˝á áŤáľá¨ááááłá
- á¨O(n*log(n)) á áááŞáá 14 áľáŤáá˝á áŤáľá¨ááááłá
- á¨O(n2) áľáá° ááá 1 áľáŤáá˝á áŤáľá¨ááááłá
ááłáĄá á áá°áŤáá, áá á O(n2) áľáá°-ááá áĄá ááá áŁáľ áá á áá áĽááá (áááľ áĽááłá!). á áá¨áá áá á áá áá 0 áŤá¨áᣠáľáá˝ áĽáá áá áááá°áľ áá áááááłáá˘
á áá áĽáá áĽáááľ
áááŁááťááľ
- áĽáŠ á¨áá˝ á áá á¨áĽ ááá á O(1) ááľáĽ á ááľ ááĽá¨ ááá áŤáááá˘
- áááá á¨áá áá áááá á O(log(n)) áá áá¤áľ áŤáľááá.
- áľááľá áááá á O(n) ááľáĽ áá¤áśá˝á áŤáľááá.
- ááᥠá¨áá°áá°á áľáá° áááŽá˝ ááľáĽáľáĽááľ O(n*log(n)) á áá¸áá˘
- ááĽá á¨áá°áá°á áľáá° ááá O(n2) ááľáĽáľáĽááľ á ááá˘
ááłá°á˘áŤáĄ á áááĽááľ áááá˝ áĽááá á áľáá° áááŽá˝ áĽá á¨áá¨á á ááááŽá˝á áĽááŤááá˘
áĽá á áááľ á¨á áááŞáá áá ááľáĽáľáĽááľ á ááĄ-
- á ááŤá á¨ááłá áááł
- ááἠááłá
- áĽá á áŁá á¨á¨á áááł
á¨áá ááľáĽáľáĽááľ áĽááá áá á áŁá á¨á¨áá áááł áá.
áĽá¨á°áááአáŤáááľ áľá á áááŞáá á¨áá ááľáĽáľáĽááľ áĽáť ááᣠááá áá ááľáĽáľáĽááľ á áá¨á°ááľ ááá áá áŤááĄ-
- á¨á áááŞáá áá á°á¨ áľááľáł áááł
- á˛áľá I / O áááł á áááŞáá
á áĽáááĽ, ᨠn2 á¨á¨á ááľáĽáľáĽ á˝ááŽá˝ á á, áááłá:
- n4: áá á á°áá áá! á¨á°á ááąáľ áľáá° áááŽá˝ ááŤá¨á á ááłááśáš áá ááľáĽáľáĽááľ á áá¸áá˘
- 3n: áá á°áá á¨á¨á áá! á áá á˝áá ááŤá¨á á¨áááŤá¸á áľáá° áááŽá˝ á ááą áá ááľáĽáľáĽááľ á áá (áĽá á áĽáááą á áĽá á¨ááἠááłáá˝ ááľáĽ áĽá á áá áááá)á˘
- factorial n: á áľáá˝ áá á ááἠáĽááłá áá¤áľáá á ááŤá˝ á áŤáááá˘
- nn: áá ááľáĽáľáĽ ááá áŤáá áááľ, áá á¨áĽááľá á¨á°ááŁá ááľá áááá áĽáŤáľáá áá áá ...
ááłá°á˘áŤáĄ á¨áľáá
ጠáľáŤá áľáááá ááşá á áá°á áá
á ááłáĽ áĽáťá˘ áá
áá á˝áá á áá ááá ἠáá˝áá
á áá áľ á°ááľá
áľáĽáľáĽá áá°áá°á á˛áŤáľááá áá áłá°áááá ? áááľá? áĽááľá ááááľ() á°ááŁá áĽáá áá áŠáłá... áĽáş áĽáŠ áááľ... ááłáłá¤á áá áá á áááľ() á°ááŁá áĽáá´áľ áĽáá°áá°áŤ áá¨áłáľ á ááŚáľá˘
áĽá áĽáŠ á¨áá°áá°á áľáá° áááŽá˝ á áᣠáľááá á áŁá á áľááá á áááľ áá á á°áŠáŤáááĄ- áá°áá°á á áá áľ. á áá ááἠáá°áá°á ááá á áá áĽáá°áá ááá¨áą áá˝áá ááááá á¨áĽáŤáá ááťáťáŤ ááá á áá ááľá¨á á ááĽááľá˘ á á°á¨ááŞáᣠá¨áá á°áľ ááááľá áá¨áłáłá˝á á¨á°á áŤáá á¨á፠áłáłá¤á ááááá á°ááŁá á áá áĽááľáá¨áł áá¨áłááᢠáááąá áľáá áśá˝ á°ááá° ááááá (áá á°áľ áá á á).
á áá áľ
áá áĽáá° áĽá á áá áľáá° áááŽá˝áŁ áá°áá°á ááááá á áĽáááľ áá á¨á°áá°á¨á° ááᥠ2 á¨á°á°á¨á°áŠ áá áá¸á N/2 á áá° N-element á¨á°á°á¨á°áŠ áľááľá ááŞáá˝ N áŚááŹá˝áá˝á áĽáť ááᢠáá ááá áá á°áľ ááŁááá˘
á ááá ááłá áá áá áááľ áĽáá°áá áĽáááĄ-
áá á áá á¨ááŤáłá¨á á¨áá¨á¨áťáá á¨á°á°á¨á°áŠ áŁá 8-á¤ááááľ áľááľá áááááŁáľ á 2 áŁá 4-á¤ááááľ áľááľáŽá˝ áá á ááľ áá áĽáť áá°ááá áŤáľáááááłáᢠáááąá áŁá 4-á áŁá áľááľáŽá˝ á áľááľáá á¨á°á°á¨á°áŠ áľááááĄ-
- 1) áááąáá á¨á ááá á áŤááľ á áááľ áľááľáŽá˝ (á ááááŞáŤá á¨á áá = ááááŞáŤ) áŤááłáľáŤá
- 2) á¨ááŤá áá° 8 á¤ááááśá˝ áľááľá áááľááŁáľ áľáášá ááá°áą
- 3) áĽá áľáášá ááĽá¨ ááá áá° áá°áąá áľ áľááľá ááľáĽ áá°áááĽáá á áŤá áááą
- áĽá á¨á ááą áľááľáŽá˝ á¨áá¨á¨áťáá á áŤá áĽáľáŞá°ááą áľá¨áľ 1,2,3áŁXNUMXáŁXNUMX ááľáááľá˘
- á¨ááŤá áá° 8 á¤ááááśá˝ áľááľá áááľááŁáľ á¨ááááá áľááľá á᪠á áŤááľ ááľá°áá¸ááá˘
áá á¨áá°áŤá áááąá áŁá 4-á¤ááááľ áľááľáŽá˝ áľáá°á°á¨á°áŠ áĽá á áĽáá፠áľááľáŽá˝ ááľáĽ "ááááľ" á¨ááĽááľáá˘
á áá áá´áá áľáá°á¨áłá á¨áá á°áľ á¨áĽá pseudocode áĽáááĄ-
array mergeSort(array a)
if(length(a)==1)
return a[0];
end if
//recursive calls
[left_array right_array] := split_into_2_equally_sized_arrays(a);
array new_left_array := mergeSort(left_array);
array new_right_array := mergeSort(right_array);
//merging the 2 small ordered arrays into a big one
array result := merge(new_left_array,new_right_array);
return result;
á¨ááááľ áá°áá°á á˝ááá áá° áľááá˝ á˝ááŽá˝ áá¨áááá á¨ááŤá á¨áľááážášá á˝ááŽá˝ áá¤áľ áŤááá á¨áááá á˝áá áá¤áľ áááááľ (ááľáłááťáĄ á¨áá á áááľ áľáá°-ááá áá¨ááá áĽá áá¸áá ááŁáá)ᢠáá á áľáá° ááá áŤáá°á¨áłá á áľá¨áá ; áááááŞáŤ áá áłá¨á á áááŁááᢠáá¨áłá á¨áá˝á á¨ááᣠáá á áľáá° ááá áĽáá° áŁá áááľ-á°á¨á áľáá°-ááá áá á¨áá¨ááĄ-
- á¨áá¨ááá á°á¨áᣠáľááľá áá° áľááá˝ áľááľáŽá˝ á¨á°á¨áááá áľ
- á¨ááá¨áľ á°á¨á áľááá˝ áľááľáŽá˝ á¨ááŁááŠá áľ (á áĽá¨áľá á áá áá) áľáá áľááľá áááá á ááá˘
á¨ááá á°á¨á
á áááá á°á¨áᣠáľááľá á 3 áĽáá¨áá˝ áá° á ááłá áľááľáŽá˝ á°á¨áááᢠáá°á áá á¨áĽááááá˝ ááĽá áá (N) áá (ᨠN = 8 ᣠlog(N) = 3)á˘
áá áá áĽáá´áľ á áááá?
áá á áá! á á ááľ áá - ááłáĽ. ááłáĄ áĽáŤááłááą áĽááá á¨áááá áľááľá áá á á 2 áá¨ááá. á¨áĽááááá˝ áĽááľ áááá áľááľá ááááľ áá¨ááá á¨áá˝áá áľ áá áĽááľ áá. áá á¨áááŞáá áľáááá ááş áá (á¤á 2)á˘
á°á¨á áá°áá°á
á áá°áá°á á°á¨áᣠá á ááľ áá á (áá á ááá) áľááľáŽá˝ ááááŤáᢠá áĽáŤááłááą áĽááá áĽá á¨ááááľ áľáŤáá˝á áá°ááĽáŤá áĽá á á ááá á᪠N = 8 ááááá˝ áá:
- á ááááŞáŤ á°á¨á áĽáŤááłááłá¸á 4 áľáŤáá˝á á¨áá¨áá 2 áá áśá˝ á áááľ
- á ááá°áá á°á¨á áĽáŤááłááłá¸á 2 ááááá˝ á¨ááŤáᥠ4 áá áśá˝ á áááľ
- á áŚáľá°áá á°á¨á 1 ááááá˝ á¨ááŤáľá¨áá 8 áá á°áľ á áááľ
á¨áááἠááľáłááť (N) á°á¨ááá˝ áľááᣠá á áá á᪠N * log (N) ááááá˝.
á¨ááááľ ááááśá˝ áĽá áá˝
áá á áááŞáá á áŁá áááá á¨ááá ááááľáá?
ááááŤáąááĄ-
- á á˛áľ áľááľáŽá˝ áĽááłáááĽáŠ ááá áá á¨áá¤áľ áľááľáá á ááĽáł áĽáá˛ááአá¨ááľáłááťáá á áťáŤ áááááľ ááá¨á áá˝ááá˘
ááłá°á˘áŤáĄ á¨áá
á áááľ áľáá° ááá ááŁáá
- ááá á¨áá á¨á˛áľá I/O á áá áłáŤá°áá á¨á˛áľá áŚáłá áĽá áľáá˝ áá á°á¨ áľááľáłá á á°ááłáłá áá ááá áá áááἠáá˝ááᢠááłáĄ á áá áĽá¨á°á°áŠ áŤááľá áááá˝ áĽáť áá° áá á°á¨ áľááľáł ááŤá ááᢠáŁááĽá áááŁááľ á áá á¨áĽ áŁá 100 áááŁááľ áá á°á¨ áľááľáł ááľ áĽáť áá°áá°á á˛áŤáľááá áá á áľááá ááá˘
ááłá°á˘áŤáĄ á¨áá
á áááľ áľáá° ááá ááŁáá
- á á ááŤáł áá°áśá˝/ááŽá˝/á°áá¨áŽá˝ áá áĽáá˛á°áŤ ááá¨á áľá˝ááá á˘
áááłáᣠá¨á°á¨ááá á¨áá
á°áľ á áááľ á¨áá áá á áŤááľ á ááą ááá˘
- áá á áááŞáá áĽááłáľá áá° ááá (á áĽáááĽ!) áááá á áá˝áá.
áá
á¨áá°áá°á áľáá°-ááá á á áĽááááš (ááá áŤááá) á¨ááἠááłáá˝ ááľáĽ áĽá
á áá áááá, áá áĽáą áĽáť á áá°áá. á¨á áá áááá
á¨ááá áá
áá ááá ἠáá˝ááá˘
áľááľá ᣠá¨áá áĽá á¨áá˝ á á¨á´á
á áá á¨áá ááľáĽáľáĽááľ áĽá á¨áá°áá°á ááłáĄá á¨á°á¨áłá, áľá 3 á¨ááἠá ááááŽá˝ ááááá áááŁá. áá á áľááá áá ááááŤáąá áĽááą á¨áááá á¨ááἠááłáá˝ áá á¨áľ áá¸á. á áá°-ááłáĄáá á áľá°áááááᢠá¨ááἠááł áá¨á á áá.
áľááľá
áŁá áááľ-ááŹáľ áľááľá ááá á¨áá¨á ááá á ááᢠá á¨á´á áĽáá° áľááľá ááłá°áĽ áá˝áá. áááłá:
áá áŁá 2-ááŹáľ áľááľá á¨áľáá˝ áĽá á ááśá˝ áŤááľ á á¨á´á áááĄ-
- áĽáŤááłááą ááľáá á ááľ á áŤáá ááááá
- á ááśá˝ á áá á áŤáá á¨ááááš ááĽá¨áśá˝á áŤá¨ááťáá˘
- áĽáŤááłááą á ááľ á¨á ááľ á¨á°áá°á á áááľ (á˘áá˛ááᣠááĽá¨áááᣠáá...) ááἠáŤá¨ááťáá˘
áá áá¨áá ááá¨áá¸áľ áĽá ááááá¨áľ ááš áá, ááá áá, á¨á°áá°á áĽá´áľ ááááľ á˛ááá, áá á°áľáá á áá°áá.
áááłáᣠá áŠáááľáľ áŞááá°á ááľáĽ á¨áá°áŠáľá áááá áááśá˝ áááááľ á¨ááááᣠá¨áľá á¨áŠáááľáľ áŞááá°á ááá á ááááá áááá áĽáŤááłááąá á¨áľá áááá¨áľ ááááĽááᢠN ááĽááśá˝á áŤáľá¨ááááłáá¨áľ N - á¨ááľááŽá˝ áĽáᾠᣠááĽá áŤááá ᣠáá ááŁá ááááľ ááá áá˝áá? á¨ááá˝ áá ááá°ááá ááá á áá ááá˘
ááłá°á˘áŤáĄ- á áĽáááš áááá á¨áá¨á ááśá˝ á á¨á´ááá˝á á áĽááľ ááá¨áá¸áľ á¨á°áŤáá á á°áŤá°áŽá˝á áŤáááŁáᥠááá á¨á°á°áŤá á á¨á´ááá˝ áĽá á˘áá´ááľ á¨á°á°áŤá á á¨á´ááá˝á˘ ááá áá áá á á ááśá˝ áĄáľá ááľáĽ á ááľ á¨á°áá°á áááł á ááĽááľ á¨ááááľ á˝ááá á ááááĽá.
á¨ááἠááł áá áĽá áá¨á á áá
áááľáŽá˝ á¨ááá áá áአááĽá¨áľ áŤáá áááľáŽá˝ áá ááᣠá áĽáŤááłááą ááľááá ááááľ áŤáá ááá ááá á áá áľáĄ-
- á á፠ááĄáľ áá ááľáĽ á¨á°áááĄáľ áááá˝ áá áá ááŁá
- á áľááááá áááľ áá ááľáĽ á¨á°áááĄáľ ááá áááá˝ áŤáá°
áá á áĽááł áá áááľ áĽáá°áá áĽáá
ááłáĽ
áá áá N = 15 ááĽá¨ áááŽá˝ á ááľ. 208 ááá áá áĽáá ááĄ-
- 136 ááá á¨ááá áľ áľá áĽáááŤáá á¨136<208 ááᎠáľáááááá á¨ááľááá ááá 136 á ááťááá˘
- 398>208 áľááá áĽá á¨áááá¨á°á á¨ááľááá ááá 398 á፠áááľ áá ááá˘
- 250>208 áľááá áĽá á¨áááá¨á°á á¨ááľááá ááá 250 á፠áááľ áá ááá˘
- 200<208áŁáľááá áĽá á¨áááá¨á°á áľáááááá á¨ááľááá ááá 200 ááᢠáá 200 ááá áľáááá áááľ áá á¨áááᢠáá á¨áá (ááááŤáąá áŤá, á áľááááá áááľ 200 ááľáĽ áááá).
á áá 40 ááá áá áĽáá á
- 136. ᨠ136> 40 ááᎠá¨á፠ááĄáľ áá 136 áá á¨áááá¨á°áá˘
- 80 > 40ᣠáľááá áĽá á¨áááá¨á°á á¨ááľááá 80 á፠áááľ áááľ áá ááá˘
- 40= 40ᣠááľááá ááááľ á áá˘. á ááľááá ááááą ááľáĽ áŤááá á¨á¨áľá ááłáá፠(á ááľá áá á¨áááłá) á°ááľáŹáŤáá áĽá áá°á°á á á¨áľá ááłáá፠á á°áá á¨áĄ ááľáĽ áĽááá¨áłááá˘
- á¨á¨áľá ááłáááŤáá ááá ááᥠá á áá á¨áĄ ááľáĽ á¨áľ áĽááłá áĽááłáá áŤáľá˝áááᣠáľááá áá˛áŤáá ááááľ áĽá˝áááá˘
á áá¨á¨áťá, áááąá ááááá˝ á áá ááľáĽ áŤááľá á°á¨ááá˝ áĽááľ áŤáľá¨áááá. áľá áá á°áľ áá°áá°á áŤááá ááá á áĽááá áŤáá áĄáŁ á¨áá(N) á°á¨ááá˝ áĽááłá áá¨áľ á ááŚáľá˘ ááááŁáᢠá¨ááá á᪠áááἠ(N), ááĽá á áá°áá!
áá° á˝ááŤá˝á áĽááááľ
áá áá á áŁá á¨áá ááá áá° á˝ááŤá˝á áĽááááľá˘ á¨ááá á˘áá˛áá ááá ᣠá áá°áá á áá á¨áĽ ááľáĽ á¨á ááľá á°á ááá á¨áááá ááĽá¨ááá á áľáĄáľá˘ á¨á áá á¨áĄá "ááá" ááľá (á ááľ 3) á¨áŤá áá á áá áĽáá áá˘
- á áŠáŹ ááľáĽ áá áĽáá°áá°áŤ ááá á¨ááá
- áłááá áĽáŞáłá፠á¨áááááá ááľááá ááááľ áááááľ ááá áľááá¨áłáá
- á "UKnode" ááľáĽ á¨áŠáŹ á¨á°áŤá°á ááááŚá˝ á¨áááá áľá áŚáł áŤáááá˘
áá ááá áľááľáá á ááĽáł á¨á°á áá á¨á¤á áŚááŹá˝áá˝ ááá áá(N) áľáŤáá˝á áŤáľá¨áááᢠá áá áŤáá¨áĽá¨á ááᢠá¨ááἠááł áá¨á á áá.
áááá˝á (á¨ááľá áĄáľáá˝á) á¨áááłá°á á°ááŁá áĽáľáŤáááľ áľá¨áľ áááááá á¨ááľáŽá˝ áĄáľá (ááĽá¨áááᣠááĽáᣠ2 ááľááŽá˝áŁ ááĽá áĽá ááĽá¨áááᣠáá...) áá፠áá ááááŁáľ áá˝ááᢠá¨ááááš ááŤá¨á ááá (áá á á áá¨á ááą ááľáĽ áááááá áá°á¨áłá ááááśá˝ áá).
B+TreeIndex
áá áá á¨á°áá°á áĽá´áľ áááááľ á á°áἠá˘á°áŤá, á ááááá áľ áá áľáá á˝áá á á á áááľ áĽá´áśá˝ ááŤá¨á áĽá ááĽá¨ áááŽá˝á áŤáá. áá áá O(N) áŤáľá¨ááá ááááŤáąá á áá ááľáĽ áŤááá áĽáŤááłááąá ááľááá ááááľ áááá¨áľ áĽá á áĽááá áááľ áĽá´áśá˝ ááŤá¨á áááá áŤá¨ááᥠ(áááłá á áłáá á¨áá ááá¨áĽ)ᢠá¨áá á á áá áááá áá ááá ἠáľáááĽááľ áá ááá á¨á˛áľá I / O á°áľáá á áá°áá. á áĽááľ á¨ááá°áŤá áľá ááááľ áááá á ááĽá ááá áĽáŤá. áá áá á˝áá ááá á¨á áááá á¨áá¨á ááśá˝ á¨á°áťáťáá á¨ááľá áá á˘+ ááá áá áááᢠá B+ áá ááľáĽ;
- á áŁá áá á°á á áááá˝ (á á áá˝) áĽáť áá¨áá áá¨áá¸áľ (á á°ááá á°áá á¨áĽ ááľáĽ á¨á¨áľáá˝ áŚáł)
- á¨á°ááŠáľ á áááá˝ áĽáá á áᢠáááááá áá° áľááááá ááľááá ááááľ á ááá áá áľ.
áĽáá°áááá¨áąáľ, áĽáá á°á¨á᪠á áááá˝ (áááľ áá) á á. á áĽáááĽ, á°á¨á᪠á áááá˝, "á¨ááłá á áááá˝" á áááľ, áá á áľáááááá ááľááá ááááľ (á á°ááłá á áá á¨áĽ ááľáĽ áŤááľá á¨á¨áľáá˝ áŚáł á¨ááŤá¨áá˝) áĽáá˛áŤáá áá¨áłááłá. áá á¨áááá ááľáĽáľáĽááľ á ááá áŚ(áá(N)) áá (á ááľ á°á¨á᪠á°á¨á áĽáť áá áŤáá)ᢠáľáá ááŠááą áá ááᢠá áá á°á á°á¨á áá áŤá á áááá˝ á¨á°á°áŞááťá¸á áá á¨á°ááá áá¸á.
á áá B+Treeᣠá 40 áĽá 100 ááŤá¨á áĽá´áśá˝á áĽá¨ááá á¨áááĄ-
- áá áĽáá° ááľáá áá 40 (ááá ᨠ40 á áá 40 á¨ááá á áŁá á áἠá¨áá áĽá´áľ) áááá áŤáľáááááłáá˘
- á¨á፠40 áĽáľáŞá°ááą áľá¨áľ ááĽáł ááŤážá˝á á áá áá 100 ááŤážá˝á áá°áĽáľáĄá˘
M á°á°áŞáá˝á á ááá áĽáá á áĽá áá N ááśá˝ á ááľá˘ á ááľ á¨á°áá°á ááľááá ááááľ áááá áá áĽáá° ááľáá áá áá (N) áŤáľá¨áááᢠáá áá á ááľááá ááááľ á áá´ áŤááᣠá°á°áŞááťá¸áá á ááŁááľ á M á°á°áŞáá˝ áŤáááᢠáá ááá M+log(N) áĽáť áŤáľá¨ááá á ááľáá áá áá á¨á¤á áŚááŹá˝áá˝ áá á˛áááá ááááá˝. á¨áá á á áá áááá áá ááá ἠá áá á á áĽááľá (M+log(N) nodes áĽáť) áá áááľ á¨á˛áľá á á áááá ááááłá áááľ ááᢠM áľáá˝ á¨áá (áááłá 200 á¨áľáá˝) áĽá N áľáá á¨áá (1 á¨áľáá˝) áľáá ááŠááľ áááŤáá˘
áá áĽáá á á˛áľ á˝ááŽá˝ á á (áĽáá°áá!). á áłáłá¤á ááľáĽ á ááľ á¨áľá áŤá¨á ááá á¨á°á¨á (áĽá áľááá á á°ááá° B+Tree á˘áá´ááľ)áĄ-
- á B+Tree ááľáĽ áŁááľ á áááá˝ ááŤá¨á áĽáááľá áá á á á ááŚáľáŁ áŤáá áá፠áŁáá°á°á¨á°á¨ áá ááľáĽ áŤááľá á áááá˝ ááááľ á áá˝ááá˘
- á B+Tree ááľáĽ á ááľá°ááá á¨á°á¨ááá˝ áĽááľ ááŤá á ááŚáľáŁ áá áŤááá áá ᨠO(áá(N)) á¨áá ááľáĽáľáĽááľ O(N) ááááá˘
á áá á áááá, B+Tree áĽáŤáąá ááá áĽá áááá ááá á áá áľ. áĽáá° áĽáľá áá, áá á áľáááľ á°áá áĽá áŚááŹá˝áá˝ á áľáᣠááťáá. ááá áá áá á áá áááŁáᥠá B+ áá áá O(áá(N)) ááľáĽ ááľááŁáľ áĽá áá°á¨áᢠááá á áá á ááłááśáťá˝á áŤáá á¨á°áá˝ááľá˘ á áŁá áĽá á˘áá´ááśá˝á áá áá áĽáŠ ááłáĽ á áá°áá. á áĽáááľáŁ á á°áá á¨áĽ ááľáĽ á¨á¨áľá á ááĽááľ ááľááŁáľ/áááá/áá°á¨á áĽáŤáááá ááá˘ááááŤáąá áłáłá¤á ááĽáŤááłááą á˘áá´ááľ ááľ á¨áá áŚ(áá(N)) á á áŤá á áá áá á¨á áá á¨áĄá á˘áá´ááśá˝ áááá áŤáľáááááᢠá¨áá á á áá á˘áá´ááśá˝á áá¨áá áá°á¨á᪠á¨áĽáŤ áŤá áááľ áá á¨ááĽááľ á áľá°áłáłáŞ (á á˝áá áá¨á¨áť áá ááááťá).
áá áá áááá á¨ááŞáá˛áŤ ááŁáĽá áá¨áľ áľá˝ááá
ááľáłááťáĄ á ááľ á ááŁá˘ á áá á°á á°á¨á áááťá¸áľ ááááŤáľ ᨠB+ áá áá á áá áááá ááá áĽááłáá áľ áááŽááá˘
Hashtable
á¨áĽá á¨áá¨á¨áťá á áľááá á¨ááἠááá á á¨áá˝ á°áá á¨áĽ áá. áĽá´áśá˝á á ááĽááľ áááá á˛ááá áá á áŁá á áá ááᢠá á°á¨ááŞáᣠá¨áá˝ á áá á¨áĽá áá¨áłáłá˝á áá˝ ááááá (áá˝ ááááá) á¨ááŁá á¨á፠áłáłá¤á ááááá áľáŤá á áá áĽááľáá¨áł áá¨áłááᢠhash ááááá). áá á¨ááἠááá á á ááłááľ ááľáŁá áááŽá˝á ááá¨áá¸áľ á áá¨á ááą áĽá á áá áááá (áááłáጠá¨áááá፠á á¨á´á ááá ááľ áááł, áááąáá áĽááá á á˝áá°-ááłáŚá˝ á áá áá áĽáááá¨áłáá).
áá˝ á áá á¨áĽ á ááľá ááĽá¨ ááá á ááá á ááĽááľ á¨ááŤáá á¨ááἠááá á ááᢠá¨áá˝ á á¨á´áá áááááŁáľ á¨áá¨á°ááľá áááá áŤáľáááááłá
- ááá ááĽááľá ááĽá¨ áááŽá˝
- á¨áá˝ á°ááŁá áááá. á¨á°á°áá ááá hashes á¨ááĽá¨ áááŽá˝ ááá áŚáł áá°áŁá (ááŁáá áááá˝ ).
- áááá˝á áááááá á°ááŁá. áľáááááá ááá áŤáá á áá, áá áá áá á á á áá áá á¨áááááľá á áŤá á ááá ááľáĽ ááááľ á ááĽááľ.
ááá ááłá
á ááľ ááá˝ ááłá áĽááá°áľáĄ-
áá á¨áá˝ á á¨á´á 10 áááá˝ á ááľá˘ á°áá áľáááአ5 áááá˝á áĽáť áá á¨áłááŠáľ ááááá áĽáá áááá á áľáááá áááá 5 á áŤáľá áĽááľáľáłá áĽáá áłááᢠáĽá á ááľ hash á°ááŁá modulo á°á ááá 10 ááá. á áá á ááááᣠáááá áááááľ á¨ááĽá¨áąá ááá á¨áá¨á¨áť á áá áĽáť á á¨áá˝áłáááĄ-
- á¨áá¨á¨áťá á áá 0 á¨áá ᣠááĽá¨ ááአáá° ááá 0 áááľáá áŁ
- á¨áá¨á¨áťá á áá 1 á¨áá ᣠááĽá¨ ááአáá° ááá 1 áááľáá áŁ
- á¨áá¨á¨áťá á áá 2 á¨áá ᣠááĽá¨ ááአáá° á áŤáŁá˘ 2 áááľáá áŁ
- ...
á¨á°á áááŠáľ á¨áá á á á°ááŁá á ááá á áááľ á˘áá˛áá ááŤá¨á áĽáŠáááľ ááá˘
á¤ááááľ 78 ááááľ ááááá áĽáá ááĄ-
- á¨áá˝ á á¨á´áá á¨áá˝ áŽáľá á78 áŤá°ááᣠáá á 8 ááá˘
- á¨áá˝ á á¨á´áá ááá 8á áááá¨áłáᣠáĽá áŤááá á¨ááááŞáŤá ááĽá¨ ááá 78 ááá˘
- áĽá 78 á áľáááľáááá˝á˘
- á¨ááá á᪠2 ááááá˝ áĽáť ááᢠ(á ááą á¨áá˝ áĽá´áąá áááľááľ áĽá áááá á ááá ááľáĽ áŤááá ááĽá¨ ááá ááááá¨áľ)á˘
á áá á¤ááááľ 59 ááááľ ááááá áĽáá ááĄ-
- á¨áá˝ á á¨á´áá á¨áá˝ áŽáľá á59 áŤá°ááᣠáá á 9 ááá˘
- á¨áá˝ á áá á¨áĽ á ááá 9 ááľáĽ ááááá ᣠá¨ááááŞáŤá ááĽá¨ ááá 99 áá ᢠᨠ99! = 59 ááᎠᣠá¤ááááľ 99 áľáááá á áŤá á áá°ááá˘
- á°ááłáłá á áááᎠá áá áá, ááá°áá ááĽá¨ ááá (9), áśáľá°áá (79), ..., á¨áá¨á¨áťá (29) ááá°áłá.
- ááĽá¨ ááá á áá°áááá˘
- áááá 7 áľáŤáá˝á á áľá¨áááá˘.
áĽáŠ á¨áá˝ á°ááŁá
áĽáá°áááá¨áąáľ, á áááááľ áĽá´áľ áá á áááľá¨áľ, ááá á ááľ á áááľ á áá°áá!
á áá á¨áá˝ á°ááŁáá á¨áá¨áአ1 áááá (áááľá á¨áá¨á¨áťáášá 000 á ááá˝ ááá°áľ) ᣠááá°áá ááá á ááá 000 ááľáĽ ááá ááĽá¨ áááŽá˝ áľááá 6 ááá áĽáť áŤáľá¨áááᢠáľááááá áá°á á áŁá áľáá˝ á¨áá ááĽá¨ áááŽá˝á á¨áŤá áŁáá˛áá˝á á¨áááĽá áĽáŠ á¨áá˝ á°ááŁá ááááľ ááá˘.
á áĽá ááłá áĽáŠ á¨áá˝ á°ááŁá ááááľ ááá ááᢠáá áá ááá ááłá ááᣠááá á áááá áľ áá áĽáŠ á¨áá˝ á°ááŁá ááááľ á¨á áá á¨áŁáľ ááá˘
- ááĽá¨ááá (áááłá - á¨á áŤáľ áľá)
- 2 ááľááŽá˝ (áááłá - á¨á áŤáľ áľá áĽá á¨ááááŞáŤ áľá)
- 2 ááľáá áĽá áá (áááłá - á¨á áŤáľ áľá, á¨ááááŞáŤ áľá áĽá á¨áľáááľ áá)
- ...
á áĽáŠ á¨áá˝ á°ááŁáᣠá¨áá˝ á áá á¨áĽ ááá áá áŚ(1).
áľááľá vs áá˝ á á¨á´á
ááá áľááľá á áľá ááá?
á áĽáŠ áĽáŤáá˘
- á¨áá˝ á á¨á´áá ááá áá˝áá á á¨áá áá° áá á°á¨ áľááľáł á°ááá, áĽá á¨á°ááŠáľ áááá˝ á á˛áľá áá ááአáá˝áá.
- á¨áľááľá áá á áá á°á¨ áľááľáł ááľáĽ á°ááá áŚáłá áá áá á ááĽááľá˘ áľáá á á¨á´á áĽá¨áŤá á¨áá á á ááŁáááľ áŤáá áŚáł ááááľ á áŁá á áľá¸á᪠áá.
- ááá˝ á áá á¨áĽáŁ á¨áááááľá ááá (áááłá á¨ááá áĽá á¨á°á áľá) ááá¨áĽ áá˝ááá˘
áá áá áá¨á áľá á˝áá ááá ἠáá˝ááá˘
ááá: hab.com