Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #83511 > unrolled thread
| Started by | Alla _ <modelling.data@gmail.com> |
|---|---|
| First post | 2016-03-09 00:52 -0800 |
| Last post | 2016-03-30 07:00 -0700 |
| Articles | 20 on this page of 330 — 24 participants |
Back to article view | Back to comp.lang.c
Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-09 00:52 -0800
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-09 10:13 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-09 02:19 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-09 02:23 -0800
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-09 13:00 +0000
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-09 02:38 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-09 02:59 -0800
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-09 10:35 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-10 00:20 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-09 02:56 -0800
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-09 13:11 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-09 06:37 -0800
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-09 15:50 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-09 08:19 -0800
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-09 17:18 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-10 00:11 -0800
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-10 08:48 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-10 04:17 -0800
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-10 11:12 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-10 04:16 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-10 04:20 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-09 08:41 -0800
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-09 17:27 +0000
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-09 22:41 -0600
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-10 10:38 +0000
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-10 09:37 -0600
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-10 15:51 +0000
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-10 18:42 -0600
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 04:17 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-10 00:18 -0800
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-10 08:51 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-09 08:50 -0800
Re: Testing nodes and lists for hashtable jadill33@gmail.com - 2016-03-09 07:16 -0800
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-09 09:27 -0600
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-09 07:46 -0800
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-09 10:56 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-10 00:25 -0800
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-10 08:55 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 01:14 -0800
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-11 01:53 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 02:25 -0800
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-11 12:31 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-12 00:03 -0800
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-12 09:04 -0800
Re: Testing nodes and lists for hashtable mark.bluemel@gmail.com - 2016-03-11 02:30 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 02:39 -0800
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-11 02:52 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 04:09 -0800
Re: Testing nodes and lists for hashtable mark.bluemel@gmail.com - 2016-03-14 08:41 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 02:34 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 02:41 -0800
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-11 12:14 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 04:20 -0800
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-11 12:33 +0000
Re: Testing nodes and lists for hashtable Randy Howard <rhoward.mx@EverybodyUsesIt.com> - 2016-03-11 12:12 -0600
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-11 10:24 -0800
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-11 19:04 +0000
Re: Testing nodes and lists for hashtable Randy Howard <rhoward.mx@EverybodyUsesIt.com> - 2016-03-11 14:20 -0600
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 23:55 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 04:23 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 04:25 -0800
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-11 12:36 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 05:56 -0800
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-11 14:55 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 07:22 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 07:29 -0800
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-11 16:01 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 23:41 -0800
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-13 13:48 +0000
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-11 20:20 +0000
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-13 13:06 +0000
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-12 17:41 -0600
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-13 05:03 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-13 13:50 +0000
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-13 10:32 -0500
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-13 09:18 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-13 16:31 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-13 10:17 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-13 10:17 -0500
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-13 09:06 -0700
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-13 09:51 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-13 10:31 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-13 12:41 -0500
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-11 08:41 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-11 23:54 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-12 08:10 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-12 08:17 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-12 08:19 -0800
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-12 09:16 -0800
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-13 04:17 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-12 19:37 +0000
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-13 11:20 -0500
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-13 21:37 +0000
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-12 09:48 -0800
Re: Testing nodes and lists for hashtable raltbos@xs4all.nl (Richard Bos) - 2016-03-12 20:31 +0000
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-12 21:18 +0000
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-12 17:54 -0600
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-13 04:25 -0700
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-13 04:44 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-13 12:31 -0500
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-13 11:14 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-13 16:17 -0500
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-13 14:37 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-13 11:43 -0700
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-13 12:08 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-13 16:31 -0500
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-14 01:12 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-14 01:21 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-14 13:48 -0500
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-15 01:43 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-14 01:35 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-14 13:44 -0500
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-15 01:39 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-13 23:04 +0000
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-13 16:09 -0700
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-13 17:54 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-14 01:58 -0700
Re: Testing nodes and lists for hashtable fir <profesor.fir@gmail.com> - 2016-03-14 03:08 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-14 10:59 +0000
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-14 04:59 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-14 13:15 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-14 11:09 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-14 03:18 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-14 11:03 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-14 11:17 -0700
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-14 15:16 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-15 01:59 -0700
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarz45@yahoo.com> - 2016-03-15 20:13 -0700
Re: Testing nodes and lists for hashtable supercat@casperkitty.com - 2016-03-15 22:09 -0700
Re: Testing nodes and lists for hashtable BartC <bc@freeuk.com> - 2016-03-16 11:53 +0000
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-16 09:39 -0500
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-16 07:57 -0700
Re: Testing nodes and lists for hashtable supercat@casperkitty.com - 2016-03-16 08:38 -0700
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-16 09:04 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-16 11:22 -0500
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-16 10:42 -0700
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-16 10:57 -0700
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-16 11:57 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-16 10:43 -0500
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-16 10:59 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-16 13:22 -0500
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-16 16:09 -0700
Re: Testing nodes and lists for hashtable supercat@casperkitty.com - 2016-03-16 17:03 -0700
Re: Testing nodes and lists for hashtable raltbos@xs4all.nl (Richard Bos) - 2016-03-20 13:04 +0000
Re: Testing nodes and lists for hashtable Tim Rentsch <txr@alumni.caltech.edu> - 2016-03-30 09:07 -0700
Re: Testing nodes and lists for hashtable luser droog <luser.droog@gmail.com> - 2016-03-31 20:34 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-14 14:04 +0000
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-14 11:07 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-14 03:49 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-14 13:03 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-14 11:24 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-14 11:41 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-14 19:35 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-15 01:53 -0700
Re: Testing nodes and lists for hashtable luser droog <luser.droog@gmail.com> - 2016-03-15 02:03 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-15 02:09 -0700
Re: Testing nodes and lists for hashtable luser droog <luser.droog@gmail.com> - 2016-03-15 02:13 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-15 02:22 -0700
Re: Testing nodes and lists for hashtable luser droog <luser.droog@gmail.com> - 2016-03-15 02:15 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-15 02:28 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-15 02:30 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-15 09:13 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-15 02:28 -0700
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-15 03:15 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-15 13:26 +0000
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-15 09:18 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-15 03:19 -0700
Re: Testing nodes and lists for hashtable David Brown <david.brown@hesbynett.no> - 2016-03-15 15:21 +0100
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-15 08:39 -0700
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-15 09:26 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 00:10 -0700
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-15 09:19 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 00:08 -0700
Re: Testing nodes and lists for hashtable David Brown <david.brown@hesbynett.no> - 2016-03-16 08:55 +0100
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-16 09:17 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 09:25 -0700
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-14 13:06 -0700
Re: Testing nodes and lists for hashtable Gareth Owen <gwowen@gmail.com> - 2016-03-14 20:29 +0000
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-14 21:03 +0000
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-14 14:57 -0700
Re: Testing nodes and lists for hashtable raltbos@xs4all.nl (Richard Bos) - 2016-03-14 22:35 +0000
Re: Testing nodes and lists for hashtable David Brown <david.brown@hesbynett.no> - 2016-03-16 19:47 +0100
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-14 14:26 -0700
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-14 11:37 -0700
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-14 11:37 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-15 08:58 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-15 16:12 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 00:04 -0700
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-15 10:48 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-15 18:00 +0000
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-15 19:20 +0000
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-15 21:24 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 00:50 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-16 11:19 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 04:37 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-16 11:51 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 05:20 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 07:13 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 09:05 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-16 11:45 +0000
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-16 13:46 +0000
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-16 14:00 +0000
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-16 07:05 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-16 16:42 +0000
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-16 10:21 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-16 17:33 +0000
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-16 10:44 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-16 18:00 +0000
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-16 11:08 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-16 18:19 +0000
Re: Testing nodes and lists for hashtable Gareth Owen <gwowen@gmail.com> - 2016-03-16 19:38 +0000
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-16 14:00 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-16 21:52 +0000
Re: Testing nodes and lists for hashtable Gareth Owen <gwowen@gmail.com> - 2016-03-16 22:12 +0000
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-16 13:39 -0500
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-16 15:39 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-17 02:59 +0000
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-17 04:20 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-17 23:46 +0000
Re: Testing nodes and lists for hashtable Jerry Stuckle <jstucklex@attglobal.net> - 2016-03-17 20:04 -0400
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-18 01:05 +0000
Re: Testing nodes and lists for hashtable Jerry Stuckle <jstucklex@attglobal.net> - 2016-03-17 22:35 -0400
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-17 17:19 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-18 01:39 +0000
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-18 02:54 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-18 09:08 -0500
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-18 11:20 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-18 21:29 +0000
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-18 17:48 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-16 22:09 -0500
Re: Testing nodes and lists for hashtable raltbos@xs4all.nl (Richard Bos) - 2016-03-17 11:49 +0000
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-17 08:45 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-17 12:11 -0500
Re: Testing nodes and lists for hashtable supercat@casperkitty.com - 2016-03-17 10:31 -0700
Re: Testing nodes and lists for hashtable Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-03-17 11:09 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-17 16:15 -0500
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-18 00:39 +0000
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-16 12:04 -0500
Re: Testing nodes and lists for hashtable Steve Thompson <stevet810@gmail.com> - 2016-03-17 14:21 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 00:53 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 01:00 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 01:24 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-16 11:08 +0000
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-16 11:25 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 00:41 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-16 08:27 -0500
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 06:43 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-16 14:07 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 08:16 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-16 15:25 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 08:30 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-16 20:32 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-17 03:26 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-17 16:15 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-17 11:07 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 08:47 -0700
Re: Testing nodes and lists for hashtable Stephen Sprunk <stephen@sprunk.org> - 2016-03-16 10:54 -0500
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 09:35 -0700
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-16 11:31 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-17 02:53 -0700
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-28 18:08 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-30 02:07 -0700
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-30 09:45 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-30 17:54 +0100
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-16 20:26 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-17 03:00 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-17 16:05 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-16 09:10 -0700
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-16 12:24 -0700
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-16 13:16 -0700
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-16 16:20 -0700
Re: Testing nodes and lists for hashtable supercat@casperkitty.com - 2016-03-16 16:54 -0700
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-16 17:27 -0700
Re: Testing nodes and lists for hashtable supercat@casperkitty.com - 2016-03-16 13:18 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-16 20:21 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-17 04:23 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-17 04:47 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-17 05:40 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-17 12:49 +0000
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-17 06:45 -0700
Re: Testing nodes and lists for hashtable mark.bluemel@gmail.com - 2016-03-17 10:00 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-17 12:40 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-28 12:00 -0700
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-28 12:37 -0700
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-28 17:43 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-30 01:31 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-30 01:55 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-30 10:23 +0100
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-30 02:32 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-30 02:33 -0700
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-30 07:04 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-30 15:17 +0100
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-30 07:46 -0700
Re: Testing nodes and lists for hashtable Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-30 16:41 +0100
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-30 09:16 -0700
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-30 09:18 -0700
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-30 09:37 -0700
Re: Testing nodes and lists for hashtable Barry Schwarz <schwarzb@dqel.com> - 2016-03-30 10:32 -0700
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-30 12:10 -0700
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-28 17:42 -0700
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-29 08:51 -0700
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-29 09:56 -0700
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-29 12:09 -0700
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-29 16:34 -0700
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-29 16:50 -0700
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-29 17:17 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-30 02:30 -0700
Re: Testing nodes and lists for hashtable Richard Heathfield <rjh@cpax.org.uk> - 2016-03-30 00:52 +0100
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-29 17:27 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-30 02:26 -0700
Re: Testing nodes and lists for hashtable mark.bluemel@gmail.com - 2016-03-30 07:09 -0700
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-30 07:33 -0700
Re: Testing nodes and lists for hashtable Jerry Stuckle <jstucklex@attglobal.net> - 2016-03-30 11:32 -0400
Re: Testing nodes and lists for hashtable mrs@kithrup.com (Mike Stump) - 2016-04-29 08:21 +0000
Re: Testing nodes and lists for hashtable Jerry Stuckle <jstucklex@attglobal.net> - 2016-04-29 10:35 -0400
Re: Testing nodes and lists for hashtable Ken Brody <kenbrody@spamcop.net> - 2016-04-29 11:29 -0400
Re: Testing nodes and lists for hashtable Jerry Stuckle <jstucklex@attglobal.net> - 2016-04-29 12:21 -0400
Re: Testing nodes and lists for hashtable Ken Brody <kenbrody@spamcop.net> - 2016-05-02 11:55 -0400
Re: Testing nodes and lists for hashtable Jerry Stuckle <jstucklex@attglobal.net> - 2016-05-02 13:13 -0400
Re: Testing nodes and lists for hashtable supercat@casperkitty.com - 2016-03-30 08:15 -0700
Re: Testing nodes and lists for hashtable Jerry Stuckle <jstucklex@attglobal.net> - 2016-03-30 11:39 -0400
Re: Testing nodes and lists for hashtable supercat@casperkitty.com - 2016-03-30 09:47 -0700
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-30 08:48 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-30 02:18 -0700
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-30 06:56 -0700
Re: Testing nodes and lists for hashtable Keith Thompson <kst-u@mib.org> - 2016-03-30 09:04 -0700
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-30 09:25 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-04-01 00:52 -0700
Re: Testing nodes and lists for hashtable Alla _ <modelling.data@gmail.com> - 2016-03-30 02:05 -0700
Re: Testing nodes and lists for hashtable Geoff <geoff@invalid.invalid> - 2016-03-30 07:00 -0700
Page 12 of 17 — ← Prev page 1 … 10 11 [12] 13 14 … 17 Next page →
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2016-03-18 01:05 +0000 |
| Message-ID | <87r3f8vbmp.fsf@bsb.me.uk> |
| In reply to | #84293 |
Jerry Stuckle <jstucklex@attglobal.net> writes: > On 3/17/2016 7:46 PM, Ben Bacarisse wrote: <snip> >> I'm not persuaded by any of this, but I'm not sure there's much value in >> going further. High load factors are never a good idea. > High load factors are seldom a good idea, but almost impossible to avoid > without wasting money on huge hardware systems. We may have crossed wires. I mean hash-table load factors which measure in some way (I think there's more than one definition) the number of hash collisions. When using chaining (i.e. lists) rather than probing you can almost always avoid high load factors because a bigger table will use no more memory than a loaded one with chaining (though there are fragmentation issues of course). -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Jerry Stuckle <jstucklex@attglobal.net> |
|---|---|
| Date | 2016-03-17 22:35 -0400 |
| Message-ID | <ncfpc6$lbj$1@jstuckle.eternal-september.org> |
| In reply to | #84297 |
On 3/17/2016 9:05 PM, Ben Bacarisse wrote: > Jerry Stuckle <jstucklex@attglobal.net> writes: > >> On 3/17/2016 7:46 PM, Ben Bacarisse wrote: > <snip> >>> I'm not persuaded by any of this, but I'm not sure there's much value in >>> going further. High load factors are never a good idea. > >> High load factors are seldom a good idea, but almost impossible to avoid >> without wasting money on huge hardware systems. > > We may have crossed wires. I mean hash-table load factors which measure > in some way (I think there's more than one definition) the number of > hash collisions. When using chaining (i.e. lists) rather than probing > you can almost always avoid high load factors because a bigger table > will use no more memory than a loaded one with chaining (though there > are fragmentation issues of course). > Ah, OK, yes, we did cross wires. But a good hash algorithm will minimize collisions; it pays to have a good one. OTOH, a binary tree (or better, an AVL tree) will be faster to search than any but the smallest lists, and are not that hard to implement. -- ================== Remove the "x" from my email address Jerry Stuckle jstucklex@attglobal.net ==================
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2016-03-17 17:19 -0700 |
| Message-ID | <04152d6c-d0b5-454c-bba8-ebe4dbd8d4d8@googlegroups.com> |
| In reply to | #84287 |
On Thursday, March 17, 2016 at 11:46:37 PM UTC, Ben Bacarisse wrote: > Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > > > On Thursday, March 17, 2016 at 3:00:01 AM UTC, Ben Bacarisse wrote: > >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > >> > >> I don't follow this. You seem to be do some sort of worst-case > >> analysis and I'm not sure why. > >> > >> Given the hand-waving you are prepared to accept, I'm not sure there's > >> any reason to think the distribution is significant. > >> > > The question is the load factor at which a balanced binary search tree starts > > to pay off. We know that a binary search tree will be better if the list of > > items in the bucket can get very long. > > So the first question is "how long are the lists likely to get?" - the answer is > > approximated by the Poisson distribution (except in cases where the number > > of buckets is so low that contents of one bucket give us reasonable information > > about the likely contents of another). > > It's approximated by many distributions. In most case the approximation > will be at it's worst in the tails which, for some reason I don't > follow, you are focusing on. > We know that a balanced binary search tree will have maximum advantage over a linked list when the lists are long. The question is "at what load factor doe s a balanced binary tree become advantageous?". So a reasonable way to answer that is to say "we must build the church Easter Sunday" - performance in the worst case is what is important to us. But "worst case" has to have some statistical limit - obviously it is possible for a million items to hash to the same bucket out of a million buckets, but, assuming a uniform hash function, it is far more likely that the computer will develop an electrical fault. So the question is, given a million items, a million buckets, and a million runs, what is the fullest bucket we are likely to see? Then take the worst case and see what win a balanced binary tree gives you over a linear search. > > > So let's take a worst case scenario - > > given a load factor, what's the longest bucket we're likely to see? > > But why? Even the crudest guess at the distribution will tell us that > the cases near the mean dominate and the tails contains very rare > cases. Why an almost worst case analysis? > > By picking (as you did) a "once in a million case" you are doing > something very odd. It is neither a worst-case analysis, nor one based > on the distribution of cases (i.e. an "average case" analysis). You use > the distribution to pick one case that is "quite bad" but, because of > the rather poor approximation at this low level, one you don't really > know how common it is. > You're right. But it's a reasonable procedure. The worst case is a million items in one bucket, but, assuming a uniform hash, we'll never see that. On the other hand, we can easily have a thousand buckets which we replenish a thousand times in the course of the program, so if p is 1.0e-6, we'll see that on almost every run. Take pe-12, and you've got a reasonable value for "impossible". But the analysis isn't very sensitive to the value you choose for "impossible", as long as you don't go for extremes like p = 5% or p = 1.0e-1000, it's only two or three items in the worst case bucket. > > I'm not persuaded by any of this, but I'm not sure there's much value in > going further. High load factors are never a good idea. > You posed the question. But I agree. In practical terms, keep the load factor below about 3.0, ad a linear list will be fine.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2016-03-18 01:39 +0000 |
| Message-ID | <87lh5gva1m.fsf@bsb.me.uk> |
| In reply to | #84295 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > On Thursday, March 17, 2016 at 11:46:37 PM UTC, Ben Bacarisse wrote: <snip> >> I'm not persuaded by any of this, but I'm not sure there's much value in >> going further. [...] >> > You posed the question. Yes, and you have answered it to your satisfaction. I don't think it can be answered like this with so many assumptions and numbers picked out of the air. <snip> -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2016-03-18 02:54 -0700 |
| Message-ID | <95250e05-1aaf-471a-aa98-771e7f921322@googlegroups.com> |
| In reply to | #84299 |
On Friday, March 18, 2016 at 1:40:01 AM UTC, Ben Bacarisse wrote: > Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > > > On Thursday, March 17, 2016 at 11:46:37 PM UTC, Ben Bacarisse wrote: > <snip> > >> I'm not persuaded by any of this, but I'm not sure there's much value in > >> going further. [...] > >> > > You posed the question. > > Yes, and you have answered it to your satisfaction. I don't think it > can be answered like this with so many assumptions and numbers picked > out of the air. > And the result is that a hash table isn't going to see any worthwhile advantage from anything more sophisticated than a linked list bucket for load factors or up to 3, whilst you need to start looking seriously at optimising the lists when load factors got up to about 10 or higher. That's more or less in line with what I would have said as a guesstimate. But some of parameters are unknown, you just have to pick reasonable figures. But change them within reasonable limits, and you won't get a very different result. Is it worth knowing? I don't know.
[toc] | [prev] | [next] | [standalone]
| From | Stephen Sprunk <stephen@sprunk.org> |
|---|---|
| Date | 2016-03-18 09:08 -0500 |
| Message-ID | <nch1v3$ccj$1@dont-email.me> |
| In reply to | #84311 |
On 18-Mar-16 04:54, Malcolm McLean wrote: > On Friday, March 18, 2016 at 1:40:01 AM UTC, Ben Bacarisse wrote: >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: >>> Ben Bacarisse wrote: >>>> I'm not persuaded by any of this, but I'm not sure there's much >>>> value in going further. [...] >>>> >>> You posed the question. >> >> Yes, and you have answered it to your satisfaction. I don't think >> it can be answered like this with so many assumptions and numbers >> picked out of the air. >> > And the result is that a hash table isn't going to see any worthwhile > advantage from anything more sophisticated than a linked list bucket > for load factors or up to 3, whilst you need to start looking > seriously at optimising the lists when load factors got up to about > 10 or higher. That's more or less in line with what I would have said > as a guesstimate. This means that if your load factor exceeds 3, you need to increase the number of buckets to bring it below 3 again. It doesn't mean that your buckets need to be more efficient. S -- Stephen Sprunk "God does not play dice." --Albert Einstein CCIE #3723 "God is an inveterate gambler, and He throws the K5SSS dice at every possible opportunity." --Stephen Hawking
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2016-03-18 11:20 -0700 |
| Message-ID | <04eb90ef-0799-40bb-b683-cbf945554c6e@googlegroups.com> |
| In reply to | #84319 |
On Friday, March 18, 2016 at 2:08:46 PM UTC, Stephen Sprunk wrote: > On 18-Mar-16 04:54, Malcolm McLean wrote: > > > And the result is that a hash table isn't going to see any worthwhile > > advantage from anything more sophisticated than a linked list bucket > > for load factors or up to 3, whilst you need to start looking > > seriously at optimising the lists when load factors got up to about > > 10 or higher. That's more or less in line with what I would have said > > as a guesstimate. > > This means that if your load factor exceeds 3, you need to increase the > number of buckets to bring it below 3 again. It doesn't mean that your > buckets need to be more efficient. > It's not always possible to re-hash. Usually that's what you do, I agree.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2016-03-18 21:29 +0000 |
| Message-ID | <87bn6bv5j6.fsf@bsb.me.uk> |
| In reply to | #84311 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > On Friday, March 18, 2016 at 1:40:01 AM UTC, Ben Bacarisse wrote: >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: >> >> > On Thursday, March 17, 2016 at 11:46:37 PM UTC, Ben Bacarisse wrote: >> <snip> >> >> I'm not persuaded by any of this, but I'm not sure there's much value in >> >> going further. [...] >> >> >> > You posed the question. >> >> Yes, and you have answered it to your satisfaction. I don't think it >> can be answered like this with so many assumptions and numbers picked >> out of the air. >> > And the result is that a hash table isn't going to see any worthwhile advantage > from anything more sophisticated than a linked list bucket for load factors > or up to 3, whilst you need to start looking seriously at optimising the lists > when load factors got up to about 10 or higher. > That's more or less in line with what I would have said as a > guesstimate. Yes, but I think you still have a guesstimate. You picked numbered based on what you think of a reasonable costs for linked list and binary tree operations. These unsurprisingly give an answer congruent with your gut feelings. > But some of parameters are unknown, you just have to pick reasonable > figures. But change them within reasonable limits, and you won't get > a very different result. Yes, because reasonable guesses must be those that produce the sort of answer you'd guess in the first place. > Is it worth knowing? I don't know. I don't know if it can be called knowing. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2016-03-18 17:48 -0700 |
| Message-ID | <0f687dc1-9b0c-438c-8967-d1036777a0de@googlegroups.com> |
| In reply to | #84345 |
On Friday, March 18, 2016 at 9:29:42 PM UTC, Ben Bacarisse wrote: > Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > > > But some of parameters are unknown, you just have to pick reasonable > > figures. But change them within reasonable limits, and you won't get > > a very different result. > > Yes, because reasonable guesses must be those that produce the sort of > answer you'd guess in the first place. > There's an element of that. But at least we state what the assumptions are. If you don't like them, plug in another value. Of course if the values are way off base - e.g. binary search costs a billion times more than linear search, you'll get radically different results. But few people would defend that sort of figure. Exactly how far you penalise binary search is a bit of an ill-defined question. > > > Is it worth knowing? I don't know. > > I don't know if it can be called knowing. >
[toc] | [prev] | [next] | [standalone]
| From | Stephen Sprunk <stephen@sprunk.org> |
|---|---|
| Date | 2016-03-16 22:09 -0500 |
| Message-ID | <ncd6uk$ipu$1@dont-email.me> |
| In reply to | #84195 |
On 16-Mar-16 17:39, Malcolm McLean wrote: > A balanced search tree finds the item in logarithmic time > plus a constant, a linear one in linear time. So call > the constant "c" and the scale "s", so time_bbst = > log2(time_link) * s + c; > > We'll assume s is 2 and c is 1 (a bit of fudge, to allow for > time to balance the bbst) > > Now the tree is twice as fast as the linked list at > N = 20 or so, and four times as fast at N = 40. > > So the answer, with admittedly a lot of hand-waving, is that > the balanced binary tree starts becoming worth it for a load > factor of about 3.0 or so, and will increasingly start to > be the method of choice for a load factor of 10 or so. *scratches head* Isn't a heavily loaded bucket balanced out by a lightly loaded bucket, i.e. the same result as if the buckets were all of average load? Given all the work (C) to keep a tree balanced, you'd need a large N for O(log N)+C to beat O(N) in practice; you can cut the load factor by increasing the number of buckets, so N should never _be_ large. S -- Stephen Sprunk "God does not play dice." --Albert Einstein CCIE #3723 "God is an inveterate gambler, and He throws the K5SSS dice at every possible opportunity." --Stephen Hawking
[toc] | [prev] | [next] | [standalone]
| From | raltbos@xs4all.nl (Richard Bos) |
|---|---|
| Date | 2016-03-17 11:49 +0000 |
| Message-ID | <56ea995a.1483062@news.xs4all.nl> |
| In reply to | #84210 |
Stephen Sprunk <stephen@sprunk.org> wrote: > On 16-Mar-16 17:39, Malcolm McLean wrote: > > So the answer, with admittedly a lot of hand-waving, is that > > the balanced binary tree starts becoming worth it for a load > > factor of about 3.0 or so, and will increasingly start to > > be the method of choice for a load factor of 10 or so. > > *scratches head* > > Isn't a heavily loaded bucket balanced out by a lightly loaded bucket, > i.e. the same result as if the buckets were all of average load? Not really; to begin with, a heavily loaded bucket is (ipso facto) hit much more often than a lightly loaded one, and therefore has a greater effect on efficiency. > Given all the work (C) to keep a tree balanced, you'd need a large N for > O(log N)+C to beat O(N) in practice; you can cut the load factor by > increasing the number of buckets, so N should never _be_ large. Which is why _almost_-balanced trees are more often used, IME, than perfectly balanced ones. Richard
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2016-03-17 08:45 -0700 |
| Message-ID | <f98e0681-77a1-42df-b949-559b2a384c02@googlegroups.com> |
| In reply to | #84237 |
On Thursday, March 17, 2016 at 11:49:43 AM UTC, Richard Bos wrote: > Stephen Sprunk <stephen@sprunk.org> wrote: > > > On 16-Mar-16 17:39, Malcolm McLean wrote: > > > > So the answer, with admittedly a lot of hand-waving, is that > > > the balanced binary tree starts becoming worth it for a load > > > factor of about 3.0 or so, and will increasingly start to > > > be the method of choice for a load factor of 10 or so. > > > > *scratches head* > > > > Isn't a heavily loaded bucket balanced out by a lightly loaded bucket, > > i.e. the same result as if the buckets were all of average load? > > Not really; to begin with, a heavily loaded bucket is (ipso facto) hit > much more often than a lightly loaded one, and therefore has a greater > effect on efficiency. > Then generally you assume the worst case - that all the entries hash to the same bucket for example. However assuming a good hash function and non-malciious input, that's less likely than that the computer will break. So you assume the worst halfway plausible case, which is that we have something like one in a million bad luck, we've got a bad bucket and an item we need to constantly look up is in that bucket. So I chose 1.0e-12 (a thousand buckets, a thousand passes, a one in a million cut-off for let's say it will never happen ). But it's hand-waving. However the probabilities drop off very quickly, so it doesn't make too much difference if you say "a thousand passes" or "a million passes". > > > Given all the work (C) to keep a tree balanced, you'd need a large N for > > O(log N)+C to beat O(N) in practice; you can cut the load factor by > > increasing the number of buckets, so N should never _be_ large. > > Which is why _almost_-balanced trees are more often used, IME, than > perfectly balanced ones. > One question is what penalty to apply to the balanced binary search tree over the linked list. Another is what's the relative importance of expected versus worst-case performance. Sometimes the worst case dominates - do you build the church for Easter Sunday?
[toc] | [prev] | [next] | [standalone]
| From | Stephen Sprunk <stephen@sprunk.org> |
|---|---|
| Date | 2016-03-17 12:11 -0500 |
| Message-ID | <nceoaq$p3u$1@dont-email.me> |
| In reply to | #84237 |
On 17-Mar-16 06:49, Richard Bos wrote: > Stephen Sprunk <stephen@sprunk.org> wrote: >> On 16-Mar-16 17:39, Malcolm McLean wrote: >>> So the answer, with admittedly a lot of hand-waving, is that the >>> balanced binary tree starts becoming worth it for a load factor >>> of about 3.0 or so, and will increasingly start to be the method >>> of choice for a load factor of 10 or so. >> >> Isn't a heavily loaded bucket balanced out by a lightly loaded >> bucket, i.e. the same result as if the buckets were all of average >> load? > > Not really; to begin with, a heavily loaded bucket is (ipso facto) > hit much more often than a lightly loaded one, and therefore has a > greater effect on efficiency. Doh! That makes sense, thanks. >> Given all the work (C) to keep a tree balanced, you'd need a large >> N for O(log N)+C to beat O(N) in practice; you can cut the load >> factor by increasing the number of buckets, so N should never _be_ >> large. > > Which is why _almost_-balanced trees are more often used, IME, than > perfectly balanced ones. Still, unless the input is truly disordered, there will be overhead in having to balance the tree, which offsets the lower search time. In Alla's case, we know the input is ordered, so without that step, the tree degenerates to a linked list. S -- Stephen Sprunk "God does not play dice." --Albert Einstein CCIE #3723 "God is an inveterate gambler, and He throws the K5SSS dice at every possible opportunity." --Stephen Hawking
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2016-03-17 10:31 -0700 |
| Message-ID | <d9713cf6-9e9b-4014-aa93-432805ba7cdd@googlegroups.com> |
| In reply to | #84264 |
On Thursday, March 17, 2016 at 12:12:00 PM UTC-5, Stephen Sprunk wrote: > Still, unless the input is truly disordered, there will be overhead in > having to balance the tree, which offsets the lower search time. In > Alla's case, we know the input is ordered, so without that step, the > tree degenerates to a linked list. If one has a known number of items in a sorted list, a perfectly-balanced tree can be readily constructed in linear time; this can be done especially nicely if the source list supports random access, but random access isn't required to make the technique work.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2016-03-17 11:09 -0700 |
| Message-ID | <1306effe-c277-4b2b-baca-ac8f6edc2d7e@googlegroups.com> |
| In reply to | #84267 |
On Thursday, March 17, 2016 at 5:32:05 PM UTC, supe...@casperkitty.com wrote: > On Thursday, March 17, 2016 at 12:12:00 PM UTC-5, Stephen Sprunk wrote: > > Still, unless the input is truly disordered, there will be overhead in > > having to balance the tree, which offsets the lower search time. In > > Alla's case, we know the input is ordered, so without that step, the > > tree degenerates to a linked list. > > If one has a known number of items in a sorted list, a perfectly-balanced > tree can be readily constructed in linear time; this can be done especially > nicely if the source list supports random access, but random access isn't > required to make the technique work. > If we know that the table will be set up with a list of sorted keys, then we can do a binary search instead of a hash, and get O log N performance with zero overhead, and that will generally be our method of choice.
[toc] | [prev] | [next] | [standalone]
| From | Stephen Sprunk <stephen@sprunk.org> |
|---|---|
| Date | 2016-03-17 16:15 -0500 |
| Message-ID | <ncf6j4$ls7$1@dont-email.me> |
| In reply to | #84275 |
On 17-Mar-16 13:09, Malcolm McLean wrote: > supe...@casperkitty.com wrote: >> Stephen Sprunk wrote: >>> Still, unless the input is truly disordered, there will be >>> overhead in having to balance the tree, which offsets the lower >>> search time. In Alla's case, we know the input is ordered, so >>> without that step, the tree degenerates to a linked list. >> >> If one has a known number of items in a sorted list, a >> perfectly-balanced tree can be readily constructed in linear time; >> this can be done especially nicely if the source list supports >> random access, but random access isn't required to make the >> technique work. > > If we know that the table will be set up with a list of sorted keys, > then we can do a binary search instead of a hash, and get O log N > performance with zero overhead, and that will generally be our > method of choice. With a reasonable number of buckets, i.e. low load factor, searching a hash table should be O(1), which beats O(log N). That's the point! S -- Stephen Sprunk "God does not play dice." --Albert Einstein CCIE #3723 "God is an inveterate gambler, and He throws the K5SSS dice at every possible opportunity." --Stephen Hawking
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2016-03-18 00:39 +0000 |
| Message-ID | <87wpp0vcur.fsf@bsb.me.uk> |
| In reply to | #84275 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > On Thursday, March 17, 2016 at 5:32:05 PM UTC, supe...@casperkitty.com wrote: >> On Thursday, March 17, 2016 at 12:12:00 PM UTC-5, Stephen Sprunk wrote: >> > Still, unless the input is truly disordered, there will be overhead in >> > having to balance the tree, which offsets the lower search time. In >> > Alla's case, we know the input is ordered, so without that step, the >> > tree degenerates to a linked list. >> >> If one has a known number of items in a sorted list, a perfectly-balanced >> tree can be readily constructed in linear time; this can be done especially >> nicely if the source list supports random access, but random access isn't >> required to make the technique work. >> > If we know that the table will be set up with a list of sorted keys, then we > can do a binary search instead of a hash, and get O log N performance > with zero overhead, and that will generally be our method of choice. Given that picture why not use a minimal perfect hash function? The cost is compile-time and execution is O(1). -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Stephen Sprunk <stephen@sprunk.org> |
|---|---|
| Date | 2016-03-16 12:04 -0500 |
| Message-ID | <ncc3hj$iqd$1@dont-email.me> |
| In reply to | #84100 |
On 16-Mar-16 09:05, Malcolm McLean wrote: > On Wednesday, March 16, 2016 at 1:46:27 PM UTC, Ben Bacarisse wrote: >> I've not seen the acronym BBST before but I presume you mean >> balanced binary search tree? I'd might try a binary tree, but I am >> not sure it's worth balancing it. When reading in a sorted dictionary, an unbalanced tree devolves into a linked list. However, when loading data in bulk, it's probably better to have a single balancing pass at the end rather than a tree that self-balances after each node is added. >> I wonder at what load factor the balanced tree starts to pay off. > > Assuming a perfectly random hash-funtion, [math stuff] > > That tells you the highest number of items in a bucket you can > reasonably expect. You will then hit that bucket Nworst/Nbuckets > times. > > So that tells you if a more sophisticated method than a linked list > is going to be worth it. OTOH, if you have so many nodes per bucket that the data structure within buckets actually matters, you're almost certainly better off increasing the number of buckets until it doesn't anymore. S -- Stephen Sprunk "God does not play dice." --Albert Einstein CCIE #3723 "God is an inveterate gambler, and He throws the K5SSS dice at every possible opportunity." --Stephen Hawking
[toc] | [prev] | [next] | [standalone]
| From | Steve Thompson <stevet810@gmail.com> |
|---|---|
| Date | 2016-03-17 14:21 +0000 |
| Message-ID | <lSf9Or.0eP.ZJtGh@gmail.com> |
| In reply to | #84097 |
On Wed, Mar 16, 2016 at 01:46:16PM +0000, Ben Bacarisse wrote: > Richard Heathfield <rjh@cpax.org.uk> writes: > > 1) a module for storing text data, and for destroying it when no > > longer needed, with the 'constructor' and 'destructor' adhering to a > > generic, flexible format; > > 2) a module for storing /arbitrary/ data in a linked list, for > > searching that list, for destroying specific nodes in that list, and > > for destroying the whole list; > > 3) a module for calculating a hash from arbitrary data; > > 4) a module for building, using, and destroying a hash table with > > arbitrarily many buckets. > > 5) main(), which would have been trivially simple to write by this stage. > > > > Except that I'd have used a BBST in each bucket, rather than a linked > > list. > > I've not seen the acronym BBST before but I presume you mean balanced > binary search tree? I'd might try a binary tree, but I am not sure it's > worth balancing it. At worse you'd get a list, and since the plan is > usually to keep the lists short, would it pay off? Have done any tests > of hashing + list, hashing + tree and hashing + some balanced tree? I > wonder at what load factor the balanced tree starts to pay off. And you call yourself a programmer? Regards, Steve Thompson
[toc] | [prev] | [next] | [standalone]
| From | Alla _ <modelling.data@gmail.com> |
|---|---|
| Date | 2016-03-16 00:53 -0700 |
| Message-ID | <a4951e79-1687-455f-9350-6dd143a1d89d@googlegroups.com> |
| In reply to | #84044 |
<snip>
> > bool unload(void)
> > {
> > bool had_to_unload = false;
> >
> > if(hashtable != NULL)
> > {
> > unload_nodes();
> > free(hashtable);
> > hashtable = NULL; /* ensure that a second call to unload()
> > will stop at the test. */
> > had_to_unload = true;
> > }
> > return had_to_unload;
> > }
>
> I don't see what the bool return is for, but I may well have missed some
> posts as the program developed.
It's a prerequisite condition - I can't change function declarations;
and I assume the staff uses this to test if a student has correctly
implemented unload() function. Not sure, though.
>
><snip>
[toc] | [prev] | [next] | [standalone]
Page 12 of 17 — ← Prev page 1 … 10 11 [12] 13 14 … 17 Next page →
Back to top | Article view | comp.lang.c
csiph-web