I'm doing Hackerearth's challenges, and the very first one is a simple clockwise array rotation. So, given an array such as:
arr = "1 2 3 4 5"
If you rotate it (clock-wise) for let's say 2 steps then you'd have the following:
arr = "4 5 1 2 3"
So I was able to built an algorithm that does this, and I also used Julias' native circshift function, but I'm still not time-efficient enough. The maximum time allowed per test is 1 second, and my current implementation takes 1.5sec.
My code is the following:
test_cases = readline() #read the amount of test cases
tests = test_cases[1:end]
tests = string(tests)
tests = parse(Int8, tests)
for i in 1:tests
second_line = readline() #reads the size of the array and the steps
third_line = readline() #read the actual array
function solution(second_line, third_line)
#first we separate the number of the array from the steps to rotate
len_steps = split(second_line, " ")
len = parse(Int8, len_steps[1])
steps = parse(Int8, len_steps[2])
#secondly we separate the third line into the actual array
line = split(third_line, " ")
#if steps > length, get the modulus. Else, do the normal stepping.
if steps > len
steps = steps%len
end
#now we start filling out the new array. This is not as effective.
return join(vcat(line[(len-steps 1):end], line[1:(len-steps)]), " ")
end
test = solution(second_line, third_line)
print(test)
println(" ")
end
This is the current version of the algorithm, and it uses some of Julias' native tools. My previous interpretation had a for loop which just made it worse. As I mentioned, circshift doesn't cut it either, so how could I improve it to make it more efficient?
Below I share a sample of the input, but the full file is on pastebin.
13
384 886
655497 374005 129593 387055 595396 152862 251289 702661 595772 811057 321410 686329 174533 17836 235740 330576 568552 472246 881591 761168 161847 121659 617522 747110 345962 187723 773947 850345 578189 611862 78672 844128 596309 716697 333193 293716 480001 584482 606819 177783 107991 30239 474554 790957 556508 710294 731975 227070 792983 715576 598681 56840 837236 318213 414392 793640 505936 798781 745995 186135 512654 824667 640706 719405 253816 75909 623563 733817 270834 840825 522042 378825 871064 98607 780224 140024 419343 614210 875527 822768 431796 576218 879608 879474 504873 396011 775124 112819 296802 623130 807386 419898 160249 550102 749746 414066 236454 475319 758325 117730 418154 382378 106997 1671 91427 887222 650127 121212 603442 238106 45991 645680 424766 536041 627165 31649 542494 504299 652900 449739 737871 562297 869637 131 722841 331835 24639 569737 417597 393406 687467 446193 386226 794465 58306 477653 394139 708434 209308 99591 556982 255299 355713 83759 791340 84888 115408 435845 199630 768309 496026 547943 43058 78115 158516 376341 409951 183155 48089 827548 187004 345998 375751 573230 242473 44500 152894 247054 752934 870634 855077 411926 227943 312801 106127 629725 397689 221536 676012 207761 600287 274048 755705 253787 352164 16231 630128 762115 707819 678217 302115 894823 634658 288308 570063 877131 332808 333399 226196 696184 306043 183283 718553 144428 106526 824680 774154 114658 656658 162618 322419 867387 436667 688566 223184 399273 315240 853313 771830 125069 243982 175955 630334 878640 74705 810839 468224 17956 246249 304862 324582 162734 98587 653577 815595 205114 580268 302201 319772 847368 464819 252633 816766 511928 43210 650392 13211 358450 605715 785041 93961 460140 571438 724295 440790 256586 637144 519456 274542 493835 824318 209566 267012 533348 863144 184617 738462 155864 97260 668676 105242 562079 23319 532450 176018 574961 284853 697661 35421 501010 584713 637814 63160 766593 464119 503951 125189 711706 633849 10173 815983 560178 219740 185005 195536 693326 878054 544440 849190 77324 315126 56442 249846 846877 199335 36306 523849 484188 733967 169712 87208 31132 417969 150369 797726 492530 264762 533357 306246 621 153973 732672 171241 882145 528119 875209 677481 508184 521659 628681 195950 447227 295565 56238 6557 494900 92544 140848 589530 436954 818992 676739 468086 338971 437550 876254 831502 702312 511622 748190 313375 665595 582872 95059 649750 213002 72278 39683 331628 204380 668364 138020 262049 574371 194259 268606 171282 795235 409454 371254 334199 838889 150003 802286 279870 197995 780550 213382 510749 4624 63583 824125 280661 256897
CodePudding user response：
Use ShiftedArrays:
using ShiftedArrays, BenchmarkTools
a=collect(1:10_000_000)
And now:
julia> CircShiftedVector(a, 3)
10000000-element CircShiftedVector{Int64, Vector{Int64}}:
9999998
9999999
10000000
1
2
3
⋮
9999995
9999996
9999997
This is non-allocating so the time cost is one nanosecond:
julia> @btime CircShiftedVector($a, 3);
1.300 ns (0 allocations: 0 bytes)
CodePudding user response：
circshift is plenty fast, and you should use that.
It is not clear exactly what you want to measure here, but is clear that almost 100% of the time in your code is spent on file reading, string parsing and printing, and that is without considering the performance issues that are caused by working in global scope.
So, first of all, you should wrap your code in functions. Performance tip number 1 in the manual (https://docs.julialang.org/en/v1/manual/performance-tips/) is "Avoid global variables". This hurts performance a lot. Wrap your code in functions, and make sure all variables are passed as input arguments, don't rely on globals.
As for the performance of circshift, consider this:
1.7.0> using BenchmarkTools
1.7.0> x = rand(1000);
1.7.0> @btime circshift($x, 500);
552.604 ns (1 allocation: 7.94 KiB) # <- nanoseconds!
1.7.0> @btime join(circshift($x, 500), " ");
135.700 μs (2013 allocations: 461.98 KiB) # <- microseconds!
Less than 0.5% of the runtime is spent on circshift, and then I'm ignoring the part where you read and parse the data from file, which probably takes much, much longer. I'm pretty confident that circshift takes up much less than 1/1000th of the time in your code.
In other words, use circshift, and then spend your time improving the performance of the other parts of your code (and read the performance tips ;)