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 11 of 17 — ← Prev page 1 … 9 10 [11] 12 13 … 17 Next page →
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2016-03-16 13:46 +0000 |
| Message-ID | <87y49izgbb.fsf@bsb.me.uk> |
| In reply to | #84083 |
Richard Heathfield <rjh@cpax.org.uk> writes: > On 16/03/16 11:19, Ben Bacarisse wrote: > > <snip> > >> But this reminds me of the another small problem I keep forgetting! You >> still have a memory leak because the storage for the words themselves is >> not being freed. A simple solution to that is to call free on >> list->word in free_node_list. > > It's interesting that such a problem survived for so long. (I am > taking you at your word about this leak, since I haven't gone back to > check.) I think this is because of the way in which the program has > been developed. First, take a poorly-designed and poorly-understood > interface. Next, bolt onto it a few pieces that you think might be > handy. The next stage is to take careful note of several pieces of > advice, trying hard to ignore the problem that, although each piece > might make sense individually, they don't necessarily work /together/ > all that well. Finally, tweak the code until it seems to do more or > less what the spec requires. This is not an uncommon way for learners > to develop programs. I'm sure I wrote many similar programs once upon > a time, and no doubt others here did the same when they were learning. I think it's particularly bad because there are too many cooks and not all the cooks are committed to the recipe. Even if it's bad, if everyone (a) read and understood the exercise, (b) accepted that this is just how it has to be, (c) gave consistent advice about how to proceed then I don't think there would have been so much fuss. (c) is the hard one. There was talk about a fixed size word in the node structure. There was talk of using a flexible array member, and I even suggested that there are ways to use a pointer and still use only use allocation which may be why I kept forgetting to talk about freeing the word. > Top-down design works well, provided that you don't nail yourself to > interfaces too early. Bottom-up design allows you to build robust > components that can then be assembled in useful ways. The best > bottom-up design is application-blind -- the components one creates > become one's own library. As the library grows and becomes more > useful, it becomes easier and easier for future programs to be > designed in a top-down way, because you've got more tools to choose > from. > > In this case, I'd have done it something like this (if I were starting > from scratch and were not constrained by the interface design): Just for fun, I'd try the old Unix spell method: hash a word to get an index into a bit-set. Use n different hash functions into n different bit-sets to reduce the false positives. > 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. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2016-03-16 14:00 +0000 |
| Message-ID | <ncbon8$4eh$1@dont-email.me> |
| In reply to | #84097 |
On 16/03/16 13:46, Ben Bacarisse wrote: <snip> > I think it's particularly bad because there are too many cooks and not > all the cooks are committed to the recipe. Amen to that. <snip> >> 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? Sorry, yes, I did mean that. > I'd might try a binary tree, but I am not sure it's > worth balancing it. Neither am I, so I'd try both, and measure. <snip> -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2016-03-16 07:05 -0700 |
| Message-ID | <8d257eeb-c34d-490e-b8e4-83d26b281cde@googlegroups.com> |
| In reply to | #84097 |
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. 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. > Assuming a perfectly random hash-funtion, the hits are Poisson-distributed with a mean of load/Nbuckets. We need to multiply by Nbuckets to get the expected number of buckets with each case. We then need to multiply again by a factor to get the 'worst expected case' (strictly raise (1-p)^N and take the complement), which is probably about 1000 runs - it just depends how often you expect the hashtable to be run, which for a learning exercise is not very meaningful, but for, say, a hash table that executes every frame of a video game that plays for about half an hour, is meaningful. 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.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2016-03-16 16:42 +0000 |
| Message-ID | <87shzqz85i.fsf@bsb.me.uk> |
| In reply to | #84100 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > 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. 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. >> > Assuming a perfectly random hash-funtion, the hits are Poisson-distributed > with a mean of load/Nbuckets. Are they? I thought it would be a multinomial distribution. > We need to multiply by Nbuckets to get > the expected number of buckets with each case. We then need to multiply > again by a factor to get the 'worst expected case' (strictly raise (1-p)^N > and take the complement), which is probably about 1000 runs - it just > depends how often you expect the hashtable to be run, which for a learning > exercise is not very meaningful, but for, say, a hash table that executes every > frame of a video game that plays for about half an hour, is meaningful. > > 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. Does it? So what's the answer then? -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2016-03-16 10:21 -0700 |
| Message-ID | <86885ffc-1437-4db3-a646-3df23a441637@googlegroups.com> |
| In reply to | #84136 |
On Wednesday, March 16, 2016 at 4:42:43 PM UTC, Ben Bacarisse wrote: > Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > > > 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. 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. > >> > > Assuming a perfectly random hash-funtion, the hits are Poisson-distributed > > with a mean of load/Nbuckets. > > Are they? I thought it would be a multinomial distribution. > If we've got Nbuckets buckets and Nitems items, then the mean number of items per bucket is Nitems/Nbuckets. The chance of get 0, 1, 2, 3, 4, 5 etc items in any bucket is given by the Poisson distribution. Call k the number of hits we are querying p = pow(mean, k) * exp(-mean)/ factorial(k); I'm pretty sure that's right, but I'm not a mathematician. We're interested in the point where p gets so low that we can say "it won't occur". We then ask whether our linked list / whizzy binary search tree is going to be adequate / significantly better for that worst case. > > Does it? So what's the answer then? > I'll work an example through for you when I have time.
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2016-03-16 17:33 +0000 |
| Message-ID | <ncc56h$pvq$1@dont-email.me> |
| In reply to | #84143 |
On 16/03/16 17:21, Malcolm McLean wrote: > On Wednesday, March 16, 2016 at 4:42:43 PM UTC, Ben Bacarisse wrote: >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: >> <snip> >>>> >>> Assuming a perfectly random hash-funtion, the hits are Poisson-distributed >>> with a mean of load/Nbuckets. >> >> Are they? I thought it would be a multinomial distribution. >> > If we've got Nbuckets buckets and Nitems items, then the mean number of items > per bucket is Nitems/Nbuckets. > > The chance of get 0, 1, 2, 3, 4, 5 etc items in any bucket is given by the Poisson > distribution. So you're saying that they're Poisson-distributed because they follow the Poisson distribution. Where I come from, that's called "begging the question". I'm not saying you're wrong. I'm saying you haven't shown that you're right. -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2016-03-16 10:44 -0700 |
| Message-ID | <28eee7a8-0c3c-48e3-a15b-2a43c491a8d3@googlegroups.com> |
| In reply to | #84144 |
On Wednesday, March 16, 2016 at 5:33:17 PM UTC, Richard Heathfield wrote: > On 16/03/16 17:21, Malcolm McLean wrote: > > On Wednesday, March 16, 2016 at 4:42:43 PM UTC, Ben Bacarisse wrote: > >> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > >> > <snip> > >>>> > >>> Assuming a perfectly random hash-funtion, the hits are Poisson-distributed > >>> with a mean of load/Nbuckets. > >> > >> Are they? I thought it would be a multinomial distribution. > >> > > If we've got Nbuckets buckets and Nitems items, then the mean number of items > > per bucket is Nitems/Nbuckets. > > > > The chance of get 0, 1, 2, 3, 4, 5 etc items in any bucket is given by the Poisson > > distribution. > > So you're saying that they're Poisson-distributed because they follow > the Poisson distribution. Where I come from, that's called "begging the > question". > > I'm not saying you're wrong. I'm saying you haven't shown that you're right. > I'm not a mathematician, I didn't derive the Poisson distribution, Monseigneur Poisson did. He was a very clever chap and I take his results on trust. It is actually wrong for the extreme cases. Clearly if we have one bucket and one item, there must be exactly one item in that bucket, p k = 0 is 0, p k = 1 is 1, p k = 2 is 0 and so on - not the Poisson distribution. But I think that it very quickly converges, and I also believe (not sure) that it's a tractable way of getting the answer.
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2016-03-16 18:00 +0000 |
| Message-ID | <ncc6qg$cn$2@dont-email.me> |
| In reply to | #84148 |
On 16/03/16 17:44, Malcolm McLean wrote: > On Wednesday, March 16, 2016 at 5:33:17 PM UTC, Richard Heathfield wrote: >> On 16/03/16 17:21, Malcolm McLean wrote: >>> On Wednesday, March 16, 2016 at 4:42:43 PM UTC, Ben Bacarisse wrote: >>>> Malcolm McLean <malcolm.mclean5@btinternet.com> writes: >>>> >> <snip> >>>>>> >>>>> Assuming a perfectly random hash-funtion, the hits are Poisson-distributed >>>>> with a mean of load/Nbuckets. >>>> >>>> Are they? I thought it would be a multinomial distribution. >>>> >>> If we've got Nbuckets buckets and Nitems items, then the mean number of items >>> per bucket is Nitems/Nbuckets. >>> >>> The chance of get 0, 1, 2, 3, 4, 5 etc items in any bucket is given by the Poisson >>> distribution. >> >> So you're saying that they're Poisson-distributed because they follow >> the Poisson distribution. Where I come from, that's called "begging the >> question". >> >> I'm not saying you're wrong. I'm saying you haven't shown that you're right. >> > I'm not a mathematician, I didn't derive the Poisson distribution, Monseigneur > Poisson did. He was a very clever chap and I take his results on trust. Irrelevant. A random distribution may indeed be a Poisson distribution, but it doesn't have to be. If you are claiming that it is, you need to show that it is, in some way that doesn't assume a Poisson distribution to start with. -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2016-03-16 11:08 -0700 |
| Message-ID | <6b949be6-fcaa-4e07-8143-820f41432d19@googlegroups.com> |
| In reply to | #84153 |
On Wednesday, March 16, 2016 at 6:00:52 PM UTC, Richard Heathfield wrote: > > Irrelevant. A random distribution may indeed be a Poisson distribution, > but it doesn't have to be. If you are claiming that it is, you need to > show that it is, in some way that doesn't assume a Poisson distribution > to start with. > We've got a large number of buckets, and each hit strikes a random bucket with equal probability. So Poisson worked out that in such circumstances, the hits have the distribution named after him. I can't redo his work from first principles because I'm not clever enough, but I can look up the proof if you're interested, but if you Google "Poisson distribution" you'll simply get the same material as I will.
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2016-03-16 18:19 +0000 |
| Message-ID | <ncc7tr$4r2$2@dont-email.me> |
| In reply to | #84155 |
On 16/03/16 18:08, Malcolm McLean wrote: > On Wednesday, March 16, 2016 at 6:00:52 PM UTC, Richard Heathfield wrote: >> >> Irrelevant. A random distribution may indeed be a Poisson distribution, >> but it doesn't have to be. If you are claiming that it is, you need to >> show that it is, in some way that doesn't assume a Poisson distribution >> to start with. >> > We've got a large number of buckets, and each hit strikes a random bucket > with equal probability. What makes you think so? How do you know the probability isn't skewed in some way? In the OP's problem, the probability is enormously skewed, because the hashed strings are English text. We can still think of the data as being random without having to think of it as generating a uniformly distributed hash. -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2016-03-16 19:38 +0000 |
| Message-ID | <87twk61aeb.fsf@gmail.com> |
| In reply to | #84159 |
Richard Heathfield <rjh@cpax.org.uk> writes: > On 16/03/16 18:08, Malcolm McLean wrote: >> On Wednesday, March 16, 2016 at 6:00:52 PM UTC, Richard Heathfield wrote: >>> >>> Irrelevant. A random distribution may indeed be a Poisson distribution, >>> but it doesn't have to be. If you are claiming that it is, you need to >>> show that it is, in some way that doesn't assume a Poisson distribution >>> to start with. >>> >> We've got a large number of buckets, and each hit strikes a random bucket >> with equal probability. > > What makes you think so? How do you know the probability isn't skewed > in some way? Well, the discussion did start "assuming a perfectly random hash function". I don't thinks its too much to infer that a hash function described as "perfect" implies a uniform distribution between buckets.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2016-03-16 14:00 -0700 |
| Message-ID | <56c6031d-27ce-4648-9450-cddaddaa4a0b@googlegroups.com> |
| In reply to | #84179 |
On Wednesday, March 16, 2016 at 7:38:17 PM UTC, gwowen wrote: > Richard Heathfield <rjh@cpax.org.uk> writes: > > > What makes you think so? How do you know the probability isn't skewed > > in some way? > > Well, the discussion did start "assuming a perfectly random hash > function". I don't thinks its too much to infer that a hash function > described as "perfect" implies a uniform distribution between buckets. > It makes the function a lot messier if we allow a non-uniform hash. The Poisson distribution is the same, but now we have different means for each bucket. So we've got to sum a different p(k) for each k rather than simply multiplying by the number of buckets. What we can do is take the worst and multiply by Nbuckets, to give us a conservative bound on the load factor we can tolerate.
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2016-03-16 21:52 +0000 |
| Message-ID | <ncckcv$ok7$1@dont-email.me> |
| In reply to | #84179 |
On 16/03/16 19:38, Gareth Owen wrote: > Richard Heathfield <rjh@cpax.org.uk> writes: > >> On 16/03/16 18:08, Malcolm McLean wrote: >>> On Wednesday, March 16, 2016 at 6:00:52 PM UTC, Richard Heathfield wrote: >>>> >>>> Irrelevant. A random distribution may indeed be a Poisson distribution, >>>> but it doesn't have to be. If you are claiming that it is, you need to >>>> show that it is, in some way that doesn't assume a Poisson distribution >>>> to start with. >>>> >>> We've got a large number of buckets, and each hit strikes a random bucket >>> with equal probability. >> >> What makes you think so? How do you know the probability isn't skewed >> in some way? > > Well, the discussion did start "assuming a perfectly random hash > function". I don't thinks its too much to infer that a hash function > described as "perfect" implies a uniform distribution between buckets. Well, the discussion actually started way before then, with a hash function that looks something like: return *s - 'a'; -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2016-03-16 22:12 +0000 |
| Message-ID | <87d1qum5ru.fsf@gmail.com> |
| In reply to | #84191 |
Richard Heathfield <rjh@cpax.org.uk> writes: > Well, the discussion actually started way before then, with a hash > function that looks something like: > > return *s - 'a'; Sorry, I meant the specific paragraph that first brought up the Poisson-distribution. What Malcolm wrote was: > *Assuming a perfectly random hash-funtion*, the hits are > Poisson-distributed with a mean of load/Nbuckets... I think its reasonable to interpret that as synonymous mean "assuming a hash function that spreads our inputs uniformly over the buckets i.e. one that is optimal for our distribution of inputs..."
[toc] | [prev] | [next] | [standalone]
| From | Stephen Sprunk <stephen@sprunk.org> |
|---|---|
| Date | 2016-03-16 13:39 -0500 |
| Message-ID | <ncc92o$ahu$1@dont-email.me> |
| In reply to | #84153 |
On 16-Mar-16 13:00, Richard Heathfield wrote: > On 16/03/16 17:44, Malcolm McLean wrote: >> Richard Heathfield wrote: >>> So you're saying that they're Poisson-distributed because they >>> follow the Poisson distribution. Where I come from, that's called >>> "begging the question". >>> >>> I'm not saying you're wrong. I'm saying you haven't shown that >>> you're right. >> >> I'm not a mathematician, I didn't derive the Poisson distribution, >> Monseigneur Poisson did. He was a very clever chap and I take his >> results on trust. > > Irrelevant. A random distribution may indeed be a Poisson > distribution, but it doesn't have to be. If you are claiming that it > is, you need to show that it is, in some way that doesn't assume a > Poisson distribution to start with. If the events are random, in this case meaning the hash values are independent, then I don't see how it wouldn't be true. Obviously, we need a deterministic, not truly random, value so we can find the items again later, but "pseudo-random" implies a distribution of values similar enough to random that we can treat it as such. Alla's current hash function is obviously not pseudo-random, but that is presumably only for educational purposes; one wouldn't want to use it in real code. OTOH, a cryptographic hash would be overkill. 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-16 15:39 -0700 |
| Message-ID | <4e88dd09-ed87-41dd-ab1f-5fe351526bd2@googlegroups.com> |
| In reply to | #84143 |
On Wednesday, March 16, 2016 at 5:22:06 PM UTC, Malcolm McLean wrote: > On Wednesday, March 16, 2016 at 4:42:43 PM UTC, Ben Bacarisse wrote: > > Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > > > > > 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. 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. > > >> > > > Assuming a perfectly random hash-funtion, the hits are Poisson-distributed > > > with a mean of load/Nbuckets. > > > > Are they? I thought it would be a multinomial distribution. > > > If we've got Nbuckets buckets and Nitems items, then the mean number of items > per bucket is Nitems/Nbuckets. > > The chance of get 0, 1, 2, 3, 4, 5 etc items in any bucket is given by the Poisson > distribution. > Call k the number of hits we are querying > > p = pow(mean, k) * exp(-mean)/ factorial(k); > > I'm pretty sure that's right, but I'm not a mathematician. > > We're interested in the point where p gets so low that we can say "it won't occur". > We then ask whether our linked list / whizzy binary search tree is going to be > adequate / significantly better for that worst case. > > > > Does it? So what's the answer then? > > > I'll work an example through for you when I have time. > Ok, done it. Let's say we have a 1000 entries in our hash table, we expect to fill the table 1000 times, and we can accept a 1 in a million chance as "impossible". It follows that when 1 - the cumulative Posisson distribution goes to about 1.0e-12 that's out worst case scenario. So for load factors and worst number of items in bucket 0.5 - about 10 1.0 - about 13 1.5 - about 15 2.0 - about 17 2.5 - about 19 3.0 - about 21 3.5 - about 22 4.0 - about 24 4.5 - about 25 5.0 - about 26 7.5 - about 33 10.0 - about 38 So it's roughly linear for likely load factors. 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.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2016-03-17 02:59 +0000 |
| Message-ID | <87io0lyfks.fsf@bsb.me.uk> |
| In reply to | #84195 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > On Wednesday, March 16, 2016 at 5:22:06 PM UTC, Malcolm McLean wrote: >> On Wednesday, March 16, 2016 at 4:42:43 PM UTC, Ben Bacarisse wrote: >> > Malcolm McLean <malcolm.mclean5@btinternet.com> writes: >> > >> > > 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. 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. >> > >> >> > > Assuming a perfectly random hash-funtion, the hits are Poisson-distributed >> > > with a mean of load/Nbuckets. >> > >> > Are they? I thought it would be a multinomial distribution. >> > >> If we've got Nbuckets buckets and Nitems items, then the mean number of items >> per bucket is Nitems/Nbuckets. >> >> The chance of get 0, 1, 2, 3, 4, 5 etc items in any bucket is given by the Poisson >> distribution. >> Call k the number of hits we are querying >> >> p = pow(mean, k) * exp(-mean)/ factorial(k); >> >> I'm pretty sure that's right, but I'm not a mathematician. The original term 'hits' was a little vague. This is almost the textbook example of a multinomial distribution, but the 'hits' you are talking about are not the vector of counts in the buckets. The distribution of the counts (I'm not sure of the best term for this) can't actually be a Poisson distribution because it is never zero for an k no matter how large. But I think it is approximated by a Poisson distribution when the number of buckets and the mean is large enough. I am not sure how well it approximates the actual distribution in question, especially as you've chosen a worst-case analysis. >> We're interested in the point where p gets so low that we can say >> "it won't occur". >> We then ask whether our linked list / whizzy binary search tree is going to be >> adequate / significantly better for that worst case. >> > >> > Does it? So what's the answer then? >> > >> I'll work an example through for you when I have time. >> > Ok, done it. > Let's say we have a 1000 entries in our hash table, we expect > to fill the table 1000 times, and we can accept a 1 in a million > chance as "impossible". > It follows that when 1 - the cumulative Posisson distribution goes > to about 1.0e-12 that's out worst case scenario. > > So for load factors and worst number of items in bucket > > 0.5 - about 10 > 1.0 - about 13 > 1.5 - about 15 > 2.0 - about 17 > 2.5 - about 19 > 3.0 - about 21 > 3.5 - about 22 > 4.0 - about 24 > 4.5 - about 25 > 5.0 - about 26 > 7.5 - about 33 > 10.0 - about 38 > > So it's roughly linear for likely load factors. > > 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. 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. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2016-03-17 04:20 -0700 |
| Message-ID | <1f2425fd-725c-4055-a560-d13ce33b60dd@googlegroups.com> |
| In reply to | #84209 |
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). So let's take a worst case scenario - given a load factor, what's the longest bucket we're likely to see? However that involves some assumptions. Given we've got the worst case, how much better does the balanced binary search tree perform? Again, assumptions. If we say that a binary search tree executes in log2(N) time and a linear search in N time, then we should always use the binary search tree if N can go over 1, so we have to penalise the binary search somehow, and that's reasonable, given that it has overhead. but how to do that involves more assumptions.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2016-03-17 23:46 +0000 |
| Message-ID | <8737rowtv7.fsf@bsb.me.uk> |
| In reply to | #84234 |
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. > 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. > However that involves some assumptions. > > Given we've got the worst case, how much better does the balanced binary > search tree perform? Again, assumptions. If we say that a binary search > tree executes in log2(N) time and a linear search in N time, then we > should always use the binary search tree if N can go over 1, so we have to > penalise the binary search somehow, and that's reasonable, given that > it has overhead. but how to do that involves more assumptions. 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. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Jerry Stuckle <jstucklex@attglobal.net> |
|---|---|
| Date | 2016-03-17 20:04 -0400 |
| Message-ID | <ncfgh3$the$1@jstuckle.eternal-september.org> |
| In reply to | #84287 |
On 3/17/2016 7:46 PM, 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. > >> 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 pick a "worst case scenario" because if that works, then all better scenarios work. If you pick something else, your program will fail in that once in a million times - which happens more often than you think. >> However that involves some assumptions. >> >> Given we've got the worst case, how much better does the balanced binary >> search tree perform? Again, assumptions. If we say that a binary search >> tree executes in log2(N) time and a linear search in N time, then we >> should always use the binary search tree if N can go over 1, so we have to >> penalise the binary search somehow, and that's reasonable, given that >> it has overhead. but how to do that involves more assumptions. > > 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. -- ================== Remove the "x" from my email address Jerry Stuckle jstucklex@attglobal.net ==================
[toc] | [prev] | [next] | [standalone]
Page 11 of 17 — ← Prev page 1 … 9 10 [11] 12 13 … 17 Next page →
Back to top | Article view | comp.lang.c
csiph-web