Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй Π² Π±Π°Π·Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ…

Поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй Π² Π΄Π°Π½Π½Ρ‹Ρ… примСняСтся Π² Ρ€Π°Π·Π½Ρ‹Ρ… направлСниях Π°Π½Π°Π»ΠΈΠ·Π° Π΄Π°Π½Π½Ρ‹Ρ…: ΡƒΠΏΡ€Π°Π²Π»Π΅Π½ΠΈΠ΅ Π±Π°Π·Π°ΠΌΠΈ Π΄Π°Π½Π½Ρ‹Ρ…, очистка Π΄Π°Π½Π½Ρ‹Ρ…, рСвёрс-ΠΈΠ½ΠΆΠΈΠ½ΠΈΡ€ΠΈΠ½Π³ Π±Π°Π· Π΄Π°Π½Π½Ρ‹Ρ… ΠΈ эксплорация Π΄Π°Π½Π½Ρ‹Ρ…. ΠŸΡ€ΠΎ сами зависимости ΠΌΡ‹ ΡƒΠΆΠ΅ ΠΏΡƒΠ±Π»ΠΈΠΊΠΎΠ²Π°Π»ΠΈ ΡΡ‚Π°Ρ‚ΡŒΡŽ Анастасии Π‘ΠΈΡ€ΠΈΠ»Π»ΠΎ ΠΈ Никиты Π‘ΠΎΠ±Ρ€ΠΎΠ²Π°. Π’ этот Ρ€Π°Π· Анастасия β€” выпускница Computer Science Center этого Π³ΠΎΠ΄Π° β€” дСлится Ρ€Π°Π·Π²ΠΈΡ‚ΠΈΠ΅ΠΌ этой Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π² Ρ€Π°ΠΌΠΊΠ°Ρ… НИР, ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ ΠΎΠ½Π° Π·Π°Ρ‰ΠΈΡ‚ΠΈΠ»Π° Π² Ρ†Π΅Π½Ρ‚Ρ€Π΅.

Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй Π² Π±Π°Π·Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ…

Π’Ρ‹Π±ΠΎΡ€ Π·Π°Π΄Π°Ρ‡ΠΈ

Π’ΠΎ врСмя обучСния Π² CS Ρ†Π΅Π½Ρ‚Ρ€Π΅ я Π½Π°Ρ‡Π°Π»Π° ΡƒΠ³Π»ΡƒΠ±Π»Ρ‘Π½Π½ΠΎ ΠΈΠ·ΡƒΡ‡Π°Ρ‚ΡŒ Π±Π°Π·Ρ‹ Π΄Π°Π½Π½Ρ‹Ρ…, Π° ΠΈΠΌΠ΅Π½Π½ΠΎ, поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… ΠΈ разностных зависимостСй. Π­Ρ‚Π° Ρ‚Π΅ΠΌΠ° Π±Ρ‹Π»Π° связана с Ρ‚Π΅ΠΌΠΎΠΉ ΠΌΠΎΠ΅ΠΉ курсовой Π² унивСрситСтС, Ρ‚Π°ΠΊ Ρ‡Ρ‚ΠΎ Π²ΠΎ врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π½Π°Π΄ курсовой я Π½Π°Ρ‡Π°Π»Π° Ρ‡ΠΈΡ‚Π°Ρ‚ΡŒ ΡΡ‚Π°Ρ‚ΡŒΠΈ ΠΏΡ€ΠΎ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ зависимости Π² Π±Π°Π·Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. Π― написала ΠΎΠ±Π·ΠΎΡ€ этой области β€” ΠΎΠ΄Π½Ρƒ ΠΈΠ· ΠΏΠ΅Ρ€Π²Ρ‹Ρ… своих статСй Π½Π° английском языкС ΠΈ ΠΏΠΎΠ΄Π°Π»Π° Π΅Ρ‘ Π½Π° ΠΊΠΎΠ½Ρ„Π΅Ρ€Π΅Π½Ρ†ΠΈΡŽ SEIM-2017. Π― Π±Ρ‹Π»Π° ΠΎΡ‡Π΅Π½ΡŒ Ρ€Π°Π΄Π°, ΠΊΠΎΠ³Π΄Π° ΡƒΠ·Π½Π°Π»Π°, Ρ‡Ρ‚ΠΎ Π΅Ρ‘ всё ΠΆΠ΅ приняли, ΠΈ Ρ€Π΅ΡˆΠΈΠ»Π° ΡƒΠ³Π»ΡƒΠ±ΠΈΡ‚ΡŒΡΡ Π² Ρ‚Π΅ΠΌΡƒ. Π‘Π°ΠΌΠ° концСпция Π½Π΅ новая β€” Π΅Ρ‘ Π½Π°Ρ‡Π°Π»ΠΈ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒ Π΅Ρ‰Π΅ Π² 90Ρ… Π³ΠΎΠ΄Π°Ρ…, Π½ΠΎ ΠΈ сСйчас ΠΎΠ½Π° Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ Π²ΠΎ ΠΌΠ½ΠΎΠ³ΠΈΡ… областях.

Π’ΠΎ Π²Ρ‚ΠΎΡ€ΠΎΠΌ сСмСстрС обучСния Π² Ρ†Π΅Π½Ρ‚Ρ€Π΅ я Π½Π°Ρ‡Π°Π»Π° Π½Π°ΡƒΡ‡Π½ΠΎ-ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΡΠΊΠΈΠΉ ΠΏΡ€ΠΎΠ΅ΠΊΡ‚ ΠΏΠΎ ΡƒΠ»ΡƒΡ‡ΡˆΠ΅Π½ΠΈΡŽ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² поиска Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй. Π Π°Π±ΠΎΡ‚Π°Π»Π° Π½Π°Π΄ Π½ΠΈΠΌ вмСстС с аспирантом Π‘ΠŸΠ±Π“Π£ Никитой Π‘ΠΎΠ±Ρ€ΠΎΠ²Ρ‹ΠΌ Π½Π° Π±Π°Π·Π΅ JetBrains Research.

Π’Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ Ρ‚Ρ€ΡƒΠ΄ΠΎΡ‘ΠΌΠΊΠΎΡΡ‚ΡŒ поиска Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй

Основная ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ° β€” Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ Ρ‚Ρ€ΡƒΠ΄ΠΎΡ‘ΠΌΠΊΠΎΡΡ‚ΡŒ. Число Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… ΠΈ Π½Π΅Ρ‚Ρ€ΠΈΠ²ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½ΠΎ свСрху Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй Π² Π±Π°Π·Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ…, Π³Π΄Π΅ Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй Π² Π±Π°Π·Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ… β€” число Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚ΠΎΠ² Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹. ВрСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² зависит Π½Π΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΡ‚ количСства Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚ΠΎΠ², Π½ΠΎ ΠΈ ΠΎΡ‚ количСства строк. Π’ 90-Ρ… Π³ΠΎΠ΄Π°Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΏΠΎ поиску Π€Π— Π½Π° ΠΎΠ±Ρ‹Ρ‡Π½ΠΎΠΌ Π½Π°ΡΡ‚ΠΎΠ»ΡŒΠ½ΠΎΠΌ ПК ΠΌΠΎΠ³Π»ΠΈ ΠΎΠ±Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒ Π½Π°Π±ΠΎΡ€Ρ‹ Π΄Π°Π½Π½Ρ‹Ρ…, содСрТащиС Π΄ΠΎ 20 Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚ΠΎΠ² ΠΈ дСсятки тысяч строк, Π΄ΠΎ Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… часов. Π‘ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹, Ρ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‰ΠΈΠ΅ Π½Π° многоядСрных процСссорах, ΠΎΠ±Π½Π°Ρ€ΡƒΠΆΠΈΠ²Π°ΡŽΡ‚ зависимости для Π½Π°Π±ΠΎΡ€ΠΎΠ² Π΄Π°Π½Π½Ρ‹Ρ…, состоящих ΠΈΠ· сотСн Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚ΠΎΠ² (Π΄ΠΎ 200) ΠΈ сотСн тысяч строк, ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π½ΠΎ Π·Π° Ρ‚ΠΎ ΠΆΠ΅ врСмя. Π’Π΅ΠΌ Π½Π΅ ΠΌΠ΅Π½Π΅Π΅ этого нСдостаточно: Ρ‚Π°ΠΊΠΎΠ΅ врСмя Π½Π΅ΠΏΡ€ΠΈΠ΅ΠΌΠ»Π΅ΠΌΠΎ для Π±ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²Π° Ρ€Π΅Π°Π»ΡŒΠ½Ρ‹Ρ… ΠΏΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠΈΜ†. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ΠΌΡ‹ Ρ€Π°Π·Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Π»ΠΈ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Ρ‹ для ускорСния ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ².

Π‘Ρ…Π΅ΠΌΡ‹ ΠΊΡΡˆΠΈΡ€ΠΎΠ²Π°Π½ΠΈΡ для пСрСсСчСния ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΉ

Π’ ΠΏΠ΅Ρ€Π²ΠΎΠΉ части Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΌΡ‹ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π»ΠΈ схСмы ΠΊΡΡˆΠΈΡ€ΠΎΠ²Π°Π½ΠΈΡ для класса Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ², ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‰ΠΈΡ… ΠΌΠ΅Ρ‚ΠΎΠ΄ пСрСсСчСния ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΉ. ΠŸΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΡ для Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚Π° прСдставляСт собой Π½Π°Π±ΠΎΡ€ списков, Π³Π΄Π΅ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΈΜ† список содСрТит Π½ΠΎΠΌΠ΅Ρ€Π° строк с ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹ΠΌΠΈ значСниями для Π΄Π°Π½Π½ΠΎΠ³ΠΎ Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚Π°. ΠšΠ°ΠΆΠ΄Ρ‹ΠΉ Ρ‚Π°ΠΊΠΎΠΉ список называСтся кластСр. МногиС соврСмСнныС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΈ для опрСдСлСния, удСрТиваСтся Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡ‚ΡŒ ΠΈΠ»ΠΈ Π½Π΅Ρ‚, Π° ΠΈΠΌΠ΅Π½Π½ΠΎ ΠΏΡ€ΠΈΠ΄Π΅Ρ€ΠΆΠΈΠ²Π°ΡŽΡ‚ΡΡ Π»Π΅ΠΌΠΌΡ‹: Π—Π°Π²ΠΈΡΠΈΠΌΠΎΡΡ‚ΡŒ Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй Π² Π±Π°Π·Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ… удСрТиваСтся, Ссли Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй Π² Π±Π°Π·Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. Π—Π΄Π΅ΡΡŒ Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй Π² Π±Π°Π·Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ… обозначаСтся партиция ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ понятиС Ρ€Π°Π·ΠΌΠ΅Ρ€ ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΈ β€” количСство кластСров Π² Π½Π΅ΠΉ. Алгоритмы, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‰ΠΈΠ΅ ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΈ, ΠΏΡ€ΠΈ Π½Π°Ρ€ΡƒΡˆΠ΅Π½ΠΈΠΈ зависимости Π΄ΠΎΠ±Π°Π²Π»ΡΡŽΡ‚ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚Ρ‹ Π² Π»Π΅Π²ΡƒΡŽ Ρ‡Π°ΡΡ‚ΡŒ зависимости, послС Ρ‡Π΅Π³ΠΎ ΠΏΠ΅Ρ€Π΅ΡΡ‡ΠΈΡ‚Ρ‹Π²Π°ΡŽΡ‚ Π΅Ρ‘, производя ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΡŽ пСрСсСчСния ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΉ. Вакая опСрация Π² ΡΡ‚Π°Ρ‚ΡŒΡΡ… называСтся спСциализациСй. Но ΠΌΡ‹ Π·Π°ΠΌΠ΅Ρ‚ΠΈΠ»ΠΈ, Ρ‡Ρ‚ΠΎ ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΈ для зависимостСй, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π±ΡƒΠ΄ΡƒΡ‚ ΡƒΠ΄Π΅Ρ€ΠΆΠ°Π½Ρ‹ лишь послС Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… Ρ€Π°ΡƒΠ½Π΄ΠΎΠ² спСциализации, ΠΌΠΎΠ³ΡƒΡ‚ Π±Ρ‹Ρ‚ΡŒ Π°ΠΊΡ‚ΠΈΠ²Π½ΠΎ ΠΏΠ΅Ρ€Π΅ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Π½Ρ‹, Ρ‡Ρ‚ΠΎ ΠΌΠΎΠΆΠ΅Ρ‚ сущСствСнно ΡΠΎΠΊΡ€Π°Ρ‚ΠΈΡ‚ΡŒ врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ², Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ опСрация пСрСсСчСния являСтся Π΄ΠΎΡ€ΠΎΠ³ΠΎΠΉ.

ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ΠΌΡ‹ ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠΈΠ»ΠΈ эвристику, ΠΎΡΠ½ΠΎΠ²Π°Π½Π½ΡƒΡŽ Π½Π° Π­Π½Ρ‚Ρ€ΠΎΠΏΠΈΠΈ Π¨Π΅Π½Π½ΠΎΠ½Π° ΠΈ нСопрСдСлённости Π”ΠΆΠΈΠ½Π½ΠΈ, Π° Ρ‚Π°ΠΊΠΆΠ΅ нашСй ΠΌΠ΅Ρ‚Ρ€ΠΈΠΊΠ΅, ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ ΠΌΡ‹ Π½Π°Π·Π²Π°Π»ΠΈ ΠžΠ±Ρ€Π°Ρ‚Π½Π°Ρ Энтропия. Она являСтся Π½Π΅Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΉ ΠΌΠΎΠ΄ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠ΅ΠΉ Π­Π½Ρ‚Ρ€ΠΎΠΏΠΈΠΈ Π¨Π΅Π½Π½ΠΎΠ½Π° ΠΈ растёт ΠΏΠΎ ΠΌΠ΅Ρ€Π΅ Ρ‚ΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ растёт ΡƒΠ½ΠΈΠΊΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ Π½Π°Π±ΠΎΡ€Π° Π΄Π°Π½Π½Ρ‹Ρ…. ΠŸΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Π½Π°Ρ эвристика выглядит ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ:

Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй Π² Π±Π°Π·Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ…

Π—Π΄Π΅ΡΡŒ Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй Π² Π±Π°Π·Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ… β€” ΡΡ‚Π΅ΠΏΠ΅Π½ΡŒ ΡƒΠ½ΠΈΠΊΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ Π½Π΅Π΄Π°Π²Π½ΠΎ вычислСнной ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΈ Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй Π² Π±Π°Π·Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ…, Π° Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй Π² Π±Π°Π·Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ… являСтся ΠΌΠ΅Π΄ΠΈΠ°Π½ΠΎΠΈΜ† стСпСнСй ΡƒΠ½ΠΈΠΊΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ для ΠΎΡ‚Π΄Π΅Π»ΡŒΠ½Ρ‹Ρ… Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚ΠΎΠ². Π’ качСствС ΠΌΠ΅Ρ‚Ρ€ΠΈΠΊΠΈ ΡƒΠ½ΠΈΠΊΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ Π±Ρ‹Π»ΠΈ ΠΎΠΏΡ€ΠΎΠ±ΠΎΠ²Π°Π½Ρ‹ всС Ρ‚Ρ€ΠΈ ΠΌΠ΅Ρ‚Ρ€ΠΈΠΊΠΈ, описанныС Π²Ρ‹ΡˆΠ΅. Π’Π°ΠΊΠΆΠ΅ ΠΌΠΎΠΆΠ½ΠΎ Π·Π°ΠΌΠ΅Ρ‚ΠΈΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ Π² эвристикС ΠΏΡ€ΠΈΡΡƒΡ‚ΡΡ‚Π²ΡƒΡŽΡ‚ Π΄Π²Π° ΠΌΠΎΠ΄ΠΈΡ„ΠΈΠΊΠ°Ρ‚ΠΎΡ€Π°. ΠŸΠ΅Ρ€Π²Ρ‹ΠΉ ΡƒΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚, насколько Π±Π»ΠΈΠ·ΠΊΠ° тСкущая партиция ΠΊ ΠΏΠ΅Ρ€Π²ΠΈΡ‡Π½ΠΎΠΌΡƒ ΠΊΠ»ΡŽΡ‡Ρƒ ΠΈ позволяСт Π² Π±ΠΎΠ»ΡŒΡˆΠ΅ΠΈΜ† стСпСни ΠΊΡΡˆΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Ρ‚Π΅ ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π΄Π°Π»Π΅ΠΊΠΈ ΠΎΡ‚ ΠΏΠΎΡ‚Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ ΠΊΠ»ΡŽΡ‡Π°. Π’Ρ‚ΠΎΡ€ΠΎΠΉ ΠΌΠΎΠ΄ΠΈΡ„ΠΈΠΊΠ°Ρ‚ΠΎΡ€ позволяСт ΠΎΡ‚ΡΠ»Π΅ΠΆΠΈΠ²Π°Ρ‚ΡŒ Π·Π°Π½ΡΡ‚ΠΎΡΡ‚ΡŒ кэша ΠΈ Ρ‚Π΅ΠΌ самым стимулируСт Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠ΅ большСго количСства ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΈΜ† Π² кэш ΠΏΡ€ΠΈ Π½Π°Π»ΠΈΡ‡ΠΈΠΈ свободного мСста. УспСшноС Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ этой Π·Π°Π΄Π°Ρ‡ΠΈ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΠ»ΠΎ ΡƒΡΠΊΠΎΡ€ΠΈΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ PYRO Π½Π° 10-40% ΠΏΡ€ΠΎΡ†Π΅Π½Ρ‚ΠΎΠ² Π² зависимости ΠΎΡ‚ датасСта. Π‘Ρ‚ΠΎΠΈΡ‚ ΠΎΡ‚ΠΌΠ΅Ρ‚ΠΈΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ PYRO являСтся Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡƒΡΠΏΠ΅ΡˆΠ½Ρ‹ΠΌ Π² этой области.

На рисункС Π½ΠΈΠΆΠ΅ ΠΌΠΎΠΆΠ½ΠΎ ΡƒΠ²ΠΈΠ΄Π΅Ρ‚ΡŒ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ примСнСния ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Π½ΠΎΠΉ эвристики ΠΏΠΎ ΡΡ€Π°Π²Π½Π΅Π½ΠΈΡŽ с Π±Π°Π·ΠΎΠ²Ρ‹ΠΌ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΎΠΌ ΠΏΠΎ ΠΊΡΡˆΠΈΡ€ΠΎΠ²Π°Π½ΠΈΡŽ, основанном Π½Π° подбрасывании ΠΌΠΎΠ½Π΅Ρ‚ΠΊΠΈ. Ось X логарифмичСская.

Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй Π² Π±Π°Π·Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ…

ΠΠ»ΡŒΡ‚Π΅Ρ€Π½Π°Ρ‚ΠΈΠ²Π½Ρ‹ΠΉ способ хранСния ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΉ

Π—Π°Ρ‚Π΅ΠΌ ΠΌΡ‹ ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠΈΠ»ΠΈ Π°Π»ΡŒΡ‚Π΅Ρ€Π½Π°Ρ‚ΠΈΠ²Π½Ρ‹ΠΉ способ хранСния ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΉ. ΠŸΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΈ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡŽΡ‚ собой Π½Π°Π±ΠΎΡ€ кластСров, Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… хранятся Π½ΠΎΠΌΠ΅Ρ€Π° ΠΊΠΎΡ€Ρ‚Π΅ΠΆΠ΅ΠΈΜ† с ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹ΠΌΠΈ значСниями ΠΏΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Ρ‘Π½Π½Ρ‹ΠΌ Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚Π°ΠΌ. Π­Ρ‚ΠΈ кластСры ΠΌΠΎΠ³ΡƒΡ‚ ΡΠΎΠ΄Π΅Ρ€ΠΆΠ°Ρ‚ΡŒ Π΄Π»ΠΈΠ½Π½Ρ‹Π΅ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ Π½ΠΎΠΌΠ΅Ρ€ΠΎΠ² ΠΊΠΎΡ€Ρ‚Π΅ΠΆΠ΅ΠΈΜ†, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, Ссли Π² Ρ‚Π°Π±Π»ΠΈΡ†Π΅ Π΄Π°Π½Π½Ρ‹Π΅ упорядочСны. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ΠΌΡ‹ ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠΈΠ»ΠΈ схСму сТатия для хранСния ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΈΜ†, Π° ΠΈΠΌΠ΅Π½Π½ΠΎ ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»ΡŒΠ½ΠΎΠ΅ Ρ…Ρ€Π°Π½Π΅Π½ΠΈΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΈΜ† Π² кластСрах ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΈΜ†:

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{ΠŸΠ΅Ρ€Π²Ρ‹ΠΉ~ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»}, underbrace{7, 8}_{Π’Ρ‚ΠΎΡ€ΠΎΠΉ~ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»}, 10}}\ downarrow{Π‘ΠΆΠ°Ρ‚ΠΈΠ΅}\ pi(X) = {{underbrace{$, 1, 5}_{ΠŸΠ΅Ρ€Π²Ρ‹ΠΉ~ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»}, underbrace{7, 8}_{Π’Ρ‚ΠΎΡ€ΠΎΠΉ~ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»}, 10}}$$display$$

Π­Ρ‚ΠΎΡ‚ ΠΌΠ΅Ρ‚ΠΎΠ΄ смог ΡΠΎΠΊΡ€Π°Ρ‚ΠΈΡ‚ΡŒ ΠΏΠΎΡ‚Ρ€Π΅Π±Π»Π΅Π½ΠΈΠ΅ памяти Π²ΠΎ врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° TANE ΠΎΡ‚ 1 Π΄ΠΎ 25%. Алгоритм TANE β€” классичСский Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΏΠΎ поиску Π€Π—, ΠΎΠ½ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ ΠΏΠ°Ρ€Ρ‚ΠΈΡ†ΠΈΠΈ Π² Ρ…ΠΎΠ΄Π΅ своСй Ρ€Π°Π±ΠΎΡ‚Ρ‹. Π’ Ρ€Π°ΠΌΠΊΠ°Ρ… ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠΈ Π±Ρ‹Π» Π²Ρ‹Π±Ρ€Π°Π½ ΠΈΠΌΠ΅Π½Π½ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ TANE, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ Π²Π½Π΅Π΄Ρ€ΠΈΡ‚ΡŒ Π² Π½Π΅Π³ΠΎ ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»ΡŒΠ½ΠΎΠ΅ Ρ…Ρ€Π°Π½Π΅Π½ΠΈΠ΅ Π±Ρ‹Π»ΠΎ Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΏΡ€ΠΎΡ‰Π΅, Ρ‡Π΅ΠΌ, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, Π² PYRO, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΎΡ†Π΅Π½ΠΈΡ‚ΡŒ, Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ Π»ΠΈ ΠΏΡ€Π΅Π΄Π»Π°Π³Π°Π΅ΠΌΡ‹ΠΉ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄. ΠŸΠΎΠ»ΡƒΡ‡Π΅Π½Π½Ρ‹Π΅ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ прСдставлСны Π½Π° рисункС Π½ΠΈΠΆΠ΅. Ось X логарифмичСская.

Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ поиск Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… зависимостСй Π² Π±Π°Π·Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ…

ΠšΠΎΠ½Ρ„Π΅Ρ€Π΅Π½Ρ†ΠΈΡ ADBIS-2019

По Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π°ΠΌ исслСдования Π² сСнтябрС 2019 Π³ΠΎΠ΄Π° я выступила со ΡΡ‚Π°Ρ‚ΡŒΡ‘ΠΉ Smart Caching for Efficient Functional Dependency Discovery Π½Π° ΠΊΠΎΠ½Ρ„Π΅Ρ€Π΅Π½Ρ†ΠΈΠΈ 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). Π’ΠΎ врСмя выступлСния Ρ€Π°Π±ΠΎΡ‚Ρƒ ΠΎΡ‚ΠΌΠ΅Ρ‚ΠΈΠ» Bernhard Thalheim, Π·Π½Π°Ρ‡ΠΈΠΌΡ‹ΠΉ Ρ‡Π΅Π»ΠΎΠ²Π΅ΠΊ Π² области Π±Π°Π· Π΄Π°Π½Π½Ρ‹Ρ…. Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ исслСдований Π»Π΅Π³Π»ΠΈ Π² основу ΠΌΠΎΠ΅ΠΉ диссСртации Π² магистратурС ΠΌΠ°Ρ‚-ΠΌΠ΅Ρ…Π° Π‘ΠŸΠ±Π“Π£, Π² Ρ…ΠΎΠ΄Π΅ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ ΠΎΠ±Π° ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Ρ… ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Π° (ΠΊΡΡˆΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΈ сТатиС) Π±Ρ‹Π»ΠΈ Π²Π½Π΅Π΄Ρ€Π΅Π½Ρ‹ Π² ΠΎΠ±Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°: TANE ΠΈ PYRO. ΠŸΡ€ΠΈ этом Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ ΠΏΠΎΠΊΠ°Π·Π°Π»ΠΈ, Ρ‡Ρ‚ΠΎ ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Π΅ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Ρ‹ ΡΠ²Π»ΡΡŽΡ‚ΡΡ ΡƒΠ½ΠΈΠ²Π΅Ρ€ΡΠ°Π»ΡŒΠ½Ρ‹ΠΌΠΈ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ Π½Π° ΠΎΠ±ΠΎΠΈΡ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°Ρ… ΠΏΡ€ΠΈ ΠΎΠ±ΠΎΠΈΡ… ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Π°Ρ… наблюдалось Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ΅ сокращСниС потрСбляСмой памяти, Π° Ρ‚Π°ΠΊΠΆΠ΅ Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ΅ сокращСниС Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ².

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ: habr.com