TCAX 字幕特效制作工具官方论坛 | ASS | TCAS | Python | Aegisub | Lua

标题: [libtcas] TCAS Chunk Index Linearization Algorithm Optimized [打印本页]
作者: milkyjing    时间: 2011-12-18 00:16:35     标题: [libtcas] TCAS Chunk Index Linearization Algorithm Optimized

suppose that we've got a massive amount of chunks (small ones, but come in random order)

How can we linearize them (the generation of linearized chunk index), there are two algorithms to achieve this goal


ONE

    1. create a list for holding index streams
    2. retrieve one index from the un-sorted index array, check if the index can be attached to the first index stream of the index streams, if so, just append it, otherwise, check the next index stream. If none of the existing index streams in the index streams list fit the requirement, we just create a new index stream, put the index into the newly created index stream, then attach the newly created index stream to the index streams list
    3. loop

    for the best case, the efficiency is about O(n)
    for the worst case, the efficiency is about O(n^2) (we have to check the first m index streams, before we know we have to create the m + 1 one! and what's worse, we have to create n index streams!, that's about n * n / 2.
    average performance is about O(m * n), m is the final number of index streams


TWO

    1. create a list for holding index streams (named indexStreams)
    2. create a list for holding the index stream whose 'last time' is the smallest amongst the index streams in the index streams list, named minIndexStream
    3. retrieve one index from the un-sorted index array, check if the index can be attached to the minIndexStream, if cannot we simply create a new index stream, put the index into the newly created index stream, then attach the newly created index stream to the index stream list.
   
    with the help of the minIndexStream, we can improve the performance to O(n), but the problem is how can we maintain such a minIndexStream?

indexStreams = []
newIndexStream = []
indexStreams.append(newIndexStream)
minIndexStream = 0
for an affine index:
    oldIndexStream = indexStreams[minIndexStream]
    if oldIndexStream.last < index.first:
        oldIndexStream.append(index)
        # how to determine the minIndexStream then?
    else:
        newIndexStream = [index]
        indexStreams.append(newIndexStream)
        # the minIndexStream stays the same, because it is still the smallest one


about maintaining a data structure for keeping the index and the 'last time', we can think of the AVL tree or Red-Black tree, which enables us to insert, delete or query a node in O(log n) time.



作者: milkyjing    时间: 2011-12-18 00:48:53     标题: Implementation

We choose Red-Black tree over AVL tree since the insertion and deletion operations may be frequent.

What information should the tree node hold?

1. id (index of the index stream in the index streams list)
2. last ('last time' of the index stream)


What we need from the tree?

1. we need the tree to calculate the minIndexStream


How can we get the minIndexStream according to the tree?

1. due to our construction of the tree, the very bottom-left node is always the minIndexStream


So how to construct (maintain) the tree?

1. by insertion and deletion. We insert a node according their values of 'last time', smaller on the left, larger on the right, and we delete or query a node by its id (the index of the index stream in the index stream list).
2. So, with each coming index, we may have to insert, delete and query the tree, which requires a time complexity of O(log n), n is the number of index streams. And in the old algorithm we have to check every existing index stream, which requires O(n).
3. As a conclusion, if the non-linearity is big, hence the number of index streams will be big as well, use of the new algorithm may dramatically improve the performance.




作者: milkyjing    时间: 2011-12-18 19:56:58     标题: Conclusion

As a conclusion, the old algorithm has a time complexity of O(n^2), while the new one has a time complexity of O(n * log n), of which the n means the number of index streams that can be regarded as the degree of non-linearity of the TCAS file. So, from the analysis, we can predict that when the n is relatively small or say the TCAS file is not so bad non-linear, the old algorithm may still work well, but this is not the case when the n goes large. Below are some real tests

Horizon_OP.tcas

horizon_op
old algorithm
new algorithm


tcas_test_non-linear.tcas

test non-linear
old algorithm
new algorithm


for more complex TCAS files (number of index streams is large), it will take much longer time for the old algorithm to finish generating the index streams. Although the number of index streams is larger when using the new algorithm, the impact to the rendering phase is trivial.





图片附件: [old algorithm] 2011-12-18_194957.jpg (2011-12-18 19:56:44, 40.61 KB) / 下载次数 462
http://www.tcax.org/forum.php?mod=attachment&aid=MTQyfDQ0MTg0MTYwfDE3MTUwMDk5NzF8MHww



图片附件: [new algorithm] 2011-12-18_194620.jpg (2011-12-18 19:56:43, 42.17 KB) / 下载次数 468
http://www.tcax.org/forum.php?mod=attachment&aid=MTQxfDdjNjg5NzY2fDE3MTUwMDk5NzF8MHww



图片附件: [horizon_op] 2011-12-18_205629.jpg (2011-12-18 20:56:55, 16.74 KB) / 下载次数 455
http://www.tcax.org/forum.php?mod=attachment&aid=MTQzfGMzNTA5Yzc5fDE3MTUwMDk5NzF8MHww



图片附件: [test non-linear] 2011-12-18_205554.jpg (2011-12-18 20:59:17, 16.54 KB) / 下载次数 466
http://www.tcax.org/forum.php?mod=attachment&aid=MTQ0fGRiMTI1YjgyfDE3MTUwMDk5NzF8MHww



图片附件: [new algorithm] 2011-12-18_214546.jpg (2011-12-18 21:49:55, 41.39 KB) / 下载次数 441
http://www.tcax.org/forum.php?mod=attachment&aid=MTQ1fDY2MTNjM2UxfDE3MTUwMDk5NzF8MHww



图片附件: [old algorithm] 2011-12-18_213642.jpg (2011-12-18 21:51:45, 43.9 KB) / 下载次数 471
http://www.tcax.org/forum.php?mod=attachment&aid=MTQ2fGQ2NDgwYTRlfDE3MTUwMDk5NzF8MHww

作者: milkyjing    时间: 2011-12-19 21:18:20

script for generating the non-linear TCAS file.
  1. from tcaxPy import *

  3. def tcaxPy_User():
  4.     file_name = GetVal(val_OutFile) + '.tcas'
  5.     fx_width = GetVal(val_ResolutionX)
  6.     fx_height = GetVal(val_ResolutionY)
  7.     fps = GetVal(val_FXFPS)
  8.     TCAS_FILE = CreateTcasFile(file_name, fx_width, fx_height, fps)
  9.     PIX_o = BlankPix(2, 2, MakeRGBA(255, 0, 0, 255))    #ImagePix(abspath('particle.png'))  #
  10.     PIX_o = PixBlur(PIX_o, 1)
  11.     _FD = 1000 / GetVal(val_FXFPS)
  12.     for f in range(1000):
  13.         n = int(fx_width / 3 * fx_height / 30)
  14.         for i in range(n):
  15.             TCAS_BUF = []
  16.             t = randint(0, int(_FD * 2))
  17.             tcas_main(TCAS_BUF, PIX_o, _FD * f + t, _FD * (f + 1) + t + randint(0, int(_FD * 2)), randint(int(fx_width * 1 / 5), int(fx_width * 4 / 5)), randint(int(fx_height * 13 / 20), int(fx_height * 17 / 20)), 0)
  18.             WriteTcasFile(TCAS_FILE, TCAS_BUF)     # write the buffer in memory to the file
  19.             progress(n * f + i + 1, n * 1000)
  20.         #progress(f + 1, 1)
  21.     FinTcasFile(TCAS_FILE)
复制代码




欢迎光临 TCAX 字幕特效制作工具官方论坛 | ASS | TCAS | Python | Aegisub | Lua (http://www.tcax.org/) Powered by Discuz! X2