GitHub PullRequestReviewCommentEvent at 2014-09-10 19:31:11
Repository: cockroach
Actor: tobstar87
Payload: {"action":"created","comment":{"url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/comments/17383153","id":17383153,"diff_hunk":"@@ -0,0 +1,131 @@\n+// Copyright 2014 The Cockroach Authors.float64\n+//\n+// Licensed under the Apache License, Version 2.0 (the \"License\");\n+// you may not use this file except in compliance with the License.\n+// You may obtain a copy of the License at\n+//\n+//     http://www.apache.org/licenses/LICENSE-2.0\n+//\n+// Unless required by applicable law or agreed to in writing, software\n+// distributed under the License is distributed on an \"AS IS\" BASIS,\n+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or\n+// implied. See the License for the specific language governing\n+// permissions and limitations under the License. See the AUTHORS file\n+// for names of contributors.\n+//\n+// Author: Tobias Schottdorf (tobias.schottdorf@gmail.com)\n+\n+package util\n+\n+import (\n+\t\"container/heap\"\n+\t\"math\"\n+\t\"math/rand\"\n+)\n+\n+// A WeightedValue is used to represent the items sampled by\n+// WeightedReservoirSample.\n+type WeightedValue struct {\n+\tWeight float64\n+\tValue  interface{}\n+\tkey    float64\n+}\n+\n+// Less implements the Ordered interface.\n+func (wv WeightedValue) Less(zv WeightedValue) bool {\n+\treturn wv.key < zv.key\n+}\n+\n+// A WeightedValueHeap implements a heap structure on a slice of weighted\n+// values for use in in-memory weighted reservoir sampling.\n+type WeightedValueHeap []WeightedValue\n+\n+// Len, Less and Swap implement sort.Interface.\n+func (h WeightedValueHeap) Len() int           { return len(h) }\n+func (h WeightedValueHeap) Less(i, j int) bool { return h[i].Less(h[j]) }\n+func (h WeightedValueHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }\n+\n+// Push appends an element to the slice.\n+func (h *WeightedValueHeap) Push(x interface{}) { *h = append(*h, x.(WeightedValue)) }\n+\n+// Pop removes the last element of the slice.\n+func (h *WeightedValueHeap) Pop() interface{} {\n+\told := *h\n+\tn := len(old)\n+\tx := old[n-1]\n+\t*h = old[0 : n-1]\n+\treturn x\n+}\n+\n+// A WeightedReservoirSample implements the weighted reservoir sampling\n+// algorithm as proposed by Efraimidis-Spirakis (2005).\n+type WeightedReservoirSample struct {\n+\tsize      int\n+\tHeap      heap.Interface\n+\tthreshold float64 // keeps track of the minimal key.\n+}\n+\n+// NewInMemWeightedReservoirSample creates a WeightedReservoirSample operating\n+// on a WeightedValueHeap and returns both.\n+func NewInMemWeightedReservoirSample(size int) (*WeightedReservoirSample,\n+\t*WeightedValueHeap) {\n+\twvh := make(WeightedValueHeap, 0, size)\n+\treturn NewWeightedReservoirSample(size, &wvh), &wvh\n+}\n+\n+// NewWeightedReservoirSample creates a new reservoir sample on the given\n+// heap.\n+func NewWeightedReservoirSample(size int, minHeap heap.Interface) *WeightedReservoirSample {\n+\tif size < 1 {\n+\t\tpanic(\"attempt to create a reservoir sample with invalid size\")\n+\t}\n+\trs := &WeightedReservoirSample{\n+\t\tsize:      size,\n+\t\tHeap:      minHeap,\n+\t\tthreshold: -1.0,","path":"util/sampling.go","position":85,"original_position":85,"commit_id":"8de685f66013d6e296a9c6e19b84aa3ae6a127de","original_commit_id":"8de685f66013d6e296a9c6e19b84aa3ae6a127de","user":{"login":"tobstar87","id":5076964,"avatar_url":"https://avatars.githubusercontent.com/u/5076964?v=2","gravatar_id":"c59a2412d0f9af583622f07184087fa2","url":"https://api.github.com/users/tobstar87","html_url":"https://github.com/tobstar87","followers_url":"https://api.github.com/users/tobstar87/followers","following_url":"https://api.github.com/users/tobstar87/following{/other_user}","gists_url":"https://api.github.com/users/tobstar87/gists{/gist_id}","starred_url":"https://api.github.com/users/tobstar87/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tobstar87/subscriptions","organizations_url":"https://api.github.com/users/tobstar87/orgs","repos_url":"https://api.github.com/users/tobstar87/repos","events_url":"https://api.github.com/users/tobstar87/events{/privacy}","received_events_url":"https://api.github.com/users/tobstar87/received_events","type":"User","site_admin":false},"body":"done.","created_at":"2014-09-10T19:31:11Z","updated_at":"2014-09-10T19:31:11Z","html_url":"https://github.com/cockroachdb/cockroach/pull/44#discussion_r17383153","pull_request_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/44","_links":{"self":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/comments/17383153"},"html":{"href":"https://github.com/cockroachdb/cockroach/pull/44#discussion_r17383153"},"pull_request":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/44"}}},"pull_request":{"url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/44","id":21003152,"html_url":"https://github.com/cockroachdb/cockroach/pull/44","diff_url":"https://github.com/cockroachdb/cockroach/pull/44.diff","patch_url":"https://github.com/cockroachdb/cockroach/pull/44.patch","issue_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/44","number":44,"state":"open","locked":false,"title":"add weighted reservoir sampling (AE-S)","user":{"login":"tobstar87","id":5076964,"avatar_url":"https://avatars.githubusercontent.com/u/5076964?v=2","gravatar_id":"c59a2412d0f9af583622f07184087fa2","url":"https://api.github.com/users/tobstar87","html_url":"https://github.com/tobstar87","followers_url":"https://api.github.com/users/tobstar87/followers","following_url":"https://api.github.com/users/tobstar87/following{/other_user}","gists_url":"https://api.github.com/users/tobstar87/gists{/gist_id}","starred_url":"https://api.github.com/users/tobstar87/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tobstar87/subscriptions","organizations_url":"https://api.github.com/users/tobstar87/orgs","repos_url":"https://api.github.com/users/tobstar87/repos","events_url":"https://api.github.com/users/tobstar87/events{/privacy}","received_events_url":"https://api.github.com/users/tobstar87/received_events","type":"User","site_admin":false},"body":"Implemented algorithm A-Res from http://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf, offering a reservoir sampling algorithm with the chance of each element being in the final sample being proportional to the (positive) weight assigned to each element.\nIf need arises we will fairly easily be able to implement A-ExpJ using this (but I don't think we'll ever need it) to save some random numbers.\nThe careful reviewer will observe that really I would have wanted a priority queue instead of an abstract heap (to get \"peek\") but in this version the exposition is clearer and the performance hit isn't more than a slightly worse constant depending on the reservoir size.\nA-Res will be used to generate the split key when it is needed, taking the size of key-value pairs as their weight. Other metrics are possible, allowing for a range of interesting split key criteria.","created_at":"2014-09-10T07:17:59Z","updated_at":"2014-09-10T19:31:11Z","closed_at":null,"merged_at":null,"merge_commit_sha":"33d56b9705a00712fa994234a81d5286214ce5cf","assignee":{"login":"spencerkimball","id":6147149,"avatar_url":"https://avatars.githubusercontent.com/u/6147149?v=2","gravatar_id":"6522ab39f122acdbad47abb893dd74b5","url":"https://api.github.com/users/spencerkimball","html_url":"https://github.com/spencerkimball","followers_url":"https://api.github.com/users/spencerkimball/followers","following_url":"https://api.github.com/users/spencerkimball/following{/other_user}","gists_url":"https://api.github.com/users/spencerkimball/gists{/gist_id}","starred_url":"https://api.github.com/users/spencerkimball/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/spencerkimball/subscriptions","organizations_url":"https://api.github.com/users/spencerkimball/orgs","repos_url":"https://api.github.com/users/spencerkimball/repos","events_url":"https://api.github.com/users/spencerkimball/events{/privacy}","received_events_url":"https://api.github.com/users/spencerkimball/received_events","type":"User","site_admin":false},"milestone":null,"commits_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/44/commits","review_comments_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/44/comments","review_comment_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/comments/{number}","comments_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/44/comments","statuses_url":"https://api.github.com/repos/cockroachdb/cockroach/statuses/8de685f66013d6e296a9c6e19b84aa3ae6a127de","head":{"label":"tobstar87:split","ref":"split","sha":"8de685f66013d6e296a9c6e19b84aa3ae6a127de","user":{"login":"tobstar87","id":5076964,"avatar_url":"https://avatars.githubusercontent.com/u/5076964?v=2","gravatar_id":"c59a2412d0f9af583622f07184087fa2","url":"https://api.github.com/users/tobstar87","html_url":"https://github.com/tobstar87","followers_url":"https://api.github.com/users/tobstar87/followers","following_url":"https://api.github.com/users/tobstar87/following{/other_user}","gists_url":"https://api.github.com/users/tobstar87/gists{/gist_id}","starred_url":"https://api.github.com/users/tobstar87/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tobstar87/subscriptions","organizations_url":"https://api.github.com/users/tobstar87/orgs","repos_url":"https://api.github.com/users/tobstar87/repos","events_url":"https://api.github.com/users/tobstar87/events{/privacy}","received_events_url":"https://api.github.com/users/tobstar87/received_events","type":"User","site_admin":false},"repo":{"id":23832429,"name":"cockroach","full_name":"tobstar87/cockroach","owner":{"login":"tobstar87","id":5076964,"avatar_url":"https://avatars.githubusercontent.com/u/5076964?v=2","gravatar_id":"c59a2412d0f9af583622f07184087fa2","url":"https://api.github.com/users/tobstar87","html_url":"https://github.com/tobstar87","followers_url":"https://api.github.com/users/tobstar87/followers","following_url":"https://api.github.com/users/tobstar87/following{/other_user}","gists_url":"https://api.github.com/users/tobstar87/gists{/gist_id}","starred_url":"https://api.github.com/users/tobstar87/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tobstar87/subscriptions","organizations_url":"https://api.github.com/users/tobstar87/orgs","repos_url":"https://api.github.com/users/tobstar87/repos","events_url":"https://api.github.com/users/tobstar87/events{/privacy}","received_events_url":"https://api.github.com/users/tobstar87/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/tobstar87/cockroach","description":"A Scalable, Geo-Replicated, Transactional Datastore","fork":true,"url":"https://api.github.com/repos/tobstar87/cockroach","forks_url":"https://api.github.com/repos/tobstar87/cockroach/forks","keys_url":"https://api.github.com/repos/tobstar87/cockroach/keys{/key_id}","collaborators_url":"https://api.github.com/repos/tobstar87/cockroach/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/tobstar87/cockroach/teams","hooks_url":"https://api.github.com/repos/tobstar87/cockroach/hooks","issue_events_url":"https://api.github.com/repos/tobstar87/cockroach/issues/events{/number}","events_url":"https://api.github.com/repos/tobstar87/cockroach/events","assignees_url":"https://api.github.com/repos/tobstar87/cockroach/assignees{/user}","branches_url":"https://api.github.com/repos/tobstar87/cockroach/branches{/branch}","tags_url":"https://api.github.com/repos/tobstar87/cockroach/tags","blobs_url":"https://api.github.com/repos/tobstar87/cockroach/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/tobstar87/cockroach/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/tobstar87/cockroach/git/refs{/sha}","trees_url":"https://api.github.com/repos/tobstar87/cockroach/git/trees{/sha}","statuses_url":"https://api.github.com/repos/tobstar87/cockroach/statuses/{sha}","languages_url":"https://api.github.com/repos/tobstar87/cockroach/languages","stargazers_url":"https://api.github.com/repos/tobstar87/cockroach/stargazers","contributors_url":"https://api.github.com/repos/tobstar87/cockroach/contributors","subscribers_url":"https://api.github.com/repos/tobstar87/cockroach/subscribers","subscription_url":"https://api.github.com/repos/tobstar87/cockroach/subscription","commits_url":"https://api.github.com/repos/tobstar87/cockroach/commits{/sha}","git_commits_url":"https://api.github.com/repos/tobstar87/cockroach/git/commits{/sha}","comments_url":"https://api.github.com/repos/tobstar87/cockroach/comments{/number}","issue_comment_url":"https://api.github.com/repos/tobstar87/cockroach/issues/comments/{number}","contents_url":"https://api.github.com/repos/tobstar87/cockroach/contents/{+path}","compare_url":"https://api.github.com/repos/tobstar87/cockroach/compare/{base}...{head}","merges_url":"https://api.github.com/repos/tobstar87/cockroach/merges","archive_url":"https://api.github.com/repos/tobstar87/cockroach/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/tobstar87/cockroach/downloads","issues_url":"https://api.github.com/repos/tobstar87/cockroach/issues{/number}","pulls_url":"https://api.github.com/repos/tobstar87/cockroach/pulls{/number}","milestones_url":"https://api.github.com/repos/tobstar87/cockroach/milestones{/number}","notifications_url":"https://api.github.com/repos/tobstar87/cockroach/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/tobstar87/cockroach/labels{/name}","releases_url":"https://api.github.com/repos/tobstar87/cockroach/releases{/id}","created_at":"2014-09-09T12:26:29Z","updated_at":"2014-09-10T15:47:52Z","pushed_at":"2014-09-10T16:48:34Z","git_url":"git://github.com/tobstar87/cockroach.git","ssh_url":"git@github.com:tobstar87/cockroach.git","clone_url":"https://github.com/tobstar87/cockroach.git","svn_url":"https://github.com/tobstar87/cockroach","homepage":null,"size":6954,"stargazers_count":0,"watchers_count":0,"language":"Go","has_issues":false,"has_downloads":true,"has_wiki":true,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"cockroachdb:master","ref":"master","sha":"c0e92d1e483e6611c0e0d15dcb6e9f9ce43c6ce2","user":{"login":"cockroachdb","id":6748139,"avatar_url":"https://avatars.githubusercontent.com/u/6748139?v=2","gravatar_id":null,"url":"https://api.github.com/users/cockroachdb","html_url":"https://github.com/cockroachdb","followers_url":"https://api.github.com/users/cockroachdb/followers","following_url":"https://api.github.com/users/cockroachdb/following{/other_user}","gists_url":"https://api.github.com/users/cockroachdb/gists{/gist_id}","starred_url":"https://api.github.com/users/cockroachdb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cockroachdb/subscriptions","organizations_url":"https://api.github.com/users/cockroachdb/orgs","repos_url":"https://api.github.com/users/cockroachdb/repos","events_url":"https://api.github.com/users/cockroachdb/events{/privacy}","received_events_url":"https://api.github.com/users/cockroachdb/received_events","type":"Organization","site_admin":false},"repo":{"id":16563587,"name":"cockroach","full_name":"cockroachdb/cockroach","owner":{"login":"cockroachdb","id":6748139,"avatar_url":"https://avatars.githubusercontent.com/u/6748139?v=2","gravatar_id":null,"url":"https://api.github.com/users/cockroachdb","html_url":"https://github.com/cockroachdb","followers_url":"https://api.github.com/users/cockroachdb/followers","following_url":"https://api.github.com/users/cockroachdb/following{/other_user}","gists_url":"https://api.github.com/users/cockroachdb/gists{/gist_id}","starred_url":"https://api.github.com/users/cockroachdb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cockroachdb/subscriptions","organizations_url":"https://api.github.com/users/cockroachdb/orgs","repos_url":"https://api.github.com/users/cockroachdb/repos","events_url":"https://api.github.com/users/cockroachdb/events{/privacy}","received_events_url":"https://api.github.com/users/cockroachdb/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/cockroachdb/cockroach","description":"A Scalable, Geo-Replicated, Transactional Datastore","fork":false,"url":"https://api.github.com/repos/cockroachdb/cockroach","forks_url":"https://api.github.com/repos/cockroachdb/cockroach/forks","keys_url":"https://api.github.com/repos/cockroachdb/cockroach/keys{/key_id}","collaborators_url":"https://api.github.com/repos/cockroachdb/cockroach/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/cockroachdb/cockroach/teams","hooks_url":"https://api.github.com/repos/cockroachdb/cockroach/hooks","issue_events_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/events{/number}","events_url":"https://api.github.com/repos/cockroachdb/cockroach/events","assignees_url":"https://api.github.com/repos/cockroachdb/cockroach/assignees{/user}","branches_url":"https://api.github.com/repos/cockroachdb/cockroach/branches{/branch}","tags_url":"https://api.github.com/repos/cockroachdb/cockroach/tags","blobs_url":"https://api.github.com/repos/cockroachdb/cockroach/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/cockroachdb/cockroach/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/cockroachdb/cockroach/git/refs{/sha}","trees_url":"https://api.github.com/repos/cockroachdb/cockroach/git/trees{/sha}","statuses_url":"https://api.github.com/repos/cockroachdb/cockroach/statuses/{sha}","languages_url":"https://api.github.com/repos/cockroachdb/cockroach/languages","stargazers_url":"https://api.github.com/repos/cockroachdb/cockroach/stargazers","contributors_url":"https://api.github.com/repos/cockroachdb/cockroach/contributors","subscribers_url":"https://api.github.com/repos/cockroachdb/cockroach/subscribers","subscription_url":"https://api.github.com/repos/cockroachdb/cockroach/subscription","commits_url":"https://api.github.com/repos/cockroachdb/cockroach/commits{/sha}","git_commits_url":"https://api.github.com/repos/cockroachdb/cockroach/git/commits{/sha}","comments_url":"https://api.github.com/repos/cockroachdb/cockroach/comments{/number}","issue_comment_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/comments/{number}","contents_url":"https://api.github.com/repos/cockroachdb/cockroach/contents/{+path}","compare_url":"https://api.github.com/repos/cockroachdb/cockroach/compare/{base}...{head}","merges_url":"https://api.github.com/repos/cockroachdb/cockroach/merges","archive_url":"https://api.github.com/repos/cockroachdb/cockroach/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/cockroachdb/cockroach/downloads","issues_url":"https://api.github.com/repos/cockroachdb/cockroach/issues{/number}","pulls_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls{/number}","milestones_url":"https://api.github.com/repos/cockroachdb/cockroach/milestones{/number}","notifications_url":"https://api.github.com/repos/cockroachdb/cockroach/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/cockroachdb/cockroach/labels{/name}","releases_url":"https://api.github.com/repos/cockroachdb/cockroach/releases{/id}","created_at":"2014-02-06T00:18:47Z","updated_at":"2014-09-10T19:11:52Z","pushed_at":"2014-09-10T19:02:26Z","git_url":"git://github.com/cockroachdb/cockroach.git","ssh_url":"git@github.com:cockroachdb/cockroach.git","clone_url":"https://github.com/cockroachdb/cockroach.git","svn_url":"https://github.com/cockroachdb/cockroach","homepage":null,"size":6954,"stargazers_count":1489,"watchers_count":1489,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":true,"forks_count":109,"mirror_url":null,"open_issues_count":16,"forks":109,"open_issues":16,"watchers":1489,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/44"},"html":{"href":"https://github.com/cockroachdb/cockroach/pull/44"},"issue":{"href":"https://api.github.com/repos/cockroachdb/cockroach/issues/44"},"comments":{"href":"https://api.github.com/repos/cockroachdb/cockroach/issues/44/comments"},"review_comments":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/44/comments"},"review_comment":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/comments/{number}"},"commits":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/44/commits"},"statuses":{"href":"https://api.github.com/repos/cockroachdb/cockroach/statuses/8de685f66013d6e296a9c6e19b84aa3ae6a127de"}}}}