{"id":962,"date":"2011-12-05T22:15:17","date_gmt":"2011-12-05T14:15:17","guid":{"rendered":"http:\/\/www.yewen.us\/blog\/?p=962"},"modified":"2011-12-05T22:15:17","modified_gmt":"2011-12-05T14:15:17","slug":"random-select-answers","status":"publish","type":"post","link":"https:\/\/www.yewen.us\/blog\/2011\/12\/random-select-answers\/","title":{"rendered":"\u89e3\u7b54\u968f\u673a\u62bd\u6570\u7cfb\u5217\u95ee\u9898\u5e76\u8bf4\u660e bug"},"content":{"rendered":"<p>\u5341\u6708\u4efd\u7684\u65f6\u5019\u5199\u4e86\u4e00\u7bc7 <strong>\u9762\u8bd5\u9898, \u968f\u673a\u62bd\u6837\u95ee\u9898\u53ca\u6269\u5c55<\/strong>, \u5f53\u65f6\u8fd9\u4e2a blog \u6ca1\u6574\u597d, \u53d1\u5728\u4e86\u597d\u51e0\u4e2a\u5730\u65b9<\/p>\n<ul>\n<li><a href=\"http:\/\/www.yewen.us\/blog\/2011\/10\/random-select-problem\/\">http:\/\/www.yewen.us\/blog\/2011\/10\/random-select-problem\/<\/a><\/li>\n<li><a href=\"http:\/\/hi.baidu.com\/whusnoopy\/blog\/item\/4f54b3de5d708344cdbf1a08.html\">http:\/\/hi.baidu.com\/whusnoopy\/blog\/item\/4f54b3de5d708344cdbf1a08.html<\/a><\/li>\n<li><a href=\"http:\/\/blog.renren.com\/blog\/bp\/Q7fr2sueah\">http:\/\/blog.renren.com\/blog\/bp\/Q7fr2sueah<\/a><\/li>\n<\/ul>\n<p>\u524d\u51e0\u5929\u8ddf Lee.Mars \u804a, \u53c8\u628a\u8fd9\u5806\u95ee\u9898\u89e3\u7b54\u4e86\u4e00\u904d, \u5e76\u6307\u51fa\u5176\u4e2d\u4e00\u4e2a\u95ee\u9898\u7684 bug.<\/p>\n<p>\u539f\u59cb\u7248, \u6570\u636e\u6d41 n \u9009 1. \u6784\u5efa\u4e00\u4e2a\u53ef\u5bb9\u7eb3\u4e00\u4e2a\u6570\u7684 buffer, \u6570\u636e\u6d41\u4e2d\u7b2c i \u4e2a\u6570\u8fc7\u6765\u65f6\u505a\u4e00\u6b21 [0, 1] \u7684 random, \u5982\u679c\u5c0f\u4e8e 1\/i, \u5219\u66f4\u65b0 buffer. (\u8bc1\u660e\u8fc7\u7a0b\u7565, \u5f88\u7b80\u5355\u7684)<\/p>\n<pre class=\"brush: python; title: ; notranslate\" title=\"\">buf = 0\ncnt = 0\nfor i in sys.stdin:\n  cnt += 1\n  if random.random() &lt; 1.0\/cnt:\n    buf = int(i)\n\nprint buf<\/pre>\n<p>\u52a0\u5f3a\u7248, \u6570\u636e\u6d41 n \u9009 k. \u540c\u4e0a, \u6784\u5efa\u7684 buffer \u5927\u5c0f\u53d8\u4e3a k, \u6bcf\u6b21 rand \u5c0f\u4e8e k\/i \u65f6, \u5c06 rand*i \u5bf9\u5e94\u7684 buffer \u66f4\u65b0<\/p>\n<pre class=\"brush: python; title: ; notranslate\" title=\"\">k = 3 \nbuf = &#x5B;]\ncnt = 0 \nfor i in sys.stdin:\n  cnt += 1\n  rd = int(random.random()*cnt)\n  if rd &lt; k:\n    if cnt &lt;= k:\n      buf.append(int(i))\n      buf&#x5B;cnt-1] = buf&#x5B;rd]\n    buf&#x5B;rd] = int(i)\n\nprint buf <\/pre>\n<p>\u5e26\u6743\u7248, \u5e26\u6743\u6570\u636e\u6d41 n \u9009 1. \u540c\u539f\u59cb\u7248, \u53ea\u662f\u5bf9\u6743\u91cd\u4e3a w[i] \u7684\u7b2c i \u4e2a\u6570, rand \u65f6\u5224\u65ad\u662f\u5426\u5c0f\u4e8e w[i]\/SUM(w)<\/p>\n<pre class=\"brush: python; title: ; notranslate\" title=\"\">sum = 0\nbuf = 0\ncnt = 0 \nfor i in sys.stdin:\n  cnt += 1\n  sum += int(i)\n  if random.random() &lt; float(i)\/sum:\n    buf = int(i)\n\nprint buf <\/pre>\n<p>\u5e26\u6743\u9009 k \u7248. \u8fd9\u4e2a\u6709 bug, \u65e0\u89e3, \u56e0\u4e3a\u65e0\u6cd5\u4fdd\u8bc1\u6700\u540e\u9009\u51fa\u6765\u7684 k \u4e2a\u6570, \u5176 SUM(w[k1..kk])\/sum(w[1..n]) = k\/n, \u90a3\u4e2a\u6982\u7387\u65e0\u6cd5\u7b97<\/p>\n<p>\u5206\u5e03\u5f0f\u7248, m \u4e2a\u5e8f\u5217\u6700\u540e\u9009 k. \u6bcf\u4e2a\u5e8f\u5217\u5148\u6309\u52a0\u5f3a\u7248\u9009 k \u4e2a, \u7136\u540e\u5c06 m*k \u4e2a\u6570\u653e\u5230\u4e00\u8d77, \u505a\u5e26\u6743\u7248\u7684 n \u9009 k. \u7531\u4e8e\u5e26\u6743\u9009 k \u7248\u6709 bug, \u6240\u4ee5\u8fd9\u91cc\u4f1a\u6709\u4e00\u5b9a\u8bef\u5dee. \u800c\u5b9e\u9645\u4e0a\u4e00\u822c\u7684\u5206\u5e03\u5f0f\u6846\u67b6\u662f\u53ef\u4ee5\u4fdd\u8bc1\u6bcf\u4e2a\u5e8f\u5217\u6570\u636e\u89c4\u6a21\u5206\u5e03\u90fd\u6bd4\u8f83\u5747\u5300, \u6240\u4ee5\u6700\u540e\u7684 m*k \u4e2a\u6570\u53ef\u4ee5\u5f53\u65e0\u6743\u7248\u76f4\u63a5\u9009 k, \u8fd9\u6837\u7684\u8bef\u5dee\u5728\u5de5\u4e1a\u5e94\u7528\u662f\u53ef\u4ee5\u63a5\u53d7\u7684<\/p>\n<p>\u6ce8: \u4ece n \u9009 k \u90a3\u4e2a\u5c31\u53ef\u4ee5\u5f88\u5bb9\u6613\u770b\u51fa\u6765, \u8fd9\u5176\u5b9e\u5c31\u662f\u90a3\u4e2a\u628a\u4e00\u4e2a\u5e8f\u5217\u6253\u4e71\u6210\u968f\u673a\u72b6\u6001\u7684\u7b97\u6cd5\u7b80\u5316, n \u9009 1 \u53ea\u662f n \u9009 k \u7684\u4e00\u4e2a\u7279\u4f8b<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u5341\u6708\u4efd\u7684\u65f6\u5019\u5199\u4e86\u4e00\u7bc7 \u9762\u8bd5\u9898, \u968f\u673a\u62bd\u6837\u95ee\u9898\u53ca\u6269\u5c55, \u5f53\u65f6\u8fd9\u4e2a blog \u6ca1\u6574\u597d, \u53d1\u5728\u4e86\u597d\u51e0\u4e2a\u5730\u65b9 http [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[7],"tags":[433,440],"class_list":["post-962","post","type-post","status-publish","format-standard","hentry","category-tech-notes","tag-433","tag-440"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p4aR5e-fw","_links":{"self":[{"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/posts\/962","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/comments?post=962"}],"version-history":[{"count":0,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/posts\/962\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/media?parent=962"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/categories?post=962"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/tags?post=962"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}