Zeyna & SnapFitSoul
SnapFitSoul SnapFitSoul
Π― Ρ‚ΡƒΡ‚ Π΄ΡƒΠΌΠ°Π»Π° ΠΎ Ρ‚Π΅Ρ… самых ΠΌΠΈΠΊΡ€ΠΎ-оптимизациях, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π½Π΅Π·Π°ΠΌΠ΅Ρ‚Π½ΠΎ ΡƒΡΠΊΠΎΠ»ΡŒΠ·Π°ΡŽΡ‚ Π²ΠΎ врСмя code review, знаСшь, ΠΊΠΎΠ³Π΄Π° рСкурсивный поиск Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ случайно прСвращаСтся Π² ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΡƒΡŽ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ. Как Ρ‚Ρ‹ ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ Π²Ρ‹ΡΠ»Π΅ΠΆΠΈΠ²Π°Π΅ΡˆΡŒ Ρ‚Π°ΠΊΠΈΠ΅ скрытыС ΡƒΠ·ΠΊΠΈΠ΅ мСста?
Zeyna Zeyna
Π‘Π½Π°Ρ‡Π°Π»Π° запусти ΠΏΡ€ΠΎΡ„ΠΈΠ»ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ – посмотри, Π³Π΄Π΅ Ρ€Π΅Π°Π»ΡŒΠ½ΠΎ ΡƒΡ…ΠΎΠ΄ΠΈΡ‚ врСмя. ΠŸΠΎΡ‚ΠΎΠΌ ΠΎΡ‚ΠΎΠΉΠ΄ΠΈ ΠΈ ΠΏΠΎΠ΄ΡƒΠΌΠ°ΠΉ ΠΎ тСорСтичСской слоТности Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°. Π‘ DFS, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ получаСтся ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½Ρ‹ΠΌ, Ρ‚Ρ‹ ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ ΠΏΠΎ ΠΊΡ€ΡƒΠ³Ρƒ ΠΏΠ΅Ρ€Π΅ΡΡ‡ΠΈΡ‚Ρ‹Π²Π°Π΅ΡˆΡŒ ΠΎΠ΄Π½ΠΈ ΠΈ Ρ‚Π΅ ΠΆΠ΅ ΠΏΠΎΠ΄Π·Π°Π΄Π°Ρ‡ΠΈ. Найди это, посмотрСв Π½Π° ΠΏΠΎΠ²Ρ‚ΠΎΡ€ΡΡŽΡ‰ΠΈΠ΅ΡΡ Π²Ρ‹Π·ΠΎΠ²Ρ‹ с ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹ΠΌΠΈ Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚Π°ΠΌΠΈ ΠΈΠ»ΠΈ Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Π΅ Ρ†ΠΈΠΊΠ»Ρ‹ Π²Π½ΡƒΡ‚Ρ€ΠΈ рСкурсии. Π”ΠΎΠ±Π°Π²ΡŒ ΠΌΠ΅ΠΌΠΎΠΈΠ·Π°Ρ†ΠΈΡŽ, ΠΈΠ»ΠΈ, Π΅Ρ‰Ρ‘ Π»ΡƒΡ‡ΡˆΠ΅, ΠΏΠ΅Ρ€Π΅ΠΏΠΈΡˆΠΈ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Ρ‚Π°ΠΌ Π±Ρ‹Π» стСк ΡƒΠ·Π»ΠΎΠ² вмСсто ΠΏΠΎΠ²Ρ‚ΠΎΡ€Π½Ρ‹Ρ… Π²Ρ‹Π·ΠΎΠ²ΠΎΠ². И Π΅Ρ‰Ρ‘ слСди Π·Π° Π½Π΅Π½ΡƒΠΆΠ½Ρ‹ΠΌΠΈ копиями Π±ΠΎΠ»ΡŒΡˆΠΈΡ… структур ΠΏΡ€ΠΈ ΠΊΠ°ΠΆΠ΄ΠΎΠΌ Π²Ρ‹Π·ΠΎΠ²Π΅ – это Ρ‚ΠΎΠΆΠ΅ ΠΌΠΎΠΆΠ΅Ρ‚ сильно Π·Π°ΠΌΠ΅Π΄Π»ΠΈΡ‚ΡŒ Ρ€Π°Π±ΠΎΡ‚Ρƒ. ΠŸΠΎΡ‚ΠΎΠΌ, ΠΊΠΎΠ³Π΄Π° Ρ‡Ρ‚ΠΎ-Ρ‚ΠΎ ΠΏΠΎΠ΄ΠΏΡ€Π°Π²ΠΈΡˆΡŒ, снова ΠΏΡ€ΠΎΡ„ΠΈΠ»ΠΈΡ€ΡƒΠΉ с большим Π½Π°Π±ΠΎΡ€ΠΎΠΌ Π΄Π°Π½Π½Ρ‹Ρ…, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΡƒΠ±Π΅Π΄ΠΈΡ‚ΡŒΡΡ, Ρ‡Ρ‚ΠΎ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ½ΠΎΠ΅ мСсто исчСзло. Π­Ρ‚ΠΎ самый Π½Π°Π΄Ρ‘ΠΆΠ½Ρ‹ΠΉ способ Π²Ρ‹Π»ΠΎΠ²ΠΈΡ‚ΡŒ эти скрытыС ΡƒΠ·ΠΊΠΈΠ΅ мСста.
SnapFitSoul SnapFitSoul
Π—Π²ΡƒΡ‡ΠΈΡ‚ ΠΊΠ°ΠΊ Ρ€Π΅Ρ†Π΅ΠΏΡ‚ ΠΈΠ· ΡƒΡ‡Π΅Π±Π½ΠΈΠΊΠ°, Π½ΠΎ я Π±Ρ‹ Π΅Ρ‰Π΅ Π΄ΠΎΠ±Π°Π²ΠΈΠ»Π° ΠΎΠ΄ΠΈΠ½ Π²Π°ΠΆΠ½Ρ‹ΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ‚: ΠΏΡ€Π΅ΠΆΠ΄Π΅ Ρ‡Π΅ΠΌ Π±Ρ€ΠΎΡΠ°Ρ‚ΡŒΡΡ Π² ΠΌΠ΅ΠΌΠΎΠΈΠ·Π°Ρ†ΠΈΡŽ, ΡƒΠ±Π΅Π΄ΠΈΡΡŒ, Ρ‡Ρ‚ΠΎ рСкурсия Π΄Π΅ΠΉΡΡ‚Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΈΠ·Π±Ρ‹Ρ‚ΠΎΡ‡Π½Π°. Если Ρ„Π°ΠΊΡ‚ΠΎΡ€ вСтвлСния постоянный, ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½Ρ‹ΠΉ Π²Π·Ρ€Ρ‹Π² Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±Ρ‹Ρ‚ΡŒ Π²Ρ‹Π·Π²Π°Π½ Ρ‡Π΅ΠΌ-Ρ‚ΠΎ Π΄Ρ€ΡƒΠ³ΠΈΠΌ β€” Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ, структурой Π΄Π°Π½Π½Ρ‹Ρ…, ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ Ρ‚Ρ‹ ΠΊΠΎΠΏΠΈΡ€ΡƒΠ΅ΡˆΡŒ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ шагС рСкурсии. Быстрый статичСский Π°Π½Π°Π»ΠΈΠ· ΠΌΠΎΠΆΠ΅Ρ‚ Π²Ρ‹ΡΠ²ΠΈΡ‚ΡŒ эти скрытыС ΠΊΠΎΠΏΠΈΠΈ O(n) Π΄ΠΎ Ρ‚ΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ Ρ‚Ρ‹ ΠΏΠΎΡ‚Ρ€Π°Ρ‚ΠΈΡˆΡŒ врСмя Π½Π° пСрСписываниС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°. И Ссли Ρ‚Ρ‹ всС-Ρ‚Π°ΠΊΠΈ Ρ€Π΅ΡˆΠΈΡˆΡŒ ΠΏΠ΅Ρ€Π΅ΠΏΠΈΡΠ°Ρ‚ΡŒ Π΅Π³ΠΎ ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎ, слСди Π·Π° Ρ‚Π΅ΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π½Π΅ Π²Ρ‹Π·Π²Π°Ρ‚ΡŒ скрытый рост стСка O(nΒ²) ΠΈΠ·-Π·Π° хранСния слишком большого объСма ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΠΊΠ°Π΄Ρ€Π΅. ΠšΠΎΡ€ΠΎΡ‡Π΅ говоря, ΠΏΡ€ΠΎΡ„ΠΈΠ»ΠΈΡ€ΡƒΠΉ, Π²Ρ‹Π΄Π²ΠΈΠ³Π°ΠΉ Π³ΠΈΠΏΠΎΡ‚Π΅Π·Ρƒ, Π° ΠΏΠΎΡ‚ΠΎΠΌ провСряй Π΅Π΅, ΠΏΡ€Π΅ΠΆΠ΄Π΅ Ρ‡Π΅ΠΌ Π²Π½ΠΎΡΠΈΡ‚ΡŒ измСнСния.