Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147715 > unrolled thread
| Started by | DFS <nospam@dfs.com> |
|---|---|
| First post | 2019-11-07 10:39 -0500 |
| Last post | 2019-11-11 00:56 +0000 |
| Articles | 20 on this page of 220 — 19 participants |
Back to article view | Back to comp.lang.c
mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-07 10:39 -0500
Re: mergesort code segfaulting on smallish arrays Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-07 07:48 -0800
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-07 16:02 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-07 11:34 -0500
Re: mergesort code segfaulting on smallish arrays Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-07 08:41 -0800
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-07 13:02 -0500
Re: mergesort code segfaulting on smallish arrays Keith Thompson <kst-u@mib.org> - 2019-11-07 10:37 -0800
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-07 14:38 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 16:44 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 13:01 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 10:39 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 10:52 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 11:12 +0100
Re: mergesort code segfaulting on smallish arrays Barry Schwarz <schwarzb@delq.com> - 2019-11-07 12:28 -0800
Re: mergesort code segfaulting on smallish arrays jadill33@gmail.com - 2019-11-07 13:13 -0800
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-08 00:55 +0000
Re: mergesort code segfaulting on smallish arrays jadill33@gmail.com - 2019-11-08 05:30 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 14:50 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 09:31 -0500
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 09:39 -0500
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-08 17:53 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 13:15 -0500
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-08 20:01 +0000
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-09 00:24 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-09 09:44 -0500
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-09 15:45 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-09 14:30 -0500
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-09 12:41 -0500
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-09 19:29 +0000
Re: mergesort code segfaulting on smallish arrays Richard Damon <Richard@Damon-Family.org> - 2019-11-09 14:59 -0500
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-09 22:00 +0000
Re: mergesort code segfaulting on smallish arrays Ian Collins <ian-news@hotmail.com> - 2019-11-10 11:24 +1300
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-09 22:48 +0000
Re: mergesort code segfaulting on smallish arrays Ian Collins <ian-news@hotmail.com> - 2019-11-10 12:09 +1300
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 14:46 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 14:11 +0000
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 17:27 +0100
Re: mergesort code segfaulting on smallish arrays Keith Thompson <kst-u@mib.org> - 2019-11-09 14:53 -0800
Re: mergesort code segfaulting on smallish arrays Ian Collins <ian-news@hotmail.com> - 2019-11-10 12:02 +1300
Re: mergesort code segfaulting on smallish arrays Ian Collins <ian-news@hotmail.com> - 2019-11-09 09:25 +1300
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-09 20:18 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-09 21:55 -0500
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-10 09:49 +0000
Re: mergesort code segfaulting on smallish arrays Keith Thompson <kst-u@mib.org> - 2019-11-07 10:34 -0800
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-07 16:12 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-07 12:19 -0500
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-07 17:42 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-07 13:32 -0500
Re: mergesort code segfaulting on smallish arrays Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-11-07 11:15 -0700
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-07 21:57 +0000
Re: mergesort code segfaulting on smallish arrays Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-11-07 19:11 -0700
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-07 21:57 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 09:21 +0100
Re: mergesort code segfaulting on smallish arrays chad <cdalten@gmail.com> - 2019-11-08 04:10 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 13:21 +0100
Re: mergesort code segfaulting on smallish arrays chad <cdalten@gmail.com> - 2019-11-13 04:12 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 13:55 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 09:20 -0500
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 10:23 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 16:36 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 11:56 -0500
Re: mergesort code segfaulting on smallish arrays Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-08 09:42 -0800
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 13:39 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 17:14 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 12:00 -0500
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-14 13:27 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-15 08:17 +0100
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-15 13:16 -0800
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-15 22:35 +0000
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-16 13:34 -0800
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-16 23:01 +0000
Re: mergesort code segfaulting on smallish arrays Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-11-17 08:34 +0000
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-17 09:13 +0000
Re: mergesort code segfaulting on smallish arrays Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-11-17 09:30 +0000
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-17 13:53 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-17 10:27 +0100
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-17 09:44 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-17 10:50 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-16 07:26 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 18:07 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-08 12:40 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 20:41 +0100
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-14 13:28 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 06:14 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 08:03 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-09 02:20 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 08:21 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 08:30 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-09 12:50 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 19:18 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-09 14:27 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 07:46 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 09:32 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-13 09:34 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 16:01 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 17:19 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-13 16:32 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 17:50 +0100
Re: mergesort code segfaulting on smallish arrays chad <cdalten@gmail.com> - 2019-11-13 11:09 -0800
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-13 19:18 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 20:31 +0100
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-13 17:12 -0800
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-13 20:26 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 06:16 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 06:40 +0100
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-14 01:11 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 10:41 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 06:42 +0100
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-13 21:56 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 10:42 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 06:39 +0100
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-13 21:38 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 14:33 +0100
Re: mergesort code segfaulting on smallish arrays Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-08 05:44 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 14:48 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 15:01 +0100
Re: mergesort code segfaulting on smallish arrays Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-08 08:00 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-08 17:12 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-08 16:34 +0000
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-12 17:05 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 18:07 +0100
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-08 23:50 +0000
Re: mergesort code segfaulting on smallish arrays Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-08 19:55 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 17:27 +0100
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-09 19:33 +0000
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-09 18:05 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 05:58 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 12:39 +0000
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 12:48 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 14:38 +0100
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-10 13:42 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 14:46 +0100
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-10 14:04 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 15:05 +0100
Re: mergesort code segfaulting on smallish arrays Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-10 14:09 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 15:19 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 14:06 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 15:22 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 14:30 +0000
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 14:36 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 15:59 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 15:26 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 15:56 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 15:21 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 16:28 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 15:38 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 16:58 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 16:59 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 16:24 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 17:37 +0100
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-10 17:22 +0000
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 18:04 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 19:10 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 19:14 +0100
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-11 02:14 +0000
Re: mergesort code segfaulting on smallish arrays DFS <nospam@dfs.com> - 2019-11-10 22:07 -0500
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-11 22:16 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-11 06:52 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-11 10:33 -0800
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-11 23:28 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 10:56 +0100
Re: mergesort code segfaulting on smallish arrays "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-12 02:35 -0800
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-12 15:01 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 16:08 +0100
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-12 15:53 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 16:56 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-11 13:45 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 08:00 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 17:03 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 08:27 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 17:29 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 08:18 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 17:27 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 08:43 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 18:01 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 09:41 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 18:44 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 11:00 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 20:03 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 11:22 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-12 20:24 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-12 11:44 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 06:23 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-13 06:40 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-13 16:34 +0100
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-13 08:41 -0800
Re: mergesort code segfaulting on smallish arrays James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-11 11:24 -0800
Re: mergesort code segfaulting on smallish arrays Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-10 05:13 -0800
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-09 19:36 +0000
Re: mergesort code segfaulting on smallish arrays Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-10 05:27 -0800
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 05:25 +0100
Re: mergesort code segfaulting on smallish arrays Richard Damon <Richard@Damon-Family.org> - 2019-11-09 11:30 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 17:49 +0100
Re: mergesort code segfaulting on smallish arrays Richard Damon <Richard@Damon-Family.org> - 2019-11-09 12:21 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 18:53 +0100
Re: mergesort code segfaulting on smallish arrays Richard Damon <Richard@Damon-Family.org> - 2019-11-09 13:33 -0500
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-09 19:37 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-09 18:51 +0000
Re: mergesort code segfaulting on smallish arrays Richard Damon <Richard@Damon-Family.org> - 2019-11-09 14:46 -0500
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 15:35 +0100
Re: mergesort code segfaulting on smallish arrays Bart <bc@freeuk.com> - 2019-11-10 14:48 +0000
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 15:35 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 15:39 +0100
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 19:54 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 19:55 +0100
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 21:34 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 21:37 +0100
Re: mergesort code segfaulting on smallish arrays Robert Wessel <robertwessel2@yahoo.com> - 2019-11-11 11:12 -0600
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 15:28 +0100
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 15:41 +0100
Re: mergesort code segfaulting on smallish arrays Keith Thompson <kst-u@mib.org> - 2019-11-09 12:47 -0800
Re: mergesort code segfaulting on smallish arrays David Brown <david.brown@hesbynett.no> - 2019-11-10 15:08 +0100
Re: mergesort code segfaulting on smallish arrays Keith Thompson <kst-u@mib.org> - 2019-11-10 14:30 -0800
Re: mergesort code segfaulting on smallish arrays Keith Thompson <kst-u@mib.org> - 2019-11-09 12:43 -0800
Re: mergesort code segfaulting on smallish arrays Richard Damon <Richard@Damon-Family.org> - 2019-11-09 17:16 -0500
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-09 19:27 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 05:55 +0100
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-10 16:45 +0000
Re: mergesort code segfaulting on smallish arrays Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-10 17:53 +0100
Re: mergesort code segfaulting on smallish arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-11 00:56 +0000
Page 3 of 11 — ← Prev page 1 2 [3] 4 5 … 11 Next page →
| From | Melzzzzz <Melzzzzz@zzzzz.com> |
|---|---|
| Date | 2019-11-09 20:18 +0000 |
| Message-ID | <Z9FxF.199078$TW2.52855@fx04.am4> |
| In reply to | #147788 |
On 2019-11-08, Bart <bc@freeuk.com> wrote: > > I wrote a merge-sort in my dynamic language based on DFS's C code. It > worked first time. > > Time to sort 10 million random integers: sorting array of integers is best done with radix sort, I think... > -- press any key to continue or any other to quit... U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec Svi smo svedoci - oko 3 godine intenzivne propagande je dovoljno da jedan narod poludi -- Zli Zec Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi bili naoruzani. -- Mladen Gogala
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-11-09 21:55 -0500 |
| Message-ID | <zZKxF.97741$vD7.16396@fx06.iad> |
| In reply to | #147849 |
On 11/9/2019 3:18 PM, Melzzzzz wrote: > On 2019-11-08, Bart <bc@freeuk.com> wrote: >> >> I wrote a merge-sort in my dynamic language based on DFS's C code. It >> worked first time. >> >> Time to sort 10 million random integers: > > sorting array of integers is best done with radix sort, I think... There are lots of sorting methods and variations, but qsort is generally the fastest. https://code.woboq.org/userspace/glibc/stdlib/qsort.c.html 1993 origins of qsort: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.8162&rep=rep1&type=pdf my C code (sort routines cadged from various places): N = 10000 merge sorted in 0.0120 seconds insertion sorted in 0.5863 seconds selection sorted in 0.3171 seconds radix sorted in 0.0076 seconds qsorted in 0.0033 seconds N = 50000 merge sorted in 0.0657 seconds insertion sorted in 14.6210 seconds selection sorted in 7.8935 seconds radix sorted in 0.0456 seconds qsorted in 0.0189 seconds next insertion sort not performed (too slow) selection sort not performed (too slow) N = 1000000 (1M) merge sorted in 1.4882 seconds radix sorted in 1.0720 seconds qsorted in 0.4815 seconds N = 10000000 (10M) merge sorted in 16.4587 seconds radix sorted in 12.2847 seconds qsorted in 5.5432 seconds
[toc] | [prev] | [next] | [standalone]
| From | Melzzzzz <Melzzzzz@zzzzz.com> |
|---|---|
| Date | 2019-11-10 09:49 +0000 |
| Message-ID | <R2RxF.368641$m0L.183608@fx15.am4> |
| In reply to | #147864 |
On 2019-11-10, DFS <nospam@dfs.com> wrote:
> On 11/9/2019 3:18 PM, Melzzzzz wrote:
>> On 2019-11-08, Bart <bc@freeuk.com> wrote:
>>>
>>> I wrote a merge-sort in my dynamic language based on DFS's C code. It
>>> worked first time.
>>>
>>> Time to sort 10 million random integers:
>>
>> sorting array of integers is best done with radix sort, I think...
>
>
> There are lots of sorting methods and variations, but qsort is generally
> the fastest.
Try to translate this from Rust:
fn radix_sort(nums:&mut Vec<i32>){
let BASE:usize = 16;
let mut bucket:Vec<Vec<i32>> = Vec::new();
for _ in 0..BASE {
bucket.push(Vec::new());
}
for n in 0..8 as usize{
for i in nums.iter() {
bucket[((*i >> (n<<2))&0xf) as usize].push(*i);
}
let mut k = 0;
for i in bucket.iter_mut() {
for j in i.iter() {
nums[k] = *j;
k+=1;
}
i.clear();
}
}
}
Rust:
rdx avx2 16777216 0.496826489 --> my assembler optimized
rdx rust 16777216 0.971492684 --> this Rust impl of radis.
vec sort 16777216 1.134089889 --> probably Rusts quicksort
btnc avx2 16777216 2.348568734 --> assembler optimized bitonic sort
btnc rust 16777216 6.013383912 --> sam impl but in Rust
C++ same 16mb elements:
~/examples/sort >>> ./bench
radix asm sort 495.985 // fastest for arrays
asm bitonic sort 2191.99
C++ sort 1077.95
VLib sort 1300.84 // my bid iterator quicksort can sort lists as well arrays
C qsort 2276.74 // slow due many calls to compare function
C++ list sort 10657.5 // not much cache friendly
VLib list sort 1904.64 // superior to C++ sort as does not change order of nodes.
all set
asm:
~/examples/sort >>> ./list_sort 10000000
seed: 1573379166
N: 10000000
unsorted
0x11508e670 1541370
0x11508e650 303300
0x11508e630 452109
0x11508e610 7264216
0x11508e5f0 3882021
0x11508e5d0 8782273
0x11508e5b0 4767489
0x11508e590 1272409
0x11508e570 7715490
0x11508e550 8934391
0x11508e530 7726359
0x11508e510 2732223
0x11508e4f0 7592011
0x11508e4d0 2713295
0x11508e4b0 8769973
0x11508e490 8176439
array radix elapsed 0.274972 seconds // sorting arrays is much faster due cache
list radix elapsed 13.023290 seconds
list merge elapsed 5.386599 seconds // merge is more cache friendly then radix for lists
equal
equal
sorted
0x10713efb0 0
0x10f8c8d90 1
0x114d9ce90 2
0x1146bcc10 4
0x11238ccf0 4
0x106140330 4
0x111b52050 4
0x102c068f0 6
0x10e70b350 6
0x1025ebc30 7
0x104bd0350 7
0x102b2cbf0 10
0x10b662a70 11
0x108ff6490 13
0x110944f50 14
0x10eeaff70 15
size of node 12, length 10000000
--
press any key to continue or any other to quit...
U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec
Svi smo svedoci - oko 3 godine intenzivne propagande je dovoljno da jedan narod poludi -- Zli Zec
Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi
bili naoruzani. -- Mladen Gogala
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2019-11-07 10:34 -0800 |
| Message-ID | <lntv7f4jte.fsf@kst-u.example.com> |
| In reply to | #147720 |
DFS <nospam@dfs.com> writes:
> On 11/7/2019 10:48 AM, Malcolm McLean wrote:
>> On Thursday, 7 November 2019 15:40:25 UTC, DFS wrote:
>>> This code mergesorts an array of ints. Works fine for small arrays, but
>>> craps out (Segmentation fault (core dumped)) at sizes > 500000.
>>>
>>> Ideas?
>>>
>>> void merge(int *arr, int left, int middle, int right) {
>>> int i=0, j=0, k=0;
>>> int leftLen = middle - left + 1;
>>> int rightLen = right - middle;
>>> int leftarr[leftLen];
>>> int rightarr[rightLen];
>>>
>>>
>> These are variable length arrays. They go on the stack. Stacks are usually
>> small in relation to the total memory, they are designed to hold a few
>> working variables, not entire datasets. You're probably exceeding stack
>> capacity.
>
> replaced
> int leftarr[leftLen];
> int rightarr[rightLen];
>
> with
> int *leftarr = malloc(sizeof(int) * (leftLen));
> int *rightarr = malloc(sizeof(int) * (rightLen));
Good, but a style point:
int *leftarr = malloc(leftLen * sizeof *leftarr);
int *rightarr = malloc(rightLen * sizeof *rightarr);
By using sizeof *leftarr, you don't have to update the type if you
decide later you want an array of double, for example. (The operand
of sizeof is not evaluated in this case, so it doesn't matter that
leftarr is uninitialized.)
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-11-07 16:12 +0000 |
| Message-ID | <UnXwF.61723$Q26.33742@fx34.am4> |
| In reply to | #147715 |
On 07/11/2019 15:39, DFS wrote:
> Ideas?
>
> void merge(int *arr, int left, int middle, int right) {
> int i=0, j=0, k=0;
> int leftLen = middle - left + 1;
> int rightLen = right - middle;
> int leftarr[leftLen];
> int rightarr[rightLen];
Try replacing this function with:
-----------------------------------------------------
int* allocintarray(int length) {
int* p = malloc(length*sizeof(int));
if (p==NULL) {puts("Malloc failed"); exit(1);};
return p;
}
void freeintarray(int* p) {
free(p);
}
void merge(int *arr, int left, int middle, int right) {
int i=0, j=0, k=0;
int leftLen = middle - left + 1;
int rightLen = right - middle;
int *leftarr = allocintarray(leftLen);
int *rightarr = allocintarray(rightLen);
// copy to left then right array
for (int i=0;i<leftLen;i++) {leftarr[i] = arr[left + i];}
for (int j=0;j<rightLen;j++) {rightarr[j] = arr[middle + 1 + j];}
i=0;
j=0;
// choose from right and left arrays and copy
while (i < leftLen && j < rightLen) {
if (leftarr[i] <= rightarr[j]) {
arr[left + k] = leftarr[i];
i++;
} else {
arr[left + k] = rightarr[j];
j++;
}
k ++;
}
// copy remaining values to the array
while (i < leftLen) {arr[left+k]=leftarr[i]; k++;i++;}
while (j < rightLen) {arr[left+k]=rightarr[j];k++;j++;}
freeintarray(leftarr);
freeintarray(rightarr);
}
-----------------------------------------------------
This allocates arrays on the heap rather than the stack. I tried it on
100,000,000 elements (after taking out your check) and it seems to work
fine.
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-11-07 12:19 -0500 |
| Message-ID | <dnYwF.18364$YF.8156@fx43.iad> |
| In reply to | #147718 |
On 11/7/2019 11:12 AM, Bart wrote:
> On 07/11/2019 15:39, DFS wrote:
>
>> Ideas?
>>
>
>
>
>> void merge(int *arr, int left, int middle, int right) {
>> int i=0, j=0, k=0;
>> int leftLen = middle - left + 1;
>> int rightLen = right - middle;
>> int leftarr[leftLen];
>> int rightarr[rightLen];
>
> Try replacing this function with:
>
> -----------------------------------------------------
> int* allocintarray(int length) {
> int* p = malloc(length*sizeof(int));
> if (p==NULL) {puts("Malloc failed"); exit(1);};
> return p;
> }
>
> void freeintarray(int* p) {
> free(p);
> }
>
> void merge(int *arr, int left, int middle, int right) {
> int i=0, j=0, k=0;
> int leftLen = middle - left + 1;
> int rightLen = right - middle;
> int *leftarr = allocintarray(leftLen);
> int *rightarr = allocintarray(rightLen);
>
> // copy to left then right array
> for (int i=0;i<leftLen;i++) {leftarr[i] = arr[left + i];}
> for (int j=0;j<rightLen;j++) {rightarr[j] = arr[middle + 1 + j];}
>
> i=0;
> j=0;
>
> // choose from right and left arrays and copy
> while (i < leftLen && j < rightLen) {
> if (leftarr[i] <= rightarr[j]) {
> arr[left + k] = leftarr[i];
> i++;
> } else {
> arr[left + k] = rightarr[j];
> j++;
> }
> k ++;
> }
>
> // copy remaining values to the array
> while (i < leftLen) {arr[left+k]=leftarr[i]; k++;i++;}
> while (j < rightLen) {arr[left+k]=rightarr[j];k++;j++;}
>
> freeintarray(leftarr);
> freeintarray(rightarr);
> }
> -----------------------------------------------------
>
> This allocates arrays on the heap rather than the stack. I tried it on
> 100,000,000 elements (after taking out your check) and it seems to work
> fine.
How long did it take to run with 100M elements? Mine takes about 15
seconds. qsort is about the same.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-11-07 17:42 +0000 |
| Message-ID | <aIYwF.28513$Gx6.11704@fx06.am4> |
| In reply to | #147724 |
On 07/11/2019 17:19, DFS wrote: > On 11/7/2019 11:12 AM, Bart wrote: >> This allocates arrays on the heap rather than the stack. I tried it on >> 100,000,000 elements (after taking out your check) and it seems to >> work fine. > > > How long did it take to run with 100M elements? Mine takes about 15 > seconds. qsort is about the same. It took 36 seconds with gcc-O3, and 69 seconds with tcc, both including generating the random array (about 5 seconds of the 36). This is on Windows where random numbers range only from 0 to 32767, so there are very long sequences of identical values in the sorted array. With a wider range, then it takes little longer (33 seconds to sort instead of 31, and 8 seconds to generate the numbers).
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-11-07 13:32 -0500 |
| Message-ID | <ArZwF.7485$aI.4847@fx44.iad> |
| In reply to | #147728 |
On 11/7/2019 12:42 PM, Bart wrote: > On 07/11/2019 17:19, DFS wrote: >> On 11/7/2019 11:12 AM, Bart wrote: > >>> This allocates arrays on the heap rather than the stack. I tried it >>> on 100,000,000 elements (after taking out your check) and it seems to >>> work fine. >> >> >> How long did it take to run with 100M elements? Mine takes about 15 >> seconds. qsort is about the same. I meant to say 15 seconds for 10M elements. > It took 36 seconds with gcc-O3, and 69 seconds with tcc, both including > generating the random array (about 5 seconds of the 36). > > This is on Windows where random numbers range only from 0 to 32767, so > there are very long sequences of identical values in the sorted array. > > With a wider range, then it takes little longer (33 seconds to sort > instead of 31, and 8 seconds to generate the numbers). 'Bonita Montero's' C++ merge sort (sequential) took just 1.5 seconds for 10M float elements on my machine. 10x faster than mine. How's that possible?
[toc] | [prev] | [next] | [standalone]
| From | Joe Pfeiffer <pfeiffer@cs.nmsu.edu> |
|---|---|
| Date | 2019-11-07 11:15 -0700 |
| Message-ID | <1bo8xnzh5t.fsf@pfeifferfamily.net> |
| In reply to | #147718 |
Bart <bc@freeuk.com> writes:
> On 07/11/2019 15:39, DFS wrote:
>
>> Ideas?
>>
>
>
>
>> void merge(int *arr, int left, int middle, int right) {
>> int i=0, j=0, k=0;
>> int leftLen = middle - left + 1;
>> int rightLen = right - middle;
>> int leftarr[leftLen];
>> int rightarr[rightLen];
>
> Try replacing this function with:
>
> -----------------------------------------------------
> int* allocintarray(int length) {
> int* p = malloc(length*sizeof(int));
> if (p==NULL) {puts("Malloc failed"); exit(1);};
> return p;
> }
>
> void freeintarray(int* p) {
> free(p);
> }
>
> void merge(int *arr, int left, int middle, int right) {
> int i=0, j=0, k=0;
> int leftLen = middle - left + 1;
> int rightLen = right - middle;
> int *leftarr = allocintarray(leftLen);
> int *rightarr = allocintarray(rightLen);
>
> // copy to left then right array
> for (int i=0;i<leftLen;i++) {leftarr[i] = arr[left + i];}
> for (int j=0;j<rightLen;j++) {rightarr[j] = arr[middle + 1 + j];}
>
> i=0;
> j=0;
>
> // choose from right and left arrays and copy
> while (i < leftLen && j < rightLen) {
> if (leftarr[i] <= rightarr[j]) {
> arr[left + k] = leftarr[i];
> i++;
> } else {
> arr[left + k] = rightarr[j];
> j++;
> }
> k ++;
> }
>
> // copy remaining values to the array
> while (i < leftLen) {arr[left+k]=leftarr[i]; k++;i++;}
> while (j < rightLen) {arr[left+k]=rightarr[j];k++;j++;}
>
> freeintarray(leftarr);
> freeintarray(rightarr);
> }
> -----------------------------------------------------
>
> This allocates arrays on the heap rather than the stack. I tried it on
> 100,000,000 elements (after taking out your check) and it seems to
> work fine.
Better yet would be to not do an extra copy of the entire array (which
would improve both speed and space), though that would do some extra
violence to the program as originally written.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2019-11-07 21:57 +0000 |
| Message-ID | <87d0e3ic43.fsf@bsb.me.uk> |
| In reply to | #147733 |
Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes: <cut> > Better yet would be to not do an extra copy of the entire array (which > would improve both speed and space), though that would do some extra > violence to the program as originally written. Do you mean an in-place merge sort using O(1) work space? If I recall correctly, That's tricky to program without losing the O(n log n) worst-case time complexity. I've not been following the thread, but it seems that a lot of allocations are being done. (A high cost was given for freeing the allocations.) Merge sort is usually implemented with one scratch copy of the array, i.e. O(n) extra space. Which array is considered work space is flipped as the recursion proceeds. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Joe Pfeiffer <pfeiffer@cs.nmsu.edu> |
|---|---|
| Date | 2019-11-07 19:11 -0700 |
| Message-ID | <1br22j2k3c.fsf@pfeifferfamily.net> |
| In reply to | #147750 |
Ben Bacarisse <ben.usenet@bsb.me.uk> writes: > Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes: > <cut> >> Better yet would be to not do an extra copy of the entire array (which >> would improve both speed and space), though that would do some extra >> violence to the program as originally written. > > Do you mean an in-place merge sort using O(1) work space? If I recall > correctly, That's tricky to program without losing the O(n log n) > worst-case time complexity. > > I've not been following the thread, but it seems that a lot of > allocations are being done. (A high cost was given for freeing the > allocations.) Merge sort is usually implemented with one scratch copy > of the array, i.e. O(n) extra space. Which array is considered work > space is flipped as the recursion proceeds. Right, this is what I had in mind as smaller and faster than the program as written..
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2019-11-07 21:57 +0000 |
| Message-ID | <877e4bic39.fsf@bsb.me.uk> |
| In reply to | #147733 |
Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes: <cut> > Better yet would be to not do an extra copy of the entire array (which > would improve both speed and space), though that would do some extra > violence to the program as originally written. Do you mean an in-place merge sort using O(1) work space? If I recall correctly, that's tricky to program without losing the O(n log n) worst-case time complexity. I've not been following the thread, but it seems that a lot of allocations are being done. (A high cost was given for freeing the allocations.) Merge sort is usually implemented with one scratch copy of the array, i.e. O(n) extra space. Which array is considered work space is flipped as the recursion proceeds. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-08 09:21 +0100 |
| Message-ID | <qq38i8$ore$1@news.albasani.net> |
| In reply to | #147715 |
Isn't this nicer ...
#include <iostream>
#include <random>
#include <limits>
#include <algorithm>
#include <cassert>
#include <iterator>
template<typename It, typename Cmp = std::less<typename
std::iterator_traits<It>::value_type>>
class merge_sort
{
public:
merge_sort( It start, It end, Cmp const &cmp );
private:
Cmp m_cmp;
template<typename UpIt, typename BufIt>
void recursion( UpIt start, UpIt end, BufIt buf );
};
template<typename It, typename Cmp>
inline
merge_sort<It, Cmp>::merge_sort( It start, It end, Cmp const &cmp ) :
m_cmp( cmp )
{
using T = typename std::iterator_traits<It>::value_type;
std::vector<T> buf;
size_t bs = 0;
for( size_t n = end - start; n > 1; bs += n, n -= n / 2 );
buf.resize( bs );
recursion( start, end, buf.begin() );
}
template<typename It, typename Cmp>
template<typename UpIt, typename BufIt>
void merge_sort<It, Cmp>::recursion( UpIt start, UpIt end, BufIt buf )
{
using namespace std;
if( end - start <= 1 )
return;
copy( start, end, buf );
size_t n = end - start;
BufIt leftBuf = buf,
leftBufEnd = buf + n / 2,
rightBuf = leftBufEnd,
bufEnd = buf + n;
recursion( leftBuf, leftBufEnd, bufEnd );
recursion( rightBuf, bufEnd, bufEnd );
for( UpIt wrtBack = start; ; )
if( m_cmp( *leftBuf, *rightBuf ) )
{
*wrtBack++ = *leftBuf;
if( ++leftBuf == leftBufEnd )
{
copy( rightBuf, bufEnd, wrtBack );
break;
}
}
else
{
*wrtBack++ = *rightBuf;
if( ++rightBuf == bufEnd )
{
copy( leftBuf, leftBufEnd, wrtBack );
break;
}
}
}
using namespace std;
int main()
{
size_t const N = 100'000'000;
vector<int> rv;
random_device rd;
uniform_int_distribution<int> uid( numeric_limits<int>::min(),
numeric_limits<int>::max() );
rv.resize( N );
for( int &r : rv )
r = uid( rd );
merge_sort<vector<int>::iterator>( rv.begin(), rv.end(),
less<int>() );
for( vector<int>::iterator scn = rv.begin(); scn < rv.end() - 1;
++scn )
assert(scn[0] <= scn[1]);
}
[toc] | [prev] | [next] | [standalone]
| From | chad <cdalten@gmail.com> |
|---|---|
| Date | 2019-11-08 04:10 -0800 |
| Message-ID | <901bc675-c326-48e2-a9cc-056efb1173b9@googlegroups.com> |
| In reply to | #147760 |
On Friday, November 8, 2019 at 12:21:38 AM UTC-8, Bonita Montero wrote:
> Isn't this nicer ...
>
> #include <iostream>
> #include <random>
> #include <limits>
> #include <algorithm>
> #include <cassert>
> #include <iterator>
>
> template<typename It, typename Cmp = std::less<typename
> std::iterator_traits<It>::value_type>>
> class merge_sort
> {
> public:
> merge_sort( It start, It end, Cmp const &cmp );
>
> private:
> Cmp m_cmp;
> template<typename UpIt, typename BufIt>
> void recursion( UpIt start, UpIt end, BufIt buf );
> };
>
> template<typename It, typename Cmp>
> inline
> merge_sort<It, Cmp>::merge_sort( It start, It end, Cmp const &cmp ) :
> m_cmp( cmp )
> {
> using T = typename std::iterator_traits<It>::value_type;
> std::vector<T> buf;
> size_t bs = 0;
> for( size_t n = end - start; n > 1; bs += n, n -= n / 2 );
> buf.resize( bs );
> recursion( start, end, buf.begin() );
> }
>
> template<typename It, typename Cmp>
> template<typename UpIt, typename BufIt>
> void merge_sort<It, Cmp>::recursion( UpIt start, UpIt end, BufIt buf )
> {
> using namespace std;
> if( end - start <= 1 )
> return;
> copy( start, end, buf );
> size_t n = end - start;
> BufIt leftBuf = buf,
> leftBufEnd = buf + n / 2,
> rightBuf = leftBufEnd,
> bufEnd = buf + n;
> recursion( leftBuf, leftBufEnd, bufEnd );
> recursion( rightBuf, bufEnd, bufEnd );
> for( UpIt wrtBack = start; ; )
> if( m_cmp( *leftBuf, *rightBuf ) )
> {
> *wrtBack++ = *leftBuf;
> if( ++leftBuf == leftBufEnd )
> {
> copy( rightBuf, bufEnd, wrtBack );
> break;
> }
> }
> else
> {
> *wrtBack++ = *rightBuf;
> if( ++rightBuf == bufEnd )
> {
> copy( leftBuf, leftBufEnd, wrtBack );
> break;
> }
> }
> }
>
> using namespace std;
>
> int main()
> {
> size_t const N = 100'000'000;
> vector<int> rv;
> random_device rd;
> uniform_int_distribution<int> uid( numeric_limits<int>::min(),
> numeric_limits<int>::max() );
> rv.resize( N );
> for( int &r : rv )
> r = uid( rd );
> merge_sort<vector<int>::iterator>( rv.begin(), rv.end(),
> less<int>() );
>
> for( vector<int>::iterator scn = rv.begin(); scn < rv.end() - 1;
> ++scn )
> assert(scn[0] <= scn[1]);
> }
Eeewww... Don't make me have to add you to my kill file.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-08 13:21 +0100 |
| Message-ID | <qq3mkk$fls$1@news.albasani.net> |
| In reply to | #147762 |
Am 08.11.2019 um 13:10 schrieb chad: >> Isn't this nicer ... >> #include <iostream> >> ... > Eeewww... Don't make me have to add you to my kill file. Do you like C so much?
[toc] | [prev] | [next] | [standalone]
| From | chad <cdalten@gmail.com> |
|---|---|
| Date | 2019-11-13 04:12 -0800 |
| Message-ID | <6110e8ea-6f31-458e-bdcd-620ae880a9cb@googlegroups.com> |
| In reply to | #147763 |
On Friday, November 8, 2019 at 4:21:51 AM UTC-8, Bonita Montero wrote: > Am 08.11.2019 um 13:10 schrieb chad: > > >> Isn't this nicer ... > >> #include <iostream> > >> ... > > > Eeewww... Don't make me have to add you to my kill file. > > Do you like C so much? It's more that I have a fairly strong dislike for C++ because it can become an absolute pain in deal with for either large scale projects. And this gets especially awesome when dealing with different upper managers.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-13 13:55 +0100 |
| Message-ID | <qqgufu$n3f$1@news.albasani.net> |
| In reply to | #148225 |
>> Do you like C so much? > It's more that I have a fairly strong dislike for C++ because it can become an absolute pain in deal with for either large scale projects. And this gets especially awesome when dealing with different upper managers. No, C i a pain with large projects, not C++. Just because you need multiple times the code for the same problem like in C++.
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-11-08 09:20 -0500 |
| Message-ID | <UQexF.59038$VR.37670@fx39.iad> |
| In reply to | #147762 |
On 11/8/2019 7:10 AM, chad wrote: > On Friday, November 8, 2019 at 12:21:38 AM UTC-8, Bonita Montero wrote: >> Isn't this nicer ... <snip gobbledygook> > Eeewww... Don't make me have to add you to my kill file. :)
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-11-08 10:23 -0500 |
| Message-ID | <5LfxF.7016$u23.893@fx13.iad> |
| In reply to | #147760 |
On 11/8/2019 3:21 AM, Bonita Montero wrote:
> Isn't this nicer ...
Not compared to my C program, it isn't. Mine is commented, accepts user
input, times the sort, and shows the results. (listing at bottom)
And yours is slow compared to mine (for 1M elements anyway).
Plus, mine (most C code) can be read and nearly, if not fully,
understood by anyone with a small amt of programming experience. Your
C++ code is almost indecipherable.
merge_sort<vector<int>::iterator>( rv.begin(), rv.end(), less<int>() );
vs
mergesort(randoms,0,arrsize-1);
huh?
And I assume you don't HAVE to create a 'class merge_sort' just to sort
an array?
Are you for real?
> #include <iostream>
> #include <random>
> #include <limits>
> #include <algorithm>
> #include <cassert>
> #include <iterator>
>
> template<typename It, typename Cmp = std::less<typename
> std::iterator_traits<It>::value_type>>
> class merge_sort
> {
> public:
> merge_sort( It start, It end, Cmp const &cmp );
>
> private:
> Cmp m_cmp;
> template<typename UpIt, typename BufIt>
> void recursion( UpIt start, UpIt end, BufIt buf );
> };
>
> template<typename It, typename Cmp>
> inline
> merge_sort<It, Cmp>::merge_sort( It start, It end, Cmp const &cmp ) :
> m_cmp( cmp )
> {
> using T = typename std::iterator_traits<It>::value_type;
> std::vector<T> buf;
> size_t bs = 0;
> for( size_t n = end - start; n > 1; bs += n, n -= n / 2 );
> buf.resize( bs );
> recursion( start, end, buf.begin() );
> }
>
> template<typename It, typename Cmp>
> template<typename UpIt, typename BufIt>
> void merge_sort<It, Cmp>::recursion( UpIt start, UpIt end, BufIt buf )
> {
> using namespace std;
> if( end - start <= 1 )
> return;
> copy( start, end, buf );
> size_t n = end - start;
> BufIt leftBuf = buf,
> leftBufEnd = buf + n / 2,
> rightBuf = leftBufEnd,
> bufEnd = buf + n;
> recursion( leftBuf, leftBufEnd, bufEnd );
> recursion( rightBuf, bufEnd, bufEnd );
> for( UpIt wrtBack = start; ; )
> if( m_cmp( *leftBuf, *rightBuf ) )
> {
> *wrtBack++ = *leftBuf;
> if( ++leftBuf == leftBufEnd )
> {
> copy( rightBuf, bufEnd, wrtBack );
> break;
> }
> }
> else
> {
> *wrtBack++ = *rightBuf;
> if( ++rightBuf == bufEnd )
> {
> copy( leftBuf, leftBufEnd, wrtBack );
> break;
> }
> }
> }
>
> using namespace std;
>
> int main()
> {
> size_t const N = 100'000'000;
> vector<int> rv;
> random_device rd;
> uniform_int_distribution<int> uid( numeric_limits<int>::min(),
> numeric_limits<int>::max() );
> rv.resize( N );
> for( int &r : rv )
> r = uid( rd );
> merge_sort<vector<int>::iterator>( rv.begin(), rv.end(),
> less<int>() );
>
> for( vector<int>::iterator scn = rv.begin(); scn < rv.end() - 1;
> ++scn )
> assert(scn[0] <= scn[1]);
> }
=======================================================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <Windows.h>
//program timing
LARGE_INTEGER frequency,master,start,end;
double elapsedtime(LARGE_INTEGER startingtimer)
{
QueryPerformanceCounter(&end);
return (end.QuadPart - startingtimer.QuadPart) /
(double)frequency.QuadPart;
}
//get random number from within range
int randInt(int low, int high) {
return (low + rand() / (RAND_MAX / (high - low + 1) + 1));
}
//print data to screen
void printdata(int *randarr, int size) {
for(int i=0;i<size;i++) {
if (i<10 || i>(size-11)) {printf("%8d. %d\n",i+1, randarr[i]);}
}
}
//part of mergesort
void merge(int *arr, int left, int middle, int right) {
int i=0, j=0, k=0;
int leftLen = middle - left + 1;
int rightLen = right - middle;
int *leftarr = malloc(sizeof(int) * (leftLen));
int *rightarr = malloc(sizeof(int) * (rightLen));
// copy to left then right array
for (int i=0;i<leftLen;i++) {leftarr[i] = arr[left + i];}
for (int j=0;j<rightLen;j++) {rightarr[j] = arr[middle + 1 + j];}
i=0;
j=0;
// choose from right and left arrays and copy
while (i < leftLen && j < rightLen) {
if (leftarr[i] <= rightarr[j]) {
arr[left + k] = leftarr[i];
i++;
} else {
arr[left + k] = rightarr[j];
j++;
}
k ++;
}
// copy remaining values to the array
while (i < leftLen) {arr[left+k]=leftarr[i]; k++;i++;}
while (j < rightLen) {arr[left+k]=rightarr[j];k++;j++;}
free(leftarr);
free(rightarr);
}
//mergesort
void mergesort(int *arr, int left, int right) {
if (left < right) {
int middle = left + (right - left) / 2;
mergesort(arr, left, middle);
mergesort(arr, middle + 1, right);
merge(arr, left, middle, right);
}
}
int main(int argc, char *argv[]) {
int i=0;
//seed
srand(time(NULL));
//validate/size the array
int arrsize = atoi(argv[1]);
if(arrsize < 1 || arrsize > 10) {
printf("Size between 1 and 10\n"); exit(0);
}
arrsize *= 1000 * 1000;
//create
int *randoms = malloc(sizeof(int) * (arrsize));
//populate and print
for(i=0;i<arrsize;randoms[i++]=randInt(0,arrsize*4));
printf("filled\n");
printdata(randoms,arrsize);
//begin timer
QueryPerformanceFrequency(&frequency);
QueryPerformanceCounter(&start);
//mergesort and print
mergesort(randoms,0,arrsize-1);
printf("\nmergesorted in %.4f seconds\n",elapsedtime(start));
printdata(randoms,arrsize);
//finish
free(randoms);
printf("Done");
exit(0);
}
=======================================================================
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-08 16:36 +0100 |
| Message-ID | <qq421d$i13$1@news.albasani.net> |
| In reply to | #147774 |
> And yours is slow compared to mine (for 1M elements anyway).
The difference in runtime comes from the the higher quality random
-number-generator. The sort-code should be equally fast at best.
std::copy uses memmove internally, which might not be optimally
because the copied tail of either subarray should be rather small
and memmove has a setup-time, looking for overlapping, alignment
to use xmm-instructions etc; a lot of things which aren't necessary.
I just wanted to code it as convenient and readable as possible.
Here's the changed code of the recursion for which you should get
at best an equal performance:
template<typename It, typename Cmp>
template<typename UpIt, typename BufIt>
void merge_sort<It, Cmp>::recursion( UpIt start, UpIt end, BufIt buf )
{
using namespace std;
if( end - start <= 1 )
return;
copy( start, end, buf );
size_t n = end - start;
BufIt leftBuf = buf,
leftBufEnd = buf + n / 2,
rightBuf = leftBufEnd,
bufEnd = buf + n;
recursion( leftBuf, leftBufEnd, bufEnd );
recursion( rightBuf, bufEnd, bufEnd );
for( UpIt wrtBack = start; ; )
if( m_cmp( *leftBuf, *rightBuf ) )
{
*wrtBack++ = *leftBuf;
if( ++leftBuf == leftBufEnd )
{
do
*wrtBack++ = *rightBuf;
while( ++rightBuf != bufEnd );
break;
}
}
else
{
*wrtBack++ = *rightBuf;
if( ++rightBuf == bufEnd )
{
do
*wrtBack++ = *leftBuf;
while( ++leftBuf != leftBufEnd );
break;
}
}
}
Consider that my code has a large runtime because of the higher quality
randomness and conditionally for the checking to be sorted at the end.
And the thing is that my code is much more flexible; it could be adapted
to any data-types throug a template-parameter. structs should be ref'd
via a pointer encapsulated in an object on which a comparison is defi-
ned.
[toc] | [prev] | [next] | [standalone]
Page 3 of 11 — ← Prev page 1 2 [3] 4 5 … 11 Next page →
Back to top | Article view | comp.lang.c
csiph-web