Comments 25
не «причём тут», а «при чём тут». раздельно
Какой то уж очень не читаемый код для компании, которая учит python'у
let's agree to disagree
Возможно вы кого то обделили? 3.141592653589793
# python3.6
find_nums_in_pi({15, 59, 92})
# {15: 3, 59: 4, 92: 62}# python3.6
find_nums_in_pi([15, 59, 92])
# {15: 3, 92: 5, 59: 61}find_nums_in_pi({15, 59, 92}, 4)
# RuntimeError: Circuit breaker!о, круто, спасибо за помощь! я поправил
find_nums_in_pi({159, 59})
# IndexError: string index out of rangeэтот кейс не проваливается на самом деле, но я нашел и исправил энивей)
Я вас, наверное, уже задолбал, но все еще если first_n > len(nums), то получим бесконечный цикл https://habrahabr.ru/company/otus/blog/332180/#comment_10295658
find_nums_in_pi([59, 159, 230])
# {59: 61, 159: 3, 230: 63}И вот почему
# pi = 3.14_159_2653589793
for pos in itertools.count():
d = str(pi_gen.next())
found_num = None
for cur_num in _nums:
cur_num.move_p(d)
# whole number found
if cur_num.p == cur_num.l:
nums_pos[cur_num.n] = pos - cur_num.l + 1
# found enough numbers
if len(nums_pos) == first_n:
return nums_pos
found_num = cur_num.n
# create new search array without found number
if found_num:
_nums = [num for num in _nums if num.n != found_num]когда мы доходим до 9 то found_num будет равно 159, т.к. он перезапишет 59 и из _nums будет удален только 159, а 59 будет найден дальше
Чтобы не подбирать числа придумаем свое пи:
def pi_digits():
fake_pi = '3143338327989793238462643383279'
for p in fake_pi:
yield p
q, r, t, k, n, l = 1, 0, 1, 1, 3, 3
while True:
if 4 * q + r - t < n * t:
yield n
q, r, t, k, n, l = (10*q, 10*(r-n*t), t, k, (10*(3*q+r))//t-10*n, l)
else:
q, r, t, k, n, l = (q*k, (2*q+r)*l, t*l, k+1, (q*(7*k+2)+r*l)//(t*l), l+2)И снова не правильно находит
class _Num(object):
def __init__(self, n):
self.n = n
self.s = str(n)
self.p = 0 # pointer in number string representation
self.l = len(self.s)
def move_p(self, d):
if self.p < self.l and d == self.s[self.p]:
self.p += 1
else:
self.p = 0 if d != self.s[0] else 1
#################
find_nums_in_pi({338})
# {338: 24}градус абсурда растет, но я не пожалел времени и поправил)
При чем тут абсурд, ваш код неправильно работает на корректных данных (не всегда, но при определенных обстоятельствах).
Более того — ниже я вам дал более простой и в тоже время быстрый код (в 30-50 раз). Но тем не менее вы все еще полагаете, что ваш код читаем и хорош, и признавать неправоту не желаете не взирая на то количество ошибок, которое я вам указал. Что же — это ваше право.
самое простое и быстро решение и так есть в начале поста.
ваше решение ниже, конечно, быстрее, но суть была не в том, чтобы придумать самое быстрее решение. Знаете как будет еще быстрее? Сгенерить цифры заранее и искать по индексу, например. А можно еще на C переписать. Можно даже, в порядке бреда, натренировать нейронку предсказывать позицию.
Еще в моем коде были(есть и будут) ошибки. К счастью не было задачи правильно искать число в Пи, была задача случайно выбрать несколько человек каким-нибудь забавным способом.
Ваше желание доказать, что я неправ в чем-то понятно и объяснимо (=
ваше решение ниже, конечно, быстрее, но суть была не в том, чтобы придумать самое быстрее решение. Знаете как будет еще быстрее? Сгенерить цифры заранее и искать по индексу, например. А можно еще на C переписать. Можно даже, в порядке бреда, натренировать нейронку предсказывать позицию.
Еще в моем коде были(есть и будут) ошибки. К счастью не было задачи правильно искать число в Пи, была задача случайно выбрать несколько человек каким-нибудь забавным способом.
Ваше желание доказать, что я неправ в чем-то понятно и объяснимо (=
… ваше решение ниже, конечно, быстрее, но суть была не в том, чтобы придумать самое быстрее решение ...
Да, но оно решает именно ту задачу, тем методом (поиском по числу пи), на том языке которые вы выбрали. При этом оно быстрее, понятнее, работает правильно.
Ваше желание доказать, что я неправ в чем-то понятно и объяснимо (=
Будь этот пост от студента, который учится писать на python — молодец, что то делает, пишет, учится. Пускай сейчас не особо правильно и перемудрено, но это не плохо, ведь он изучает возможности языка.
Но этот пост от компании, которая учит других людей писать на python'е.
Критикуешь — предлагай, не исключаю, что и тут найдутся ошибки:
MAX_POS = 10 ** 4
class _Num:
def __init__(self, n):
self.s = str(n)
self.p = 0 # pointer in number string representation
def move_p(self, d):
if d == self.s[self.p]:
self.p += 1
else:
self.p = 0
def is_whole_found(self):
return self.p == len(self.s)
def find_next(_nums, pos, d):
nums_pos = {}
nums = {}
for n, cur_num in _nums.items():
cur_num.move_p(d)
if cur_num.is_whole_found():
nums_pos[n] = pos - len(cur_num.s) + 1
else:
nums[n] = cur_num
return nums, nums_pos
def find_nums_in_pi(nums: set, first_n: int = None):
pi_gen = pi_digits()
max_count = min(first_n or len(nums), len(nums))
_nums = {n: _Num(n) for n in nums}
nums_pos = {}
for pos, d in enumerate(pi_gen):
_nums, next_pos = find_next(_nums, pos, str(d))
nums_pos.update(next_pos)
if len(nums_pos) >= max_count:
return nums_pos
if pos % 1000 == 0:
print("Current Pi position: %s. Nums found: %s" % (pos, len(nums_pos)))
if pos == MAX_POS:
raise RuntimeError("Circuit breaker!")ок вариант, я хотел так вынести проверку на то, что число найдено и прочее, но мне стало жалко дополнительных call'ов ¯\_(ツ)_/¯
Если исходить из того что все числа одной длины, то вот суперкиллер:
def ff(nums: set, first_n: int = None):
pi_gen = pi_digits()
max_count = min(first_n or len(nums), len(nums))
_nums = nums
nums_pos = {}
start = ''
for p in range(6):
start += str(next(pi_gen))
for pos, d in enumerate(pi_gen):
if int(start) in _nums:
nums_pos[int(start)] = pos
_nums = _nums - {int(start)}
if len(nums_pos) >= max_count:
return nums_pos
start = start[1:] + str(d)
if pos % 10000 == 0:
print("Current Pi position: %s. Nums found: %s" % (pos, len(nums_pos)))
if pos == MAX_POS:
raise RuntimeError("Circuit breaker!")r = set(range(10**5, 10**6))
c = ff(r, 666)
print("res: ", c)
a = find_nums_in_pi(r, 66)
print("res: ", a)
b = _find_nums_in_pi(r, 66)
print("res: ", b)
print(a == b, a == c)Вывод
Current Pi position: 0. Nums found: 1
ff: 16.3442
res: {314159: 0, 141592: 1, 415926: 2, 159265: 3, 592653: 4, 926535: 5, 265358: 6, 653589: 7, 535897: 8, 358979: 9, 589793: 10, 897932: 11, 979323: 12, 793238: 13, 932384: 14, 323846: 15, 238462: 16, 384626: 17, 846264: 18, 462643: 19, 626433: 20, 264338: 21, 643383: 22, 433832: 23, 338327: 24, 383279: 25, 832795: 26, 327950: 27, 279502: 28, 795028: 29, 950288: 30, 502884: 31, 288419: 33, 884197: 34, 841971: 35, 419716: 36, 197169: 37, 971693: 38, 716939: 39, 169399: 40, 693993: 41, 939937: 42, 399375: 43, 993751: 44, 937510: 45, 375105: 46, 751058: 47, 510582: 48, 105820: 49, 582097: 51, 820974: 52, 209749: 53, 974944: 55, 749445: 56, 494459: 57, 944592: 58, 445923: 59, 459230: 60, 592307: 61, 923078: 62, 230781: 63, 307816: 64, 781640: 66, 816406: 67, 164062: 68, 640628: 69, 406286: 70, 628620: 72, 286208: 73, 862089: 74, 620899: 75, 208998: 76, 899862: 78, 998628: 79, 986280: 80, 862803: 81, 628034: 82, 280348: 83, 803482: 84, 348253: 86, 482534: 87, 825342: 88, 253421: 89, 534211: 90, 342117: 91, 421170: 92, 211706: 93, 117067: 94, 170679: 95, 706798: 96, 679821: 98, 798214: 99, 982148: 100, 821480: 101, 214808: 102, 148086: 103, 480865: 104, 808651: 105, 865132: 107, 651328: 108, 513282: 109, 132823: 110, 328230: 111, 282306: 112, 823066: 113, 230664: 114, 306647: 115, 664709: 117, 647093: 118, 470938: 119, 709384: 120, 938446: 122, 384460: 123, 844609: 124, 446095: 125, 460955: 126, 609550: 127, 955058: 129, 550582: 130, 505822: 131, 582231: 133, 822317: 134, 223172: 135, 231725: 136, 317253: 137, 172535: 138, 725359: 139, 253594: 140, 535940: 141, 359408: 142, 594081: 143, 940812: 144, 408128: 145, 812848: 147, 128481: 148, 284811: 149, 848111: 150, 481117: 151, 811174: 152, 111745: 153, 117450: 154, 174502: 155, 745028: 156, 450284: 157, 502841: 158, 284102: 160, 841027: 161, 410270: 162, 102701: 163, 270193: 165, 701938: 166, 193852: 168, 938521: 169, 385211: 170, 852110: 171, 521105: 172, 211055: 173, 110555: 174, 105559: 175, 555964: 177, 559644: 178, 596446: 179, 964462: 180, 644622: 181, 446229: 182, 462294: 183, 622948: 184, 229489: 185, 294895: 186, 948954: 187, 489549: 188, 895493: 189, 954930: 190, 549303: 191, 493038: 192, 930381: 193, 303819: 194, 381964: 196, 819644: 197, 196442: 198, 964428: 199, 644288: 200, 442881: 201, 428810: 202, 288109: 203, 881097: 204, 810975: 205, 109756: 206, 975665: 208, 756659: 209, 566593: 210, 665933: 211, 659334: 212, 593344: 213, 933446: 214, 334461: 215, 344612: 216, 446128: 217, 461284: 218, 612847: 219, 128475: 220, 284756: 221, 847564: 222, 475648: 223, 756482: 224, 564823: 225, 648233: 226, 482337: 227, 823378: 228, 233786: 229, 337867: 230, 378678: 231, 786783: 232, 867831: 233, 678316: 234, 783165: 235, 831652: 236, 316527: 237, 165271: 238, 652712: 239, 527120: 240, 271201: 241, 712019: 242, 120190: 243, 201909: 244, 190914: 246, 909145: 247, 914564: 249, 145648: 250, 456485: 251, 564856: 252, 648566: 253, 485669: 254, 856692: 255, 566923: 256, 669234: 257, 692346: 258, 923460: 259, 234603: 260, 346034: 261, 460348: 262, 603486: 263, 348610: 265, 486104: 266, 861045: 267, 610454: 268, 104543: 269, 454326: 271, 543266: 272, 432664: 273, 326648: 274, 266482: 275, 664821: 276, 648213: 277, 482133: 278, 821339: 279, 213393: 280, 133936: 281, 339360: 282, 393607: 283, 936072: 284, 360726: 285, 607260: 286, 726024: 288, 260249: 289, 602491: 290, 249141: 292, 491412: 293, 914127: 294, 141273: 295, 412737: 296, 127372: 297, 273724: 298, 737245: 299, 372458: 300, 724587: 301, 245870: 302, 458700: 303, 587006: 304, 870066: 305, 700660: 306, 660631: 309, 606315: 310, 631558: 312, 315588: 313, 155881: 314, 558817: 315, 588174: 316, 881748: 317, 817488: 318, 174881: 319, 748815: 320, 488152: 321, 881520: 322, 815209: 323, 152092: 324, 520920: 325, 209209: 326, 920962: 328, 209628: 329, 962829: 331, 628292: 332, 282925: 333, 829254: 334, 292540: 335, 925409: 336, 254091: 337, 540917: 338, 409171: 339, 917153: 341, 171536: 342, 715364: 343, 153643: 344, 536436: 345, 364367: 346, 643678: 347, 436789: 348, 367892: 349, 678925: 350, 789259: 351, 892590: 352, 925903: 353, 259036: 354, 590360: 355, 903600: 356, 360011: 358, 600113: 359, 113305: 362, 133053: 363, 330530: 364, 305305: 365, 530548: 367, 305488: 368, 548820: 370, 488204: 371, 882046: 372, 820466: 373, 204665: 374, 466521: 376, 665213: 377, 652138: 378, 521384: 379, 213841: 380, 138414: 381, 384146: 382, 841469: 383, 414695: 384, 146951: 385, 469519: 386, 695194: 387, 951941: 388, 519415: 389, 194151: 390, 941511: 391, 415116: 392, 151160: 393, 511609: 394, 116094: 395, 160943: 396, 609433: 397, 943305: 399, 433057: 400, 330572: 401, 305727: 402, 572703: 404, 727036: 405, 270365: 406, 703657: 407, 365759: 409, 657595: 410, 575959: 411, 759591: 412, 595919: 413, 959195: 414, 591953: 415, 919530: 416, 195309: 417, 953092: 418, 530921: 419, 309218: 420, 921861: 422, 218611: 423, 186117: 424, 861173: 425, 611738: 426, 117381: 427, 173819: 428, 738193: 429, 381932: 430, 819326: 431, 193261: 432, 932611: 433, 326117: 434, 261179: 435, 611793: 436, 117931: 437, 179310: 438, 793105: 439, 931051: 440, 310511: 441, 105118: 442, 511854: 444, 118548: 445, 185480: 446, 854807: 447, 548074: 448, 480744: 449, 807446: 450, 744623: 452, 446237: 453, 462379: 454, 623799: 455, 237996: 456, 379962: 457, 799627: 458, 996274: 459, 962749: 460, 627495: 461, 274956: 462, 749567: 463, 495673: 464, 956735: 465, 567351: 466, 673518: 467, 735188: 468, 351885: 469, 518857: 470, 188575: 471, 885752: 472, 857527: 473, 575272: 474, 752724: 475, 527248: 476, 272489: 477, 724891: 478, 248912: 479, 489122: 480, 891227: 481, 912279: 482, 122793: 483, 227938: 484, 279381: 485, 793818: 486, 938183: 487, 381830: 488, 818301: 489, 183011: 490, 830119: 491, 301194: 492, 119491: 494, 194912: 495, 949129: 496, 491298: 497, 912983: 498, 129833: 499, 298336: 500, 983367: 501, 833673: 502, 336733: 503, 367336: 504, 673362: 505, 733624: 506, 336244: 507, 362440: 508, 624406: 509, 244065: 510, 440656: 511, 406566: 512, 656643: 514, 566430: 515, 664308: 516, 643086: 517, 430860: 518, 308602: 519, 860213: 521, 602139: 522, 213949: 524, 139494: 525, 394946: 526, 949463: 527, 494639: 528, 946395: 529, 463952: 530, 639522: 531, 395224: 532, 952247: 533, 522473: 534, 224737: 535, 247371: 536, 473719: 537, 737190: 538, 371907: 539, 719070: 540, 190702: 541, 907021: 542, 702179: 544, 217986: 546, 179860: 547, 798609: 548, 986094: 549, 860943: 550, 609437: 551, 943702: 553, 437027: 554, 370277: 555, 702770: 556, 277053: 558, 770539: 559, 705392: 560, 539217: 562, 392171: 563, 921717: 564, 217176: 565, 171762: 566, 717629: 567, 176293: 568, 762931: 569, 629317: 570, 293176: 571, 931767: 572, 317675: 573, 176752: 574, 767523: 575, 675238: 576, 752384: 577, 523846: 578, 238467: 579, 384674: 580, 846748: 581, 467481: 582, 674818: 583, 748184: 584, 481846: 585, 818467: 586, 184676: 587, 846766: 588, 467669: 589, 676694: 590, 766940: 591, 669405: 592, 694051: 593, 940513: 594, 405132: 595, 513200: 597, 132000: 598, 320005: 599, 200056: 600, 568127: 604, 681271: 605, 812714: 606, 127145: 607, 271452: 608, 714526: 609, 145263: 610, 452635: 611, 526356: 612, 263560: 613, 635608: 614, 356082: 615, 560827: 616, 608277: 617, 827785: 619, 277857: 620, 778577: 621, 785771: 622, 857713: 623, 577134: 624, 771342: 625, 713427: 626, 134275: 627, 342757: 628, 427577: 629, 275778: 630, 757789: 631, 577896: 632, 778960: 633, 789609: 634, 896091: 635, 960917: 636, 609173: 637, 917363: 639, 173637: 640, 736371: 641, 363717: 642, 637178: 643, 371787: 644, 717872: 645, 178721: 646, 787214: 647, 872146: 648, 721468: 649, 214684: 650, 146844: 651, 468440: 652, 684409: 653, 844090: 654, 440901: 655, 409012: 656, 901224: 658, 122495: 660, 224953: 661, 249534: 662, 495343: 663, 953430: 664, 534301: 665, 343014: 666, 430146: 667, 301465: 668, 146549: 670, 465495: 671, 654958: 672, 549585: 673, 495853: 674, 958537: 675, 585371: 676, 853710: 677, 537105: 678, 371050: 679, 710507: 680, 105079: 681, 507922: 683, 792279: 685, 922796: 686, 227968: 687, 279689: 688, 796892: 689, 968925: 690, 689258: 691, 892589: 692, 925892: 693, 258923: 694, 589235: 695, 892354: 696, 923542: 697, 235420: 698, 354201: 699, 542019: 700, 420199: 701, 201995: 702, 199561: 704, 995611: 705, 956112: 706, 561121: 707, 611212: 708, 112129: 709, 121290: 710, 212902: 711, 129021: 712, 290219: 713, 902196: 714, 219608: 716, 196086: 717, 960864: 718, 608640: 719, 864034: 721, 640344: 722, 403441: 723, 344181: 725, 441815: 726, 418159: 727, 181598: 728, 815981: 729, 159813: 730, 598136: 731, 981362: 732, 813629: 733}
Current Pi position: 0. Nums found: 0
find_nums_in_pi: 62.4308
res: {314159: 0, 141592: 1, 415926: 2, 159265: 3, 592653: 4, 926535: 5, 265358: 6, 653589: 7, 535897: 8, 358979: 9, 589793: 10, 897932: 11, 979323: 12, 793238: 13, 932384: 14, 323846: 15, 238462: 16, 384626: 17, 846264: 18, 462643: 19, 626433: 20, 264338: 21, 643383: 22, 433832: 23, 338327: 24, 832795: 26, 327950: 27, 279502: 28, 795028: 29, 950288: 30, 502884: 31, 288419: 33, 884197: 34, 419716: 36, 197169: 37, 971693: 38, 716939: 39, 169399: 40, 693993: 41, 939937: 42, 399375: 43, 993751: 44, 937510: 45, 375105: 46, 751058: 47, 510582: 48, 105820: 49, 582097: 51, 820974: 52, 209749: 53, 974944: 55, 749445: 56, 494459: 57, 944592: 58, 445923: 59, 592307: 61, 923078: 62, 230781: 63, 307816: 64, 781640: 66, 816406: 67, 164062: 68, 640628: 69, 406286: 70, 628620: 72, 286208: 73}
Current Pi position: 0. Nums found: 0
_find_nums_in_pi: 46.1488
res: {314159: 0, 141592: 1, 415926: 2, 159265: 3, 592653: 4, 926535: 5, 265358: 6, 653589: 7, 535897: 8, 358979: 9, 589793: 10, 897932: 11, 979323: 12, 793238: 13, 932384: 14, 323846: 15, 238462: 16, 384626: 17, 846264: 18, 462643: 19, 626433: 20, 264338: 21, 643383: 22, 433832: 23, 338327: 24, 832795: 26, 327950: 27, 279502: 28, 795028: 29, 950288: 30, 502884: 31, 288419: 33, 884197: 34, 419716: 36, 197169: 37, 971693: 38, 716939: 39, 169399: 40, 693993: 41, 939937: 42, 399375: 43, 993751: 44, 937510: 45, 375105: 46, 751058: 47, 510582: 48, 105820: 49, 582097: 51, 820974: 52, 209749: 53, 974944: 55, 749445: 56, 494459: 57, 944592: 58, 445923: 59, 592307: 61, 923078: 62, 230781: 63, 307816: 64, 781640: 66, 816406: 67, 164062: 68, 640628: 69, 406286: 70, 628620: 72, 286208: 73}
True FalseВозле каждой из функций в выводе указано время выполнения.
Также прошу обратить внимание что ваша функция (как и моя https://habrahabr.ru/company/otus/blog/332180/#comment_10295706) не нашли 25 елемент (383279)
PS в коде захардкорджено маленько и названия переменных/функций — не ахти, уж простите.
Я уж подумал, что речь идет о том, чтобы взять модельный геном отсюда и искать его в числе Пи
Википедия ссылается на утверждение что вопрос о нормальности числа пи открыт.
А из колмогоровской теория сложности следует то архиватор не влетит.
А из колмогоровской теория сложности следует то архиватор не влетит.
Sign up to leave a comment.
Как искать людей в числе Пи и при чем тут Python