mirror of
https://github.com/ntop/ntopng.git
synced 2026-07-28 00:58:40 +00:00
207 lines
8.6 KiB
HTML
207 lines
8.6 KiB
HTML
<?xml version="1.0" ?>
|
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
|
|
<html xmlns="http://www.w3.org/1999/xhtml">
|
|
<head>
|
|
<title>rpntutorial</title>
|
|
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
|
|
<link rev="made" href="mailto:root@localhost" />
|
|
</head>
|
|
|
|
<body style="background-color: white">
|
|
|
|
|
|
<!-- INDEX BEGIN -->
|
|
<div name="index">
|
|
<p><a name="__index__"></a></p>
|
|
<!--
|
|
|
|
<ul>
|
|
|
|
<li><a href="#name">NAME</a></li>
|
|
<li><a href="#description">DESCRIPTION</a></li>
|
|
<li><a href="#reading_comparison_operators">Reading Comparison Operators</a></li>
|
|
<li><a href="#reading_the_if_operator">Reading the IF Operator</a></li>
|
|
<li><a href="#some_examples">Some Examples</a></li>
|
|
<li><a href="#exercises">Exercises</a></li>
|
|
<li><a href="#author">AUTHOR</a></li>
|
|
</ul>
|
|
|
|
-->
|
|
|
|
|
|
</div>
|
|
<!-- INDEX END -->
|
|
|
|
<p>
|
|
</p>
|
|
<h1><a name="name">NAME</a></h1>
|
|
<p>rpntutorial - Reading RRDtool RPN Expressions by Steve Rader</p>
|
|
<p>
|
|
</p>
|
|
<hr />
|
|
<h1><a name="description">DESCRIPTION</a></h1>
|
|
<p>This tutorial should help you get to grips with RRDtool RPN expressions
|
|
as seen in CDEF arguments of RRDtool graph.</p>
|
|
<p>
|
|
</p>
|
|
<hr />
|
|
<h1><a name="reading_comparison_operators">Reading Comparison Operators</a></h1>
|
|
<p>The LT, LE, GT, GE and EQ RPN logic operators are not as tricky as
|
|
they appear. These operators act on the two values on the stack
|
|
preceding them (to the left). Read these two values on the stack
|
|
from left to right inserting the operator in the middle. If the
|
|
resulting statement is true, then replace the three values from the
|
|
stack with "1". If the statement if false, replace the three values
|
|
with "0".</p>
|
|
<p>For example, think about "2,1,GT". This RPN expression could be
|
|
read as "is two greater than one?" The answer to that question is
|
|
"true". So the three values should be replaced with "1". Thus the
|
|
RPN expression 2,1,GT evaluates to 1.</p>
|
|
<p>Now consider "2,1,LE". This RPN expression could be read as "is
|
|
two less than or equal to one?". The natural response is "no"
|
|
and thus the RPN expression 2,1,LE evaluates to 0.</p>
|
|
<p>
|
|
</p>
|
|
<hr />
|
|
<h1><a name="reading_the_if_operator">Reading the IF Operator</a></h1>
|
|
<p>The IF RPN logic operator can be straightforward also. The key
|
|
to reading IF operators is to understand that the condition part
|
|
of the traditional "if X than Y else Z" notation has *already*
|
|
been evaluated. So the IF operator acts on only one value on the
|
|
stack: the third value to the left of the IF value. The second
|
|
value to the left of the IF corresponds to the true ("Y") branch.
|
|
And the first value to the left of the IF corresponds to the false
|
|
("Z") branch. Read the RPN expression "X,Y,Z,IF" from left to
|
|
right like so: "if X then Y else Z".</p>
|
|
<p>For example, consider "1,10,100,IF". It looks bizarre to me.
|
|
But when I read "if 1 then 10 else 100" it's crystal clear: 1 is true
|
|
so the answer is 10. Note that only zero is false; all other values
|
|
are true. "2,20,200,IF" ("if 2 then 20 else 200") evaluates to 20.
|
|
And "0,1,2,IF" ("if 0 then 1 else 2) evaluates to 2.</p>
|
|
<p>Notice that none of the above examples really simulate the whole
|
|
"if X then Y else Z" statement. This is because computer programmers
|
|
read this statement as "if Some Condition then Y else Z". So it's
|
|
important to be able to read IF operators along with the LT, LE,
|
|
GT, GE and EQ operators.</p>
|
|
<p>
|
|
</p>
|
|
<hr />
|
|
<h1><a name="some_examples">Some Examples</a></h1>
|
|
<p>While compound expressions can look overly complex, they can be
|
|
considered elegantly simple. To quickly comprehend RPN expressions,
|
|
you must know the algorithm for evaluating RPN expressions:
|
|
iterate searches from the left to the right looking for an operator.
|
|
When it's found, apply that operator by popping the operator and some
|
|
number of values (and by definition, not operators) off the stack.</p>
|
|
<p>For example, the stack "1,2,3,+,+" gets "2,3,+" evaluated (as "2+3")
|
|
during the first iteration and is replaced by 5. This results in
|
|
the stack "1,5,+". Finally, "1,5,+" is evaluated resulting in the
|
|
answer 6. For convenience, it's useful to write this set of
|
|
operations as:</p>
|
|
<pre>
|
|
1) 1,2,3,+,+ eval is 2,3,+ = 5 result is 1,5,+
|
|
2) 1,5,+ eval is 1,5,+ = 6 result is 6
|
|
3) 6</pre>
|
|
<p>Let's use that notation to conveniently solve some complex RPN expressions
|
|
with multiple logic operators:</p>
|
|
<pre>
|
|
1) 20,10,GT,10,20,IF eval is 20,10,GT = 1 result is 1,10,20,IF</pre>
|
|
<p>read the eval as pop "20 is greater than 10" so push 1</p>
|
|
<pre>
|
|
2) 1,10,20,IF eval is 1,10,20,IF = 10 result is 10</pre>
|
|
<p>read pop "if 1 then 10 else 20" so push 10. Only 10 is left so
|
|
10 is the answer.</p>
|
|
<p>Let's read a complex RPN expression that also has the traditional
|
|
multiplication operator:</p>
|
|
<pre>
|
|
1) 128,8,*,7000,GT,7000,128,8,*,IF eval 128,8,* result is 1024
|
|
2) 1024 ,7000,GT,7000,128,8,*,IF eval 1024,7000,GT result is 0
|
|
3) 0, 7000,128,8,*,IF eval 128,8,* result is 1024
|
|
4) 0, 7000,1024, IF result is 1024</pre>
|
|
<p>Now let's go back to the first example of multiple logic operators,
|
|
but replace the value 20 with the variable "input":</p>
|
|
<pre>
|
|
1) input,10,GT,10,input,IF eval is input,10,GT ( lets call this A )</pre>
|
|
<p>Read eval as "if input > 10 then true" and replace "input,10,GT"
|
|
with "A":</p>
|
|
<pre>
|
|
2) A,10,input,IF eval is A,10,input,IF</pre>
|
|
<p>read "if A then 10 else input". Now replace A with it's verbose
|
|
description again and--voila!--you have an easily readable description
|
|
of the expression:</p>
|
|
<pre>
|
|
if input > 10 then 10 else input</pre>
|
|
<p>Finally, let's go back to the first most complex example and replace
|
|
the value 128 with "input":</p>
|
|
<pre>
|
|
1) input,8,*,7000,GT,7000,input,8,*,IF eval input,8,* result is A</pre>
|
|
<p>where A is "input * 8"</p>
|
|
<pre>
|
|
2) A,7000,GT,7000,input,8,*,IF eval is A,7000,GT result is B</pre>
|
|
<p>where B is "if ((input * 8) > 7000) then true"</p>
|
|
<pre>
|
|
3) B,7000,input,8,*,IF eval is input,8,* result is C</pre>
|
|
<p>where C is "input * 8"</p>
|
|
<pre>
|
|
4) B,7000,C,IF</pre>
|
|
<p>At last we have a readable decoding of the complex RPN expression with
|
|
a variable:</p>
|
|
<pre>
|
|
if ((input * 8) > 7000) then 7000 else (input * 8)</pre>
|
|
<p>
|
|
</p>
|
|
<hr />
|
|
<h1><a name="exercises">Exercises</a></h1>
|
|
<p>Exercise 1:</p>
|
|
<p>Compute "3,2,*,1,+ and "3,2,1,+,*" by hand. Rewrite them in
|
|
traditional notation. Explain why they have different answers.</p>
|
|
<p>Answer 1:</p>
|
|
<pre>
|
|
3*2+1 = 7 and 3*(2+1) = 9. These expressions have
|
|
different answers because the altering of the plus and
|
|
times operators alter the order of their evaluation.</pre>
|
|
<p>Exercise 2:</p>
|
|
<p>One may be tempted to shorten the expression</p>
|
|
<pre>
|
|
input,8,*,56000,GT,56000,input,*,8,IF</pre>
|
|
<p>by removing the redundant use of "input,8,*" like so:</p>
|
|
<pre>
|
|
input,56000,GT,56000,input,IF,8,*</pre>
|
|
<p>Use traditional notation to show these expressions are not the same.
|
|
Write an expression that's equivalent to the first expression, but
|
|
uses the LE and DIV operators.</p>
|
|
<p>Answer 2:</p>
|
|
<pre>
|
|
if (input <= 56000/8 ) { input*8 } else { 56000 }
|
|
input,56000,8,DIV,LE,input,8,*,56000,IF</pre>
|
|
<p>Exercise 3:</p>
|
|
<p>Briefly explain why traditional mathematic notation requires the
|
|
use of parentheses. Explain why RPN notation does not require
|
|
the use of parentheses.</p>
|
|
<p>Answer 3:</p>
|
|
<pre>
|
|
Traditional mathematic expressions are evaluated by
|
|
doing multiplication and division first, then addition and
|
|
subtraction. Parentheses are used to force the evaluation of
|
|
addition before multiplication (etc). RPN does not require
|
|
parentheses because the ordering of objects on the stack
|
|
can force the evaluation of addition before multiplication.</pre>
|
|
<p>Exercise 4:</p>
|
|
<p>Explain why it was desirable for the RRDtool developers to implement
|
|
RPN notation instead of traditional mathematical notation.</p>
|
|
<p>Answer 4:</p>
|
|
<pre>
|
|
The algorithm that implements traditional mathematical
|
|
notation is more complex then algorithm used for RPN.
|
|
So implementing RPN allowed Tobias Oetiker to write less
|
|
code! (The code is also less complex and therefore less
|
|
likely to have bugs.)</pre>
|
|
<p>
|
|
</p>
|
|
<hr />
|
|
<h1><a name="author">AUTHOR</a></h1>
|
|
<p>Steve Rader <<a href="mailto:rader@wiscnet.net">rader@wiscnet.net</a>></p>
|
|
|
|
</body>
|
|
|
|
</html>
|