Berechnung der Arbeit von f getan x = (x, x)

Question

Lassen Sie uns sagen, ich habe diese Funktion: (Haskell Syntax)

f x = (x,x) 

Was ist die Arbeit (Berechnungsmenge) durch die Funktion ausgeführt?

Zuerst dachte ich, es sei offensichtlich konstant, aber was ist, wenn der Typ von x nicht endlich ist, was bedeutet, dass x eine beliebige Menge an Speicher aufnehmen kann? Man müsste die Arbeit berücksichtigen, die durch das Kopieren von x gemacht wurde, oder?

Dies führte zu der Annahme, dass die von der Funktion geleistete Arbeit in der Größe der Eingabe tatsächlich linear ist.

Diese für sich nicht Hausaufgaben, aber kam, als ich die Arbeit von der Funktion getan definieren musste:

f x = [x] 

, die ein ähnliches Problem hat, glaube ich.

Answer 1

Sehr informell hängt die geleistete Arbeit von der operativen Semantik Ihrer Sprache ab. Haskell, na ja, es ist faul, so zahlen Sie nur konstante Faktoren:

• Push-Zeiger auf x auf dem Stapel
• für (,)
• gelten (,) auf ihre Argumente
• Rückkehr ein einen Haufen Zelle zuweisen Zeiger auf die Heap-Zelle

Fertig. O (1) funktionieren, wenn der Anrufer das Ergebnis von f betrachtet.

Jetzt werden Sie weitere Auswertung auslösen, wenn Sie in die (,) schauen - und diese Arbeit ist abhängig von der Arbeit zu bewerten x selbst. Da in Haskell die Referenzen auf x geteilt werden, werten Sie diese nur einmal aus.

Also die Arbeit in Haskell ist O (Arbeit von x), wenn Sie das Ergebnis vollständig auswerten. Ihre Funktion f fügt nur konstante Faktoren hinzu.

Answer 2

Chris Okasaki hat eine wunderbare Methode, die Arbeit zu bestimmen, die geladen wird, um zu funktionieren, wenn etwas (oder totale) Faulheit eingeführt wird. Ich glaube, es ist in seinem Artikel über rein funktionale Datenstrukturen. Ich weiß, dass es in der Buchversion ist - ich habe diesen Teil des Buches letzten Monat gelesen. Grundsätzlich berechnen Sie einen konstanten Faktor für das Versprechen/Thunk erstellt, laden Sie nichts für die Bewertung der übergebenen Versprechen/Thunks (angenommen, sie wurden bereits gezwungen/sind in normaler Form [nicht nur WHNF]). Das ist eine Unterschätzung. Wenn Sie eine überschätzen Ladung wollen, auch die Kosten der Forcierung/Umwandlung in Normalform jedes Versprechen/Thunk von der Funktion erstellt. Zumindest erinnere ich mich daran in meinem extrem müden Zustand.

Schauen Sie in Okasaki: http://www.westpoint.edu/eecs/SitePages/Chris%20Okasaki.aspx#thesis - Ich schwöre die These verwendet werden herunterladbar.