Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147222
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Challenge for Feeb: dealing with large numbers in C |
| Date | 2019-10-25 02:48 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <87eez1vbmi.fsf@bsb.me.uk> (permalink) |
| References | (6 earlier) <zB_rF.60706$VU2.40054@fx12.iad> <87y2xbvuzb.fsf@bsb.me.uk> <s3fsF.1855772$HWr.1014722@fx36.am4> <877e4uvstq.fsf@bsb.me.uk> <F2qsF.52890$zQ2.14958@fx10.iad> |
DFS <nospam@dfs.com> writes: > On 10/24/2019 3:36 PM, Ben Bacarisse wrote: >> Bart <bc@freeuk.com> writes: >> >>> On 24/10/2019 01:38, Ben Bacarisse wrote: >>>> DFS <nospam@dfs.com> writes: >>>> >>>>> You don't have to make a separate list V[] to store the sorted letters >>>>> (though using such a list would be faster). >>>>> >>>>> This code makes one pass thru the dictionary, comparing the sorted >>>>> letters of the search word against the sorted letters of each word in >>>>> the dictionary. >>>> >>>> Surely it's faster to count letters? On my machine a simple letter >>>> counting version takes about 1/4 of the time your program takes. >>> >>> Can you post code for a letter-counting version (that works off an >>> external word list), or have you posted one already? >> >> I didn't want to because I had not fixed any of the issues with the >> original. I just hacked a letter count into the code. For what it's >> worth, I've appended it as the end. >> >>> With the OP's sorting version: >>> >>> (1) The words are read via fgets with line-endings attached, and need >>> to be trimmed >> >> I kept that. I wanted a direct comparison. Profiling on Linux showed >> that most of the time was spent in wsort so there was clearly room for >> improvement. >> >>> (2) Bubble sort is applied to every word in the list >> >> I don't call that bubble sort, but let's not have that discussion again! > > ha! > > 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." We seem always to be talking at cross purposes. My point is simply that what you wrote is not bubble sort, so whether anyone hates it or not is beside the point. > https://users.cs.duke.edu/~ola/papers/bubble.pdf As this paper shows, bubble sort only ever compares (and therefore swaps) adjacent elements. Personally, I think bubble sort should also stop when no swaps are done in a pass, but obviously, not everyone agrees with that. >>> (I don't know if your '1/4' of the time compares times on your machine >>> with the OP's reported time, but they appear to be using Tiny C.) >> >> It compared the original (compiled with gcc -O2) with the counting >> version (obtained simply by adding -DCOUNTING), both running on the same >> Linux laptop. The numbers a so small that I doubt the ratio is really >> accurate (roughly 0.132 vs 0.035 seconds when I tried today). > > > $ tcc -o ben.exe -DCOUNTING ana_Ben_counts.c > $ ptime ben words_alpha.txt players > 7 anagram(s) found in 370099 words > Execution time: 0.215 s > > my code (no letter counting, uses strlen()): > $ ptime alpha words_alpha.txt players > 7 anagram(s) found in 370099 words > Execution time: 0.192 s I'm not sure what your point is. In case it was not obvious, /my/ point was that counting letter frequencies is faster than sorting letters. If you only sort letters on words that match in length then the results will depend on all sorts of other factors, including the data. But I am surprised your times are so high. Maybe your tests are being swamped by IO processing, but if they are not, you can get a further speed-up (though obviously a much less dramatic one) by using letter counting in your second program as well. -- Ben.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web