{"id":207873,"date":"2025-07-08T15:38:14","date_gmt":"2025-07-08T07:38:14","guid":{"rendered":"https:\/\/server.hk\/cnblog\/207873\/"},"modified":"2025-07-08T15:38:14","modified_gmt":"2025-07-08T07:38:14","slug":"%e4%bb%8e-golang-%e4%b8%ad%e5%8f%97%e9%99%90%e9%94%ae%e8%8c%83%e5%9b%b4%e5%86%85%e7%9a%84%e6%98%a0%e5%b0%84%e7%94%9f%e6%88%90%e7%9a%84%e5%88%87%e7%89%87%e4%b8%ad%e9%9a%8f%e6%9c%ba%e9%80%89%e6%8b%a9","status":"publish","type":"post","link":"https:\/\/server.hk\/cnblog\/207873\/","title":{"rendered":"\u4ece golang \u4e2d\u53d7\u9650\u952e\u8303\u56f4\u5185\u7684\u6620\u5c04\u751f\u6210\u7684\u5207\u7247\u4e2d\u968f\u673a\u9009\u62e9\u5143\u7d20\u3002\u6709 O(1) \u7684\u6377\u5f84\u5417\uff1f"},"content":{"rendered":"

<\/b> <\/p>\n

\u5f53\u524d\u4f4d\u7f6e\uff1a ><\/span> ><\/span> ><\/span> ><\/span> \u4ece golang \u4e2d\u53d7\u9650\u952e\u8303\u56f4\u5185\u7684\u6620\u5c04\u751f\u6210\u7684\u5207\u7247\u4e2d\u968f\u673a\u9009\u62e9\u5143\u7d20\u3002\u6709 O(1) \u7684\u6377\u5f84\u5417\uff1f<\/span><\/p>\n

\u6765\u6e90\uff1astackoverflow<\/span>
\n2024-04-26 11:39:37<\/span>
\n<\/i>0\u6d4f\u89c8<\/span>
\n<\/i>\u6536\u85cf<\/span> <\/p>\n

\u73cd\u60dc\u65f6\u95f4\uff0c\u52e4\u594b\u5b66\u4e60\uff01\u4eca\u5929\u7ed9\u5927\u5bb6\u5e26\u6765\u300a\u4ece golang \u4e2d\u53d7\u9650\u952e\u8303\u56f4\u5185\u7684\u6620\u5c04\u751f\u6210\u7684\u5207\u7247\u4e2d\u968f\u673a\u9009\u62e9\u5143\u7d20\u3002\u6709 O(1) \u7684\u6377\u5f84\u5417\uff1f\u300b<\/span>\uff0c\u6b63\u6587\u5185\u5bb9\u4e3b\u8981\u6d89\u53ca\u5230<\/span>\u7b49\u7b49\uff0c\u5982\u679c\u4f60\u6b63\u5728\u5b66\u4e60Golang<\/span>\uff0c\u6216\u8005\u662f\u5bf9Golang<\/span>\u6709\u7591\u95ee\uff0c\u6b22\u8fce\u5927\u5bb6\u5173\u6ce8\u6211\uff01\u540e\u9762\u6211\u4f1a\u6301\u7eed\u66f4\u65b0\u76f8\u5173\u5185\u5bb9\u7684\uff0c\u5e0c\u671b\u90fd\u80fd\u5e2e\u5230\u6b63\u5728\u5b66\u4e60\u7684\u5927\u5bb6\uff01<\/p>\n

\u95ee\u9898\u5185\u5bb9
\n <\/p>\n

\u5728\u6211\u7684\u6a21\u62df\u591a\u7c92\u5b50\u8fdb\u5316\u7684\u7a0b\u5e8f\u4e2d\uff0c\u6211\u6709\u4e00\u4e2a\u5730\u56fe\uff0c\u5b83\u91c7\u7528\u952e\u503c pop<\/code> \uff08\u79cd\u7fa4\u5927\u5c0f\uff09\u5e76\u8fd4\u56de\u5305\u542b\u5177\u6709\u6b64\u79cd\u7fa4\u7684\u7ad9\u70b9\u7684\u5207\u7247\uff1amymap[pop][]int<\/code>\u3002\u8fd9\u4e9b\u5207\u7247\u901a\u5e38\u90fd\u5f88\u5927\u3002 <\/p>\n

\u5728\u6bcf\u4e2a\u8fdb\u5316\u6b65\u9aa4\u4e2d\uff0c\u6211\u9009\u62e9\u968f\u673a\u7fa4\u4f53\u5927\u5c0f randompop<\/code>\u3002\u7136\u540e\uff0c\u6211\u60f3\u968f\u673a\u9009\u62e9\u4e00\u4e2a\u4eba\u53e3\u81f3\u5c11\u4e3a randompop<\/code> \u7684\u7ad9\u70b9\u3002 sitechosen<\/code> \u7528\u4e8e\u66f4\u65b0\u6211\u7684\u4eba\u53e3\u7ed3\u6784\uff0c\u6211\u5229\u7528\u7b2c\u4e8c\u4e2a\u5730\u56fe\u6765\u6709\u6548\u66f4\u65b0 mymap \u952e\u3002\u6211\u5f53\u524d\uff08\u7f13\u6162\uff09\u7684\u5b9e\u73b0\u770b\u8d77\u6765\u50cf <\/p>\n

func Evolve( ..., myMap map[int][]int ,...){\n\n    RandomPop = rand.Intn(rangeofpopulation)+1\n\n    for i:=RandPop,; i<rangeofpopulation;i++{\n        preallocatedslice=append(preallocatedslice,myMap[i]...)\n    }\n\n    randomindex:= rand.Intn(len(preallocatedslice))\n    sitechosen= preallocatedslice[randomindex]\n\n    UpdateFunction(site)\n\n    \/\/reset preallocated slice \n    preallocatedslice=preallocatedslice[0:0]\n\n}<\/pre>\n
\u8fd9\u6bb5\u4ee3\u7801\uff08\u663e\u7136\uff09\u5728\u5c06\u503c\u4ece\u6620\u5c04\u590d\u5236\u5230\u9884\u5206\u914d\u5207\u7247\u65f6\u9047\u5230\u4e86\u5de8\u5927\u7684\u74f6\u9888\uff0cruntime.memmove \u5360\u7528\u4e86\u6211 87% \u7684 cpu \u4f7f\u7528\u7387\u3002\u6211\u60f3\u77e5\u9053\u662f\u5426\u6709\u4e00\u79cd o(1) \u65b9\u6cd5\u53ef\u4ee5\u968f\u673a\u9009\u62e9 mymap \u6307\u793a\u7684\u5207\u7247\u5e76\u96c6\u4e2d\u5305\u542b\u7684\u6761\u76ee\uff0c\u5176\u952e\u503c\u4ecb\u4e8e 0<\/code> \u548c randompop<\/code> \u4e4b\u95f4\uff1f\u5982\u679c\u6709\u4eba\u77e5\u9053\u7684\u8bdd\uff0c\u6211\u5bf9\u5141\u8bb8\u60a8\u64cd\u4f5c\u81ea\u5b9a\u4e49\u54c8\u5e0c\u8868\u7684\u8f6f\u4ef6\u5305\u6301\u5f00\u653e\u6001\u5ea6\u3002\u5efa\u8bae\u4e0d\u9700\u8981\u4fdd\u8bc1\u5e76\u53d1\u5b89\u5168<\/p>\n
\u5c1d\u8bd5\u8fc7\u7684\u5176\u4ed6\u4e8b\u60c5\uff1a\u6211\u4e4b\u524d\u8ba9\u6211\u7684\u5730\u56fe\u8bb0\u5f55\u4e86\u6240\u6709\u503c\u81f3\u5c11\u4e3a pop<\/code> \u7684\u7ad9\u70b9\uff0c\u4f46\u8fd9\u5360\u7528\u4e86 >10gb \u7684\u5185\u5b58\uff0c\u800c\u4e14\u5f88\u611a\u8822\u3002\u6211\u5c1d\u8bd5\u5c06\u6307\u9488\u9690\u85cf\u5230\u76f8\u5173\u5207\u7247\u4ee5\u521b\u5efa\u67e5\u627e\u5207\u7247\uff0c\u4f46 go \u7981\u6b62\u8fd9\u6837\u505a\u3002\u6211\u53ef\u4ee5\u603b\u7ed3\u6bcf\u4e2a\u5207\u7247\u7684\u957f\u5ea6\u5e76\u57fa\u4e8e\u6b64\u751f\u6210\u4e00\u4e2a\u968f\u673a\u6570\uff0c\u7136\u540e\u6309\u957f\u5ea6\u8fed\u4ee3 mymap \u4e2d\u7684\u5207\u7247\uff0c\u4f46\u8fd9\u6bd4\u4ec5\u4fdd\u7559\u4eba\u53e3\u7684\u66f4\u65b0 cdf \u5e76\u8fdb\u884c\u4e8c\u5206\u641c\u7d22\u8981\u6162\u5f97\u591a\u5728\u4e0a\u9762\u3002\u4e8c\u5206\u67e5\u627e\u901f\u5ea6\u5f88\u5feb\uff0c\u4f46\u66f4\u65b0 cdf\uff08\u5373\u4f7f\u624b\u52a8\u5b8c\u6210\uff09\u4e5f\u662f o(n)\u3002\u6211\u771f\u7684\u5e0c\u671b\u6ee5\u7528\u54c8\u5e0c\u8868\u6765\u52a0\u901f\u968f\u673a\u9009\u62e9\u548c\u66f4\u65b0\uff08\u5982\u679c\u53ef\u80fd\u7684\u8bdd\uff09<\/p>\n
\u6211\u7684\u4e00\u4e2a\u6a21\u7cca\u7684\u60f3\u6cd5\u662f\u7f16\u9020\u67d0\u79cd\u5730\u56fe\u7684\u5d4c\u5957\u7ed3\u6784\uff0c\u6307\u5411\u5176\u5185\u5bb9\uff0c\u5e76\u4e14\u8fd8\u6307\u5411\u5177\u6709\u6bd4\u4ed6\u4eec\u7684\u952e\u5c11\u7684\u952e\u6216\u5176\u4ed6\u4e1c\u897f\u7684\u5730\u56fe\u3002 <\/p>\n
 <\/p>\n
\u89e3\u51b3\u65b9\u6848<\/h2>\n
 <\/p>\n
\u6211\u6b63\u5728\u67e5\u770b\u60a8\u7684\u4ee3\u7801\uff0c\u6211\u6709\u4e00\u4e2a\u95ee\u9898\u3002 \u4e3a\u4ec0\u4e48\u5fc5\u987b\u5c06\u503c\u4ece\u5730\u56fe\u590d\u5236\u5230\u5207\u7247\uff1f\u6211\u7684\u610f\u601d\u662f\uff0c\u6211\u8ba4\u4e3a\u6211\u6b63\u5728\u9075\u5faa\u80cc\u540e\u7684\u903b\u8f91……\u4f46\u6211\u60f3\u77e5\u9053\u662f\u5426\u6709\u529e\u6cd5\u8df3\u8fc7\u8fd9\u4e00\u6b65\u3002<\/p>\n
\u6240\u4ee5\u6211\u4eec\u6709\uff1a<\/p>\n
func evolve( ..., mymap map[int][]int ,...){\n\n    randompop = rand.intn(rangeofpopulation)+1\n\n    for i:=randpop,; i<rangeofpopulation;i++{\n        \/\/ slice of preselected `sites`. one of this will be 'sitechosen'\n        \/\/ we expect to have `n sites` on `preallocatedslice`\n        \/\/ where `n` is the amount of iterations, \n        \/\/ ie; n = rangeofpopulation - randpop\n        preallocatedslice=append(preallocatedslice,mymap[i]...) \n    }\n\n    \/\/ once we have a list of sites, we select `one`\n    \/\/ under a normal distribution every site ha a chance of 1\/n to be selected.\n    randomindex:= rand.intn(len(preallocatedslice))\n    sitechosen= preallocatedslice[randomindex]\n\n    updatefunction(site)\n    ...\n\n}<\/pre>\n
\u4f46\u662f\u5982\u679c\u6211\u4eec\u5c06\u5176\u66f4\u6539\u4e3a\uff1a<\/p>\n
func Evolve( ..., myMap map[int][]int ,...){\n\n    if len(myMap) == 0 {\n        \/\/ Nothing to do, print a log! \n        return\n    }\n\n    \/\/ This variable will hold our site chosen!\n    var siteChosen []int\n\n    \/\/ Our random population size is a value from 1 to rangeOfPopulation \n    randPopSize := rand.Intn(rangeOfPopulation) + 1\n\n    for i := randPopSize; i < rangeOfPopulation; i++ {\n        \/\/ We are going to pretend that the current candidate is the siteChosen \n        siteChosen = myMap[i]\n\n        \/\/ Now, instead of copying `myMap[i]` to preAllocatedSlice\n        \/\/ We will test if the current candidate is actually the 'siteChosen` here:\n\n        \/\/ We know that the chances for an specific site to be the chosen is 1\/n,\n        \/\/ where n = rangeOfPopulation - randPopSize\n        n := float64(rangeOfPopulation - randPopSize)\n        \/\/ we roll the dice...\n        isTheChosenOne := rand.Float64() > 1\/n\n\n        if isTheChosenOne {\n            \/\/ If the candidate is the Chosen site, \n            \/\/ then we don't need to iterate over all the other elements.\n            break\n        }\n\n    }\n\n    \/\/ here we know that `siteChosen` is a.- a selected candidate, or \n    \/\/ b.- the last element assigned in the loop \n    \/\/ (in the case that `isTheChosenOne` was always false [which is a probable scenario])\n    UpdateFunction(siteChosen)\n    ...\n}<\/pre>\n
\u6b64\u5916\uff0c\u5982\u679c\u60a8\u60f3\u53ef\u4ee5\u5728\u5faa\u73af\u5916\u8ba1\u7b97 n<\/code> \u6216 1\/n<\/code> \u3002 \u56e0\u6b64\uff0c\u6211\u4eec\u7684\u60f3\u6cd5\u662f\u5728\u5faa\u73af\u5185\u6d4b\u8bd5\u5019\u9009\u8005\u662f\u5426\u662f sitechosen\uff0c\u5e76\u907f\u514d\u5c06\u5019\u9009\u8005\u590d\u5236\u5230\u6b64\u9884\u9009\u6c60\u4e2d\u3002<\/p>\n
\u4eca\u5929\u5173\u4e8e\u300a\u4ece golang \u4e2d\u53d7\u9650\u952e\u8303\u56f4\u5185\u7684\u6620\u5c04\u751f\u6210\u7684\u5207\u7247\u4e2d\u968f\u673a\u9009\u62e9\u5143\u7d20\u3002\u6709 O(1) \u7684\u6377\u5f84\u5417\uff1f\u300b\u7684\u5185\u5bb9\u4ecb\u7ecd\u5c31\u5230\u6b64\u7ed3\u675f\uff0c\u5982\u679c\u6709\u4ec0\u4e48\u7591\u95ee\u6216\u8005\u5efa\u8bae\uff0c\u53ef\u4ee5\u5728\u516c\u4f17\u53f7\u4e0b\u591a\u591a\u56de\u590d\u4ea4\u6d41\uff1b\u6587\u4e2d\u82e5\u6709\u4e0d\u6b63\u4e4b\u5904\uff0c\u4e5f\u5e0c\u671b\u56de\u590d\u7559\u8a00\u4ee5\u544a\u77e5\uff01<\/p>\n","protected":false},"excerpt":{"rendered":"
\u5f53\u524d\u4f4d\u7f6e\uff1a > > ...<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4925],"tags":[],"class_list":["post-207873","post","type-post","status-publish","format-standard","hentry","category-4925"],"_links":{"self":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts\/207873","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/comments?post=207873"}],"version-history":[{"count":0,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts\/207873\/revisions"}],"wp:attachment":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/media?parent=207873"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/categories?post=207873"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/tags?post=207873"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}