Skip to content
2 / 10

ΠšΠΎΠ»ΠΎΠ½ΠΎΡ‡Π½ΠΎΠ΅ Ρ…Ρ€Π°Π½Π΅Π½ΠΈΠ΅: ΠΏΠΎΡ‡Π΅ΠΌΡƒ ΠΎΠ½ΠΎ быстрСС для Π°Π½Π°Π»ΠΈΡ‚ΠΈΠΊΠΈ ΠΈ Π³Π΄Π΅ ΠΏΡ€ΠΎΠΈΠ³Ρ€Ρ‹Π²Π°Π΅Ρ‚?

ΠšΠΎΠ»ΠΎΠ½ΠΎΡ‡Π½ΠΎΠ΅ Ρ…Ρ€Π°Π½Π΅Π½ΠΈΠ΅ ΠΊΠ»Π°Π΄Ρ‘Ρ‚ рядом значСния ΠΎΠ΄Π½ΠΎΠΉ ΠΊΠΎΠ»ΠΎΠ½ΠΊΠΈ, Π° Π½Π΅ ΠΎΠ΄Π½ΠΎΠΉ строки. ΠžΡ‚ΡΡŽΠ΄Π° Ρ‚Ρ€ΠΈ источника ускорСния. Π§Ρ‚Π΅Π½ΠΈΠ΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π½ΡƒΠΆΠ½ΠΎΠ³ΠΎ: запрос ΠΏΠΎ Ρ‚Ρ€Ρ‘ΠΌ ΠΊΠΎΠ»ΠΎΠ½ΠΊΠ°ΠΌ ΠΈΠ· сорока Ρ‡ΠΈΡ‚Π°Π΅Ρ‚ Ρ‚Ρ€ΠΈ ΠΊΠΎΠ»ΠΎΠ½ΠΊΠΈ, Π° Π½Π΅ всю Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ β€” Π½Π° ΡˆΠΈΡ€ΠΎΠΊΠΈΡ… Ρ‚Π°Π±Π»ΠΈΡ†Π°Ρ… это Ρ€Π°Π·Π½ΠΈΡ†Π° Π² порядок. Π‘ΠΆΠ°Ρ‚ΠΈΠ΅: сосСдниС значСния ΠΎΠ΄Π½ΠΎΠΉ ΠΊΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠΎΠ΄Π½ΠΎΡ‚ΠΈΠΏΠ½Ρ‹ ΠΈ часто ΠΏΠΎΠ²Ρ‚ΠΎΡ€ΡΡŽΡ‚ΡΡ, поэтому Ρ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‚ Π΄Π΅Π»ΡŒΡ‚Π°-ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅, словарноС сТатиС ΠΈ RLE; коэффициСнт 5–20Γ— ΠΎΠ±Ρ‹Ρ‡Π΅Π½, Π° мСньшС Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° дискС ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ мСньшС Π²Π²ΠΎΠ΄Π°-Π²Ρ‹Π²ΠΎΠ΄Π°. Π’Π΅ΠΊΡ‚ΠΎΡ€ΠΈΠ·ΠΎΠ²Π°Π½Π½ΠΎΠ΅ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅: ΠΊΠΎΠ»ΠΎΠ½ΠΊΠ° β€” это Π½Π΅ΠΏΡ€Π΅Ρ€Ρ‹Π²Π½Ρ‹ΠΉ массив, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ обрабатываСтся Π±Π»ΠΎΠΊΠ°ΠΌΠΈ, Π° Π½Π΅ построчно, Ρ‡Ρ‚ΠΎ Π΄Π°Ρ‘Ρ‚ эффСктивноС использованиС кэша процСссора ΠΈ SIMD. ΠŸΡ€ΠΎΠΈΠ³Ρ€Ρ‹Π²Π°Π΅Ρ‚ ΠΊΠΎΠ»ΠΎΠ½ΠΎΡ‡Π½ΠΎΠ΅ Ρ…Ρ€Π°Π½Π΅Π½ΠΈΠ΅ Ρ‚Π°ΠΌ, Π³Π΄Π΅ Π½ΡƒΠΆΠ½Π° вся строка: Ρ‚ΠΎΡ‡Π΅Ρ‡Π½ΠΎΠ΅ Ρ‡Ρ‚Π΅Π½ΠΈΠ΅ ΠΏΠΎ ΠΊΠ»ΡŽΡ‡Ρƒ собираСт Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ ΠΈΠ· дСсятков мСст, Π° ΠΎΠ±Π½ΠΎΠ²Π»Π΅Π½ΠΈΠ΅ ΠΎΠ΄Π½ΠΎΠΉ строки Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ пСрСписывания Π±Π»ΠΎΠΊΠΎΠ². ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ΠΊΠΎΠ»ΠΎΠ½ΠΎΡ‡Π½Ρ‹Π΅ систСмы ΠΏΠΎΡ‡Ρ‚ΠΈ всСгда append-only с ΠΎΡ‚Π»ΠΎΠΆΠ΅Π½Π½Ρ‹ΠΌ слияниСм, Π° Π½Π΅ Π·Π°ΠΌΠ΅Π½ΠΎΠΉ Π½Π° мСстС.

ΠšΠΎΠ»ΠΎΠ½ΠΎΡ‡Π½ΠΎΠ΅ Ρ…Ρ€Π°Π½Π΅Π½ΠΈΠ΅: ΠΏΠΎΡ‡Π΅ΠΌΡƒ ΠΎΠ½ΠΎ быстрСС для Π°Π½Π°Π»ΠΈΡ‚ΠΈΠΊΠΈ ΠΈ Π³Π΄Π΅ ΠΏΡ€ΠΎΠΈΠ³Ρ€Ρ‹Π²Π°Π΅Ρ‚? | JScriptiser