Alternatives to modifying loop var in the loop.

[Matt]

I'm sure I've read somewhere that it's considered bad practice to modify
the value of the variable on the right of a comparison operator inside
the loop concerned. If I have remembered this correctly then what is the
usual way to do this:

int del_at(int i, int len, type arr[])
{
int j;
for(j = i + 1; j < len; j++, i++)
arr = arr[j];

return len - 1;
}

and somewhere else:

type arr[len];
/*fill it with some items*/

int i;
for(i=0; i < len; i++){
if(needs_deleting(arr))
len = del_at(i, len, arr);
}

This code works as intended and isn't complained about by gcc -Wall.

Isn't one of the things about C that you're able to do what you want?

Why shouldn't I do it the way I showed above? Could it come back to bite
me somehow?

Matt.

 

[glen herrmannsfeldt]

I'm sure I've read somewhere that it's considered bad practice to modify
the value of the variable on the right of a comparison operator inside
the loop concerned.

There are many things that it is better not to do because
readers won't expect it. Others to help avoid common mistakes.

If I have remembered this correctly then what is the
usual way to do this:

int del_at(int i, int len, type arr[])
{
int j;
for(j = i + 1; j < len; j++, i++)
arr = arr[j];
return len - 1;
}

Well, this one doesn't modify len while the loop is active...

and somewhere else:

type arr[len];
/*fill it with some items*/

int i;
for(i=0; i < len; i++){
if(needs_deleting(arr))
len = del_at(i, len, arr);
}

I don't see a problem with it, but it should be well commented to
be sure anyone reading it understands what it does.

This code works as intended and isn't complained about by gcc -Wall.

Isn't one of the things about C that you're able to do what you want?

Yes, especially for entries to the IOCCC. But other than that,
you want to write so it is more readable.

Why shouldn't I do it the way I showed above? Could it come
back to bite me somehow?

It is common, for example, to write the inner loop of quicksort
with both i and j varying, and both in the comparison. In that case,
though, it is pretty obvious what it is doing.

-- glen

 

[Willem]

Matt wrote:
) I'm sure I've read somewhere that it's considered bad practice to modify
) the value of the variable on the right of a comparison operator inside
) the loop concerned. If I have remembered this correctly then what is the
) usual way to do this:
)
) int del_at(int i, int len, type arr[])
) {
) int j;
) for(j = i + 1; j < len; j++, i++)
) arr = arr[j];
)
) return len - 1;
) }
)
) and somewhere else:
)
) type arr[len];
) /*fill it with some items*/
)
) int i;
) for(i=0; i < len; i++){
) if(needs_deleting(arr))
) len = del_at(i, len, arr);
) }

The usual way to do that, specifically, is to do it in a single loop, to
avoid having to copy and re-copy the items:

int j = 0;
for (i = j = 0; i < len; i++)
if (!needs_deleting(arr))
arr[j++] = arr;
len = j;

) This code works as intended and isn't complained about by gcc -Wall.
)
) Isn't one of the things about C that you're able to do what you want?
)
) Why shouldn't I do it the way I showed above? Could it come back to bite
) me somehow?

Perhaps the 'bad practice' you read about was this idiom, which is used to
avoid 'break' statements:

for (i = 0; i < len; i++) {
if (needs_ending(arr)) {
i = len;
} else {
do_something_with(arr);
}
}


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Tim Prince]

Matt wrote:
) I'm sure I've read somewhere that it's considered bad practice to modify
) the value of the variable on the right of a comparison operator inside
) the loop concerned.
Perhaps the 'bad practice' you read about was this idiom, which is used to
avoid 'break' statements:

for (i = 0; i < len; i++) {
if (needs_ending(arr)) {
i = len;
} else {
do_something_with(arr);
}
}

This one may prevent or break optimizations based on setting the loop
count prior to entering the loop. The break also would prevent such
optimizations, but the compiler would have no excuse for missing it.

 

[Eric Sosman]

I'm sure I've read somewhere that it's considered bad practice to modify
the value of the variable on the right of a comparison operator inside
the loop concerned. If I have remembered this correctly then what is the
usual way to do this:

int del_at(int i, int len, type arr[])
{
int j;
for(j = i + 1; j < len; j++, i++)
arr = arr[j];

return len - 1;
}

and somewhere else:

type arr[len];
/*fill it with some items*/

int i;
for(i=0; i < len; i++){
if(needs_deleting(arr))
len = del_at(i, len, arr);
}

This code works as intended and isn't complained about by gcc -Wall.

Since you've not revealed what is "intended," we can't dispute
your claim that it "works." Still, it looks fragile to me. Consider
this possible concretization:

typedef int type;

int needs_deleting(type value) {
return value % 2 == 0; // even numbers are unlucky
}

type arr[] = { 1, 2, 4, 6, 7 };
int len = 5;

Given this, it sort of looks like your code should squeeze out all
the even numbers and leave only the two odds. However, what your
code actually does is set arr[] to {1, 4, 7, 7, 7} and len to 3:
The 4 has survived deletion. More generally, *any* value immediately
following a deleted element will survive, whatever needs_deleting()
might say.

Isn't one of the things about C that you're able to do what you want?

There are lots of things I want to do for which C is no help.
Your wants are probably different from mine.

Why shouldn't I do it the way I showed above? Could it come back to bite
me somehow?

It all depends on "intended." The code does X, and if X is
what you intended, then no: The code will not come back to bite you.
But if you actually intended X', you've already felt its fangs.

 

[James Kuyper]

I'm sure I've read somewhere that it's considered bad practice to modify
the value of the variable on the right of a comparison operator inside
the loop concerned.

The validity of that guideline depends upon what you're doing. For
instance, if a loop starts with

for(int item=0; item < item_count; item++)

then it is potentially very confusing to change either item or
item_count within the loop. That doesn't mean you shouldn't do it - if
there's sufficiently good reason so do so, then you should; but you
should draw attention to the lines where you perform the modification by
inserting comments.

On the other hand, I've written code to do a bracketed binary search of
a sorted array like the following:

while(low < high)
{
int mid = (low+high)/2;
if(array[mid] < x)
low = mid+1;
else
high = mid;
}

The fact that this code modifies both "low" and "high" inside the loop
is not a problem, because it's very clear why and how it's modifying them.

 

[Matt]

you've not revealed what is "intended,"

I'm implementing the Knuth 5 guess algorithm for solving mastermind puzzles:

http://en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm

----<

#define PEGS 4
#define COLORS 6
#define ALL 1296 // (int)pow(COLORS, PEGS)

typedef struct{
int code[PEGS];
int knuth_number; // how many guesses this one gets solved in
} mcode;

mcode all_codes[ALL];
int npos;// the number of remaining possibilities for the secret code
// after processing the feedback from each guess.

----<

Before the first guesss:

----< npos = ALL;
----<

At each pass through the algorithm possibilities are eliminated
until npos == 1. Here is sample output using all_codes[1294]:

----<

solve 5554
guess 0011 0,0
npos 256
guess 2234 1,0
npos 18
guess 2545 1,2
npos 3
guess 0044 1,0
npos 1
guess 5554 4,0
solve 5554 K5

----<

Full context: http://code.mattsmith.org.nz/mastermind/ansic/

In different incarnations of this project I've used different ways of
managing the list of remaining possibilities. The actual codes, indexes,
manual memory allocation and freeing, high level c++ libraries. Now I'm
writing the game in plain ansi c as an ncurses application for
gnu/linux, then porting it piece by piece to an older compiler to build
as a prodos .SYS program for apple][.

On modern hardware it makes no difference how you do things as long as
it works. Except that I want to learn which ways are faster, which are
slower, which more or less elegant, which appropriate or not for a given
situation.

For the prodos version though there is a practical reason to learn this
stuff: speed. As currently implemented the prodos version takes about 15
min to come up with the first guess. This in an emulator at top speed.
Can't really expect a user to sit there on his chuff while the computer
player is "thinking" for this long.

it looks fragile to me. Consider
this possible concretization:

typedef int type;

int needs_deleting(type value) {
return value % 2 == 0; // even numbers are unlucky
}

type arr[] = { 1, 2, 4, 6, 7 };
int len = 5;

Given this, it sort of looks like your code should squeeze out all
the even numbers and leave only the two odds. However, what your
code actually does is set arr[] to {1, 4, 7, 7, 7} and len to 3:
The 4 has survived deletion. More generally, *any* value immediately
following a deleted element will survive, whatever needs_deleting()
might say.

All true. I "tested" del_at using

int arr[] = {0,1,2 ......,99};

and

if(arr % 5 == 0)
del_at(i, ...);

then assumed from that it would probably work in other situations. Not cool.

Pretty sure just your last point above excludes my del_at code from
working in the mastermind program because there are big contiguous
blocks of possibilities which get eliminated.

Thanks for your help.

Matt.

 

[Matt]

The usual way to do that, specifically, is to do it in a single loop, to
avoid having to copy and re-copy the items:

int j = 0;
for (i = j = 0; i < len; i++)
if (!needs_deleting(arr))
arr[j++] = arr;
len = j;

Thanks this is much better than what I did.

Matt.

 

[Ben Bacarisse]

Pretty sure just your last point above excludes my del_at code from
working in the mastermind program because there are big contiguous
blocks of possibilities which get eliminated.

Two things to consider: First, depending on the amount of data being
copied after the delete, you might find that memmove might be better
than your own loop. Second, you might want to alter the data structure.
Deletes from a linked list are fast, or you could keep a "deleted" flag
for every element so that nothing in the array need actually be copied.

But I also had a look a the code, and you have a redundant loop in
getscore which is the time-limiting function right now. You can count
the matching colours without looping over colours.

 

[Eric Sosman]

you've not revealed what is "intended,"

I'm implementing the Knuth 5 guess algorithm for solving mastermind
puzzles:
[...]
At each pass through the algorithm possibilities are eliminated
until npos == 1. [...]

Then you are doing *way* too much work. I'd suggest something
more along the lines of

int newlen = 0;
for (int i = 0; i < len; ++i) {
if (should_keep(array))
array[newlen++] = array;
}
len = newlen;

.... which moves each survivor once and each decedent zero times,
instead of moving both many times as they slide down again and
again and again to cover vacancies behind them.

For the prodos version though there is a practical reason to learn this
stuff: speed. As currently implemented the prodos version takes about 15
min to come up with the first guess. This in an emulator at top speed.
Can't really expect a user to sit there on his chuff while the computer
player is "thinking" for this long.

I'm not familiar with ProDOS, nor with whatever emulator you're
using, but the time seems overlong by maybe two orders of magnitude.
I recall writing a MasterMind game in the early 1970's and it made
its guesses faster than I could make mine. I suspect something's
seriously amiss with your setup -- could be your program, could be
a pitifully poor emulator, could be a lot of things -- but it doesn't
seem right that a machine from four decades ago (IBM S/370 145) could
out-perform current hardware on this kind of task.

 

[Aleksandar Kuktin]

Hi all.

I'm sure I've read somewhere that it's considered bad practice to
modify the value of the variable on the right of a comparison operator
inside the loop concerned. If I have remembered this correctly then
what is the usual way to do this:

int del_at(int i, int len, type arr[])
{
int j;
for(j = i + 1; j < len; j++, i++)
arr = arr[j];

return len - 1;
}

and somewhere else:

type arr[len];
/*fill it with some items*/

int i;
for(i=0; i < len; i++){
if(needs_deleting(arr))
len = del_at(i, len, arr);
}

This code works as intended and isn't complained about by gcc -Wall.

[snip]

More generally, *any* value immediately
following a deleted element will survive, whatever needs_deleting()
might say.

One possible way to solve the survivability error is to backtrack the
counter.

for (i=0; i<len; i++)
if (needs_deleting(arr)) {
len = del_at(i, len, arr);
i--;
}

The solution proposed by Willem and Eric is obviously better because
there is infinitelly less copying going on, but I am interested in the
general opinion on backtracking counters (unless that is also heavily
dependent on context). Is such a practice considered un-elegant, or
perhaps something similar?

 

[Eric Sosman]

[...]
One possible way to solve the survivability error is to backtrack the
counter.

for (i=0; i<len; i++)
if (needs_deleting(arr)) {
len = del_at(i, len, arr);
i--;
}

The solution proposed by Willem and Eric is obviously better because
there is infinitelly less copying going on, but I am interested in the
general opinion on backtracking counters (unless that is also heavily
dependent on context). Is such a practice considered un-elegant, or
perhaps something similar?

It doesn't seem to me that "elegance" is a useful criterion
for making decisions about software tactics. Like beauty, elegance
is in the eye of the beholder, and beholders will disagree. I've
heard "elegant" used to describe some stupendous botches, like
moving a file from one directory to another by copying it across
a network to an entirely different system and then copying it back
(true story, I kid you not)!

To my way of thinking, the most important consideration should
be correctness: Does the software (or fragment) do what is desired,
under all circumstances that might arise? Incorrectness, not
inefficiency, was the biggest flaw in the original code. After
that should come clarity and/or elegance, because they help build
confidence in the code's correctness and because they make it easier
to alter and extend. Performance is less important than either,
usually, unless it's so bad that it compromises correctness (the
O.P. spoke of a fifteen-minute wait for his game program to make
its first move; that's probably not "within specification").

So, back to the loop question: IMHO, fiddling with what looks
like a loop counter and/or fiddling with the termination condition
are threats to clarity. If you can recast the loop in a simpler
and more readable form, you should consider doing so. The loop
forms that I think most readable (but remember the "eye of the
beholder" stuff) are

// Counted loops:
for (i = START; i < LIMIT; i += STEP) ...
for (i = LIMIT; (i -= STEP) >= START; ) ...

// Predicated loops:
for (i = START; predicate(i); i += STEP) ...
while (predicate()) ...

Here, I'm supposing that START, LIMIT, and STEP are values that
do not change in the loop; they may not be "constants" in the C
sense, but if they vary while the loop is in progress the code
may well be harder to follow. But there are exceptions even to
this fuzzy guideline; for example a binary search:

for (lo = START, hi = LIMIT; lo < hi; ) {
mid = lo + (hi - lo) / 2;
if (key < array[mid])
hi = mid;
else if (key > array[mid])
lo = mid + 1;
else
return mid; // found it!
}
return -1; // not there (sob!)

Even though *both* participants in this loop's predicate are
subject to change during the loop, I don't think people will
find it confusing. If there's any doubt, perhaps it should be
rewritten as:

lo = START;
hi = LIMIT;
while (lo < hi) ...

Finally, to your "backtracking counter" loop: I really,
really don't like it. A better formulation, I think, would be

for (i = 0; i < len; ) {
if (needs_deleting(arr)
len = del_at(i, len, arr);
else
++i;
}

.... because the reader will not be fooled by the familiar-looking
`i++' in the first line and perhaps overlook the unfamiliar in-loop
adjustment. Seeing no index adjustment at all in the `for', he
will look inside the loop to learn what happens to `i', and (I
think) his route to understanding will be a shorter one.

 

[Matt]

you have a redundant loop in
getscore which is the time-limiting function right now. You can count
the matching colours without looping over colours.

Cool I'll look at this thanks.

 

[Matt]

I recall writing a MasterMind game in the early 1970's and it made
its guesses faster than I could make mine. I suspect something's
seriously amiss with your setup -- could be your program, could be
a pitifully poor emulator, could be a lot of things -- but it doesn't
seem right that a machine from four decades ago (IBM S/370 145) could
out-perform current hardware on this kind of task.

I'm pretty sure it'll turn out to be my program. As a self-taught hobby
programmer I just have no background in any of this stuff. Sometimes I
think I'll go back to school but at the universities where I live it's
java, then some java, then more java so I'm not convinced I would learn
what I want to anyway.

One point of pedantry: on current hardware my code also guesses faster
than I can. The Apple //e was current in 1983. Your point is 100% correct.

The emulator is http://linapple.sourceforge.net/. Quoting:

instead of inventing a wheel, I decided to port AppleWin to Linux,
using SDL library (Simple DirectMedia Layer) and changing all Windows
API functions to their POSIX equivalents.

From lurking on comp.apple2.sys.* it seems like AppleWin is considered
to be one of the better ][ emulators going around. I'm going to look at
my code first, trying different emulators is lower down the list.

First I'll fix get_score according to Ben's advice then maybe try a
linked list since that is something I want to learn anyway.

Thanks all,

Matt.

 

[Matt]

it doesn't
seem right that a machine from four decades ago (IBM S/370 145) could
out-perform current hardware on this kind of task.

[...]

One point of pedantry: on current hardware my code also guesses faster
than I can. The Apple //e was current in 1983. Your point is 100% correct.

I can word this more clearly:

Imo the S/370 145 is not outperforming current(2013) hardware. It is
outperforming current(1983) hardware. In any case the hardware isn't
realy the issue. Allowing for hardware Eric's code outperforms mine. I
have a lot to learn.

 

[Matt]

you have a redundant loop in
getscore which is the time-limiting function right now. You can count
the matching colours without looping over colours.

http://code.mattsmith.org.nz/mastermind/bits/new_get_score.c

I still iterated through colors once to set some stuff to 0.
Even then I'm never telling anyone how long it took me. I have a gift
for making simple things complicated lol. It always amazes me how
something you do as a human without even knowing how you do it (scoring
your opponents guess in a board game) can be so difficult (for me
anyway) to explain to a computer.

$ time ./testfunc old

real 0m0.255s
user 0m0.252s
sys 0m0.004s

$ time ./testfunc new

real 0m0.150s
user 0m0.144s
sys 0m0.004s

$ cat /proc/cpuinfo
processor : 0
vendor_id : AuthenticAMD
cpu family : 21
model : 2
model name : AMD FX(tm)-6300 Six-Core Processor
stepping : 0
microcode : 0x6000803
cpu MHz : 1400.000
[...]

$ cat /proc/meminfo
MemTotal: 33048056 kB
[...]

It's beer o'clock in utc +12 land. Tomorrow I plug new_get_score in to
the apple//e code.

 

[Seebs]

It doesn't seem to me that "elegance" is a useful criterion
for making decisions about software tactics.

Oh, I'd disagree on that. I think it's one of the best. Unfortunately,
that doesn't necessarily make it flawless.

Like beauty, elegance
is in the eye of the beholder, and beholders will disagree. I've
heard "elegant" used to describe some stupendous botches, like
moving a file from one directory to another by copying it across
a network to an entirely different system and then copying it back
(true story, I kid you not)!

That is certainly a problem, but I would argue that this is best resolved
by pointing out the ways in which it fails to be elegant.

But elegance solves a really useful problem, which is getting some of
our very fast cognitive function that isn't consciously available aligned
to a task that helps us get things fixed.

To my way of thinking, the most important consideration should
be correctness: Does the software (or fragment) do what is desired,
under all circumstances that might arise?

While this is certainly very important, I think another thing, while
strictly speaking less important, is functionally a prerequisite for
making useful decisions: Can we *tell* whether the software does what
we want?

And that's where "elegant" can become an important consideration.

Incorrectness, not
inefficiency, was the biggest flaw in the original code. After
that should come clarity and/or elegance, because they help build
confidence in the code's correctness and because they make it easier
to alter and extend.

I would say that if code is sufficiently unclear, that evaluating
its correctness is quite likely to be less useful than changing it so
you can at least tell what it's doing.

If you can't evaluate a criterion, it's not useful to you, and "elegant"
tends to be a very close proxy for "easily understood and checked for
correctness".

-s

 

[Ben Bacarisse]

http://code.mattsmith.org.nz/mastermind/bits/new_get_score.c

I still iterated through colors once to set some stuff to 0.

You can use '= {0};' as the initialiser to zero the arrays.

<snip>

 

[Eric Sosman]

Oh, I'd disagree on that. I think it's one of the best. Unfortunately,
that doesn't necessarily make it flawless.


That is certainly a problem, but I would argue that this is best resolved
by pointing out the ways in which it fails to be elegant.

But elegance solves a really useful problem, which is getting some of
our very fast cognitive function that isn't consciously available aligned
to a task that helps us get things fixed.


While this is certainly very important, I think another thing, while
strictly speaking less important, is functionally a prerequisite for
making useful decisions: Can we *tell* whether the software does what
we want?

And that's where "elegant" can become an important consideration.


I would say that if code is sufficiently unclear, that evaluating
its correctness is quite likely to be less useful than changing it so
you can at least tell what it's doing.

If you can't evaluate a criterion, it's not useful to you, and "elegant"
tends to be a very close proxy for "easily understood and checked for
correctness".

I think that "elegance" means different things to the two
of us (eye of the beholder, again). The quality you describe
as "elegance" is something I'd prefer to call "clarity," and I
agree that it's a desirable attribute regardless of whether you
call it clarigance or eleganity.

"Clarity" is something one could attempt to measure, much as
one measures "readability" in natural language. You could show
scraps of code to suitable populations of readers, ask them
verifiable questions about what the code does, run t-tests and
so on to decide whether scrap A is more or less clear than B, ...
This is the sort of experiment one can imagine performing.[*]

But is there an experiment that could attempt to measure
"elegance?" One could show code samples to a bunch of fashion
writers, I guess, but ... Can you think of any way to elevate
opinion and taste to something measurable? I can't.

... and that's why I don't think "elegance" is a useful
criterion: If you can't measure it, you can't tell whether it's
present or absent, or to what degree. And if you can't really
say whether A is more or less elegant than B, you can't make
good decisions based on how elegant they are or aren't.

[*] IIRC, Weinberg reported on a similar experiment in "The
Psychology of Computer Programming." Groups of computer science
students read the same piece of code, either in its original form
or with the comments removed. The students who saw the UNcommented
code found and fixed more of its errors than those who had the
"benefit" of the commentary ...

 

[Phil Carmody]

Oh, I'd disagree on that. I think it's one of the best. Unfortunately,
that doesn't necessarily make it flawless.

I'm not sure with whom I agree, as I agree with both!

Perhaps "elegance" is a tag that is only applied to code *after*
it's been checked that it seems correct? (2 wiggle words there,
checking isn't proving, and seems covers many sins!) One of the
best things about elegant code is that it is easily checked for
correctness.

Correct code wasn't attempting to evolve in the direction of elegance,
it's just that elegant code had the evolutionary advantage when it
came to populating correct-code-space.

For example Willem's (and Eric's?) needs_deleting() loop earlier is
such an elegant snippet, you can almost view it as an atomic whole
and see instantly if it's been done correctly or not.

I may be jabbering nonsense here, contrary views are welcome.
Phil