{"action":"created","comment":{"url":"https://api.github.com/repos/apache/flink/pulls/comments/39002941","id":39002941,"diff_hunk":"@@ -102,15 +106,31 @@ public T next() {\n \t\t\t}\n \n \t\t\tprivate T getNextSampledElement() {\n-\t\t\t\twhile (input.hasNext()) {\n-\t\t\t\t\tT element = input.next();\n-\n-\t\t\t\t\tif (random.nextDouble() <= fraction) {\n+\t\t\t\tif (fraction <= THRESHOLD) {\n+\t\t\t\t\tdouble rand = random.nextDouble();\n+\t\t\t\t\tdouble u = Math.max(rand, EPSILON);\n+\t\t\t\t\tint gap = (int) (Math.log(u) / Math.log(1 - fraction));\n+\t\t\t\t\tint elementCount = 0;\n+\t\t\t\t\tif (input.hasNext()) {\n+\t\t\t\t\t\tT element = input.next();\n+\t\t\t\t\t\twhile (input.hasNext() && elementCount < gap) {\n+\t\t\t\t\t\t\telement = input.next();\n+\t\t\t\t\t\t\telementCount++;\n+\t\t\t\t\t\t}\n \t\t\t\t\t\treturn element;\n+\t\t\t\t\t} else {\n+\t\t\t\t\t\treturn null;\n \t\t\t\t\t}\n-\t\t\t\t}\n+\t\t\t\t}else {","path":"flink-java/src/main/java/org/apache/flink/api/java/sampling/BernoulliSampler.java","position":41,"original_position":41,"commit_id":"b4b431471736cd32a50b49cc9e91e038a4387808","original_commit_id":"b4b431471736cd32a50b49cc9e91e038a4387808","user":{"login":"ChengXiangLi","id":4425616,"avatar_url":"https://avatars.githubusercontent.com/u/4425616?v=3","gravatar_id":"","url":"https://api.github.com/users/ChengXiangLi","html_url":"https://github.com/ChengXiangLi","followers_url":"https://api.github.com/users/ChengXiangLi/followers","following_url":"https://api.github.com/users/ChengXiangLi/following{/other_user}","gists_url":"https://api.github.com/users/ChengXiangLi/gists{/gist_id}","starred_url":"https://api.github.com/users/ChengXiangLi/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ChengXiangLi/subscriptions","organizations_url":"https://api.github.com/users/ChengXiangLi/orgs","repos_url":"https://api.github.com/users/ChengXiangLi/repos","events_url":"https://api.github.com/users/ChengXiangLi/events{/privacy}","received_events_url":"https://api.github.com/users/ChengXiangLi/received_events","type":"User","site_admin":false},"body":"Format: add a blank between right brace and \"else\".","created_at":"2015-09-09T02:53:46Z","updated_at":"2015-09-09T02:53:46Z","html_url":"https://github.com/apache/flink/pull/1110#discussion_r39002941","pull_request_url":"https://api.github.com/repos/apache/flink/pulls/1110","_links":{"self":{"href":"https://api.github.com/repos/apache/flink/pulls/comments/39002941"},"html":{"href":"https://github.com/apache/flink/pull/1110#discussion_r39002941"},"pull_request":{"href":"https://api.github.com/repos/apache/flink/pulls/1110"}}},"pull_request":{"url":"https://api.github.com/repos/apache/flink/pulls/1110","id":44504478,"html_url":"https://github.com/apache/flink/pull/1110","diff_url":"https://github.com/apache/flink/pull/1110.diff","patch_url":"https://github.com/apache/flink/pull/1110.patch","issue_url":"https://api.github.com/repos/apache/flink/issues/1110","number":1110,"state":"open","locked":false,"title":"[FLINK-2533] [core] Gap based random sample optimization.","user":{"login":"gallenvara","id":12931563,"avatar_url":"https://avatars.githubusercontent.com/u/12931563?v=3","gravatar_id":"","url":"https://api.github.com/users/gallenvara","html_url":"https://github.com/gallenvara","followers_url":"https://api.github.com/users/gallenvara/followers","following_url":"https://api.github.com/users/gallenvara/following{/other_user}","gists_url":"https://api.github.com/users/gallenvara/gists{/gist_id}","starred_url":"https://api.github.com/users/gallenvara/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gallenvara/subscriptions","organizations_url":"https://api.github.com/users/gallenvara/orgs","repos_url":"https://api.github.com/users/gallenvara/repos","events_url":"https://api.github.com/users/gallenvara/events{/privacy}","received_events_url":"https://api.github.com/users/gallenvara/received_events","type":"User","site_admin":false},"body":"For random sampler with fraction, like BernoulliSampler and PoissonSampler, Gap based random sampler could exploit O(np) sample implementation instead of previous O(n) sample implementation, it should perform better while sample fraction is very small.When deal with large fraction, it's better to use previous sample implementation. So we add a threshold to control the sampling method according to the fraction.(threshold_Bernoulli = 0.33, threshold_Poisson = 0.4)\r\n![bernoullisampler](https://cloud.githubusercontent.com/assets/12931563/9751893/fd4195a2-56dc-11e5-8937-30ebfa927960.PNG)\r\n![poissonsampler](https://cloud.githubusercontent.com/assets/12931563/9751894/fd4c35a2-56dc-11e5-9d71-e7b62e5dcc05.PNG)","created_at":"2015-09-09T02:26:37Z","updated_at":"2015-09-09T02:53:46Z","closed_at":null,"merged_at":null,"merge_commit_sha":"b83e6be8dd9fb41cc41b24b7e65981861014b795","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/apache/flink/pulls/1110/commits","review_comments_url":"https://api.github.com/repos/apache/flink/pulls/1110/comments","review_comment_url":"https://api.github.com/repos/apache/flink/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/flink/issues/1110/comments","statuses_url":"https://api.github.com/repos/apache/flink/statuses/b4b431471736cd32a50b49cc9e91e038a4387808","head":{"label":"gallenvara:gap_sampling","ref":"gap_sampling","sha":"b4b431471736cd32a50b49cc9e91e038a4387808","user":{"login":"gallenvara","id":12931563,"avatar_url":"https://avatars.githubusercontent.com/u/12931563?v=3","gravatar_id":"","url":"https://api.github.com/users/gallenvara","html_url":"https://github.com/gallenvara","followers_url":"https://api.github.com/users/gallenvara/followers","following_url":"https://api.github.com/users/gallenvara/following{/other_user}","gists_url":"https://api.github.com/users/gallenvara/gists{/gist_id}","starred_url":"https://api.github.com/users/gallenvara/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gallenvara/subscriptions","organizations_url":"https://api.github.com/users/gallenvara/orgs","repos_url":"https://api.github.com/users/gallenvara/repos","events_url":"https://api.github.com/users/gallenvara/events{/privacy}","received_events_url":"https://api.github.com/users/gallenvara/received_events","type":"User","site_admin":false},"repo":{"id":40312457,"name":"flink","full_name":"gallenvara/flink","owner":{"login":"gallenvara","id":12931563,"avatar_url":"https://avatars.githubusercontent.com/u/12931563?v=3","gravatar_id":"","url":"https://api.github.com/users/gallenvara","html_url":"https://github.com/gallenvara","followers_url":"https://api.github.com/users/gallenvara/followers","following_url":"https://api.github.com/users/gallenvara/following{/other_user}","gists_url":"https://api.github.com/users/gallenvara/gists{/gist_id}","starred_url":"https://api.github.com/users/gallenvara/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gallenvara/subscriptions","organizations_url":"https://api.github.com/users/gallenvara/orgs","repos_url":"https://api.github.com/users/gallenvara/repos","events_url":"https://api.github.com/users/gallenvara/events{/privacy}","received_events_url":"https://api.github.com/users/gallenvara/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/gallenvara/flink","description":"Mirror of Apache Flink","fork":true,"url":"https://api.github.com/repos/gallenvara/flink","forks_url":"https://api.github.com/repos/gallenvara/flink/forks","keys_url":"https://api.github.com/repos/gallenvara/flink/keys{/key_id}","collaborators_url":"https://api.github.com/repos/gallenvara/flink/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/gallenvara/flink/teams","hooks_url":"https://api.github.com/repos/gallenvara/flink/hooks","issue_events_url":"https://api.github.com/repos/gallenvara/flink/issues/events{/number}","events_url":"https://api.github.com/repos/gallenvara/flink/events","assignees_url":"https://api.github.com/repos/gallenvara/flink/assignees{/user}","branches_url":"https://api.github.com/repos/gallenvara/flink/branches{/branch}","tags_url":"https://api.github.com/repos/gallenvara/flink/tags","blobs_url":"https://api.github.com/repos/gallenvara/flink/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/gallenvara/flink/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/gallenvara/flink/git/refs{/sha}","trees_url":"https://api.github.com/repos/gallenvara/flink/git/trees{/sha}","statuses_url":"https://api.github.com/repos/gallenvara/flink/statuses/{sha}","languages_url":"https://api.github.com/repos/gallenvara/flink/languages","stargazers_url":"https://api.github.com/repos/gallenvara/flink/stargazers","contributors_url":"https://api.github.com/repos/gallenvara/flink/contributors","subscribers_url":"https://api.github.com/repos/gallenvara/flink/subscribers","subscription_url":"https://api.github.com/repos/gallenvara/flink/subscription","commits_url":"https://api.github.com/repos/gallenvara/flink/commits{/sha}","git_commits_url":"https://api.github.com/repos/gallenvara/flink/git/commits{/sha}","comments_url":"https://api.github.com/repos/gallenvara/flink/comments{/number}","issue_comment_url":"https://api.github.com/repos/gallenvara/flink/issues/comments{/number}","contents_url":"https://api.github.com/repos/gallenvara/flink/contents/{+path}","compare_url":"https://api.github.com/repos/gallenvara/flink/compare/{base}...{head}","merges_url":"https://api.github.com/repos/gallenvara/flink/merges","archive_url":"https://api.github.com/repos/gallenvara/flink/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/gallenvara/flink/downloads","issues_url":"https://api.github.com/repos/gallenvara/flink/issues{/number}","pulls_url":"https://api.github.com/repos/gallenvara/flink/pulls{/number}","milestones_url":"https://api.github.com/repos/gallenvara/flink/milestones{/number}","notifications_url":"https://api.github.com/repos/gallenvara/flink/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/gallenvara/flink/labels{/name}","releases_url":"https://api.github.com/repos/gallenvara/flink/releases{/id}","created_at":"2015-08-06T15:28:37Z","updated_at":"2015-08-06T15:28:49Z","pushed_at":"2015-09-09T02:00:31Z","git_url":"git://github.com/gallenvara/flink.git","ssh_url":"git@github.com:gallenvara/flink.git","clone_url":"https://github.com/gallenvara/flink.git","svn_url":"https://github.com/gallenvara/flink","homepage":null,"size":57558,"stargazers_count":0,"watchers_count":0,"language":"Java","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"apache:master","ref":"master","sha":"304139d48101d5c7eb9f0d5fa79cce37f235b0ab","user":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"repo":{"id":20587599,"name":"flink","full_name":"apache/flink","owner":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/apache/flink","description":"Mirror of Apache Flink","fork":false,"url":"https://api.github.com/repos/apache/flink","forks_url":"https://api.github.com/repos/apache/flink/forks","keys_url":"https://api.github.com/repos/apache/flink/keys{/key_id}","collaborators_url":"https://api.github.com/repos/apache/flink/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/apache/flink/teams","hooks_url":"https://api.github.com/repos/apache/flink/hooks","issue_events_url":"https://api.github.com/repos/apache/flink/issues/events{/number}","events_url":"https://api.github.com/repos/apache/flink/events","assignees_url":"https://api.github.com/repos/apache/flink/assignees{/user}","branches_url":"https://api.github.com/repos/apache/flink/branches{/branch}","tags_url":"https://api.github.com/repos/apache/flink/tags","blobs_url":"https://api.github.com/repos/apache/flink/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/apache/flink/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/apache/flink/git/refs{/sha}","trees_url":"https://api.github.com/repos/apache/flink/git/trees{/sha}","statuses_url":"https://api.github.com/repos/apache/flink/statuses/{sha}","languages_url":"https://api.github.com/repos/apache/flink/languages","stargazers_url":"https://api.github.com/repos/apache/flink/stargazers","contributors_url":"https://api.github.com/repos/apache/flink/contributors","subscribers_url":"https://api.github.com/repos/apache/flink/subscribers","subscription_url":"https://api.github.com/repos/apache/flink/subscription","commits_url":"https://api.github.com/repos/apache/flink/commits{/sha}","git_commits_url":"https://api.github.com/repos/apache/flink/git/commits{/sha}","comments_url":"https://api.github.com/repos/apache/flink/comments{/number}","issue_comment_url":"https://api.github.com/repos/apache/flink/issues/comments{/number}","contents_url":"https://api.github.com/repos/apache/flink/contents/{+path}","compare_url":"https://api.github.com/repos/apache/flink/compare/{base}...{head}","merges_url":"https://api.github.com/repos/apache/flink/merges","archive_url":"https://api.github.com/repos/apache/flink/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/apache/flink/downloads","issues_url":"https://api.github.com/repos/apache/flink/issues{/number}","pulls_url":"https://api.github.com/repos/apache/flink/pulls{/number}","milestones_url":"https://api.github.com/repos/apache/flink/milestones{/number}","notifications_url":"https://api.github.com/repos/apache/flink/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/apache/flink/labels{/name}","releases_url":"https://api.github.com/repos/apache/flink/releases{/id}","created_at":"2014-06-07T07:00:10Z","updated_at":"2015-09-08T08:46:59Z","pushed_at":"2015-09-09T02:26:37Z","git_url":"git://github.com/apache/flink.git","ssh_url":"git@github.com:apache/flink.git","clone_url":"https://github.com/apache/flink.git","svn_url":"https://github.com/apache/flink","homepage":null,"size":2640397,"stargazers_count":606,"watchers_count":606,"language":"Java","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":407,"mirror_url":"git://git.apache.org/incubator-flink.git","open_issues_count":82,"forks":407,"open_issues":82,"watchers":606,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/flink/pulls/1110"},"html":{"href":"https://github.com/apache/flink/pull/1110"},"issue":{"href":"https://api.github.com/repos/apache/flink/issues/1110"},"comments":{"href":"https://api.github.com/repos/apache/flink/issues/1110/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/flink/pulls/1110/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/flink/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/flink/pulls/1110/commits"},"statuses":{"href":"https://api.github.com/repos/apache/flink/statuses/b4b431471736cd32a50b49cc9e91e038a4387808"}}}}