结论
100个item带权查找10w次
bisect方法（每次查找1个，循环10w）：0.092867s
np.random.choice方法（每次查找1个，循环10w）：3.552577s
np.random.choice方法（设置size=10w）：0.006639s
更多参数
| 数据量 (testfile行数) |
查找数量n | bisect方法 | np.random.choice方法 (每次查找1个，循环n) |
np.random.choice方法 (设置size=n) |
|---|---|---|---|---|
| 100 | 10w | 0.092867 | 3.552577 | 0.006639 |
| 10w | 100 | 0.001113 | 1.996459 | 0.022885 |
| 1w | 100 | 0.000224 | 0.115010 | 0.001150 |
| 10w | 1000 | 0.012222 | 21.3085 | 0.023290 |
| 100w | 100 | 0.001579 | 20.5543 | 0.226376 |
代码
weight_choise.py
#-*- coding=utf8 -*-
import sys
import random
import bisect
import numpy as np
import time
uid_list = []
weight_list = []
weight_sum_list = []
weight_sum = 0
#bisect方法（每次查找1个，循环10w）
uid_cnt1 = {}
#np.random.choice方法（设置size=1，循环10w）
uid_cnt2 = {}
#np.random.choice方法（设置size=10w）
uid_cnt22 = {}
print('Loading')
f = open('testfile', 'r')
for line in f:
uid, ti = line.strip().split('\t')
weight = float(ti)
uid_list.append(uid)
weight_list.append(weight)
weight_sum += weight
weight_sum_list.append(weight_sum)
uid_cnt1[uid] = 0
uid_cnt2[uid] = 0
uid_cnt22[uid] = 0
if len(uid_list) == 100:
break
f.close()
for i in range(0, len(weight_list)):
weight_list[i] = weight_list[i]/weight_sum
print('Choosing')
NUM = 100000
t1 = t2 = 0
for i in range(0, NUM):
beg = time.time()
idx = bisect.bisect_right(weight_sum_list, random.random() * weight_sum_list[-1])
u1 = uid_list[idx]
end = time.time()
t1 += end - beg
beg = time.time()
u2 = np.random.choice(uid_list, 1, True, weight_list)
end = time.time()
t2 += end - beg
uid_cnt1[u1] += 1
uid_cnt2[u2[0]] += 1
beg = time.time()
u22 = np.random.choice(uid_list, NUM, True, weight_list)
end = time.time()
t3 = end - beg
print t1, t2, t3
print uid_cnt1
print uid_cnt2
for uid in u22:
uid_cnt22[uid] += 1
print uid_cnt22
testfile
19779 21.232
77447 28.651
73223 15.849
51913 40.297
73457 11.078
38101 12.103
19260 13.038
31772 62.82
57741 61.65
57035 27.828
72459 66.808
63523 19.884
66687 36.575
58699 25.661
75678 10.372
66337 110.67
74544 38.3
54095 13.232
63731 52.909
16025 23.459
53081 11.423
60331 12.504
65806 15.386
22756 58.919
17636 55.287
75057 26.746
56381 16.076
21625 16.777
64890 10.239
24393 12.283
70360 177.15
56959 13.896
77604 31.645
50253 23.914
20053 12.014
39536 12.095
37214 16.498
28922 19.659
64862 23.61
17916 22.151
19380 14.361
58537 16.037
73398 12.064
57887 34.652
63886 40.006
18194 10.577
17747 48.629
60507 13.865
65093 167.505
75299 15.065
64919 33.571
24353 41.048
60565 16.422
57442 32.688
32913 86.659
65317 66.97
27352 24.314
73675 35.233
61589 26.896
22774 23.421
76398 13.494
76411 33.549
73746 18.362
72780 13.73
51918 11.306
29572 10.002
73972 28.671
76264 31.775
56922 15.387
62620 86.727
10385 17.513
37942 89.466
75527 11.743
19889 20.173
58738 53.789
77288 30.857
73235 27.545
77326 24.613
66600 77.341
21766 37.384
62062 30.338
67818 11.524
31779 26.135
31954 89.889
20000 12.088
67349 50.726
61997 74.658
72001 14.462
27124 31.528
59698 35.234
19511 24.731
20222 22.46
20042 10.334
58747 10.158
20073 10.644
18822 44.959
35232 15.448
18659 50.007
16021 16.659
77133 26.88
输出
Loading
Choosing
0.0928673744202 3.55257725716 0.00663900375366
{'19260': 405, '65093': 5023, '57442': 968, '39536': 377, '60565': 525, '22774': 728, '63523': 629, '53081': 348, '35232': 465, '24353': 1250, '58738': 1635, '21766': 1116, '24393': 360, '56959': 401, '65806': 452, '61589': 858, '58537': 504, '77133': 849, '63886': 1181, '64862': 707, '77288': 940, '17916': 624, '73398': 361, '77604': 953, '77447': 843, '73972': 885, '19380': 443, '56922': 463, '32913': 2563, '57035': 772, '76264': 976, '37214': 475, '72780': 457, '63731': 1580, '60507': 455, '51918': 317, '70360': 5363, '20042': 348, '20053': 370, '31779': 808, '31772': 1874, '64919': 1004, '60331': 365, '19511': 729, '75527': 347, '51913': 1239, '67818': 361, '20073': 337, '20222': 705, '73675': 1012, '19779': 662, '72001': 415, '57741': 1889, '75299': 433, '17636': 1693, '18194': 297, '54095': 404, '10385': 504, '62062': 905, '66337': 3318, '75057': 776, '28922': 615, '73457': 332, '27124': 955, '66687': 1119, '77326': 749, '67349': 1540, '72459': 2110, '73223': 474, '75678': 321, '31954': 2721, '20000': 365, '59698': 1066, '58747': 322, '21625': 542, '76398': 480, '56381': 476, '61997': 2306, '73235': 844, '57887': 1111, '17747': 1460, '22756': 1765, '64890': 291, '58699': 789, '73746': 557, '76411': 989, '16021': 450, '16025': 678, '66600': 2336, '19889': 594, '74544': 1170, '65317': 2126, '18659': 1502, '62620': 2559, '38101': 358, '29572': 320, '50253': 730, '37942': 2744, '27352': 722, '18822': 1366}
{'19260': 402, '65093': 5076, '57442': 999, '39536': 363, '60565': 497, '22774': 706, '63523': 609, '53081': 360, '35232': 475, '24353': 1215, '58738': 1740, '21766': 1163, '24393': 392, '56959': 398, '65806': 471, '61589': 822, '58537': 499, '77133': 868, '63886': 1251, '64862': 725, '77288': 908, '17916': 629, '73398': 352, '77604': 944, '77447': 888, '73972': 902, '19380': 402, '56922': 488, '32913': 2625, '57035': 830, '76264': 937, '37214': 496, '72780': 454, '63731': 1588, '60507': 386, '51918': 336, '70360': 5314, '20042': 306, '20053': 365, '31779': 789, '31772': 1908, '64919': 1043, '60331': 382, '19511': 770, '75527': 372, '51913': 1181, '67818': 363, '20073': 316, '20222': 639, '73675': 1099, '19779': 653, '72001': 460, '57741': 1887, '75299': 487, '17636': 1645, '18194': 361, '54095': 364, '10385': 536, '62062': 924, '66337': 3321, '75057': 820, '28922': 590, '73457': 323, '27124': 940, '66687': 1098, '77326': 757, '67349': 1458, '72459': 2047, '73223': 482, '75678': 298, '31954': 2688, '20000': 366, '59698': 1048, '58747': 303, '21625': 530, '76398': 428, '56381': 488, '61997': 2265, '73235': 828, '57887': 1005, '17747': 1468, '22756': 1793, '64890': 328, '58699': 789, '73746': 542, '76411': 1028, '16021': 498, '16025': 745, '66600': 2315, '19889': 574, '74544': 1137, '65317': 2053, '18659': 1529, '62620': 2517, '38101': 396, '29572': 293, '50253': 754, '37942': 2726, '27352': 694, '18822': 1378}
{'19260': 408, '65093': 5107, '57442': 1000, '39536': 386, '60565': 488, '22774': 724, '63523': 623, '53081': 341, '35232': 456, '24353': 1241, '58738': 1686, '21766': 1170, '24393': 388, '56959': 398, '65806': 493, '61589': 840, '58537': 459, '77133': 828, '63886': 1247, '64862': 695, '77288': 846, '17916': 704, '73398': 374, '77604': 963, '77447': 862, '73972': 859, '19380': 455, '56922': 460, '32913': 2653, '57035': 853, '76264': 911, '37214': 510, '72780': 391, '63731': 1529, '60507': 392, '51918': 340, '70360': 5333, '20042': 332, '20053': 332, '31779': 752, '31772': 1890, '64919': 1017, '60331': 367, '19511': 781, '75527': 385, '51913': 1140, '67818': 331, '20073': 297, '20222': 702, '73675': 1066, '19779': 644, '72001': 427, '57741': 1911, '75299': 440, '17636': 1672, '18194': 307, '54095': 397, '10385': 533, '62062': 898, '66337': 3553, '75057': 766, '28922': 627, '73457': 336, '27124': 852, '66687': 1082, '77326': 809, '67349': 1513, '72459': 1953, '73223': 495, '75678': 315, '31954': 2776, '20000': 393, '59698': 1133, '58747': 300, '21625': 490, '76398': 416, '56381': 470, '61997': 2251, '73235': 829, '57887': 1044, '17747': 1478, '22756': 1775, '64890': 274, '58699': 819, '73746': 540, '76411': 1098, '16021': 531, '16025': 735, '66600': 2330, '19889': 613, '74544': 1145, '65317': 1979, '18659': 1473, '62620': 2614, '38101': 386, '29572': 329, '50253': 716, '37942': 2728, '27352': 670, '18822': 1330}
