147 lines
3.9 KiB
Python
147 lines
3.9 KiB
Python
from utils.algo_context import AlgoContext
|
||
from utils.algo_array import Array
|
||
from utils.algo_int import Int
|
||
from utils.algo_range import Range
|
||
|
||
|
||
def max_sequence_1(z: Array, ctx: AlgoContext):
|
||
"""O(n³) – dreifach verschachtelte Schleife."""
|
||
n = len(z)
|
||
m = Int(float('-inf'), ctx)
|
||
s = Int(0, ctx)
|
||
l = Int(0, ctx)
|
||
r = Int(0, ctx)
|
||
|
||
for i in Range(n):
|
||
for j in Range(int(i), n):
|
||
s.set(0)
|
||
for k in Range(int(i), int(j)):
|
||
s += z[k]
|
||
if s > m:
|
||
m.set(s)
|
||
l.set(Int(int(i), ctx))
|
||
r.set(Int(int(j), ctx))
|
||
return m, l, r
|
||
|
||
|
||
def max_sequence_2(z: Array, ctx: AlgoContext):
|
||
"""O(n²) – doppelt verschachtelte Schleife."""
|
||
n = len(z)
|
||
m = Int(float('-inf'), ctx)
|
||
s = Int(0, ctx)
|
||
left = Int(0, ctx)
|
||
right = Int(0, ctx)
|
||
|
||
for i in Range(n):
|
||
s.set(0)
|
||
for j in Range(int(i), n):
|
||
s += z[j]
|
||
if s > m:
|
||
m.set(s)
|
||
left.set(Int(int(i), ctx))
|
||
right.set(Int(int(j), ctx))
|
||
return m, left, right
|
||
|
||
|
||
def _finde_zwischen(z: Array, ctx: AlgoContext, l: int, m: int, r: int):
|
||
"""Hilfsfunktion für max_sequence_3: findet die maximale Teilsumme,
|
||
die die Mitte m überschreitet (3. Fall von Teile-und-Herrsche)."""
|
||
links_max = Int(float('-inf'), ctx)
|
||
s = Int(0, ctx)
|
||
links = Int(l, ctx)
|
||
for i in Range(m, l - 1, -1):
|
||
s += z[i]
|
||
if s > links_max:
|
||
links_max.set(s)
|
||
links.set(Int(int(i), ctx))
|
||
|
||
rechts_max = Int(float('-inf'), ctx)
|
||
s.set(0)
|
||
rechts = Int(m + 1, ctx)
|
||
for i in Range(m + 1, r + 1):
|
||
s += z[i]
|
||
if s > rechts_max:
|
||
rechts_max.set(s)
|
||
rechts.set(Int(int(i), ctx))
|
||
|
||
return links_max + rechts_max, links, rechts
|
||
|
||
|
||
def max_sequence_3(z: Array, ctx: AlgoContext, l: int = None, r: int = None):
|
||
"""O(n ld n) – Teile-und-Herrsche."""
|
||
if l is None:
|
||
l = 0
|
||
if r is None:
|
||
r = len(z) - 1
|
||
|
||
if l == r:
|
||
return z[l], Int(l, ctx), Int(r, ctx)
|
||
|
||
m = (l + r) // 2
|
||
links_max, links_l, links_r = max_sequence_3(z, ctx, l, m)
|
||
rechts_max, rechts_l, rechts_r = max_sequence_3(z, ctx, m + 1, r)
|
||
zwi_max, zwi_l, zwi_r = _finde_zwischen(z, ctx, l, m, r)
|
||
|
||
if links_max >= rechts_max and links_max >= zwi_max:
|
||
return links_max, links_l, links_r
|
||
if rechts_max >= links_max and rechts_max >= zwi_max:
|
||
return rechts_max, rechts_l, rechts_r
|
||
return zwi_max, zwi_l, zwi_r
|
||
|
||
|
||
def max_sequence_4(z: Array, ctx: AlgoContext):
|
||
"""O(n) – Kadane's Algorithmus."""
|
||
n = len(z)
|
||
m = Int(float('-inf'), ctx)
|
||
cur_sum = Int(0, ctx)
|
||
cur_left = Int(0, ctx)
|
||
left = Int(0, ctx)
|
||
right = Int(0, ctx)
|
||
|
||
for i in Range(n):
|
||
cur_sum += z[i]
|
||
if cur_sum > m:
|
||
m.set(cur_sum)
|
||
left.set(cur_left)
|
||
right.set(Int(int(i), ctx))
|
||
if cur_sum < 0:
|
||
cur_sum.set(0)
|
||
cur_left.set(Int(int(i) + 1, ctx))
|
||
|
||
return m, left, right
|
||
|
||
|
||
def example(max_sequence_func):
|
||
ctx = AlgoContext()
|
||
data = [-59, 52, 46, 14, -50, 58, -87, -77, 34, 15]
|
||
print(data)
|
||
z = Array(data, ctx)
|
||
m, l, r = max_sequence_func(z, ctx)
|
||
print(m, l, r)
|
||
|
||
|
||
def seq(filename, max_sequence_func):
|
||
ctx = AlgoContext()
|
||
z = Array.from_file(filename, ctx)
|
||
m, l, r = max_sequence_func(z, ctx)
|
||
print(m, l, r)
|
||
|
||
|
||
def analyze_complexity(max_sequence_func, sizes):
|
||
ctx = AlgoContext()
|
||
for size in sizes:
|
||
ctx.reset()
|
||
z = Array.random(size, -100, 100, ctx)
|
||
max_sequence_func(z, ctx)
|
||
ctx.save_stats(size)
|
||
|
||
ctx.plot_stats(["additions"])
|
||
|
||
|
||
if __name__ == '__main__':
|
||
example(max_sequence_3)
|
||
for filename in ["data/seq0.txt", "data/seq1.txt"]:
|
||
print(filename)
|
||
seq(filename, max_sequence_3)
|
||
analyze_complexity(max_sequence_3, [10, 20, 30, 40, 50, 60, 70, 80, 90, 100])
|