Iteration Techniques

Currently covers what I term as queues.

When we, as programmers, want the computer to remember a past sequence of events in a certain order, that remembering can loosely be termed a queue. A queue can be managed internally and dynamically by calling functions recursively, or it can be managed externally and statically by using iteration techniques.

Iteration techniques profer several advantages/disadvantages versus recursive techniques.

Advantages of an iteration queue:
*You can set a limit on the queue, making it possibly faster.
*You can define how the queue looks like.
*You can call the queue's data at a later time if you need it.

Advantages, with qualifications:
*For some people and/or in some instances, an iteration queue is easier to visualize.
*It may make re-designing a more complex queue easier.

Disadvantages:
*You don't have to worry about the size of the queue with dynamic queues, but you do with iteration queues.
*Same disadvantages with qualifications as "advantages with qualifications".




How to design an iteration queue:

Let us consider the queue where data is processed to become further data with varying inter-relatedness. You could have 1 piece become 2, which are scanned to become 4, then 8, etc. Or it could vary on the condition of the scan, ie: 1, then 3, then 6, then 7, etc. Examples: breadth-first search, factoring numbers.

First, realize the structure of your queue. If each piece of data results in more than one succeeding piece of data, you should have two "position" points on your queue array.

The first is the scanning position point; ie., at what position should your data next be examined?

The second is the result position point; ie., at what position in the queue should your resulting data next be put?

Remember, it is never necessary to have two alternating data/result-of-data queues, if the result and the input fundamentally structured in the same way; i.e., %, or $, or 500 to -500, or strings of length-5, 8-bit characters.

Example of iteration queue used for factoring a number:

CLS
DIM testfactor&(1 TO 100)
DIM isfactored%(1 TO 100)
n% = 1
newfree% = 1
INPUT "What is the number you want to factor"; testfactor&(n%)
DO
if testfactor%(n%) = 0 THEN EXIT DO

FOR testdiv& = 2 TO testfactor%(n%) ^ .5
'There is a more efficient way to do \ and /, but I don't remember it.
result1& = testfactor&(n%) \ testdiv&
IF result1& = testfactor&(n%) / testdiv& THEN
isfactored%(n%) = 1
testfactor&(newfree% + 1) = result1&
testfactor&(newfree% + 2) = testdiv&
newfree% = newfree% + 2
EXIT FOR
END IF
NEXT testdiv&
n% = n% + 1
LOOP

FOR i% = 1 TO newfree%
IF isfactored%(i%) = 0 THEN PRINT testfactor&(i%)
next i%
SLEEP


More to come, if someone adds something.

-by Agamemnus


IterationTechniques - page last edited 2005-10-08 00:32:53 by 24.128.143.175 (home) (edit)
Blast WIKI - by RoboticBoy - edited and tweaked for our evil purposes by Hexadecimal Disaster