Jump to content

Talk:Approximate counting algorithm

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Coin tossing

[edit]

Is it really necessary to toss the coin N times for a counter with value N on every event just to see if they're all heads? Couldn't we stop as soon as a tail is observed? -- Ralph Corderoy (talk) 08:28, 6 July 2011 (UTC)[reply]

No, you could have multiple tails. All the best: Rich Farmbrough, 16:52, 17 October 2018 (UTC).[reply]

Actually you don't need multiple tosses at all. Simply generate a random number and take it modulo 2^V, where V is the current value. If the modulo is 0, then increment the counter. --CAFxX (talk) 15:14, 4 January 2012 (UTC)[reply]

This would be true if you knew the value. The point is that you don't, you only have the previous approximation, and knowledge that another instance has occured. Certainly if you have a run of X you might be able to optimise. All the best: Rich Farmbrough, 16:52, 17 October 2018 (UTC).[reply]

Recent developments

[edit]

Developments like the HyperLogLog algorithm (see highscalability.com) should perhaps be included. — Preceding unsigned comment added by Herojoker (talkcontribs) 22:42, 26 August 2012 (UTC) http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation <= This is a great description of the algorithm — Preceding unsigned comment added by 173.252.71.4 (talk) 23:24, 22 January 2013 (UTC)[reply]

[edit]

Hello fellow Wikipedians,

I have just modified one external link on Approximate counting algorithm. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 16:58, 16 October 2016 (UTC)[reply]