HDTenEightyP/NetNews huggingface dataset:
From: ray@rann.sbi.com (Raymond Blum)
Newsgroups: comp.programming
Subject: Re: Dr Dobb's Journal - available online?
Date: 12 Jan 93 16:45:12 GMT
Reply-To: ray@rann.sbi.com
Organization: Salomon Inc.

the DDJFORUM on Compuserve, has files and source referenced in mag, they also (used to) have a BBS that carried much of the same stuff. Last time I looked, there was info. in the magazine giving details.
---Raymond
---
------------------------------------------------------------------------
-----                                                              -----
-----                                                              -----
----                  \\\\\\\                                       ----
----                 \\\    \\   People ask me                      ----
----                  \\ o o       "Why are you smiling?"           ----
----                             I'm just happy!                    ----
----                     \_/                                        ----
----                                                                ----
----   Raymond Blum                                                 ----
----   ray@rann.sbi.com                                             ----
----   (201) 896-7594                                               ----

  Of course these are MY opinions! Whattya think, my EMPLOYER 
  could've thought this stuff up?
Newsgroups: comp.programming
From: karr@cs.cornell.edu (David Karr)
Subject: Re: Locating duplicates
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Date: Thu, 7 Jan 1993 02:11:46 GMT

In article <1993Jan5.224141.21639@organpipe.uug.arizona.edu> dave@cs.arizona.edu (Dave Schaumann) writes:
>Hmmm.  An even more robust algorithm would scan through the array to find
>the difference between the largest and smallest elements, and then malloc()
>an appropriate sized array.  Of course, if malloc() returns NULL, you'll
>have to fall back to some kind of in-place sorting scheme.

How about this:

Assume in the following that all integers are 32 bits.
Given array v of integers in which we have to detect duplicates,
say v contains n entries.
Allocate an array p of n integers and an array h of 512 integers, both
initialized to all zeros.

Consider the 32-bit integers to be partitioned into 512=2^9 "segments"
of 2^23 contiguous numbers sharing the same leading 9 bits.  Each
entry in h is the index of the head of a list of entries in v (offset
by 1 if this is in C, so that index 0 can indicate the empty list).
The array p gives the "next" index for each item in a list (again
offset by 1 if necessary).

The first pass over the data will put all the values from v that belong
to the i-th segment into the list h[i], for each i.  This is done by
scanning linearly once through the array; for each entry in v, examine
the upper 9 bits and insert that value at the head of the corresponding
list in h.  This takes a small constant time for each of n entries.

Now run through the 512 entries of h.  For each entry h[i], allocate a
one-megabyte bit vector f (2^20 bytes=2^23 bits) initialized to all
zeros.  Then scan the list pointed to by h[i], reading the lower 23
bits of each value and setting the corresponding bit in f, and marking
this entry in v as a duplicate if the flag was already set (we can put
a distinguished value in the corresponding entry of p, for example,
because we won't need to scan the list again).  Deallocate f when the
end of the list is reached.  This phase takes a constant time to
process each of the n entries in v, plus the time required to
examine the 512 pointers in h.

And that's the end of the algorithm.  It takes K*n + K' time, where K
is the time to perform the small number of operations required for
each entry of v in the two phases, and K' represents a small overhead
for each of the 512 head pointers.  That is, the algorithm is O(n),
with a constant that I think compares reasonably well with algorithms
that pre-scan v for min and max only and assume you can allocate an
array large enough to index the entire range.

A shortcoming of course is that the running-time analysis is valid
only if you can repeatedly allocate large amounts of zeroed-out memory
in a small (essentially constant) time.  But pessimistic assumptions
about memory initialization are bad for other index-array algorithms
as well.

Of course any of the constants I used (e.g. 2^20, 512) can be
adjusted to suit practical considerations, perhaps even at runtime.

-- David Karr (karr@cs.cornell.edu)
From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: comp.programming
Subject: Arbitrary precision with large bases
Date: 5 Jan 1993 19:27:02 GMT
Organization: Computing Services Division, University of Wisconsin - Milwaukee
NNTP-Posting-Host: 129.89.7.4

   A while back, I came up with an efficient arbitrary precision BCD arithmetic
package that uses base 1,000,000,000 (which happens to be close to 2^30).

   I'm looking for other packages for comparison that use large bases, either
BCD or binary.  The non-trivial aspects to such as package are the following:

   (1) An algorithm to carry out A, B -> AB div BASE, AB mod BASE
   (2) A division algorithm that minimizes the amount of backtracking.
       The grade school algorithm is a backtracking algorithm, and only
       in base 2 is backtracking avoided.
   (3) A square root algorithm, like the one taught in school, that likewise
       minimizes backtracking.
Newsgroups: comp.programming
From: tallis@starbase.mitre.org (Hans Tallis)
Subject: Help me find Don & Melanie
Organization: The MITRE Corporation
Date: Wed, 13 Jan 1993 00:17:47 GMT



This is a description of a problem for which I need an efficient solution
algorithm.  Any ideas or hints, please mail to tallis@mitre.org.  Thanks,
--Hans


				Don and Melanie

Don and Melanie, desiring a quiet wedding, need to get from their hotel to the
chapel without being detected.  The paparazzi, sharing one car and housed away
from the hotel, know that Don and Melanie will take one of N routes from the
hotel to the chapel.  They must plan a route that will quickly intercept each
of the N routes before Don and Melanie have any chance of getting to the chapel
successfully.  Since the paparazzi know how fast Don and Mel can drive, they
can predict where the quarry would be at any time along a given route.  How do
they plan their intercept strategy?
Newsgroups: comp.programming
From: karr@cs.cornell.edu (David Karr)
Subject: Re: Locating duplicates
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Date: Thu, 7 Jan 1993 17:38:22 GMT

In article <1993Jan7.021146.2290@cs.cornell.edu> karr@cs.cornell.edu (David Karr) writes:
>A shortcoming of course is that the running-time analysis is valid
>only if you can repeatedly allocate large amounts of zeroed-out memory
>in a small (essentially constant) time.  But pessimistic assumptions
>about memory initialization are bad for other index-array algorithms
>as well.

Mark Tillotson objected that my assumption about O(1) memory
allocation was a bad one.  In fact I ran some benchmarks on a Sun 4
and found that the running time of calloc() was proportional to k
where K is the number of bytes allocated and initialized to 0.  (I
also noticed that allocating new space took 4 times as long as
reallocating freed space, perhaps virtual memory management is even
more expensive than traversing the physical memory?)

In fact the time required for all the allocations in my algorithm was
about 40 seconds on the Sun 4.  What a shame!  It seems that support
for large blocks of data initialized to a constant byte value would be
quite practical in hardware and a useful feature to support.

Mark Tillotson also suggests a second pass over each sublist of the
input in order to clear all the bit flags that were set for that list.
This makes the algorithm once again proportional to N (though with
almost twice the constant factor) with a much smaller constant term,
i.e. whatever it takes to allocate one copy of the flag array.  In
that case I believe it makes sense to use a much smaller flag array,
say 2^16, with a correspondingly larger array for head-of list, in
this case 2^13 entries.  Then the constant term will be something on
the order of 2^16 instructions (note you should be able to zero out
the bit vector four bytes at a time).  Still I suspect for fairly
small problem sizes a fast O(n log n) sort will still win, and it's
quite possible that Mark Tillotson's hashing scheme has better
average-case performance on any problem size.

-- David Karr (karr@cs.cornell.edu)
From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: comp.programming
Subject: Memory management models
Date: 4 Jan 1993 20:32:58 GMT
Organization: Computing Services Division, University of Wisconsin - Milwaukee
NNTP-Posting-Host: 129.89.7.4

   I'm looking for efficient models for source-level memory management that
resolve fragmentation and allows contiguous segments of arbitrary size to be
allocated.  They should be compared to the model which I presently use:

        * Free lists maintained for blocks of size 2^N for each N < 32,

        * Allocated segment are fit into the smallest available block of
          size 2^N, using the Nth free-list if it's non-empty.

Default malloc is insufficient because it doesn't normally protect against
external fragmentation, and source-level paging is insufficient because it
doesn't resolve the need for contiguity.

   The model above guarantees that fragmentation will always lie under 50%,
that allocation will usually be a constant-time operation and that deallocation
will always be constant time.
From: jos@and.nl (Jos Horsmeier)
Newsgroups: comp.programming
Subject: Re: Help With String Comparisons
Date: 12 Jan 93 10:09:46 GMT
Organization: AND Software BV Rotterdam

In article <1993Jan11.224515.24729@dragon.acadiau.ca> 890584r@dragon.acadiau.ca (Barrie Rody) writes:

|    I am writing a database and I need some help in comparing strings.
|What I need is an algorithm to compare 2 strings {PChar, array[]of Char}.
|I need this algorithm to be able to identify similar strings.
|ie. a misspelled word would be found in a list.
|    I am writing this in Turbo Pascal for Windows.  Any pseudocode,
|Pascal, C, C++ or text answers would be greatly appreciated.

Two approached come to mind:

- Soundex matching:

  1) Map the consonants to their respective classes:

  - gutturals: g, h, k, q, r, x
  - dentals  : c, d, s, t, z
  - labials  : b, f, j, l, m, n, p, v, w

  2) Remove identical adjacent phonemes and compare the two resulting strings

- `Gestalt' matching (function P):

  1) Given two strings V and W, find the largest substring X, such that
     V= Vl X Vr and W = Wl X Wr. In case of a tie, take one X at random.
     Let S equal 2*|X| (the length of the largest substring X)

  2) Let L be the value of P applied to Vl and Wl (if both not empty)
     and let R be the value of P applied to Vr and Wr (if both not empty)

  3) The 'match value' is (L+S+R)/(|V|+|W|)

An example may clarify the second method a bit. Consider two strings
`color' and `colour'. The largest substring is `colo'. There are no
prefix substrings and the two suffix substrings are `r' and `or'. 
Applying the same method to those strings yields the value 1 (`r'). 
So, the total `match value' is (2*0+2*4+2*1)/(5+6) = 10/11. 

I hope this helps a bit,

kind regards,

Jos aka jos@and.nl
Newsgroups: comp.programming
From: karr@cs.cornell.edu (David Karr)
Subject: Re: Locating duplicates
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Date: Mon, 4 Jan 1993 17:57:28 GMT

I posted a somewhat stupid reply to the following last night; hopefully I
canceled it before it did too much damage.  I'll try to be wiser this time:

In article <DOUGM.93Jan2014723@titan.cs.rice.edu> dougm@titan.cs.rice.edu (Doug Moore) writes:
>But if these are fixed size integers (like C ints), you can radix sort
>in linear time anyway, which is as fast as you can reasonably expect.

The algorithm that follows is indeed linear time, but look at the
constant factor:  

>  while (mask <= max && mask) /* <= 32 times on my machine */
>[...]
>      for (j = 0; j < n; ++j)
...etc.

The program is doing up to 32 passes over a set of loops (of which I
just showed the first) that always execute 5 lines of code for every
entry in the array.  That's up to 160*n lines of code to be executed,
depending on the range of values in your array.  Is that really 
better than a well-written O(n log n) sorting algorithm?

In fact what you're doing is changing K1*n*log(n) time to K2*n*log(m)
where m is the largest integer in the array.  For K1 ~= K2, this is
good if m << n (lots and lots of duplicates) but bad if m >> n (e.g. a
moderate sized array with widely varying data, few duplicates and lots
of holes in the "range" it covers).

Personally, for the latter case I like the suggestions to use either a
flag array indexing the range of your data or a hashing scheme along
with an array of flags.  You can reduce the amount of extra memory
considerably in either case by using bits of a bit vector for flags
rather than using whole bytes, though this entails a little extra run
time.  Of course you need to consider how long it takes to obtain an
array intialized to all zeros.  (Depends on the machine
implementation, I'd think.)  If you have to loop through the array to
initialize it, I think it might more than wipe out any speed advantage.

When the range of your data is large, e.g. values up to 2^32, the bit
array ends up being half a gigabyte, a bit large for comfort, so you
might make a few passes of the radix sort to partition the array into
"segments" in each of which the first p digits of each number are
constant.  Then walk the array once using the unsorted digits of each
segment to index a flag array.  You only need to keep the array for
the current segment.  I suggest radix sorting from the left rather
than the right; this makes the resulting order bizarre but who cares,
all you need is the segmentation and I suspect the indexing arithmetic
is fastest on the low-order bits.

-- David Karr (karr@cs.cornell.edu)
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Newsgroups: comp.programming
Subject: Re: Locating duplicates
Date: 7 Jan 93 17:01:06 GMT
Organization: Naval Research Laboratory, Washington, DC

karr@cs.cornell.edu (David Karr) writes:
>A shortcoming of course is that the running-time analysis is valid
>only if you can repeatedly allocate large amounts of zeroed-out memory
>in a small (essentially constant) time.

You can actually skip the zeroing out at a cost of a constant factor
at access time.  It's well-known; email me if you're interested.

There's a known linear-time solution for the element uniqueness
problem on the real-ram-with-floor model (none of this bogus 32-bit
integer restriction) that uses a kind of hash table in this way.  It
was in JACM in the seventies, if I recall.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil
Newsgroups: comp.programming
From: hn314sc@unidui.uni-duisburg.de (Schuering)
Newsgroups: comp.programming
Subject: Looking for ELIZA/DOCTOR source
Date: 6 Jan 1993 13:03:12 +0100
Organization: Universitaet Duisburg GH
NNTP-Posting-Host: unidui.uni-duisburg.de
Keywords: eliza

                               Hi !
I am looking for the source of ELIZA and DOCTOR; i got it in C, but i need
the source in PASCAL. Is there perhaps a translater C --> PASCAL ?
I hope you can help me, thanks.

                                                   Thomas Schuering
Newsgroups: comp.programming
From: emcoop@bnr.ca (hume smith)
Subject: Re: Re: Arbitrary precision with large bases
Organization: Bell-Northern Research, Ottawa, Canada
X-Poster: Emacs-NNTP-0.1
Date: Wed, 6 Jan 1993 14:45:19 GMT

In <martin.726311424@bert>, martin@math.rwth-aachen.de (  Martin Schoenert) said:
> a)  the larger the base the fewer digits any given integer has in this
>     base.  Since (for example) the performance of the multiplication
>     is proportional to the product of the number of digits of the
>     operands it is always a win to use larger bases (though the win
>     with base 2^32 over base 10^9 is only about 12.5%).

not quite true - see aho/hopcroft/ullman.  f1*f2 can be done
in O(n log(n)) where n=max(log(f1), log(f2)).  there's a rather large
constant involved though... it may be better to implement the two
and find out empirically when to switch methods.
--
Hume Smith                      Wenn ich des Tages nicht dreimal
hume.smith@acadiau.ca           mein Schaelchen Coffee trinken darf,
emcoop@bnr.ca              //   so werd' ich ju zu meiner Qual
                         \X/    wie ein verdorrtes Ziegenbraetchen.
From: dave@cs.arizona.edu (Dave Schaumann)
Newsgroups: comp.programming
Subject: Re: Locating duplicates
Date: 8 Jan 93 05:10:51 GMT
Reply-To: dave@cs.arizona.edu (Dave Schaumann)
Organization: University of Arizona

In article <MARKT.93Jan7122729@wundt.harlqn.co.uk>, markt@harlqn (Mark Tillotson) writes:
>Use a hash table from integers to the number of occurrences, then you
>do N hash-lookups, and one scan of the hash table looking for
>duplicates, giving an expected time O(N),

But what happens when the number of elements to be scanned is much
larger than the number of buckets you choose?  You get collisions
up the wazoo, and then your algorithm is suddenly O(N*f(N/#buckets)),
where your collision resolution algorithm is O(f(N/#buckets)).

If you choose the number of buckets at run-time based on the number
of elements, you might as well just use the "radix sort" solution
already posted.

-- 
You're traveling through another dimension -- a dimension not only of sight and
sound but of mind. A journey into a wonderous land whose boundaries are that of
imagination.  That's a signpost up ahead: your next stop -- the Twilight Zone!
Newsgroups: comp.programming
From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: comp.programming
Subject: Re: Arbitrary precision with large bases
Date: 8 Jan 1993 01:00:14 GMT
Organization: Computing Services Division, University of Wisconsin - Milwaukee
NNTP-Posting-Host: 129.89.7.4

In article <martin.726311424@bert> martin@math.rwth-aachen.de (  Martin Schoenert) writes:
>Base 2^32 has the following advantages.
>
>a)  the larger the base the fewer digits any given integer has in this
>    base.  Since (for example) the performance of the multiplication
>    is proportional to the product of the number of digits of the
>    operands it is always a win to use larger bases (though the win
>    with base 2^32 over base 10^9 is only about 12.5%).
>
>b)  many modern processors have a 32bit x 32bit -> 64bit instruction.
>    This instruction cannot directly be used from within C, so one needs
>    a little bit of assembler.  However if one does that one gets
>    AB div BASE and AB mod BASE with one instruction.

These are disadvantages too.  If you want extra room for work space in
intermediate calculations (such as adding two digits in base 2^N) in a portable
manner, you should really use 2^31 or 2^30 as the base instead.

The advantages of 2^30 (or 10^9) are that (1) it's (almost) equal to a perfect
power of 2, it (almost) factors evenly into two equal factors (both (almost)
equal to 2^15) which comes in handy for multiplication, and it's a perfect
cube, which comes in handy for division.

>With respect to aspect (2).  Knuth shows that if you normalize the
>divisor such that its leading digit is larger than or equal to BASE/2 and
>compute an appoximation of a digit of the quotient by dividing the
>leading three digits of the remainder by the leading two digits of the
>divisor the approximation is at most too large by 1 *independent* of the
>base.  It is easy to detect if the digit is too large and make the
>appropriate corrections.

Another way to normalize, with a base that is a perfect cube (N^3) is to
(1) normalize the divisor so that its leading digit lies between N and N^2 - 1,
and (2) always arrange so that the dividend's leading digit never exceed N
times the divisor's leading digit (divide by N if need be).

This will likewise guarantee that the approximation never be off by more than
1.

Also, it's easier to underestimate the quotient's digit, rather than
overestimate it.  Then division just consists of shifts and subtracts -- no
corrections and no backtracking.  The basic algorithm becomes:

remainder = dividend; quotient = 0;
while (1) {
   if (divisor > remainder) {
      multiply quotient and remainder by N
   } else {
      digit = leading_digit(remainder) / (leading_digit(divisor) + 1)
      remainder -= digit*divisor; quotient += digit
   }
}
From: rmah@panix.com (Robert Mah)
Newsgroups: comp.programming
Subject: Re: Dr Dobb's Journal - available online?
Date: 6 Jan 93 21:43:13 GMT
Distribution: usa
Organization: PANIX Public Access Unix, NYC

In <C0Ew3G.DAu@cs.columbia.edu> ykim@cs.columbia.edu (Yong Su Kim) writes:

>Where can I get current and back issues of Dr Dobb's Journal?  Is it
>available online on some ftp site?

Yes, it's available at "ftp.mv.com" in the "/pub/ddj" directory.

Cheers,
Rob
-- 
[--------------------------------------------------]
[  Robert S. Mah   |  "Every day an adventure,     ]
[  rmah@panix.com  |   every moment a challenge."  ]
[--------------------------------------------------]
Newsgroups: comp.programming
From: kpv@ulysses.att.com (Phong Vo)
Subject: Re: Locating duplicates
Date: Tue, 5 Jan 1993 15:00:10 GMT
Organization: AT&T Bell Labs

In article <1993Jan2.041658.21596@organpipe.uug.arizona.edu> dave@cs.arizona.edu (Dave Schaumann) writes:
>In article <C07FJo.4vq@ux1.cso.uiuc.edu>, ceblair@ux1 (Charles Blair) writes:
>>   Given a large array of integers.  Is there a way to identify duplicates
>>which is substantially less work than sorting the array?
>
>...lots of good suggestions for the general case...

But most often this kind of question comes up in practice
because you have a large array of integers in a small range.
In that case, using a bit map for the range, you can do it
in linear time and space proportion to the range size.
  
Phong Vo, kpv@ulysses.att.com
AT&T Bell Labs, 600 Mountain Ave, Murray Hill, NJ07974
From: dave@cs.arizona.edu (Dave Schaumann)
Newsgroups: comp.programming
Subject: Re: Locating duplicates
Date: 5 Jan 93 22:41:41 GMT
Reply-To: dave@cs.arizona.edu (Dave Schaumann)
Organization: University of Arizona

In article <1993Jan5.043456.29130@micor.ocunix.on.ca>, goss@micor (Timothy D. Goss) writes:
>You can locate ALL duplicates in a list of integers with a single pass of the
>list which is O(n) in time but it will require an array with 64K elements.  The
>program below should explain...
>
>typedef unsigned char byte;
>
>static byte found[65536];
>int intlist[NUM];		
>
>void main(void) {
>
>   int i; int check;
>
>   /* assume intlist is filled with NUM integers */
>
>   for (i=0; i<NUM; i++) {
>      check = intlist[i];
>      if (found[check] > 0 && found[check] != 0xff) {
>         printf("%d\n", check);
>         found[check] = 0xff; /* don't report same dupe twice */
>      } else {
>         found[check] += 1; /* first time we saw this one */
>      }
>   }
>
>}

This is fine if you know all of your values are between 0 and 65536.
A slightly more robust (but still linear time) algorithm could be written
which would only require that the difference between the maximum and minimum
elements is 65536.

Also, if you use a bit-vector instead of an array of chars for "found", you
get an 8x space improvement at the cost of a small amound of bit twiddling.

Hmmm.  An even more robust algorithm would scan through the array to find
the difference between the largest and smallest elements, and then malloc()
an appropriate sized array.  Of course, if malloc() returns NULL, you'll
have to fall back to some kind of in-place sorting scheme.

-- 
Dave Schaumann			dave@cs.arizona.edu
Newsgroups: comp.programming