1
\$\begingroup\$

I am new to python and coding in general and I recently found HackerRank. I have been mostly doing easy problems until now. Today, I saw the problem "Queen's Attack II" (https://www.hackerrank.com/challenges/queens-attack-2/problem), wrote my code, and it didn't execute in time for some of the testcases. I optimized it best to what I could and then I went in the discussions, where I found a code from u/Arviy which follows basically the same algorithm as mine but the implementation was a bit different. But it ran just fine comparing all the test cases.

I also compared them to best of my knowledge, and tried to time different portions of code using time.time() from import time. In the end, I got my code to pass the test cases but it still runs about 2x slower than the other code.

Problem Summary -
A queen is standing on an n times n chessboard. The chess board's rows are numbered from 1 to n, going from bottom to top. Its columns are numbered from 1 to n, going from left to right. Each square is referenced by a tuple, (r,c), describing the row r, and column c, , where the square is located.
The queen is standing at position (r_q, c_q). In a single move, she can attack any square in any of the eight directions (left, right, up, down, and the four diagonals). There are obstacles on the chessboard, each preventing the queen from attacking any square beyond it on that path. Given the queen's position and the locations of all the obstacles, find and print the number of squares the queen can attack from her position.

Variables setup -

n, k = 100000, 100000
r_q, c_q = 1, 1
obstacles = [[1000, 1000], [714, 169], [619, 264], [609, 274], [809, 74], [819, 64], [714, 264], [714, 74], [952, 569], [623, 471], [256, 985], [934, 419], [745, 280], [926, 189], [159, 859], [106, 912], [509, 894], [170, 402], [476, 238], [173, 546], [674, 438], [539, 597], [215, 724], [675, 975], [128, 814], [789, 162], [492, 142], [694, 384], [206, 253], [347, 625], [491, 147], [243, 639], [408, 401], [850, 293], [310, 901], [925, 147], [138, 471], [610, 203], [571, 658], [724, 762], [456, 908], [710, 842], [203, 321], [972, 254], [527, 214], [945, 750], [103, 561], [374, 947], [439, 716], [958, 504], [830, 182], [902, 635], [901, 158], [804, 532], [903, 957], [126, 916], [418, 485], [493, 385], [410, 247], [217, 712], [936, 340], [805, 645], [940, 430], [194, 148], [719, 247], [872, 928], [251, 231], [136, 240], [609, 860], [401, 230], [168, 759], [531, 907], [546, 927], [729, 590], [648, 912], [407, 793], [917, 256], [671, 489], [926, 874], [438, 467], [602, 462], [239, 328], [104, 510], [260, 739], [864, 741], [837, 493], [418, 345], [798, 754], [841, 710], [169, 365], [954, 389], [160, 496], [183, 108], [741, 796], [753, 682], [159, 324], [417, 306], [261, 509], [587, 194], [805, 907], [218, 204], [591, 389], [916, 894], [963, 103], [461, 689], [937, 520], [350, 730], [436, 208], [381, 617], [546, 361], [719, 512], [305, 794], [509, 820], [915, 570], [408, 420], [609, 973], [872, 710], [465, 409], [459, 427], [918, 847], [142, 943], [457, 364], [360, 273], [276, 289], [427, 537], [317, 475], [864, 832], [845, 639], [463, 520], [741, 617], [762, 734], [160, 804], [192, 739], [289, 715], [340, 826], [827, 872], [186, 836], [967, 639], [145, 137], [581, 147], [479, 897], [203, 960], [967, 691], [891, 680], [593, 651], [172, 257], [258, 325], [351, 859], [153, 801], [705, 589], [832, 832], [718, 864], [971, 652], [567, 561], [715, 729], [689, 821], [178, 891], [962, 408], [829, 639], [561, 413], [401, 261], [491, 952], [831, 741], [271, 471], [826, 312], [482, 317], [413, 769], [231, 561], [579, 735], [769, 916], [184, 586], [820, 208], [476, 298], [587, 157], [194, 642], [341, 647], [478, 731], [951, 620], [401, 912], [837, 358], [249, 349], [158, 201], [195, 968], [294, 132], [291, 193], [158, 480], [849, 761], [832, 157], [364, 809], [293, 526], [164, 865], [193, 429], [158, 520], [342, 574], [409, 815], [627, 765], [413, 316], [426, 508], [902, 620], [278, 385], [587, 342], [982, 812], [753, 721], [176, 192], [289, 729], [845, 729], [698, 205], [597, 378], [570, 251], [853, 742], [903, 126], [546, 172], [792, 491], [160, 926], [321, 597], [835, 356], [894, 207], [153, 807], [106, 372], [716, 105], [638, 281], [814, 597], [970, 926], [175, 943], [135, 642], [372, 142], [701, 980], [720, 184], [695, 491], [682, 354], [371, 246], [421, 574], [803, 108], [429, 687], [465, 953], [157, 385], [624, 893], [201, 896], [975, 295], [635, 348], [351, 659], [127, 109], [705, 852], [471, 327], [915, 750], [720, 637], [126, 358], [506, 690], [317, 923], [285, 725], [957, 406], [372, 810], [971, 170], [920, 452], [756, 743], [791, 158], [698, 835], [576, 470], [209, 329], [902, 948], [854, 249], [347, 780], [386, 215], [713, 130], [516, 760], [964, 374], [781, 340], [763, 402], [408, 824], [476, 642], [752, 320], [605, 185], [231, 745], [941, 962], [354, 760], [927, 426], [340, 164], [809, 720], [465, 152], [487, 280], [386, 690], [401, 605], [351, 517], [421, 120], [571, 870], [409, 581], [647, 268], [254, 168], [290, 687], [982, 452], [184, 813], [942, 726], [829, 856], [305, 874], [759, 456], [623, 930], [813, 984], [297, 432], [609, 397], [257, 921], [320, 375], [109, 570], [126, 210], [763, 189], [798, 708], [803, 368], [971, 631], [967, 791], [962, 850], [906, 201], [849, 403], [905, 389], [284, 231], [726, 275], [742, 562], [754, 948], [724, 481], [903, 168], [523, 231], [735, 452], [930, 149], [503, 950], [572, 473], [561, 967], [296, 281], [352, 283], [638, 856], [760, 602], [801, 170], [598, 417], [841, 965], [479, 485], [859, 916], [293, 248], [457, 791], [238, 462], [725, 943], [821, 372], [543, 901], [473, 507], [982, 723], [726, 394], [418, 350], [834, 150], [218, 437], [584, 290], [934, 271], [294, 895], [543, 671], [623, 784], [485, 478], [276, 643], [513, 136], [957, 407], [621, 340], [972, 817], [971, 291], [950, 315], [674, 315], [451, 982], [327, 829], [294, 154], [732, 601], [739, 352], [529, 495], [240, 720], [918, 387], [597, 715], [186, 716], [824, 875], [190, 852], [524, 328], [531, 753], [392, 985], [164, 849], [715, 864], [438, 935], [591, 946], [528, 690], [296, 560], [210, 102], [458, 148], [513, 615], [561, 324], [594, 451], [546, 159], [506, 473], [367, 107], [172, 230], [651, 629], [345, 628], [627, 425], [973, 940], [923, 914], [603, 437], [986, 684], [679, 230], [560, 204], [102, 578], [154, 863], [241, 153], [107, 152], [109, 530], [154, 849], [610, 175], [753, 213], [852, 279], [328, 287], [952, 832], [487, 904], [869, 519], [915, 809], [704, 657], [843, 871], [371, 351], [645, 963], [925, 638], [692, 623], [492, 786], [692, 708], [945, 658], [176, 736], [369, 547], [578, 812], [873, 763], [620, 418], [589, 209], [906, 418], [426, 976], [120, 451], [475, 735], [831, 746], [908, 270], [246, 721], [541, 120], [352, 286], [128, 826], [210, 431], [865, 687], [817, 576], [139, 907], [674, 491], [671, 396], [536, 604], [809, 396], [284, 817], [941, 841], [712, 370], [649, 931], [395, 689], [429, 249], [869, 218], [370, 730], [570, 140], [475, 136], [408, 509], [958, 294], [874, 847], [362, 807], [401, 301], [892, 204], [874, 365], [549, 780], [487, 146], [432, 293], [270, 901], [968, 891], [386, 642], [812, 801], [834, 860], [987, 237], [568, 894], [562, 271], [189, 704], [230, 928], [501, 905], [870, 189], [980, 421], [258, 126], [960, 402], [531, 852], [450, 374], [327, 840], [172, 405], [960, 680], [279, 532], [284, 829], [230, 701], [289, 218], [423, 580], [865, 895], [635, 129], [831, 809], [934, 568], [234, 901], [639, 976], [265, 256], [347, 194], [204, 863], [275, 748], [274, 973], [653, 793], [854, 873], [741, 917], [981, 653], [194, 642], [897, 538], [542, 914], [579, 701], [983, 459], [342, 857], [398, 650], [139, 973], [214, 216], [240, 684], [135, 529], [128, 780], [638, 493], [513, 240], [428, 168], [615, 423], [317, 560], [821, 791], [973, 724], [431, 729], [521, 267], [740, 231], [519, 706], [273, 897], [269, 902], [284, 362], [859, 912], [178, 352], [432, 513], [250, 248], [368, 614], [527, 319], [341, 125], [481, 543], [932, 412], [398, 428], [237, 648], [698, 870], [760, 352], [279, 749], [194, 607], [972, 973], [865, 136], [198, 750], [312, 871], [793, 159], [985, 923], [913, 635], [726, 813], [940, 948], [294, 364], [913, 482], [239, 127], [457, 390], [407, 679], [820, 327], [372, 867], [238, 794], [637, 546], [374, 857], [416, 130], [650, 650], [306, 926], [810, 823], [431, 378], [562, 593], [931, 715], [925, 256], [831, 718], [132, 837], [153, 571], [613, 436], [712, 817], [819, 527], [497, 947], [917, 629], [648, 548], [835, 164], [854, 324], [829, 859], [970, 694], [478, 860], [528, 204], [397, 925], [126, 457], [735, 593], [910, 532], [967, 930], [462, 718], [932, 867], [712, 827], [794, 534], [546, 162], [213, 941], [750, 980], [487, 761], [219, 263], [139, 870], [573, 932], [194, 609], [278, 839], [201, 305], [159, 576], [250, 857], [350, 607], [350, 674], [386, 702], [835, 561], [361, 817], [974, 187], [194, 984], [257, 201], [846, 973], [597, 361], [745, 658], [192, 397], [463, 738], [935, 913], [167, 572], [324, 210], [178, 641], [436, 890], [705, 795], [548, 721], [745, 104], [450, 612], [106, 613], [796, 908], [586, 374], [410, 827], [348, 561], [867, 573], [371, 493], [951, 438], [130, 302], [367, 156], [635, 926], [912, 346], [596, 732], [163, 850], [495, 725], [935, 849], [617, 789], [254, 952], [592, 748], [598, 514], [869, 215], [503, 906], [856, 865], [671, 893], [203, 298], [618, 168], [610, 207], [150, 634], [159, 906], [318, 867], [413, 412], [985, 134], [180, 280], [403, 781], [462, 370], [895, 567], [431, 876], [702, 583], [536, 514], [518, 364], [467, 697], [872, 853], [435, 245], [420, 134], [746, 109], [329, 278], [432, 389], [156, 875], [981, 312], [876, 361], [417, 269], [670, 762], [180, 405], [270, 319], [846, 345], [839, 863], [524, 418], [923, 704], [523, 489], [561, 913], [723, 369], [156, 620], [519, 164], [689, 354], [754, 324], [795, 459], [531, 931], [761, 187], [280, 289], [130, 907], [340, 173], [174, 846], [307, 456], [409, 729], [129, 418], [925, 465], [684, 563], [932, 582], [350, 471], [496, 547], [825, 875], [306, 245], [130, 678], [932, 264], [180, 109], [140, 520], [937, 247], [648, 954], [423, 957], [578, 254], [917, 514], [382, 539], [406, 405], [354, 486], [182, 392], [547, 124], [245, 760], [574, 187], [413, 618], [906, 976], [709, 931], [637, 891], [759, 253], [307, 684], [215, 168], [427, 683], [751, 132], [924, 182], [149, 528], [794, 564], [305, 386], [350, 497], [215, 963], [841, 102], [829, 130], [641, 149], [185, 527], [402, 804], [840, 740], [635, 641], [896, 573], [916, 987], [149, 209], [408, 904], [379, 528], [243, 863], [319, 721], [923, 942], [285, 523], [746, 429], [609, 645], [538, 528], [265, 321], [502, 615], [314, 432], [316, 349], [312, 493], [694, 260], [908, 541], [950, 630], [482, 234], [760, 548], [963, 345], [675, 569], [628, 591], [509, 485], [832, 610], [761, 480], [486, 841], [153, 841], [902, 750], [204, 905], [894, 539], [608, 137], [156, 721], [146, 435], [345, 647], [736, 239], [987, 346], [247, 319], [752, 568], [597, 796], [378, 180], [872, 601], [816, 853], [489, 583], [591, 506], [764, 603], [963, 261], [964, 702], [569, 910], [817, 649], [841, 487], [146, 609], [453, 468], [914, 684], [721, 216], [261, 703], [736, 687], [369, 927], [720, 640], [829, 741], [671, 987], [934, 248], [105, 368], [987, 714], [973, 672], [890, 840], [906, 786], [134, 351], [250, 394], [457, 540], [289, 237], [537, 104], [837, 437], [148, 504], [409, 654], [485, 895], [804, 706], [816, 943], [234, 156], [
149, 206], [340, 542], [840, 691], [652, 514], [526, 942], [732, 347], [280, 541], [806, 521], [523, 629], [835, 359], [176, 702], [370, 732], [975, 586], [674, 857], [852, 364], [869, 376], [719, 591], [182, 469], [175, 132], [691, 417], [124, 294], [103, 809], [912, 214], [597, 203], [549, 385], [896, 970], [463, 691], [508, 701], [360, 183], [650, 471], [169, 249], [824, 198], [734, 312], [679, 308], [927, 513], [261, 384], [873, 451], [876, 972], [265, 604], [746, 594], [652, 863], [127, 608], [692, 493], [675, 958], [564, 584], [742, 206], [816, 563], [906, 209], [931, 694], [608, 203], [580, 405], [631, 315], [129, 950], [596, 496], [826, 583], [365, 928], [842, 902], [508, 497], [903, 127], [381, 916], [458, 721], [685, 469], [720, 875], [351, 319], [178, 296], [830, 740], [547, 365], [823, 679], [507, 950], [297, 395], [217, 460], [186, 354], [405, 402], [245, 641], [975, 153], [758, 604], [390, 172], [936, 672], [823, 271], [590, 462], [470, 302], [680, 837], [371, 463], [605, 560], [248, 172], [856, 813], [152, 795], [254, 739], [705, 285], [576, 968], [270, 214], [539, 793], [376, 560], [175, 843], [341, 148], [423, 458], [631, 659], [428, 640], [935, 649], [946, 105], [950, 103], [807, 964], [976, 456], [230, 607], [460, 829], [915, 489], [164, 761], [815, 395], [784, 385], [417, 412], [708, 124], [247, 716], [869, 695], [179, 795], [504, 982], [175, 497], [215, 467], [284, 638], [638, 295], [248, 510], [481, 895], [715, 528], [527, 549], [478, 875], [716, 764], [327, 168], [456, 526], [170, 356], [249, 219], [602, 850], [142, 194], [821, 609], [104, 564], [948, 842], [851, 537], [375, 823], [408, 792], [195, 465], [490, 241], [981, 235], [175, 265], [679, 347], [293, 473], [406, 259], [156, 397], [784, 360], [306, 139], [258, 689], [369, 964], [386, 172], [971, 475], [893, 286], [438, 842], [690, 249], [183, 643], [374, 150], [256, 147], [432, 346], [508, 465], [324, 546], [584, 985], [164, 160], [395, 865], [381, 971], [928, 742], [862, 715], [850, 296], [491, 214], [753, 650], [814, 256]]

My first approach -

def queensAttack(n, k, r_q, c_q, obstacles):
    direction_vectors = ((1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1))
    count = 0
    for i in range(8):
        r_q_temp, c_q_temp = r_q, c_q
        while True:
            r_q_temp += direction_vectors[i][0]
            c_q_temp += direction_vectors[i][1]
            if [r_q_temp,c_q_temp] in obstacles or not(0<r_q_temp<n+1) or not(0<c_q_temp<n+1):
                break
            count += 1
    return count
print(queensAttack(n, k, r_q, c_q, obstacles))

Now in u/Arviy 's code -

def move_queen(n, updated_row, updated_col, r , c, obs):
    p = 0
    while True:
        r = updated_row(r)
        c = updated_col(c)
        key = (r - 1) * n + c
        if (c < 1 or c > n or r < 1 or r > n) or (key in obstacles):
            return p
        p += 1
    return p


def queensAttack(n, k, r_q, c_q, obstacles):
    obs = {}
    for b in obstacles:
        obs[(b[0] - 1) * n + b[1]] = None

    p = 0
    dr = [-1, -1, -1, 0, 0 , 1 , 1,1]
    dc = [0, -1, 1, 1, -1 , 0 , 1,-1]

    for i in range(8):
        p += move_queen(n, (lambda r: r + dr[i]), (lambda c: c + dc[i] ), r_q, c_q, obs)

    return p

print(queensAttack(n, k, r_q, c_q, obstacles))

This code ran significantly faster than mine and I investigated and found that it was how he checked for obstacles, so I did the same it my code and it was immediate 10x speedup. But still my code runs about 2x slower than u/Alviy 's code. And I am unable to figure out 1. why there was a huge speedup the first time and 2. why my code is still slower?

My updated code -

def queensAttack(n, k, r_q, c_q, obstacles):
    direction_vectors = ((1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1))
    count = 0
    obstacle_dir = {}
    for obstacle in obstacles:
        obstacle_dir[(obstacle[0] - 1) * n + obstacle[1]] = None
    for i in range(8):
        r_q_temp, c_q_temp = r_q, c_q
        while True:
            r_q_temp += direction_vectors[i][0]
            c_q_temp += direction_vectors[i][1]
            key = (r_q_temp - 1) * n + c_q_temp
            if key in obstacle_dir or not(0<r_q_temp<n+1) or not(0<c_q_temp<n+1):
                break
            count += 1
    return count
\$\endgroup\$
  • \$\begingroup\$ The answer to your question is 1^n. It can never attack more than 1 square at a time! \$\endgroup\$ – Barb Nov 28 '19 at 23:08
  • \$\begingroup\$ Yes, it can attack only one square at a time but the question is more like how many squares are in the queen's reach. \$\endgroup\$ – Naveen Dookia Nov 29 '19 at 3:00
  • \$\begingroup\$ And my code gets the answer but it runs 2x slow (20x slow before borrowing a line from other code) than a similar looking implementation, and I am unable to figure out why that is ? \$\endgroup\$ – Naveen Dookia Nov 29 '19 at 3:02
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. Feel free to post a follow-up question instead, or an answer if there are insightful remarks in the text. \$\endgroup\$ – Mast Nov 30 '19 at 11:26
2
\$\begingroup\$

There are two main problems with your code.

  1. Repeated Lookups
  2. Unnecessary Calculations

Repeated Lookups

With a 100,000 x 100,000 chess board, when you begin moving in a particular direction, you lookup direction_vectors[i][0] and direction_vectors[i][1] and add those values to r_q_temp and c_q_temp. And on the next move you look up those values again. And on the move after that, you look up those values again.

To be clear, each time you look up those values, the Python interpreter must:

  • Look up direction_vectors in the local symbol table for queensAttack,
  • Look up i in the local symbol table for queensAttack,
  • Index to the [i] entry,
  • Index to the [0] entry of that,
  • Look up direction_vectors in the local symbol table for queensAttack, again,
  • Look up i in the local symbol table for queensAttack, again,
  • Index to the [i] entry, again,
  • Index to the [1] entry of that.

So all that happens on up to 100,000 iterations in each given direction! That is a lot of indexing & lookups. They are each very fast, but a hundred thousand iterations of very fast starts becoming slow.

First, let's speed that up.

Instead of indexing over the (hard coded) 8 direction indices, let's loop directly over the direction_vectors:

for direction in direction_vectors:
    r_q_temp, c_q_temp = r_q, c_q
    while True:
        r_q_temp += direction[0]
        c_q_temp += direction[1]
        ...

Two wins! First, we've eliminated that ugly hard-coded 8. If you repeat the same challenge with bishops or rooks, you don't have to remember that the number of direction vectors has changed. Second, we're no longer doing the [i] indexing operation twice per loop. Should be faster, since on each iteration we now only:

  • Look up direction in the local symbol table for queensAttack,
  • Index to the [0] entry of that,
  • Look up direction in the local symbol table for queensAttack, again,
  • Index to the [1] entry of that.

But why stop there? Let's get rid of the [0] and [1] indexing operations as well:

for dr, dc in direction_vectors:
    r_q_temp, c_q_temp = r_q, c_q
    while True:
        r_q_temp += dr
        c_q_temp += dc
        ...

Now, when we loop over the direction_vectors elements, we unpack the tuples directly into two local variables. Again, should be faster, since on each iteration we now only:

  • Look up dr in the local symbol table for queensAttack,
  • Look up dc in the local symbol table for queensAttack

So, how did u/Alviy's code avoid this?

    ..., (lambda r: r + dr[i]), (lambda c: c + dc[i]), ...

They are indexing dr[i] and dc[i] once per direction index, and constructing lambda functions from the values. Tricky, but it works. We're now doing effectively the same thing, just without the lambdas.

Unnecessary Calculations

Consider the statement:

if key in obstacle_dir or not(0<r_q_temp<n+1) or not(0<c_q_temp<n+1):

Let's assume for the moment that key in obstacle_dir is frequently False, so we need to evaluate not(0<r_q_temp<n+1) or not(0<c_q_temp<n+1). Since we spend a lot of the time examining moves which are on the board, we frequently have to fully evaluate 0<r_q_temp<n+1 and 0<c_q_temp<n+1.

So we need to evaluate n+1 ... twice ... per direction iteration. Hundreds of thousands of adding 1 to n, to get exactly the same value. Ouch.

Compiled languages can do data flow analysis, and move constant expressions outside of loops. As Python is interpreted, (insert technobabble here), it cannot. So you end up doing an expensive n+1 addition each iteration. Why expensive? Because, integers are objects, and adding one to a large integer requires allocating a new integer object for the result. Since it is not saved in a variable, this newly created integer becomes unreferenced and then discarded from the heap, only to be computed again (including allocation & freeing) a microsecond later. Hundreds of thousands of times!

Should we store n + 1 in a local variable? Sure, that would work. But so would changing the sub-expression to:

    not (0 < r_q_temp <= n) or not (0 < c_q_temp <= n)

Using "less than or equal to" instead of "less than" means the expensive n + 1 addition goes away.


Micro optimization: By De Morgan's Laws we know that not x or not y is equivalent to not (x and y), so we can write:

    not ((0 < r_q_temp <= n) and (0 < c_q_temp <= n))

which saves one not operation. Further, we can reverse the second sub-expression:

    not ((0 < r_q_temp <= n) and (n >= c_q_temp > 0))

which then allows us to chain the two subexpression, eliminating the second lookup of the n variable in the local symbol table:

    not (0 < r_q_temp <= n >= c_q_temp > 0)

There is another unnecessary calculation that is repeated over and over again, hundreds of thousands of times:

        key = (r_q_temp - 1) * n + c_q_temp

Specifically, r_q_temp - 1. Why are you subtracting 1 from r_q_temp? On a 10x10 grid, does it make any difference if (1,1) maps to 11 or 1, as long as it is the only coordinate that does so? Subtracting 1 just reduces the value of key by n for all key values. But you chose to create those key values here:

    obstacle_dir[(obstacle[0] - 1) * n + obstacle[1]] = None

All you need to do is use the same calculation ... removing the subtract 1 from that key calculation, and the obstacles will be stored under the new, more efficient-to-calculate key values. Since you are using a dictionary, the exact key values don't matter; only that they are unique.

But while we are looking at this obstacle_dir ... why is it a dictionary? The only value ever stored in it is None. You only ever test the existence of the key in the dictionary ... so you could use a set(), which is more memory efficient, and as such, could be faster.

\$\endgroup\$
  • \$\begingroup\$ I agree with your optimizations for how the code is currently written, but my gut is saying that this can be done in O(1) time. After all, if you have a 100x100 board, the maximum vertical and horizontal reach that you can have is 99 (because the queen cannot attack itself). The same actually goes for the diagonals, if you rotate them. If the queen is on, say, (5, 5), the maximum reach for diagonals will be (5 - 1) + (100 - 5). You can check if an obstacle is on a diagonal easily by offsetting y = mx (of course you also have to go the opposite direction) \$\endgroup\$ – ChatterOne Nov 29 '19 at 11:24
  • \$\begingroup\$ @ChatterOne While you have a point, keep in mind CodeReview is a code reviewing site, not a programming challenge answering, grading or tutoring site. The OP wrote that they “optimized it best to what (they) could ... follows basically the same algorithm... but it still runs about 2x slower”. I wasn’t trying to show them the best algorithm; I was reviewing their code, showing them where they could optimize their code further, leaving basically the same algorithm. \$\endgroup\$ – AJNeufeld Nov 29 '19 at 14:43
  • \$\begingroup\$ @ChatterOne I am aware there are other way to go about this problem and I would have turn to those if this hadn't work. For now I just wanted to know that what I'm doing wrong in my code that it is slower than a code that follows the same algorithm \$\endgroup\$ – Naveen Dookia Nov 30 '19 at 10:13
  • \$\begingroup\$ @AJNeufeld first of all thank you for taking time to review my code. Your answer is very detailed and addressed my question in a way I can understand. - Now you asked why am I subtracting 1 from every index when forming a directory, or why don't I use a set instead. The thing is I didn't understand what he was doing as I'm not familiar with directories. I saw that it ran faster so 'copy pasta' .I haven't formally studied python. I am just having fun with coding in my free time. I was hoping you can explain what he was doing with directories and how to do it better? \$\endgroup\$ – Naveen Dookia Nov 30 '19 at 10:19
  • \$\begingroup\$ Sorry. Code Review requires “the code be posted by the author or maintainer of the code (...) and that the poster know why the code is written the way it is.” It may not be obvious, but I tried to avoid commenting on u/Alviy’s code, and just concentrated on reviewing your code. If you do not understand “what he was doing as (you’re) not familiar with dictionaries”, you shouldn’t be asking for review of the code on Code Review. You should ask for help elsewhere (but can probably glean useful knowledge from @Setris’s answer post). \$\endgroup\$ – AJNeufeld Dec 1 '19 at 22:41
2
\$\begingroup\$

To answer your first question of why there was such a big speedup when comparing your first version to your updated version (which took inspiration from Alviy's solution), it's because the first version is doing an expensive lookup within a loop that runs many times:

# obstacles is List[List[int]]
if [r_q_temp,c_q_temp] in obstacles  # [...]

In the above snippet, we are doing an \$O(k)\$ search (where \$k\$ is the length of obstacles) for [r_q_temp, c_q_temp] in obstacles, and we're doing this every time we advance the queen by one space!

The updated version uses a dictionary obstacle_dir, where lookup operations are on average \$O(1)\$, which makes a huge difference:

v1: 3.901795560005121 seconds per run (total 5 runs)
v2: 0.07246560000348837 seconds per run (total 5 runs)

v1 is the first version, and v2 is the updated version.

And actually, if we just make two small changes to your first version (let's call it v1_tweaked), it runs faster than your updated version:

  1. Instead of an obstacle dictionary, create an obstacle set of (row, column) tuples. Like dictionaries, sets in Python also have an average \$O(1)\$ lookup time. In this case, a set is the more appropriate data structure because we only need to test membership; we don't need to map the board coordinates to anything.

    # Set[Tuple[int, int]]
    obstacles = {tuple(obstacle) for obstacle in obstacles}
    
  2. Checking if a space contains an obstacle now looks like this:

    if (r_q_temp, c_q_temp) in obstacles # [...]
    
v1: 3.901795560005121 seconds per run (total 5 runs)
v2: 0.07246560000348837 seconds per run (total 5 runs)
v1_tweaked: 0.06353590001817792 seconds per run (total 5 runs)

EDIT: There appears to be some difference in the way you and I are timing the functions, because when I ran v2 (the updated version), v1_tweaked (my adjusted version of your v1), and Arviy's version, both v2 and v1_tweaked ran faster than Arviy's version:

from functools import partial
import timeit

n, k = 100000, 100000
r_q, c_q = 1, 1
obstacles = [[1000, 1000], [714, 169], ...]

v2 = partial(queensAttack_v2, n, k, r_q, c_q, obstacles)
v1_tweaked = partial(queensAttack_v1_tweaked, n, k, r_q, c_q, obstacles)
f_arviy = partial(queensAttack_Arviy, n, k, r_q, c_q, obstacles)

def measure(f, fname, num_trials=1):
    t = timeit.timeit(f'{fname}()', setup=f'from __main__ import {fname}', number=num_trials)
    print(f'{fname}: {t / num_trials} seconds per run (total {num_trials} runs)')

if __name__ == '__main__':
    TRIALS = 50
    measure(v2, 'v2', num_trials=TRIALS)
    measure(v1_tweaked, 'v1_tweaked', num_trials=TRIALS)
    measure(f_arviy, 'f_arviy', num_trials=TRIALS)
v2: 0.07151672399835661 seconds per run (total 50 runs)
v1_tweaked: 0.06288900200044736 seconds per run (total 50 runs)
f_arviy: 0.0828415279998444 seconds per run (total 50 runs)

I am using the timeit module, which is the recommended way to measure execution time of code snippets (more accurate than saving the time with time.time() before and after and calculating the difference).

\$\endgroup\$
  • \$\begingroup\$ Thank you. I understand it now. I guess I'll have to study what sets, dictionaries are. Also, can you explain what Alviy was doing with obstacle_dir[(obstacle[0] - 1) * n + obstacle[1]] = None . I still don't understand that. \$\endgroup\$ – Naveen Dookia Nov 30 '19 at 11:08
  • \$\begingroup\$ @NaveenDookia My guess is that Alviy was trying to generate a unique value (from obstacle[0] and obstacle[1]) that could be stored as the key to a dictionary, not knowing that one can just store the tuple (obstacle[0], obstacle[1]) as the key (or even better, just use a set as I mentioned earlier). So the intent of the function (obstacle[0] - 1) * n + obstacle[1] is to translate a List[int] (which cannot be used as a key to a dictionary, because it is a mutable data structure) into an int (which can be used as a key to a dictionary, but in this case there are faster alternatives) \$\endgroup\$ – Setris Nov 30 '19 at 11:24
  • \$\begingroup\$ Okay. That makes sense. \$\endgroup\$ – Naveen Dookia Nov 30 '19 at 11:26
  • \$\begingroup\$ @NaveenDookia Please see the above edit -- you should be using the timeit module to measure execution time of your code, not doing it manually via time.time(). That could be the reason why your test results differ from mine. \$\endgroup\$ – Setris Nov 30 '19 at 11:46
  • \$\begingroup\$ I'm a little confused by the naming scheme. I know that v1_tweaked uses set for lookup but v2 was arviy's code wasn't it? and then what is f_arviy? Anyhow, I agree with your conclusions, lookup in list > lookup in dir > lookup in set. But the thing is even if you use set for lookup in both codes my code still seem slower. I'll retime it with timeit and see what happenes. \$\endgroup\$ – Naveen Dookia Nov 30 '19 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.