Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

[REBOL] Re: More on expressions

From: joel:neely:fedex at: 8-Feb-2003 11:26

Hi, Sunanda, Interesting observations, all! You've certainly taken the discussion to another "level" (pun intended). Let me suggest that some of your points take us out of the arena of algorithm design into the arenae of system design and language design. [SunandaDH--aol--com] wrote:
> I'm glad to see that one of my "solutions" was so slow that it > didn't make the cut into the benchmarks... >
I'll rectify that omission shortly! (The original version using RANDOM/SECURE took about 13x as long as "sort network"; when I changed it to use plain RANDOM a quick check looked to be about 8x times as long as "sort network".) I was originally being paranoid about how long I would need to run the entire competition, feeling pressure to get results out. I'm tidying up the benchmark harness for publication, and will have that published to the community soon.
> Other dimensions for scoring how "good" the various solutions are > include: > > Range of data types handled: > ** Some existing solutions only work with integers > ** Some only work with numbers > ** Some won't work with pairs (try a: 6x2 b: 2x6 c: 4x4) > ** Some work with most Rebol data type -- though they fail on things > like a: true b: false c: false > ** There's just one (I think) that'll work with any Rebol data type. >
Of course, some of that is my responsibility; my original post said: Three variables, A, B, and C which we'll assume have been set to numeric values. Equally obvious is the point that there's a different mind-set (and experience level) involved in addressing each of the following issues: - designing an algorithm/function/program to accomplish a narrowly- defined goal; - designing a solution for a class of tasks/goals you think are likely in a given environment, given a specific (narrow) instance of that class; or - designing a generalized tool for reuse in the widest possible set of environments/cases. The further we go in that direction, the more likely we are: - to tradeoff optimal performance for generality (which you address later on); and - to need support from the language (as in the next point).
> Flexibility in ordering > ** All solutions so far use Rebol's built-in logic for ordering. > But if we're trying to find the middle Czech surname from a > list, how quickly can the solution be adapted to Czech > collating sequence? >
I see that as raising at least three questions: - How much work would it be to *replace* a "smaller" solution with one which is extended to cover a larger domain? - With that extension done, how much is the performance over the original domain affected? - Alternately, could the underlying design of a "smaller" solution be (re)used in the development of *another* solution tailored for a different domain? In all three cases, of course, the generality of the design (not necessarily the initial implementation!) is crucial. Below is my attempt to identify the key design dependencies of each of the tested solutions. 1) Requires arithmetic and ordering of two elements: sums less twice max +/- max sum less extremes +/- min/max 2) Requires abiltity to test two elements for "in order" or "out of order": any all (explicit) >=/< any all (w/ default) >=/< any xor with default >=/< second bogosort < 3) Requires ability to order two elements: sort network min/max max of mins min/max sort network (parens) min/max unwrapped sort with sets min/max 4) Requires ability to find extrema of any number of elements: pick max remove max maximum-of int form remove extremes minimum-of/maximum-of 5) Requires both 2-element ordering and n-element extrema: max of remove max maximum-of/max 6) Requires ability to sort any number of values: second sort sort Clearly group (1) can only be used with numbers (or some abstract type with an ordering relation and an order-preserving invertible composition operator ;-) so I won't try to generalize that group. Groups (2) thru (5) could be generalized in two ways: - Modify the design to accept data-appropriate comparison/ordering operators to be specified by the caller (passed as parameters or set as attributes of an object containing a median method based on those attributes. - Reuse the design as a pattern, replacing the generic operators with functions over the alternate data type to be supported in a different version. This takes us to a language-design issue, in that we might expect the key functions of (2) thru (5) to be related nicely, as in min: func [a b] [either a <= b [a] [b]] minimum-of: func [s /local a] [ a: first s foreach b s [a: min a b] a ] sort: func [s /abstract... rearrange elements of s until a <= b is true for all pairs of consecutive elements ] Alas, in REBOL this is not the case! SORT and the extrema functions (MINIMUM-OF and MAXIMUM-OF) will order values that can't be compared with the standard ordering/comparison operators. Of course we could turn things around, and use SORT as the basis of the known universe, as follows: sort: ...native... minimum-value-of: func [s] [first sort copy s] min: func [a b] [minimum-value-of reduce [a b]] <=: func [a b] [a = min a b] (except we'd need a new name for <= because of REBOL lexical syntax rules!) If REBOL were truly object-oriented, we'd just call the appropriate methods on the values being compared/ordered/sorted, and let dynamic dispatch and inheritance "sort it out" (pun intended ;-)!
> Flexibility in processing the data > * Find the median, but ignore missing values when doing so -- how > many of our solutions return 10 from this data? a: 10 b: none > c: 10 or from this: a: none b: none c: 10 >
Now we're into a different set of issues: 1) What is the "contract" between caller and callee? 2) Who is responsible for enforcing that contract? 3) What should the callee do if the contract is broken? 4) What should the callee do if asked to perform the impossible? Some writers argue that error-checking and policy-enforcement should be done at the highest/outermost levels of a system, and the remainder of the system should be build on the assumption that this has been done. Their argument is based on the notion that performance is diminished if validity is constantly being vetted. The other side of the argument is that pushing the error-checking (at least -- policy-enforcement tends to beg the question of "whose policies?" and cause application-concept leakage) as far *down* as possible makes the lower-level routines more re-usable. Of course in the physical world, we confront this all the time! My house has a breaker panel to prevent circuit overload, and I can use a plain extension cord with any outlet. The error-checking duties are pushed "upstream". I could buy extension cords with a fuse or circuit breaker in each strand, I suppose... ;-) On the other hand, earlier this morning the circuit-breaker in the power conditioner that feeds this computer and monitor popped, which took down the computer but none of the other outlets in the room. Part of this gets to the heart of the distinction between dynamically- typed languages (REBOL, Python, Scheme, ...) versus statically-typed languages (PASCAL, JAVA, ...) and how much work we can do early on to avoid work later. (Look at the definition of FOR in REBOL to see an interesting example of this issue.)
> Number of items to compare > ** Very few scale easily beyond three items How quickly can the > various solutions be adapted to 13 items? or N where N isn't > known until run time? >
And how many special cases (e.g. 13) will one tolerate before just implementing the generalized case and trading programmer/coding cycles for CPU cycles?
> The fastest solution usually isn't the one that runs longest (if you > see what I mean) before being replace by something more generalised. >
The truth of that statement IMHO is highly dependent on the application domain. Real-time embedded systems are much more likely to require the fastest solution (even if that means having multiple type-specific routines) versus throw-away exploratory programs. Of course, that means that we typically use different tools for those domains! -jn-