Su'e lelei fa'alagolago galuega i fa'amaumauga

Su'eina fa'alagolago galuega i fa'amaumauga e fa'aaogaina i vaega eseese o su'esu'ega o fa'amaumauga: fa'atonuga o fa'amaumauga, fa'amama fa'amaumauga, fa'ainisinia fa'aliliu ma su'esu'ega fa'amaumauga. Ua uma ona matou fa'asalalau e uiga i fa'alagolago lava latou tusiga Anastasia Birillo ma Nikita Bobrov. O le taimi lenei, Anastasia, o se faʻauʻu mai le Computer Science Center i lenei tausaga, faʻasoa le atinaʻeina o lenei galuega o se vaega o le galuega suʻesuʻe na ia puipuia i le ogatotonu.

Filifiliga o galuega

A o ou aʻoga i le CS centre, na amata ona ou suʻesuʻeina faʻamaumauga i le loloto, o lona uiga, o le suʻesuʻeina o galuega faʻalagolago ma eseesega. O lenei autu e fesoʻotaʻi ma le autu o laʻu aʻoga i le iunivesite, o lea aʻo ou galue i le kosi, na amata ona ou faitauina tala e uiga i faʻalagolago eseese i faʻamaumauga. Na ou tusia se iloiloga o lenei vaega - o se tasi o laʻu mea muamua tusiga i le Igilisi ma tuʻuina atu i le SEIM-2017 conference. Sa ou matua fiafia lava ina ua ou iloa ua taliaina o ia, ma filifili ai e suesue loloto i le autu. O le manatu lava ia e le fou - na amata ona faʻaaogaina i tua i le 90s, ae e oʻo lava i le taimi nei o loʻo faʻaaogaina i le tele o eria.

I le taimi o laʻu semesa lona lua i le ogatotonu, sa ou amataina se galuega suʻesuʻe e faʻaleleia ai algorithms mo le sailia o faʻalagolago galuega. Sa ia galue i ai faatasi ma St. Petersburg State University faauu tamaiti aoga Nikita Bobrov i JetBrains Research.

Lavelave fa'akomepiuta o le su'eina o fa'alagolago galuega

Ole fa'afitauli autu ole lavelave fa'akomepiuta. Ole numera ole fa'alagolago la'ititi ma le le taualoa e fa'atapula'aina ile tau fea - numera o uiga laulau. Ole taimi ole gaioiga ole algorithms e faʻalagolago e le gata ile numera o uiga, ae faʻapea foi ile numera o laina. I le 90s, feterale tulafono su'esu'e algorithms i luga o le PC desktop masani e mafai ona fa'agasolo fa'amaumauga fa'amaumauga e o'o atu i le 20 uiga ma le fiasefulu afe o laina i totonu o ni nai itula. Algoritimi fa'aonaponei o lo'o fa'aogaina i luga ole tele-core processors e iloa ai fa'alagolago mo seti fa'amaumauga e aofia ai le fiaselau o uiga (e o'o atu i le 200) ma le faitau selau o afe o laina ile taimi tutusa. Ae ui i lea, e le lava lenei mea: o sea taimi e le taliaina mo le tele o talosaga i le lalolagi moni. O le mea lea, na matou atiina ae auala e faʻavave ai algorithms o iai.

Fuafuaga fa'akomepiuta mo vaeluaga vaeluaga

I le vaega muamua o le galuega, na matou atiaeina ni fuafuaga faʻapipiʻi mo se vasega o algorithms e faʻaogaina le auala vaeluaga vaeluaga. O se vaeluaga mo se uiga o se seti o lisi, lea o lisi taʻitasi o loʻo i ai numera laina ma tutusa tau mo se uiga tuʻuina atu. O ia lisi taitasi e ta'ua o se fuifui. O le tele o algorithms faʻaonapo nei e faʻaogaina vaega e iloa ai pe o loʻo faʻalagolago pe leai, o lona uiga, latou te pipii i le lemma: Dependency umia pe afai . O iinei o se vaeluaga ua tofia ma o le manatu o le vaeluaga tele o loʻo faʻaaogaina - o le numera o fuifui i totonu. Algorithms e faʻaogaina vaega, pe a solia le faʻalagolago, faʻaopoopo uiga faʻaopoopo i le itu agavale o le faʻalagolago, ona toe faʻatatau lea, faʻatino le gaioiga o le vaeluaga o vaega. O lenei gaioiga e taʻua o le faʻapitoa i tala. Ae na matou matauina o vaeluaga mo faʻalagolago e naʻo le taofia pe a maeʻa ni nai taamilosaga faʻapitoa e mafai ona toe faʻaaogaina, lea e mafai ona faʻaitiitia ai le taimi o le algorithms, talu ai e taugata le faʻaogaina o fesoʻotaʻiga.

O le mea lea, na matou tuʻuina atu ai se faʻamatalaga e faʻavae i luga o Shannon Entropy ma Ginny Uncertainty, faʻapea foʻi ma le matou metric, lea na matou taʻua o Reverse Entropy. O se suiga laʻititi o Shannon Entropy ma faʻateleina aʻo faʻateleina le tulaga ese o faʻamaumauga faʻamaumauga. O le heuristic fuafuaina e faapea:

o - tikeri o le tulaga ese o le vaeluaga talu ai nei fuafuaina ma o le vaeluagalemu o tikeri o le tulaga ese mo uiga taitasi. O metotia uma e tolu o loʻo faʻamatalaina i luga na faʻataʻitaʻiina o se metric tulaga ese. E mafai foi ona e matauina e lua suiga i le heuristic. O le mea muamua o loʻo faʻaalia ai le vavalalata o le vaeluaga o loʻo i ai nei i le ki autu ma faʻatagaina oe e faʻapipiʻi i se tulaga sili atu na vaega e mamao mai le ki e mafai. O le suiga lona lua e mafai ai e oe ona mataʻituina le nofoia o le cache ma faʻamalosia ai le faʻaopoopoina o isi vaega i le cache pe a maua avanoa avanoa. O le fofo manuia o lenei faʻafitauli na faʻatagaina ai i matou e faʻavave le PYRO algorithm e 10-40%, faʻalagolago i faʻamaumauga. E taua le maitauina o le PYRO algorithm e sili ona manuia i lenei vaega.

I le ata o lo'o i lalo e mafai ona e va'ai i fa'ai'uga o le fa'aogaina o le heuristic fa'atulagaina pe a fa'atusatusa i se faiga fa'apipi'i coin-flip caching. Ole X axis ole logarithmic.

O se isi auala e teu ai vaega

Ona matou tuuina atu lea o se isi auala e teu ai vaega. O vaeluaga o se seti o fuifui, o ia mea taʻitasi e teu ai numera o tuples ma tutusa tau mo nisi uiga. O nei fuifui e mafai ona iai ni fa'asologa umi o numera tuple, mo se fa'ata'ita'iga pe a fa'atonu fa'amaumauga i se laulau. O le mea lea, matou te tuʻuina atu se faiga faʻamalosi mo le teuina o vaeluaga, e taʻua o le teuina o taimi o tau i fuifui o vaega:

$$fa'aali$$pi(X) = {{fa'a'au i lalo{1, 2, 3, 4, 5}_{Fa'ataga muamua}, fa'amau i lalo{7, 8}_{Vao lona lua}, 10}}\ arrow { Compression} \ pi(X) = {{fa'alava {$, 1, 5}_{Muamua~ va'aiga}, fa'amaulalo{7, 8}_{Lua~ vaelua}, 10}}$$fa'aaliga$$

O lenei metotia na mafai ona faʻaitiitia le faʻaaogaina o le mafaufau i le taimi o le faʻaogaina o le TANE algorithm mai le 1 i le 25%. O le TANE algorithm o se fa'asologa masani mo le su'eina o tulafono feterale; e fa'aogaina vaega i le taimi o lana galuega. I le avea ai o se vaega o le faʻataʻitaʻiga, na filifilia le TANE algorithm, talu ai e sili atu ona faigofie le faʻatinoina o le teuina o taimi i totonu nai lo, mo se faʻataʻitaʻiga, i le PYRO ina ia mafai ai ona iloilo pe aoga le auala fuafuaina. O fa'ai'uga na maua o lo'o tu'uina atu ile ata o lo'o i lalo. Ole X axis ole logarithmic.

Konafesi ADBIS-2019

Faʻavae i luga o faʻaiʻuga o suʻesuʻega, ia Setema 2019 na ou lolomiina ai se tusiga Smart Caching mo Su'esu'ega Fa'alagolago Fa'atino Lelei i le 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). I le taimi o le folasaga, sa matauina le galuega e Bernhard Thalheim, o se tagata taua i le tulaga o faʻamaumauga. O fa'ai'uga o su'esu'ega na fa'avaeina ai la'u su'esu'ega i le tikeri o le matuaofaiva i le matematika ma le inisinia i le Iunivesite o le Setete o St. Petersburg, lea na fa'atinoina uma ai auala (caching ma compression) i algorithms uma e lua: TANE ma PYRO. E le gata i lea, o faʻaiʻuga na faʻaalia ai o auala faʻatulagaina e lautele, talu ai i luga o algorithms uma e lua, faʻatasi ai ma auala uma e lua, o se faʻaitiitiga taua o le taumafaina manatua na matauina, faʻapea foʻi ma se faʻaitiitiga taua i le taimi faʻaogaina o algorithms.

puna: www.habr.com