Versionsvergleich
Aus ProgrammingWiki
Vergleich: 2020-09-02T20:36:54+00:00 → 2020-09-02T20:36:54+00:00
<language>Python</language> | |
Das folgende Programm berechnet die Anzahl der Aufrufe für die Tabellenfelder am Beispiel von "Zufallsgegenständen". Der Einfluss von Memoizing ist sehr deutlich. | |
<code id="5f500266ca578"> | |
import random as rnd | |
import matplotlib.pyplot as plt | |
from matplotlib.ticker import MaxNLocator | |
import numpy as np | |
def rand_items(n): | |
items = [] | |
for i in range(0, n): | |
items.append((rnd.randint(1, 100), rnd.randint(1, 100))) | |
return items | |
calls_with_memo = [] | |
calls_without_memo = [] | |
for i in range(2, 21): | |
calls1 = 0 | |
calls2 = 0 | |
for j in range(0, 5): | |
K = 20 * i | |
items = rand_items(i) | |
n = len(items) - 1 | |
global weights | |
weights = [] | |
global values | |
values = [] | |
global calls | |
calls = 0 | |
for item in items: | |
weights.append(item[0]) | |
values.append(item[1]) | |
value_memo(n, K) | |
calls1 += calls | |
calls = 0 | |
value(n, K) | |
calls2 += calls | |
calls = 0 | |
calls_with_memo.append(calls1 / 5) | |
calls_without_memo.append(calls2 / 5) | |
x = np.arange(2, 21) | |
y1 = np.asarray(calls_with_memo) | |
y2 = np.asarray(calls_without_memo) | |
fig = plt.figure(figsize=(11,8)) | |
ax1 = fig.add_subplot(111) | |
ax1.plot(x, y1, label='Funktionsaufrufe mit Memoization') | |
ax1.plot(x, y2, label='Funktionsaufrufe ohne Memoization') | |
ax1.xaxis.set_major_locator(MaxNLocator(integer=True)) | |
plt.legend() | |
plt.show() | |
</code> | |
[[Datei:Dynamic_programming_plot.png|450px]] |