|====================== Intro =========================|
Acoustic Guitar:
G#m - C#m - Bdim7 - C#m
G#m - C#m - Bdim7 - C#m
G#m - E - B - Gdim7
G#m - C#m - Bdim7 - C#m
Electric Guitar:
e|------------------------------------------------------------------
B|-----------------------------------5--4--5--4--5/7/5--4-----4v----
D|---------------------------------------------------------6--------
G|------------------------------------------------------------------
A|------------------------------------------------------------------
E|------------------------------------------------------------------
e|------------------------------------------------------------------
B|--5--4--5--4--5/7/5--4-----4v------5--4--5--4--5/7/5--4-----------
D|------------------------6--------------------------------6--4v----
G|------------------------------------------------------------------
A|------------------------------------------------------------------
E|------------------------------------------------------------------
e|------------------------------------------------------------------
B|------------------------------------------------------------------
D|--4--3--4--3--4/6-/4----3/4---------------------------------------
G|-----------------------------6-----6^8^6\5------------------------
A|------------------------------------------------------------------
E|------------------------------------------------------------------
|======================= Verse =========================|
Acoustic Guitar: G#m - E - D# - F#
Electric Guitar:
e|----------------------------------------------------
B|--5--4---------------------5--4---------------------
D|--------6--4--6/-8v--------------6--4--6/-3v--------
G|----------------------------------------------------
A|----------------------------------------------------
E|----------------------------------------------------
|===================== Pre-Chorus ======================|
Acoustic Guitar: E - B - Gdim7
e|------------------------3---------------------
B|-------0----------4-----2---------------------
D|----------1--4-------4--3---------------------
G|--2----------4----------2---------------------
A|--2----------2--------------------------------
E|--0-------------------------------------------
|====================== Chorus =========================|
Acoustic Guitar:
G#m - C#m - Bdim7 - C#m
G#m - C#m - Bdim7 - C#m
G#m - E - B - Gdim7
G#m - C#m - Bdim7 - C#m
Electric Guitar:
* Bu bölümdeki slidelar çok kısa
e|--3/4--3/4--3/4----6/7-6----4--3-----------------------
B|----------------------------------5--4-----------------
D|----------------------------------------6--4v----------
G|-------------------------------------------------------
A|-------------------------------------------------------
E|-------------------------------------------------------
e|--6/7-6----4-6/9--7--6----3--4v------------------------
B|-------------------------------------------------------
D|-------------------------------------------------------
G|-------------------------------------------------------
A|-------------------------------------------------------
E|-------------------------------------------------------
e|------------------3-----4------------------------------
B|-------4-----2-------2--4-----5--4--5--4--5/7/5--4-----
D|--4-------4--3----------4---------------------------6--
G|--4----------2-----------------------------------------
A|--2----------------------------------------------------
E|-------------------------------------------------------
|======================= Solo ==========================|
~ let ring
e|--------------------------------------------------
B|-----5-----5-----5-----5-----5-----5--7--5--------
D|-/8-----8-----8-----8-----8-----8-----------8--6--
G|--------------------------------------------------
A|--------------------------------------------------
E|--------------------------------------------------
e|--------------------------------------------------
B|-----5-----5-----5-----5-----4-----4-----4-----4--
D|--8-----8-----8-----8-----6-----6-----4-----4-----
G|--------------------------------------------------
A|--------------------------------------------------
E|--------------------------------------------------
e|--------------------------------------------------
B|-----0-----0-----0-----0-----0-----0-----0-----0--
D|--3-----3-----3-----3-----3-----3-----3-----3-----
G|--------------------------------------------------
A|--------------------------------------------------
E|--------------------------------------------------
e|--------------------------------------------------
B|--------------------------------------------------
D|-----3-----3-----3-----3-----1--------------------
G|--6-----6-----6-----6-----5-----5-----------------
A|--------------------------------------------------
E|--------------------------------------------------
...ve daha sonra şarkıdaki farklı kısımları tekrar çalarak
şarkıyı bitiriyorlar. Eminim hangi kısımda nereyi tekrar
çaldıklarını kendiniz de anlayabilirsiniz. Ek olarak canlı
performanslarında 2. versede bazen aşağıdaki kısmı çalıyorlar.
Ayrıca 2. pre-chorusu uzatarak çaldıklarını farketmişsinizdir.
e|------11----------11----------12----------12------
B|----------12----------12----------12----------12--
D|--13----------13----------13----------13----------
G|--------------------------------------------------
A|--------------------------------------------------
E|--------------------------------------------------
e|------11----------11----------11----------11------
B|----------11----------11----------11----------11--
D|--12----------12----------12----------12----------
G|--------------------------------------------------
A|--------------------------------------------------
E|--------------------------------------------------
|====================== Outro =========================|
~staccato
e|--------------------------------------------------
B|--------------------------------------------------
D|--------------------------------------------------
G|--6v----------------------------------------------
A|--------8/9---8---7---5---6/----------------------
E|--------------------------------------------------
Ayrıca Adamlar - Kapısı Kapalı tabı için tıklayın.
27 Aralık 2015 Pazar
21 Aralık 2015 Pazartesi
Pretty-Printing (Dynamic Programming)
Hepimiz bir metin yazarken satır uzunluklarının birbirine denk gelmemesine ara sıra gıcık olmuşuzdur. Doğrusu belki de herkes buna benim kadar takmıyordur. Yine de bu problem Algortihm Design kitabında karşılastığım en iyi hikayaye sahip egzersizlerden biriydi. Bu yüzden buna biraz zaman ayırdım. İşte kitapta problemin geçtiği kısım.
Problemi daha formal bir hale getirmek için, satır uzunluklarının olabildiğince eşit olmasına ölçüt olarak, kenar boşluklarının uzunluklarının karesinin toplamına bakılmış. Eğer kareleri alınmasaydı, her satıra yer kalmayana kadar kelime eklemek problemi çözmek için yeterli olurdu. Ama karelerine bakmamız gerektiğinde, problem greedy olarak çözülmesi pek mümkün görünmüyor. Bundan dolayı dynamic programming'e başvuruyoruz.
Problemi tam anlayamadıysanız bu wikipedia sayfasına bir göz atabilirsiniz.
Aslında, dynamic programming için gereken recurrence'i bulmak bu soru için çok zor değil.
&space;-&space;\sum_{k=i}^{j}c_k&space;\newline&space;OPT(j)&space;=&space;min&space;\{OPT(i-1)+S_{i,j}^{2}\;\,|\;1\leq&space;i\leq&space;j,\;S_{i,j}\geq&space;0&space;\} "\;\;S_{i,j} = L -(j - i) - \sum_{k=i}^{j}c_k \newline OPT(j) = min \{OPT(i-1)+S_{i,j}^{2}\;\,|\;1\leq i\leq j,\;S_{i,j}\geq 0 \}")
Ayrıca slackleri her başlangıç ve bitiş değeri için ayrı ayrı hesaplamak çok zaman alacağından bir tablo oluşturdum. Yukarıdaki eşitlikten Si,i = L - ci ve eklenen her kelime wk için kenar boşluğu ck+1 kadar azalır. Böylece tablodaki her bir eleman birim zamanda doldurulabilir. Toplamda tabloda n(n+1)/2 hücre doldurulduğundan O(n^2) zaman alır. OPT ve back-pointer değerleri hesaplamak her iterasyonda minumum alındığından O(n^2) zaman alır. Son kısın ise O(n) olduğuna göre algoritmanın time-complexitysi O(n^2)'dir.
Aşağıda ise python'un curses modulü ile yazdığım, terminal üzerinde çalışan küçük bir editör var. Bu editör her yeni kelime girdiğiniz de yukarıdaki algoritmayı uyguluyor. Ne yazık ki trinket curses modülünü desteklemediğinden dolayı kendi terminalinizde çalıştırmanız gerekecek.
Problemi daha formal bir hale getirmek için, satır uzunluklarının olabildiğince eşit olmasına ölçüt olarak, kenar boşluklarının uzunluklarının karesinin toplamına bakılmış. Eğer kareleri alınmasaydı, her satıra yer kalmayana kadar kelime eklemek problemi çözmek için yeterli olurdu. Ama karelerine bakmamız gerektiğinde, problem greedy olarak çözülmesi pek mümkün görünmüyor. Bundan dolayı dynamic programming'e başvuruyoruz.
Problemi tam anlayamadıysanız bu wikipedia sayfasına bir göz atabilirsiniz.
Aslında, dynamic programming için gereken recurrence'i bulmak bu soru için çok zor değil.
Si,j wi, wi+1, ..., wj kelimelerinden oluşan satırının kenar boşluğu(slack) uzunluğudur. Eşitlikte (j - i) boşluk sayılarıdır. Satır uzunluğunun L'yi geçemeyeceği için Si,j 0'dan büyük eşittir. OPT(j) ise w1, w2, ..., wj kelimeleri için slacklerin kareleri toplamının mümkün olan en düşük değeridir. Optimum çözümdeki en son satır wi kelimesi ile başlar. Bu durumda son satır çözümü Si,j'nin karesi kadar arttırır. Son satırdan önceki kenar boşluklarının karesi ise OPT(i-1)'e eşittir.Ancak problemin amacı OPT(n) değelerini bulmanın yanı sıra, bu değere ulaşmak için her satırın hangi kelimelerden oluştuğunuda bulmak. Bundan dolayı OPT(j) değerin yanında i'nin yani en son satırın hangi kelime ile başladığını da hafızada tutmalıyız. Bunun için aşağıdaki python kodunda back_pointer isimli bir liste kullanıyorum. Daha sonra bu listeyi tersinden dolanarak, her satırın hangi kelime ile bittiğini sol adlı listeye ekliyorum.
Ayrıca slackleri her başlangıç ve bitiş değeri için ayrı ayrı hesaplamak çok zaman alacağından bir tablo oluşturdum. Yukarıdaki eşitlikten Si,i = L - ci ve eklenen her kelime wk için kenar boşluğu ck+1 kadar azalır. Böylece tablodaki her bir eleman birim zamanda doldurulabilir. Toplamda tabloda n(n+1)/2 hücre doldurulduğundan O(n^2) zaman alır. OPT ve back-pointer değerleri hesaplamak her iterasyonda minumum alındığından O(n^2) zaman alır. Son kısın ise O(n) olduğuna göre algoritmanın time-complexitysi O(n^2)'dir.
Aşağıda ise python'un curses modulü ile yazdığım, terminal üzerinde çalışan küçük bir editör var. Bu editör her yeni kelime girdiğiniz de yukarıdaki algoritmayı uyguluyor. Ne yazık ki trinket curses modülünü desteklemediğinden dolayı kendi terminalinizde çalıştırmanız gerekecek.
import curses import curses.ascii class PrettyTextBox: def __init__(self, win): self.win = win self.maxy, self.maxx = win.getmaxyx() self.maxy = self.maxy - 1 self.maxx = self.maxx - 1 win.keypad(1) def _end_of_line(self, y): last = self.maxx while True: if curses.ascii.ascii(self.win.inch(y, last)) != curses.ascii.SP: last = min(self.maxx, last + 1) break elif last == 0: break last = last - 1 return last def do_command(self, ch): y, x = self.win.getyx() if ch == curses.ascii.SP: self._pretty_print() elif curses.ascii.isprint(ch): if y <= self.maxy and x <= self.maxx: try: self.win.addch(ch) except curses.error: pass elif ch == curses.KEY_LEFT: if x > 0: self.win.move(y, x - 1) elif ch == curses.KEY_RIGHT: if x < self.maxx: self.win.move(y, x + 1) elif ch == curses.KEY_UP: if y > 0: self.win.move(y - 1, x) elif ch == curses.KEY_DOWN: if y < self.maxy: self.win.move(y + 1, x) elif ch == curses.KEY_BACKSPACE: if x > 0: self.win.move(y, x - 1) self.win.delch() elif ch == curses.ascii.NL: if y < self.maxy: self.win.move(y + 1, 0) elif ch == curses.ascii.ESC: return 0 return 1 def gather(self): result = "" for y in range(self.maxy + 1): self.win.move(y, 0) stop = self._end_of_line(y) if stop == 0: continue for x in range(self.maxx + 1): if x > stop: break result = result + chr(curses.ascii.ascii(self.win.inch(y, x))) return result def edit(self): while 1: ch = self.win.getch() if not ch: continue if not self.do_command(ch): break self.win.refresh() def _pretty_print(self): word = [None] + self.gather().split() slack = [[None for x in range(len(word))] for x in range(len(word))] table = [0] * len(word) back_pointer = [0] * len(word) for i in range(1, len(word)): slack[i][i] = self.maxx - len(word[i]) for j in range(i + 1, len(word)): slack[i][j] = slack[i][j - 1] - (len(word[j]) + 1) for j in range(1, len(word)): table[j], back_pointer[j] = min( [ (table[i - 1] + slack[i][j]**2, i) for i in range(1, j + 1) if slack[i][j] >= 0 ] ) opt = [] j = len(word) - 1 while j > 0: opt.insert(0, j) j = back_pointer[j] - 1 self.win.erase() self.win.move(0, 0) i = 1 for j in opt[:len(opt) - 1]: for k in range(i, j + 1): self.win.addstr(word[k] + ' ') y, _ = self.win.getyx() self.win.move(y + 1, 0) i = j + 1 for k in range(i, opt[len(opt) - 1] + 1): self.win.addstr(word[k] + ' ') def main(stdscr): w = curses.newwin(100, 30, 1, 2) box = PrettyTextBox(w) box.edit() curses.wrapper(main)
Kaydol:
Kayıtlar (Atom)