Date: 07 Oct 94 11:37:42 EDT
From: Andy Norton <76350.1604@compuserve.com>
To: Patterns list <patterns@cs.uiuc.edu>
Subject: Re: General binary search

Let me try to generalize the binary search pattern posted by Chris Perrott.

Pattern Name:  DON'T WASTE YOUR TIME 

Problem:   

The job takes more resources than you would like.

Solution:  

discard part of the job which is not needed to achieve the solution.

Context:

1.  You have to be able to tell that part of the job is irrelevant, and this
determination must be flawless. 

2.  Not doing the irrelevant part must save resources compared to doing it.

3.  You have to be able to determine #1 more efficiently (in whatever terms
apply) than you would save in #2.
 
Example:  Binary Search
Problem:  Binary search takes IO's and CPU time.
Context:  
  1.  The file is sorted so that you can determine (given the first and last
value of a segment) that the target is not in that segment.
  2.  Random access to the file lets you read individual values, a significant
savings over reading every value.
  3.  Comparing the target to the range (first and last value) is cheap.  

[ be kind, it's my first one ]

Andy Norton
Trilogy Consulting Corporation
Kalamazoo Michigan
76350.1604@compuserve.com  


Date: 07 Oct 94 15:52:38 EDT
From: Ward Cunningham <72147.3056@compuserve.com>
To: Patterns <patterns@cs.uiuc.edu>
Subject: A Home for Binary Search in Pattern Land

"What is "it"? Could be a value in an ordered table ... Could be the end of a
message ... Could be the bug in a LaTeX file." -- Chris Perrott

Chris points out that binary search applies in many circumstances.  "It" could
be a word in the dictionary too.  Binary search does solve problems.  So, is
what we have always known as an algorithm also a pattern?

Ralph suggests it is and that Chris simply failed to use the pattern form.
Hmmm.  Sounds like a challenge.  Here is what I came up with as a pattern
language home for binary search.

Pattern: SEQUENCE
Some things you have can be ordered.  Therefore:  Go ahead and keep them in that
order.  You may be able to offer INDEX as part of your sequence or as a seperate
thing.

Pattern: INDEX
When you look for something in a SEQUENCE you may be able to exploit their
order.  Therefore: Provide an index to the sequence that can be probed based on
the order. When several orders are possible, consider having several indices.
You will need to choose a PROBE STRATEGY that makes good use of your index.

Pattern: PROBE STRATEGY
It often takes many probes to find something in an INDEX.  And, probes can be
costly.  Therefore: Use a strategy, like divide and conquer, that makes the most
of every probe.

These patterns approach the generality of Chris's examples while still nameing
things.  I particulary like that INDEX could be an index register (an innovation
on the IBM-709 scientific computer) or an index file in a database.  But what
about PROBE STRATEGY? I could feel my pattern language getting a little soft as
I pulled it out of INDEX.  Is every algorithm a strategy?  Well, yea, I suppose
it's possible.  But we may not have to actually write a pattern for every one.


Date: 14 Oct 94 15:27:38 EDT
From: Ward Cunningham <72147.3056@compuserve.com>
To: "INTERNET:chris%mailhost@toshiba.tic.oz.au" <chris%mailhost@toshiba.tic.oz.au>
Cc: Patterns <patterns@cs.uiuc.edu>
Subject: Re: A Home for Binary Search in Pattern Land

"Yes, I was referring to a probe strategy and to a sequence. However, I don't
think the
sequence has to be ordered, and I don't see the relevance of INDEX." -- Chris
Perrott

Chris -- A sequence need not be sorted for binary search to work but it does
need to be ordered.  Otherwise we can't talk about its first or second half.
Your text formatting example (search for a bug by commenting out half of the
statements) is an ordered sequence.  My patterns apply as follows:

        SEQUENCE:  Statements stored on lines of a text file.

        INDEX: The text editor that allows you to address lines 
        of a file and the comment semantic that allows you to 
        mark the lines you have addressed. 

        PROBE STRATEGY: Mark recursivly smaller sections 
        of text as comments.

A text editor command for probing the first half of the sequence might look
something like, "1,$/2s\^\%\", which reads as "from the first line to half way
through the file substitute the comment character (%) for the null string at the
beginning of each line."  This is how the INDEX allows the PROBE STRATEGY to
address potential bug locations in the SEQUENCE.

Is there such a thing as an unordered sequence?  Yes. Consider itteration over a
Smalltalk Set.  The following code parallels the above text editor command.

        aSet with: (1 to: aSet size) do:
            [:each :index | 
            index < (aSet size / 2) 
                ifTrue: [each markAsComment]]

The with:do: applies an index all right, but binary search won't work reliably
because 
subsequent probes may sequence the Set in a different order.  

I hope this helps.  -- Ward Cunningham