search

TIM-JYU / TIM

TIM (The Interactive Material) is an open-source cloud-based platform for creating interactive learning documents.
https://tim.education/view/about/en-US
MIT License
15 stars 4 forks source link

fullprogram csplugin tekeminen kestää kauan jos ei ole // BYCODEBEGIN #1343

Open dezhidki opened 5 years ago

dezhidki commented 5 years ago

In GitLab by @vesal on Feb 18, 2019, 08:20

Ks:

https://tim.jyu.fi/view/users/vesal/koe/csplugin/demo6

ja ota pois `BYCODEBEGIN'

dezhidki commented 5 years ago

In GitLab by @vesal on Feb 24, 2019, 19:51

Tuo regexp oli käsittämättömän hidas:

cs.py, rivi: 676

m = re.search("[^\n]\n(.)\n.*?BYCODEEND", program, flags=re.S)

Korjattu niin, että etsitään findilla ensin onko tuota BYCODEENDiä lainkaan. Voisi miettiä tarviiko tuossa regexpiä lainkaan, koska riittää löytää rivi, jolla on BYCODEEND ja sitten ottaa kaikki sitä ennen oleva ja sen jälkeiset rivit

dezhidki commented 5 years ago

In GitLab by @vesal on Feb 27, 2019, 17:17

On 26 Feb 2019 10:21, Tapani Tarvainen (tapani.j.tarvainen@jyu.fi) wrote:

re.search("^.\n((.\n))(?=.BYCODEEND)", s)

Muuten ellei sattunut silmään, tuossa alussa oleva ^ on olennainen, se pudottaa suoritusajan O(n²):sta O(n):ään.

Tämä oli aika hauska harjoitus. Alkuperäinen,

   re.search("[^\\n]*\n(.*)\n.*?BYCODEEND", s, flags=re.S)

on O(n³) ja jo 1000 riviä vie koneellani yli 40 s.

Pelkällä alku-^:lla siinä pudottaa yhden n:n pois, samoin ensin ehdottamani säätö loppuun, nämä ovat molemmat O(n²):

  re.search("^[^\\n]*\n(.*)\n.*?BYCODEEND", s, flags=re.S)
  re.search("[^\\n]*\n(.*)\n[^\\n]*BYCODEEND", s, flags=re.S)

Näistä edellinen on noin 7x nopeampi, mutta jälkimmäinenkin puree 1000 riviä 0.15 sekunnissa.

O(n):ään päästään kun poistetaan moniriviset patternit sekä alusta että lopusta, näissä ei ole suurta eroa:

  re.search("^[^\\n]*\n(.*)\n[^\\n]*BYCODEEND", s, flags=re.S)
  re.search("^.*\n((.*\n)*)(?=.*BYCODEEND)", s)

Edellinen on hieman nopeampi mutta vain noin 30% ja sekunti menee puhki jälkimmäiselläkin vasta 10 miljoonan rivin hujakoilla.

Enempi optimointi ei liene vaivan arvoista, viimeksimainittu on minusta luettavampi, mutta se taitaa olla lähinnä makuasia.