Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147130 > unrolled thread
| Started by | DFS <nospam@dfs.com> |
|---|---|
| First post | 2019-10-20 18:12 -0400 |
| Last post | 2019-10-29 15:15 +0100 |
| Articles | 14 on this page of 114 — 19 participants |
Back to article view | Back to comp.lang.c
Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-20 18:12 -0400
Re: Challenge for Feeb: dealing with large numbers in C Barry Schwarz <schwarzb@delq.com> - 2019-10-20 18:33 -0700
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-20 23:16 -0400
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-21 13:15 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 14:40 -0400
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-22 00:54 +0100
Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-22 10:05 +0200
Re: Challenge for Feeb: dealing with large numbers in C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-23 07:18 -0700
Re: Challenge for Feeb: dealing with large numbers in C Manfred <noname@invalid.add> - 2019-10-26 20:01 +0200
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-26 17:50 -0400
Re: Challenge for Feeb: dealing with large numbers in C Manfred <noname@add.invalid> - 2019-10-28 16:33 +0100
Re: Challenge for Feeb: dealing with large numbers in C Barry Schwarz <schwarzb@delq.com> - 2019-10-21 07:56 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 16:46 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 14:57 -0400
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 20:53 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 16:05 -0400
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 21:12 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 20:08 -0400
Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-22 10:27 +0200
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-22 19:45 +0100
Re: Challenge for Feeb: dealing with large numbers in C Eli the Bearded <*@eli.users.panix.com> - 2019-10-22 19:58 +0000
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-23 11:46 -0400
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-23 20:02 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 01:38 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-23 22:10 -0400
Re: Challenge for Feeb: dealing with large numbers in C Ike Naar <ike@sdf.lonestar.org> - 2019-10-24 07:24 +0000
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 09:29 -0400
Re: Challenge for Feeb: dealing with large numbers in C James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-10-24 08:45 -0700
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 11:56 -0400
Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-24 09:13 -0700
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 18:28 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 10:36 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 09:26 -0400
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 18:29 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 14:38 -0400
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 21:30 +0100
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-24 11:30 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 20:36 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-24 21:34 +0100
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-24 22:42 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-24 18:59 -0400
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-25 02:48 +0100
Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-26 04:33 -0700
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 17:21 +0100
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-26 18:47 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 23:24 +0100
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-27 00:29 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-27 01:58 +0100
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-27 12:02 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 02:08 +0000
Re: Challenge for Feeb: dealing with large numbers in C Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-10-26 14:29 -0600
Re: Challenge for Feeb: dealing with large numbers in C Keith Thompson <kst-u@mib.org> - 2019-10-26 13:36 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-26 22:06 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 23:04 +0100
Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-27 12:49 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-27 18:20 +0000
Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-27 22:45 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 00:08 +0000
Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-27 14:57 -0700
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 01:08 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 01:44 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 02:31 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 10:42 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 12:45 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 17:39 +0000
Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-28 20:31 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 20:22 +0000
Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-28 22:07 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 22:22 +0000
Re: Challenge for Feeb: dealing with large numbers in C David Brown <david.brown@hesbynett.no> - 2019-10-29 10:17 +0100
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 11:21 +0000
Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-28 11:05 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 19:26 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 21:08 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-28 21:57 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-28 23:59 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 00:53 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 01:09 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 01:32 +0000
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-28 22:44 -0400
Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-29 03:05 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 11:12 +0000
Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-29 04:19 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 11:47 +0000
Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-29 05:03 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 13:16 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 17:13 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 17:35 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ike Naar <ike@sdf.lonestar.org> - 2019-10-30 07:19 +0000
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 16:19 +0000
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 16:50 +0000
Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-29 10:03 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-29 17:13 +0000
Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-29 10:23 -0700
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-29 22:20 +0000
Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-30 03:04 -0700
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-30 15:39 +0000
Re: Challenge for Feeb: dealing with large numbers in C Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-30 09:02 -0700
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-30 19:35 +0000
Re: Challenge for Feeb: dealing with large numbers in C already5chosen@yahoo.com - 2019-10-30 14:11 -0700
Re: Challenge for Feeb: dealing with large numbers in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-31 03:34 +0000
Re: Challenge for Feeb: dealing with large numbers in C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-04 17:02 -0800
Re: Challenge for Feeb: dealing with large numbers in C Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2019-10-26 12:30 -0400
Re: Challenge for Feeb: dealing with large numbers in C Robert Wessel <robertwessel2@yahoo.com> - 2019-10-26 12:03 -0500
Re: Challenge for Feeb: dealing with large numbers in C Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-10-26 14:25 -0600
Re: Challenge for Feeb: dealing with large numbers in C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-24 18:06 -0700
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 22:44 +0100
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-21 19:00 -0400
Re: Challenge for Feeb: dealing with large numbers in C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2019-10-21 10:20 +0800
Re: Challenge for Feeb: dealing with large numbers in C Bart <bc@freeuk.com> - 2019-10-21 12:44 +0100
Re: Challenge for Feeb: dealing with large numbers in C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2019-10-21 10:24 +0800
Re: Challenge for Feeb: dealing with large numbers in C DFS <nospam@dfs.com> - 2019-10-20 23:05 -0400
Re: Challenge for Feeb: dealing with large numbers in C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2019-10-21 11:32 +0800
Re: Challenge for Feeb: dealing with large numbers in C Autist <autist69@gmail.com> - 2019-10-29 15:15 +0100
Page 6 of 6 — ← Prev page 1 2 3 4 5 [6]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2019-10-31 03:34 +0000 |
| Message-ID | <87lft1mvv1.fsf@bsb.me.uk> |
| In reply to | #147392 |
already5chosen@yahoo.com writes:
<cut>
> Just to be sure that we are talking about the same thing.
> That's the code for what you call "native comparison":
>
> void bubblesort_Ben(int x[], int nElem)
> {
> while (nElem > 1) {
> int swapped = 0;
> for (int i = 1; i < nElem; ++i) {
> if (x[i-1] > x[i]) {
> int temp = x[i-1];
> x[i-1] = x[i];
> x[i] = temp;
> swapped = 1;
> }
> }
> if (!swapped)
> break;
> --nElem;
> }
> }
The code has instrumentation to count swaps, accesses and compares so is
looks like this:
void bsort2(int n, T A[])
{
bool swapped;
do {
swapped = false;
for (int i = 1; i < n; i++)
if (out_of_order(get(A, i-1), get(A, i))) {
swap(A, i-1, i);
swapped = true;
}
n -= 1;
} while (swapped);
}
out_of_order, get and swap are inline functions.
> void bubblesort_Don(int x[], int nElem)
> {
> while (nElem > 1) {
> int next_nElem = 0;
> for (int i = 1; i < nElem; ++i) {
> if (x[i-1] > x[i]) {
> int temp = x[i-1];
> x[i-1] = x[i];
> x[i] = temp;
> next_nElem = i;
> }
> }
> nElem = next_nElem;
> }
> }
That is slightly neater than my version. I'd added another variable to
avoid using n, and I was not stopping at 1:
void bsortk(int n, T A[])
{
int max_swap = n;
do {
int bound = max_swap;
max_swap = 0;
for (int i = 1; i < bound; i++)
if (out_of_order(get(A, i-1), get(A, i))) {
swap(A, i-1, i);
max_swap = i;
}
} while (max_swap);
}
If I plug-in your exact code (so there's no counting of swaps and so on)
then Kunth's version is always faster (except for one run out of about
15 which was probably down to noise in the measuring).
<cut>
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2019-11-04 17:02 -0800 |
| Message-ID | <86d0e7f84u.fsf@linuxsc.com> |
| In reply to | #147300 |
Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>
>> On Sunday, 27 October 2019 18:20:20 UTC, Ben Bacarisse wrote:
>>
>>> Eh? A learner see how insertion sort can be usefully replaced with
>>> merge sort, heap sort, shell sort, quick sort, etc. Is bubble sort's
>>> advantage that it is bad enough to replace with another quadratic
>>> algorithm? That's an odd reason to teach it.
>>
>> Usually bubble sort will be the first algorithm taught (other than
>> things like the pencil and paper method for long multiplication,
>> which aren't understood at the time to be algorithms).
>
> Most such courses include data structures, so many algorithms may well
> have been covered by the time in-place array sorting is discussed.
> Anyway, the question is why bother with bubble sort when the time comes?
>
>> Next lesson is other sort methods the students can devise themselves,
>> which will usually be O(N^2) algorithms, and a discussion of the advantages
>> and disadvantages. So you are teaching that some algorithms are better
>> than others in different circumstances.
>
> All good provided (a) bubble sort isn't taught unless it comes up as a
> student-devised algorithm, and (b) the students understand that there
> are no situations in which bubble sort would be the best choice. In
> practice the problem is that, after taking some courses, the students
> /can't/ choose because they can't remember any other algorithm than the
> not-really-bubble-sort that's being discussed here.
>
> A key outcome should be that the students understand that insertion sort
> is the best choice when a simple quadratic algorithm will do. They
> should be able to come up with this:
>
> for (int i = 1; i < n; i++)
> for (int j = i; j > 0 && A[j-1] > A[j]; j--)
> swap(&A[j-1], &A[j]);
>
> as easily as the dreaded quasi bubble sort. It's not hard -- all the
> bounds are logical.
>
>> Third lesson is quicksort, and the concept of big O notation for
>> algorithms.
>
> I would have already covered big O. Sorting algorithms have actual,
> average and worst-case complexities so its better, in my opinion, to
> have big O already reasonably well understood by having used it for
> simpler algorithms.
Just a few personal reactions or observations.
For many of the comments made about bubble sort versus insertion
sort (or other sorting methods), whether one agrees or not depends
on what qualifies as "bubble sort" and how one understands the
different algorithms. For me the simple nested loop
for( int m = n; m > 1; m-- ){
for( int i = 1; i < m; i++ ){
if( a[i-1] > a[i] ) swap( &a[i-1], &a[i] );
}
}
qualifies as a bubble sort (probably because this was the first
way I learned it, although I don't remember if it was), with any
sort of early exit as just an embellishment or optimization. I
find bubble sort easier to understand than, eg, insertion sort
not because the code is simpler but because it is conceptually
simpler. Obviously that impression is a subjective one, but in
essence that is what I'm trying to point out - which is simpler
or more comprehensible depends on how one thinks of the various
algorithms.
Whether one considers teaching bubble sort a waste of time depends
on what one thinks we are hoping to accomplish in teaching a
course on Algorithms. In my view that is a lot more than just
being able to program the various algorithms. Just learning how
to code up a particular algorithm is usually better done by
consulting a reference such as Numerical Recipes. Bubble sort has
little to offer as a practical sorting algorithm. But learning
about bubble sort, and how it relates to other sorting methods,
carries a fair amount (as I see it, in case that needs repeating)
of educational value beyond just learning how to code it.
I don't know how common it is for students coming out of a course
on Algorithms to reach reflexively for bubble sort before other,
faster (even if still quadratic) sorting algorithms. If and when
that happens clearly it indicates some sort of problem with how
the course was taught. That doesn't mean bubble sort should just
be left out necessarily -- it depends on what the alternatives are
and what educational value we think those other possibilities may
provide.
[toc] | [prev] | [next] | [standalone]
| From | Lew Pitcher <lew.pitcher@digitalfreehold.ca> |
|---|---|
| Date | 2019-10-26 12:30 -0400 |
| Message-ID | <qp1sc3$ht$1@dont-email.me> |
| In reply to | #147219 |
DFS wrote: [snip] > Some people really hate it: "some researchers such as Owen Astrachan > have gone to great lengths to disparage bubble sort and its continued > popularity in computer science education, recommending that it no longer > even be taught." IMHO, while the bubble sort may be close to the worst sorting method to teach /as a sorting method/, it has it's benefits to be taught, /as an exercise/, on how to write useful loops in a target language. [snip] -- Lew Pitcher "In Skills, We Trust"
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2019-10-26 12:03 -0500 |
| Message-ID | <q1v8repa310dpmi7c8qd6h3aumgn2q1hgr@4ax.com> |
| In reply to | #147246 |
On Sat, 26 Oct 2019 12:30:58 -0400, Lew Pitcher <lew.pitcher@digitalfreehold.ca> wrote: >DFS wrote: > >[snip] >> Some people really hate it: "some researchers such as Owen Astrachan >> have gone to great lengths to disparage bubble sort and its continued >> popularity in computer science education, recommending that it no longer >> even be taught." > >IMHO, while the bubble sort may be close to the worst sorting method to >teach /as a sorting method/, it has it's benefits to be taught, /as an >exercise/, on how to write useful loops in a target language. Why wouldn't insertion sort fulfill that need?
[toc] | [prev] | [next] | [standalone]
| From | Joe Pfeiffer <pfeiffer@cs.nmsu.edu> |
|---|---|
| Date | 2019-10-26 14:25 -0600 |
| Message-ID | <1bsgnf9rvk.fsf@pfeifferfamily.net> |
| In reply to | #147247 |
Robert Wessel <robertwessel2@yahoo.com> writes: > On Sat, 26 Oct 2019 12:30:58 -0400, Lew Pitcher > <lew.pitcher@digitalfreehold.ca> wrote: > >>DFS wrote: >> >>[snip] >>> Some people really hate it: "some researchers such as Owen Astrachan >>> have gone to great lengths to disparage bubble sort and its continued >>> popularity in computer science education, recommending that it no longer >>> even be taught." >> >>IMHO, while the bubble sort may be close to the worst sorting method to >>teach /as a sorting method/, it has it's benefits to be taught, /as an >>exercise/, on how to write useful loops in a target language. > > > Why wouldn't insertion sort fulfill that need? The three common O(n**2) sorting algorithms (bubble, insertion, and selection) are so similar that any of the three would fulfill the role equally well. I haven't seen the full quote that is being excerpted above, but I would assume it's aimed at all three of them as well.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2019-10-24 18:06 -0700 |
| Message-ID | <86sgnhfxbj.fsf@linuxsc.com> |
| In reply to | #147210 |
Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> [..determining anagrams via letter counts comparison..]
I have a variation on the comparing-letter-counts approach
that some people may find interesting.
Some preliminaries: one, I assume the word list has been
pre-binned by length, so only words of the same length
will be tested; and two, there is an array for converting
character codes to indices in the counts arrays (with any
non-letters having an out-of-range index value).
Here is the code (disclaimer: not tested):
#define ALPHABET_SIZE 26
static unsigned char *const letter_map; /* character value => index */
int
is_anagram_of( const char *s, unsigned char counts[ static ALPHABET_SIZE ] ){
unsigned char h[ ALPHABET_SIZE ] = { 0 };
for( int c = *s; c; c = *++s ){
unsigned k = letter_map[c];
if( k >= ALPHABET_SIZE || ++h[k] > counts[k] ) return 0;
}
return 1;
}
The checking goes through the test string, s, incrementing counts
as it goes. If any character is encountered (a) that is not a
letter (so its index is out of range), or (b) whose count exceeds
that of the corresponding letter of the word being tested against,
the test string cannot be an anagram of the pre-counted word, so
zero is returned immediately.
If the loop completes, we know no counts have been exceeded, and
we know the lengths match, so the only remaining possibility is
that all the counts match. Voila! That's an anagram.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-10-21 22:44 +0100 |
| Message-ID | <VEprF.1545041$qU.483839@fx20.am4> |
| In reply to | #147151 |
On 21/10/2019 16:46, Bart wrote:
> On 21/10/2019 04:16, DFS wrote:
> The correct values are:
>
> superincomprehensibleness :
> 2116343913154240043567072445807789615
> antidisestablishmentarianism :
> 10816738360843396874796178492197077328
> microspectrophotometrically :
> 5063607945377863816547272523387703764750
> dichlorodiphenyltrichloroetha :
> 29387878280664889590552354940915144150850
This looks truncated (but is as shown in the OP). The hash value is
correct for the word as shown, but the proper word (I assume it is the
full name of DDT) should be:
dichlorodiphenyltrichloroethane:
13900466426754492776331263887052863183352050
Not that it matters, but I like to get things right...
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-10-21 19:00 -0400 |
| Message-ID | <4NqrF.53943$jO1.7497@fx32.iad> |
| In reply to | #147157 |
On 10/21/2019 5:44 PM, Bart wrote: > On 21/10/2019 16:46, Bart wrote: >> On 21/10/2019 04:16, DFS wrote: > >> The correct values are: >> >> superincomprehensibleness : >> 2116343913154240043567072445807789615 >> antidisestablishmentarianism : >> 10816738360843396874796178492197077328 >> microspectrophotometrically : >> 5063607945377863816547272523387703764750 > >> dichlorodiphenyltrichloroetha : >> 29387878280664889590552354940915144150850 > > This looks truncated (but is as shown in the OP). The hash value is > correct for the word as shown, but the proper word (I assume it is the > full name of DDT) should be: > > dichlorodiphenyltrichloroethane: > 13900466426754492776331263887052863183352050 > > Not that it matters, but I like to get things right... Good catch. My code maxes the input at 30: char wordin[30]; I figured there might be some longer. I'll do a quick check and expand it to the largest word length.
[toc] | [prev] | [next] | [standalone]
| From | Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> |
|---|---|
| Date | 2019-10-21 10:20 +0800 |
| Message-ID | <CB8rF.903786$893.288102@fx02.am4> |
| In reply to | #147130 |
On 21/10/2019 6:12 am, DFS wrote: > What do you know about dealing with large numbers in C. > > I don't want to deal with 'big int' libraries or anything like that. That is exactly how you'd typically deal with large numbers in C. Last time I checked, Wikipedia had a list of several. For a portable solution you can try LibTomMath. https://www.libtom.net/LibTomMath/ Though I haven't used it myself. -- Johann | email: invalid -> com | www.myrkraverk.com/blog/ I'm not from the Internet, I just work there. | twitter: @myrkraverk
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-10-21 12:44 +0100 |
| Message-ID | <DSgrF.842014$VE7.326385@fx11.am4> |
| In reply to | #147140 |
On 21/10/2019 03:20, Johann 'Myrkraverk' Oskarsson wrote: > On 21/10/2019 6:12 am, DFS wrote: >> What do you know about dealing with large numbers in C. >> >> I don't want to deal with 'big int' libraries or anything like that. > > That is exactly how you'd typically deal with large numbers in C. Last > time I checked, Wikipedia had a list of several. For a portable > solution you can try LibTomMath. > > https://www.libtom.net/LibTomMath/ > > Though I haven't used it myself. Here's one of mine: https://github.com/sal55/qx/blob/master/bignum.h https://github.com/sal55/qx/blob/master/bignum.c More basic, but also much simpler, as it is just those 2 files as can be seen. If the OP posts some code, I can show how to do it with this library. But it /will/ be more fiddly than using built-in long long arithmetic.
[toc] | [prev] | [next] | [standalone]
| From | Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> |
|---|---|
| Date | 2019-10-21 10:24 +0800 |
| Message-ID | <xF8rF.1130913$Nw3.160301@fx40.am4> |
| In reply to | #147130 |
On 21/10/2019 6:12 am, DFS wrote: > This large numbers issue shows prime factors isn't a good hash value. Hashing is a complex topic. The only summary of different hashing algorithms I know about is this answer: https://softwareengineering.stackexchange.com/a/145633 Is there a reason you can't use one of these algorithms? -- Johann | email: invalid -> com | www.myrkraverk.com/blog/ I'm not from the Internet, I just work there. | twitter: @myrkraverk
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-10-20 23:05 -0400 |
| Message-ID | <7h9rF.289683$iJ2.72384@fx47.iad> |
| In reply to | #147141 |
On 10/20/2019 10:24 PM, Johann 'Myrkraverk' Oskarsson wrote: > On 21/10/2019 6:12 am, DFS wrote: >> This large numbers issue shows prime factors isn't a good hash value. > > Hashing is a complex topic. The only summary of different hashing > algorithms I know about is this answer: > > https://softwareengineering.stackexchange.com/a/145633 > > Is there a reason you can't use one of these algorithms? I doubt it, but I haven't tried any yet. Thanks for the link.
[toc] | [prev] | [next] | [standalone]
| From | Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> |
|---|---|
| Date | 2019-10-21 11:32 +0800 |
| Message-ID | <0F9rF.994043$Jh2.16212@fx39.am4> |
| In reply to | #147142 |
On 21/10/2019 11:05 am, DFS wrote: > On 10/20/2019 10:24 PM, Johann 'Myrkraverk' Oskarsson wrote: >> On 21/10/2019 6:12 am, DFS wrote: >>> This large numbers issue shows prime factors isn't a good hash value. >> >> Hashing is a complex topic. The only summary of different hashing >> algorithms I know about is this answer: >> >> https://softwareengineering.stackexchange.com/a/145633 >> >> Is there a reason you can't use one of these algorithms? > > > I doubt it, but I haven't tried any yet. > > Thanks for the link. You can also take a look at this, if your data set is static. http://cmph.sourceforge.net/ I haven't used myself though. -- Johann | email: invalid -> com | www.myrkraverk.com/blog/ I'm not from the Internet, I just work there. | twitter: @myrkraverk
[toc] | [prev] | [next] | [standalone]
| From | Autist <autist69@gmail.com> |
|---|---|
| Date | 2019-10-29 15:15 +0100 |
| Message-ID | <qp9hh5$ntk$1@news.albasani.net> |
| In reply to | #147130 |
Better use C++ and a C++ large integer arithmetic library. With such a library you can handle your calculation as they were built-in types because of operator-overloading.
[toc] | [prev] | [standalone]
Page 6 of 6 — ← Prev page 1 2 3 4 5 [6]
Back to top | Article view | comp.lang.c
csiph-web