comp.lang.c - 7 new messages in 3 topics - digest

comp.lang.c
http://groups.google.com/group/comp.lang.c?hl=en

comp.lang.c@googlegroups.com

Today's topics:

* substring finding problem! - 5 messages, 2 authors
http://groups.google.com/group/comp.lang.c/t/cf9bd97208e0c3a3?hl=en
* Warning to newbies - 1 messages, 1 author
http://groups.google.com/group/comp.lang.c/t/9597fd702985dff4?hl=en
* Efficency and the standard library - 1 messages, 1 author
http://groups.google.com/group/comp.lang.c/t/ad9fea19f2f7dd61?hl=en

==============================================================================
TOPIC: substring finding problem!
http://groups.google.com/group/comp.lang.c/t/cf9bd97208e0c3a3?hl=en
==============================================================================

== 1 of 5 ==
Date: Wed, Feb 17 2010 11:27 pm
From: "Chris M. Thomasson"

Here is a simple technique that can possibly cut down on the number of
search operations one needs to perform. It does this by using the length of
the string, (e.g., fits in well with counted string), and initializes a hash
table of the stores characters of the comparand string from right-to-left.
It performs a search from left-to-right, however it compares source against
comparand in right-to-left. If a search character does not exist within the
comparand, the search index can be incremented by the length of the
comparand. For instance:
_______________________________________________________________
src = ChrisHelloJohn
cmp = Hello
hash['o'] = 5
hash['l'] = 4
hash['e'] = 2
hash['H'] = 1
_______________________________________________________________

Okay, we want to find `cmp' in `src. So you put the head index on `s' and
you put the tail on 'C'. You can skip 5 characters if `hash[src[head]]' is
zero. There are more elaborate ways to skip characters and I think you can
use the right-to-left hash list to determine other things as well. Here is
some a very crude initial code sketch of the algorithm I am thinking about:

http://clc.pastebin.com/f7df86b63

Here is the output I get for search for "Hello" in the following string:

"ldsefkdsjehuoeewhs;dfjpewfjHello9438jfgohj"
_______________________________________________________________
right-to-left hash hit 'o'!
right-to-left hash hit 'l'!
right-to-left hash miss 'l' chars
right-to-left hash hit 'e'!
right-to-left hash hit 'H'!
compare(1) 'f' to 'o'
skip 5 chars!
compare(2) 'e' to 'o'
compare(3) 'h' to 'o'
skip 5 chars!
compare(4) 'w' to 'o'
skip 5 chars!
compare(5) 'f' to 'o'
skip 5 chars!
compare(6) 'f' to 'o'
skip 5 chars!
compare(7) 'l' to 'o'
compare(8) 'o' to 'o'
compare(9) 'l' to 'l'
compare(10) 'l' to 'l'
compare(11) 'e' to 'e'
compare(12) 'H' to 'H'
((12) compares + (5) hashes) out of (42) characters target at (27)
Hello9438jfgohj
_______________________________________________________________

The algorithm was able to skip some characters and only perform 12
comparisons in order to find the comparand at index 27 in a string 42
characters wide. I think there are many more optimizations that could be
made...

== 2 of 5 ==
Date: Wed, Feb 17 2010 11:32 pm
From: "Chris M. Thomasson"

"Chris M. Thomasson" <no@spam.invalid> wrote in message
news:jZ5fn.556$Ee1.429@newsfe12.iad...
> Here is a simple technique that can possibly cut down on the number of
> search operations one needs to perform. It does this by using the length
> of the string, (e.g., fits in well with counted string), and initializes a
> hash table of the stores characters of the comparand string from
> right-to-left. It performs a search from left-to-right, however it
> compares source against comparand in right-to-left. If a search character
> does not exist within the comparand, the search index can be incremented
> by the length of the comparand. For instance:
> _______________________________________________________________
> src = ChrisHelloJohn
> cmp = Hello
> hash['o'] = 5
> hash['l'] = 4
> hash['e'] = 2
> hash['H'] = 1
> _______________________________________________________________
>
>
> Okay, we want to find `cmp' in `src. So you put the head index on `s' and
> you put the tail on 'C'. You can skip 5 characters if `hash[src[head]]' is
> zero. There are more elaborate ways to skip characters and I think you can
> use the right-to-left hash list to determine other things as well. Here is
> some a very crude initial code sketch of the algorithm I am thinking
> about:
>
>
> http://clc.pastebin.com/f7df86b63

[...]

I know there should be some bugs in there, so, don't use the code for
anything. I will post fixes as I find them. If you can fix a bug, that would
be very nice as well! Thanks in advance, I really would appreciate it.

:^)

== 3 of 5 ==
Date: Wed, Feb 17 2010 11:38 pm
From: "Chris M. Thomasson"

I found a stupid bug; here is fix:

http://clc.pastebin.com/f4f063111

And here is the difference from the previous code:

http://clc.pastebin.com/pastebin.php?diff=f4f063111

== 4 of 5 ==
Date: Thurs, Feb 18 2010 12:07 am
From: Nick Keighley

On 18 Feb, 06:02, spinoza1111 <spinoza1...@yahoo.com> wrote:
> On Feb 18, 12:33 pm, Walter Banks <wal...@bytecraft.com> wrote:
> > spinoza1111wrote:
> > > On Feb 18, 6:08 am, Walter Banks <wal...@bytecraft.com> wrote:

> > > > Software development practices have improved a lot as applications
> > > > have become more complex and requirements better defined.

I'm not sure this is true !

> > > How can "defining requirements" improve "software development
> > > practices"?

acquiring good requirements is part of good software development
practice.

> > > "Defining requirements" is being able to express the
> > > requirements in English, other human languages, visuals, and if
> > > necessary mathematical formalisms:

yes. Though various graphical representaions are popular as well.

> > > if you define them in code, you're
> > > not, by definition, "defining requirements": you are coding.

well yes, but he didn't say define the requirements in code

> > You just answered your own question.
>
> But [...] you said that software improves if we define
> requirements.

no he didn't he said "Software development practices [are] improved
[if] requirements [are] better defined." (the actual quote is at the
beginning of the post).

> Please explain how this work, and note that industrial
> experience is that the success of a software development project is
> completely independent of requirements quality.

really, could you expand on that. I was under the impression that many
projects had failed due to badly defined requirements.

> Sometimes, beautiful
> requirements produce beautiful code, sometimes, beautiful requirements
> beautifully miss the point.

then they aren't good requirements! If you ask a guy to build a garage
then complain he missed the swimming pool out that means you gave him
a poor requirement.

> Sometimes, Extreme programming projects
> start out with no requirements and beauty results.

in a sense you're deriving the requirement by iterative refinement.
Have you read "Principles of Software Engineering Management" by Tom
Gilb. He was extreme programming before the (slightly silly) name was
invented.

== 5 of 5 ==
Date: Thurs, Feb 18 2010 12:16 am
From: Nick Keighley

On 17 Feb, 21:14, Richard Heathfield <r...@see.sig.invalid> wrote:

<snip>

> The scanf function is basically a mess, and is rarely used correctly. I
> am at a loss to understand why it is introduced so early in programming
> texts.

a former clc regular once posted

***
The fscanf equivalent of fgets is so simple
that it can be used inline whenever needed:-
char s[NN + 1] = "", c;
int rc = fscanf(fp, "%NN[^\n]%1[\n]", s, &c);
if (rc == 1) fscanf("%*[^\n]%*c);
if (rc == 0) getc(fp);
***

I think scanf() is seen as a straight forward way to read simple
unvalidated input. I'm not convinced that's a good idea.

> The strtok function is of limited use, but there are times when it is
> just the ticket. It would be better, however, for it to take a state
> pointer. I'm not convinced that its interface is particularly non-intuitive.

==============================================================================
TOPIC: Warning to newbies
http://groups.google.com/group/comp.lang.c/t/9597fd702985dff4?hl=en
==============================================================================

== 1 of 1 ==
Date: Thurs, Feb 18 2010 12:17 am
From: Nick <3-nospam@temporary-address.org.uk>

Seebs <usenet-nospam@seebs.net> writes:

> On 2010-02-12, Richard Heathfield <rjh@see.sig.invalid> wrote:
>> I know you'll find this hard to believe, but
>> there's more to life than comp.lang.c.
>
> Eek!
>
> No wonder my boss never seems to accept "argued with Edward Nilges" as
> a week's work. :P
>
> Actually, in a fit of irony, we ended up needing the revised string replace
> function I posted here the other day, because new data revealed that our
> original spec wasn't flexible enough. Needless to say, it worked fine
> on the first try. :P

You see! Now you've got nothing to do. Had you been properly
educated (spent the last 30 years taking CS classes for example) you'd
still be arguing about whether to use the standard library and would
still have plenty of work for the next three months.
--
Online waterways route planner | http://canalplan.eu
Plan trips, see photos, check facilities | http://canalplan.org.uk

==============================================================================
TOPIC: Efficency and the standard library
http://groups.google.com/group/comp.lang.c/t/ad9fea19f2f7dd61?hl=en
==============================================================================

== 1 of 1 ==
Date: Thurs, Feb 18 2010 12:15 am
From: Keith Thompson

Richard Heathfield <rjh@see.sig.invalid> writes:
> spinoza1111 wrote:
>> On Feb 18, 12:48 am, Tim Streater <timstrea...@waitrose.com> wrote:
>
> <prior nonsense snipped>
>
>>> There are certainly programmers who are unable to communicate
>>> meaningfully. I'm not one of those.
>>
>> You've given no evidence here.
>
> It is ironic that you, who almost never support your own claims with
> hard facts, should ask for someone else to provide evidence. It is the
> height of hypocrisy.
[snip]
> <subsequent nonsense snipped>

Yes, spinoza1111 is wrong again, and on a topic having nothing
to do either with C or with the supposed subject of this thread.
Is pointing it out really a good use of time and bandwidth?

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

==============================================================================

You received this message because you are subscribed to the Google Groups "comp.lang.c"
group.

To post to this group, visit http://groups.google.com/group/comp.lang.c?hl=en

To unsubscribe from this group, send email to comp.lang.c+unsubscribe@googlegroups.com

To change the way you get mail from this group, visit:
http://groups.google.com/group/comp.lang.c/subscribe?hl=en

To report abuse, send email explaining the problem to abuse@googlegroups.com

==============================================================================
Google Groups: http://groups.google.com/?hl=en