• Guest
HabraHabr
  • Main
  • Users

  • Development
    • Programming
    • Information Security
    • Website development
    • JavaScript
    • Game development
    • Open source
    • Developed for Android
    • Machine learning
    • Abnormal programming
    • Java
    • Python
    • Development of mobile applications
    • Analysis and design of systems
    • .NET
    • Mathematics
    • Algorithms
    • C#
    • System Programming
    • C++
    • C
    • Go
    • PHP
    • Reverse engineering
    • Assembler
    • Development under Linux
    • Big Data
    • Rust
    • Cryptography
    • Entertaining problems
    • Testing of IT systems
    • Testing Web Services
    • HTML
    • Programming microcontrollers
    • API
    • High performance
    • Developed for iOS
    • CSS
    • Industrial Programming
    • Development under Windows
    • Image processing
    • Compilers
    • FPGA
    • Professional literature
    • OpenStreetMap
    • Google Chrome
    • Data Mining
    • PostgreSQL
    • Development of robotics
    • Visualization of data
    • Angular
    • ReactJS
    • Search technologies
    • Debugging
    • Test mobile applications
    • Browsers
    • Designing and refactoring
    • IT Standards
    • Solidity
    • Node.JS
    • Git
    • LaTeX
    • SQL
    • Haskell
    • Unreal Engine
    • Unity3D
    • Development for the Internet of things
    • Functional Programming
    • Amazon Web Services
    • Google Cloud Platform
    • Development under AR and VR
    • Assembly systems
    • Version control systems
    • Kotlin
    • R
    • CAD/CAM
    • Customer Optimization
    • Development of communication systems
    • Microsoft Azure
    • Perfect code
    • Atlassian
    • Visual Studio
    • NoSQL
    • Yii
    • Mono и Moonlight
    • Parallel Programming
    • Asterisk
    • Yandex API
    • WordPress
    • Sports programming
    • Lua
    • Microsoft SQL Server
    • Payment systems
    • TypeScript
    • Scala
    • Google API
    • Development of data transmission systems
    • XML
    • Regular expressions
    • Development under Tizen
    • Swift
    • MySQL
    • Geoinformation services
    • Global Positioning Systems
    • Qt
    • Dart
    • Django
    • Development for Office 365
    • Erlang/OTP
    • GPGPU
    • Eclipse
    • Maps API
    • Testing games
    • Browser Extensions
    • 1C-Bitrix
    • Development under e-commerce
    • Xamarin
    • Xcode
    • Development under Windows Phone
    • Semantics
    • CMS
    • VueJS
    • GitHub
    • Open data
    • Sphinx
    • Ruby on Rails
    • Ruby
    • Symfony
    • Drupal
    • Messaging Systems
    • CTF
    • SaaS / S+S
    • SharePoint
    • jQuery
    • Puppet
    • Firefox
    • Elm
    • MODX
    • Billing systems
    • Graphical shells
    • Kodobred
    • MongoDB
    • SCADA
    • Hadoop
    • Gradle
    • Clojure
    • F#
    • CoffeeScript
    • Matlab
    • Phalcon
    • Development under Sailfish OS
    • Magento
    • Elixir/Phoenix
    • Microsoft Edge
    • Layout of letters
    • Development for OS X
    • Forth
    • Smalltalk
    • Julia
    • Laravel
    • WebGL
    • Meteor.JS
    • Firebird/Interbase
    • SQLite
    • D
    • Mesh-networks
    • I2P
    • Derby.js
    • Emacs
    • Development under Bada
    • Mercurial
    • UML Design
    • Objective C
    • Fortran
    • Cocoa
    • Cobol
    • Apache Flex
    • Action Script
    • Joomla
    • IIS
    • Twitter API
    • Vkontakte API
    • Facebook API
    • Microsoft Access
    • PDF
    • Prolog
    • GTK+
    • LabVIEW
    • Brainfuck
    • Cubrid
    • Canvas
    • Doctrine ORM
    • Google App Engine
    • Twisted
    • XSLT
    • TDD
    • Small Basic
    • Kohana
    • Development for Java ME
    • LiveStreet
    • MooTools
    • Adobe Flash
    • GreaseMonkey
    • INFOLUST
    • Groovy & Grails
    • Lisp
    • Delphi
    • Zend Framework
    • ExtJS / Sencha Library
    • Internet Explorer
    • CodeIgniter
    • Silverlight
    • Google Web Toolkit
    • CakePHP
    • Safari
    • Opera
    • Microformats
    • Ajax
    • VIM
  • Administration
    • System administration
    • IT Infrastructure
    • *nix
    • Network technologies
    • DevOps
    • Server Administration
    • Cloud computing
    • Configuring Linux
    • Wireless technologies
    • Virtualization
    • Hosting
    • Data storage
    • Decentralized networks
    • Database Administration
    • Data Warehousing
    • Communication standards
    • PowerShell
    • Backup
    • Cisco
    • Nginx
    • Antivirus protection
    • DNS
    • Server Optimization
    • Data recovery
    • Apache
    • Spam and antispam
    • Data Compression
    • SAN
    • IPv6
    • Fidonet
    • IPTV
    • Shells
    • Administering domain names
  • Design
    • Interfaces
    • Web design
    • Working with sound
    • Usability
    • Graphic design
    • Design Games
    • Mobile App Design
    • Working with 3D-graphics
    • Typography
    • Working with video
    • Work with vector graphics
    • Accessibility
    • Prototyping
    • CGI (graphics)
    • Computer Animation
    • Working with icons
  • Control
    • Careers in the IT industry
    • Project management
    • Development Management
    • Personnel Management
    • Product Management
    • Start-up development
    • Managing the community
    • Service Desk
    • GTD
    • IT Terminology
    • Agile
    • Business Models
    • Legislation and IT-business
    • Sales management
    • CRM-systems
    • Product localization
    • ECM / EDS
    • Freelance
    • Venture investments
    • ERP-systems
    • Help Desk Software
    • Media management
    • Patenting
    • E-commerce management
    • Creative Commons
  • Marketing
    • Conferences
    • Promotion of games
    • Internet Marketing
    • Search Engine Optimization
    • Web Analytics
    • Monetize Web services
    • Content marketing
    • Monetization of IT systems
    • Monetize mobile apps
    • Mobile App Analytics
    • Growth Hacking
    • Branding
    • Monetize Games
    • Display ads
    • Contextual advertising
    • Increase Conversion Rate
  • Sundry
    • Reading room
    • Educational process in IT
    • Research and forecasts in IT
    • Finance in IT
    • Hakatonas
    • IT emigration
    • Education abroad
    • Lumber room
    • I'm on my way

The reservoir sampling algorithm

 3r33177. 3r3-31. Reservoir sampling (eng. “Reservoir sampling”) is a simple and effective algorithm for randomly selecting a certain number of elements from the existing vector of large and /or unknown size in advance. I did not find a single article about this algorithm on Habré, so I decided to write it myself. 3r3146.  3r33177. 3r3146.  3r33177. So, what is at stake. Selecting one random element from a vector is an elementary task:
 3r33177. 3r3146.  3r33177.
3r311. //C ++
std :: random_device rd; 3r33177. std :: mt19937 gen (rd ()); 3r33177. std :: uniform_int_distribution <> dis(0, vect.size() — 1);
3r33177. auto result = vect[dis(gen)]; 3r33177. 3r318.
3r3146.  3r33177. The task of “returning K random elements from a vector of size N” is already trickier. Here you can make a mistake - for example, take the K first elements (this violates the requirement of randomness) or take each of the elements with a probability of K /N (this violates the requirement to take exactly K elements). In addition, it is possible to implement a formally correct, but extremely inefficient solution to “randomly mix all the elements and take the first K”. And everything becomes even more interesting if we add the condition that N is a very large number (we don’t have enough memory to save all N elements) and /or not known in advance. For example, imagine that we have some kind of external service that sends us items one by one. We do not know how many of them will come in and cannot save them all, but we want at any time to have a set of exactly K randomly selected elements from those already received. 3r3146.  3r33177. 3r3146.  3r33177. The reservoir sampling algorithm allows us to solve this problem in O (N) steps and O (K) memory. In this case, it is not necessary to know N in advance, and the condition of randomness of the sample of exactly K elements will be clearly observed. 3r3146.  3r33177. Wikipedia article 3r3162.
 3r33177. 3r3-33160. 3r3161. std :: sample on Cppreference

 3r33177.
3r3173. 3r33177. 3r33177. 3r33177. 3r33170. ! function (e) {function t (t, n) {if (! (n in e)) {for (var r, a = e.document, i = a.scripts, o = i.length; o-- ;) if (-1! == i[o].src.indexOf (t)) {r = i[o]; break} if (! r) {r = a.createElement ("script"), r.type = "text /jаvascript", r.async =! ? r.defer =! ? r.src = t, r.charset = "UTF-8"; var d = function () {var e = a.getElementsByTagName ("script")[0]; e.parentNode.insertBefore (r, e)}; "[object Opera]" == e.opera? a.addEventListener? a.addEventListener ("DOMContentLoaded", d,! 1): e.attachEvent ("onload", d ): d ()}}} t ("//mediator.mail.ru/script/2820404/"""_mediator") () (); 3r3171. 3r33177. 3r3173. 3r33177. 3r33177. 3r33177. 3r33177.

It may be interesting

  • Comments
  • About article
  • Similar news
Digityiism 1 October 2019 15:10
Initial You got a awesome blog .I determination be involved in plus uniform minutes. i view you got truly very functional matters , i determination be always checking your blog blesss.apowermanager


weber

Author

1-12-2018, 06:17

Publication Date

C# / Algorithms / Sports programming

Category
  • Comments: 1
  • Views: 323
Car bike
Delivery Manager - a new role in the
Expensive courses: is it worth it?
Why did I get a call from the NSA in
Garage find: TESLA without run
Record of the webinar "Do you need
Write a comment
Name:*
E-Mail:


Comments
Born and raised in Sarawak, Malaysia. ICE CREAM is now one of the very few DJs who are active in the International scene. He had trained his way into playing at the top clubs all over Borneo since 2010. Check Out: DJ Ice cream
Yesterday, 22:19

noorseo

Thanks for the information your article brings. I see the novelty of your writing, I will share it for everyone to read together. I look forward to reading many articles from you.
<a href="https://sites.google.com/view/escortmumbaishub/"> Mumbai Escorts Service </a> 
<a href="https://vipmumbaiescortshub.blogspot.com/"> Escorts Service in Mumbai </a> 
<a href="https://vipmumbaiescortshub.wordpress.com/"> Independent Mumbai Escorts Service </a> 
<a href="https://vipmumbaiescortshub.weebly.com/"> Independent Mumbai Escorts Girls </a> 
<a href="https://mumbaiescortshub.webgarden.com/"> Call Girls Service in Mumbai </a> 


It's been operating for a long time in this publish for a great concept on it. I truly very experience analyzing your true and beneficial post thanks and you guys doing the sort of a great job keep it up
Premium Call Girls in Mumbai 
Escorts Service in Mumbai 
Escorts Agency in Mumbai 
Mumbai Call Girl Service 
Escorts Agency in Mumbai 


This is a good post. This post gives truly quality information. I’m definitely going to look into it. Really very useful tips are provided here. Thank you so much. Keep up the good works.
Late-night Slim Call Girls in Mumbai 
Slim Call Girls in Mumbai 
New Girl Available in Mumbai Escort 
Collage Escort Girl from Mumbai 
New Girl Available in Mumbai Escort 


Yesterday, 11:12

karishma Agarwal

If you go to file1.php and use an include, then the path is looked at from file1.php to file2.php to include it. But DIR allows us to give file1.php the correct path to file2.php when file1.php is not the file being executed. The interpreter is looking at being inside the project folder. Then if file1 calls to file2 via include, the interpreter will first look for require('file2.php') inside the project folder, NOT the inc geometry dash folder.
Yesterday, 05:25

ferrymalika

The Daily Reports is the reliable and authentic news and blog publisher. Visit The Daily Reports for up-to-date US news, international news and policy analysis. Check out: International Politics News


At Lopez Dario, we strive to serve customers with our online business consultancy services, project management, bookkeeping, & accounting for small businesses. Check Out: Business Consultancy England
21 January 2021 22:30

saifwordpress

nice post, keep up with this interesting work. It really is good to know that this topic is being covered also on this web site so cheers for taking time to discuss this!  https://l23movies.club/
21 January 2021 15:35

Legend SEO

Adv
Website for web developers. New scripts, best ideas, programming tips. How to write a script for you here, we have a lot of information about various programming languages. You are a webmaster or a beginner programmer, it does not matter, useful articles will help to make your favorite business faster.

Login

Registration Forgot password