LoT-modeling/theoretical.py at main · bendemonium/LoT-modeling · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
class wm():
    def __init__(self):
        wm.value = 0
        wm.cache = []
    def update(self, value):
        wm.value += value
        wm.cache.append(wm.value)
    @property
    def max_space(self):
        return max(wm.cache)

def calculate_theoretical_complexity(algorithm, n, divs = None):
    kolmo = 0
    space = wm()
    if algorithm == 'chaning':
        pass
    if algorithm == 'ordinal':
        pass
    if algorithm == 'iterate':
        group = n / divs
        space.update(divs * (1 + 2*group)) #lexicon
        while(n):
            space.update(2) # current
            kolmo += 1 # current pf.sample
            kolmo += 1 # remove
            space.update(-2) # update lexicon
            n -= 1 # update lexicon
            # write_all
            # making find lexicon uses move so total space is not affected
            kolmo += (1 + (group - 1)*2) # find pf
            for _ in range(group - 2):
                kolmo += 3 # pfs: sample, add, remove
                space.update(-2)
                n -= 1
            kolmo += 2 # pfs: sample, add, remove for the last item
            space.update(-2) # remove last element from sub_lex
            space.update(-1) # remove attrbute node from sub_lex
            n -= 1
            space.update(-2) # purge current

    if algorithm == 'palindrome':
        space.update(divs * (1 + 2*group)) # lexicon
        for _ in range(n/2):
            kolmo += 1 # loop
            # sample current
            space.update(2)
            kolmo += 1
            # add to basis
            kolmo += 1
            space.update(2)
            # remove from lexicon
            kolmo += 1
            space.update(-2)
            # pushing out to a diff lex
            kolmo += 2 # finding sublex
            kolmo += 0 # sample after finding
            kolmo += 2 # add, remove
            space.update(-2) # purge current
        basis = n/2
        for _ in range(n/2):
            kolmo += 1 # loop
            # push out from basis
            kolmo += 1 #space stays the same since it's being moved to remainder
            # iterate through basis, a queue
            remainder = 0
            while(basis):
                kolmo += 1 # loop
                # add to remainder
                kolmo += 1
                remainder += 1
                # push_out next
                kolmo += 1
                basis -= 1
            # write the other one
            kolmo += 1 # find and sample
            kolmo += 2 # add and remove
            basis = remainder
            space.update(-4) # removed from lexixon and basis

    if algorithm == 'alternate':
        space.update(divs * (1 + 2*group)) # lexicon
        # current
        kolmo += 1 # sample
        space.update(2)
        # remove from lexicon
        kolmo += 1
        space.update(-2)
        alternates = n/2
        for _ in range (n - 2):
            kolmo += 1 # loop
            # find_alternates
            kolmo += alternates
            # sample
            kolmo += 1
            # remove
            kolmo += 1
            if _ % 2 == 0:
                alternates -= 1
            space.update(-2)
            if _ == n-3:
                space.update(-1) # remove the attribute node
        #getting rid of the last one
        kolmo += 1 #find the other one
        kolmo += 1 # remove
        space.update(-3) # remove token and the attr node from lexicon

    if algorithm == 'seriate':
        group = n/divs
        kolmo += (divs*3)
        kolmo += divs*((group - 1)*(1 + 3) - 1) # for the write_all
        kolmo += (group - 1)*(1+1+1) # buffer except write random
        kolmo += ((group-1)*(group-2))/2 + (group-2) + 2*(group-1)


    if algorithm == 'serial-crossed':
        pass
    if algorithm == 'center-embedded':
        pass
    if algorithm == 'tail-recursive':
        pass

    return (kolmo, space.max_space)