API tools faq
paste
magneto903

super fast unstable graph algo

magneto903
Mar 23rd, 2021 (edited)
118
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
HTML 14.19 KB | None | 0 0
raw download clone embed print report
  1. <!DOCTYPE html>
  2. <html>
  3. <head>
  4.     <title></title>
  5. </head>
  6. <body>
  7. <script type="text/javascript">
  8.  
  9. var arrAvg = arr => arr.reduce((a,b) => a + b, 0) / arr.length
  10. var all_edges = [[0,6,70.71067811865476],[1,0,810],[1,2,70.71067811865476],[3,2,1592],[3,5,70.71067811865476],[3,153,205.87711451966396],[4,7,70.71067811865476],[4,112,512.6115351930363],[4,153,737.0774717197235],[5,153,135.6583919878893],[6,94,310.40008748620136],[7,94,1281.6150329914337],[8,9,55.43314410935759],[8,27,394.91497146070554],[8,89,249.25217498817833],[9,10,62.68381161480822],[9,85,257.37611801643203],[9,119,357.92609495024175],[10,11,22.00603386355706],[10,43,325.893754212365],[10,95,145.6349677143284],[10,114,495.27154468751036],[11,12,40.754770931103174],[11,66,338.44828019294425],[11,154,277.7768610143829],[12,13,63.96396957495827],[12,71,279.46200199816974],[12,130,423.73430144247175],[12,142,605.3109163530141],[13,14,42.685329113484585],[13,22,267.044681207588],[13,18,383.79570105328406],[13,89,295.1151050396651],[13,97,173.37684490280637],[13,147,644.3394809974541],[14,15,45.39123913699872],[15,16,47.047036449194316],[15,65,294.0887879580657],[15,86,183.6721765115165],[15,114,486.6941103104043],[16,17,25.7772200449739],[16,43,298.08763602419685],[16,39,354.1679638306291],[16,70,371.37278825824006],[16,74,670.2294043204714],[16,132,378.87860482952715],[17,8,37.97639596422426],[17,22,283.4489103653117],[17,136,499.55002623505305],[17,142,589.0762111107545],[18,19,68.56451044560333],[19,20,60.809531997686655],[19,64,400.06011580087164],[19,156,445.50275071828963],[20,21,41.7268040869492],[21,22,44.409786926805985],[21,70,244.19177296204867],[21,91,205.16309784978526],[21,131,170.98157093493768],[22,23,73.41351083187409],[22,44,578.7057992684693],[22,39,603.7781336207288],[22,49,794.3115697606781],[22,57,486.1389713865941],[22,86,298.95911490661615],[22,128,342.80891355908545],[22,135,282.6431518625895],[22,142,308.1360659862511],[22,147,378.58967001309463],[23,24,47.156569853258866],[23,63,299.1373917294431],[23,156,424.0775352517563],[24,25,86.13825660873893],[24,131,210.320160984807],[25,26,33.06353502569152],[26,27,67.91460112401641],[26,57,540.3387174980588],[26,92,228.93825991593803],[26,120,412.75883815805963],[26,128,418.9168740031914],[26,142,333.7521131385038],[27,18,31.90572098820839],[27,80,593.5258503155924],[27,89,148.5928396302128],[27,147,349.297544643658],[28,29,59.67018420401978],[28,81,209.96278270854182],[28,106,69.99034725665763],[28,149,340.8623984131601],[29,30,23.113480906778186],[29,60,155.8179847580466],[29,77,297.5407757529884],[30,31,24.194433832360634],[30,48,312.87236629082633],[31,32,95.03245812683691],[31,52,306.82477443979093],[31,107,78.85870804148841],[32,33,28.769841069179858],[32,60,147.93878749367386],[33,34,26.884913041414087],[33,149,324.73490720293273],[34,35,34.539644671799884],[34,48,312.60280041119495],[34,82,298.7966839326061],[35,36,47.88309910969351],[35,52,298.6492567682363],[35,78,270.88254329096384],[36,37,55.92799176338086],[36,146,250.2794421195491],[37,28,28.746317165572204],[37,101,174.53904785374436],[39,40,28.56292626279466],[39,136,827.1618749297187],[39,142,911.9072364060776],[40,41,71.83348433366919],[40,87,385.18415791555594],[41,42,25.66448755744104],[41,84,301.86449922516306],[41,119,304.09006218105435],[42,43,25.041564347271354],[42,114,201.32515950767336],[43,44,53.81505716045718],[43,70,668.6142302142265],[43,95,464.5912380083568],[43,132,675.2576499747647],[44,45,41.40801209082323],[44,57,1063.3996891527247],[44,136,809.6193736796965],[45,38,41.60346490016386],[45,86,326.14140573310647],[45,83,413.3998108385815],[45,118,301.0257064648056],[46,47,32.324323407861954],[47,48,74.97098636842881],[47,150,482.148526864346],[48,49,51.584467579702824],[48,61,244.27972531448285],[48,106,336.640487491796],[49,57,308.50551001966323],[49,128,451.6465055929891],[49,135,511.844500792933],[50,51,49.512416392803104],[51,52,53.04787162699196],[52,53,76.43056418497244],[52,82,547.120073731121],[52,110,325.05226324305437],[52,150,458.3924820628751],[53,54,20.039265191224455],[54,46,25.030634943141447],[54,58,244.9260216552532],[54,67,756.3463895463947],[54,76,482.3227102069046],[54,124,422.2533744531271],[55,56,58.460583239231624],[55,102,115.82406310298205],[55,125,152.5815324765102],[56,57,55.57519143003837],[57,58,48.45767081071381],[57,158,180.39992938539922],[57,136,253.7803363149803],[57,142,206.67779462996376],[58,59,24.092997373752972],[59,60,82.39211060953677],[59,76,268.66979964854914],[59,124,204.95995317424766],[60,61,56.8386682833888],[61,77,395.3342593777817],[61,106,94.82870098367673],[62,63,50.239660941572126],[62,138,456.67384076187767],[63,64,49.29188012559735],[64,65,34.9390920450358],[64,91,484.70495246456426],[65,66,44.386933593419634],[65,86,473.4945906187595],[66,67,46.35007638082747],[66,97,354.99096425656126],[66,155,98.46201480548129],[67,68,83.11118143775956],[67,76,275.22916188389814],[67,124,334.3275404295602],[68,69,61.82288775247714],[69,70,32.72720780632854],[70,71,82.01328044192185],[70,74,299.3033974268629],[70,86,467.8800531253375],[70,114,795.7351820979673],[70,131,74.14997079035552],[71,62,38.53358308507445],[71,97,376.4367138297526],[71,122,299.55665657848795],[71,132,92.36209904758263],[71,131,67.09223542194184],[71,156,229.10251215735252],[72,73,22.44295867376786],[72,124,96.7927637387651],[74,75,41.39428112635902],[74,121,140.7096972711017],[74,132,291.38771611392053],[75,76,30.0627689482037],[76,72,30.383770443458943],[77,78,52.00968489404878],[77,106,300.6735447670068],[77,145,213.64883986492893],[78,79,44.23783407847146],[79,80,38.118361538425795],[80,81,88.22727131494065],[80,92,748.610228678086],[80,117,922.5836952812741],[81,82,65.51209274182104],[81,101,323.12731048143235],[81,147,350.10072558836436],[82,111,269.9434631344396],[83,84,49.04899812555336],[84,85,63.71188304619065],[85,86,49.09351203637654],[86,87,83.46480593410709],[86,119,151.90228469087668],[86,114,329.0079671927419],[86,128,641.7308695509025],[86,132,471.07620316344014],[86,135,581.5450583764579],[87,88,41.619088536378854],[88,89,19.022840656019405],[89,90,35.841603038774416],[90,91,32.398612793756314],[91,92,48.582975729764854],[92,83,30.837464050468025],[92,120,188.7591372909066],[92,117,174.02812344524793],[92,146,572.3906052533645],[95,96,20.309465539051313],[95,114,637.3889554757393],[96,97,63.213233743350074],[97,93,102.0522575060609],[97,100,240.91712277511493],[97,130,525.9007129529984],[97,142,709.2888517760487],[97,147,817.6275336689539],[97,155,256.52958550596395],[98,99,38.26238414408713],[99,100,81.55030224358033],[100,130,766.6709881560315],[100,142,949.697709689759],[101,102,47.30056869901373],[101,143,92.85603330225935],[102,103,35.380667355785846],[102,125,257.26089278078433],[102,145,86.69660180432261],[103,104,43.58038875739012],[105,106,49.00253118207074],[106,107,27.405833077229865],[107,108,39.67467085048693],[107,146,161.5285374896578],[108,109,28.034817769574357],[109,101,48.22919045283958],[110,111,25.375224080516592],[110,150,133.5176916667986],[112,113,83.28092580028589],[112,153,239.32930481887956],[114,115,101.77827438406392],[114,132,799.5716987622106],[115,116,55.33658324913234],[116,117,64.34602362067791],[117,118,25.616725172113455],[118,119,49.34327971363866],[119,120,92.13543408276188],[121,122,49.158380910815055],[122,123,22.072670207307805],[122,132,207.55080569931508],[123,124,23.95147516157658],[124,125,37.10612238764236],[125,126,34.927378155183234],[125,141,258.1518700205428],[126,127,32.98615477724716],[127,128,16.22742340952728],[128,158,35.94532649063341],[128,135,60.199671727187834],[130,131,89.63249969243708],[131,132,70.44518620133896],[131,142,273.78551731820147],[131,138,351.5407196157602],[131,156,296.14115910691856],[132,133,53.20257740632008],[133,134,50.32148162147291],[135,136,49.49620942581232],[136,137,31.43818529653531],[137,130,44.67921793243463],[138,139,23.777001819899976],[138,156,645.5864796077194],[139,140,47.7270317027185],[140,141,23.039143895070726],[141,142,70.27931275561932],[142,143,64.98383750211529],[143,144,30.097551026293797],[144,145,100.10632073495346],[145,146,43.76422694558446],[146,147,62.554721469410964],[147,138,60.21879922428856],[149,150,40.27917844217807],[151,152,16.05179269405632],[152,153,95.08995160516936],[153,148,83.09197814327331],[154,155,33.19341980748434],[155,156,58.397228717203404],[157,10,475.0410693030716],[157,16,434.2784913076533],[157,43,149.3858968154142],[157,70,798.2577975693512],[157,86,337.27659265236],[157,117,242.8128909397011],[157,132,803.2044974295419],[159,10,424.5428223515612],[159,15,416.3689141062264],[159,42,136.50001088374017],[159,70,728.6111329180097],[159,86,264.5824947674739],[159,92,344.37896644057383],[159,95,567.3380419121927],[159,117,170.35193802012466],[159,114,71.39727162164735],[159,132,733.0042344492691],[160,10,386.9207320551183],[160,15,344.37793610826577],[160,38,259.95392603739697],[160,41,191.66415098549578],[160,65,638.3194987663459],[160,80,981.0925983047125],[160,86,170.91599639926625],[160,92,232.48237745520552],[160,117,58.715883663506396],[160,115,63.25551243883601],[160,158,44.1282092957909],[160,159,112.12052199347016],[161,10,293.9650424785912],[161,16,262.12088923847034],[161,22,491.24332514971724],[161,43,35.96703115932087],[161,41,42.17582986887332],[161,70,632.6993752105095],[161,87,285.65519727136444],[161,84,262.445211274406],[161,95,434.67294753052647],[161,119,262.52409073917073],[161,114,202.98164149753293],[161,132,639.4014374495188],[161,136,721.2341683340406],[161,159,134.34656675925888]]
  11.  
  12.  
  13.  
  14. var edges_start = new Int16Array(3000)
  15. var edges_end = new Int16Array(3000)
  16. var edges_len = new Float32Array(3000)
  17.  
  18. var g_links_id = [];
  19. var g_links_weight = [];
  20.  
  21.  
  22. var cache_id = new Int32Array(1000);
  23. var cache_distance = new Float32Array(1000);
  24. var cache_prev = new Int32Array(1000);
  25. var cache_links_id = []
  26. var cache_links_weight = []
  27.  
  28. for (var j=0; j < 1000; j++) {
  29.     cache_links_id.push(new Int32Array(100))
  30.     cache_links_weight.push(new Float32Array(100))
  31. }
  32.  
  33. for (var i=0; i < 1000; i++) {
  34.     g_links_id.push(new Int32Array(100))
  35.     g_links_weight.push(new Float32Array(100))
  36. }
  37.  
  38. var queue_id = new Int32Array(1000);
  39. var queue_distance = new Float32Array(1000);
  40. var queue_prev = new Int32Array(1000);
  41. var queue_links_id_len = new Int32Array(1000);
  42. var queue_links_id = []
  43. var queue_links_weight = []
  44. for (var j=0; j < 1000; j++) {
  45.     queue_links_id.push(new Int32Array(100))
  46.     queue_links_weight.push(new Float32Array(100))
  47. }
  48.  
  49. var init_cpp = function() {
  50.     for (var i=0; i < 1000; i++) {
  51.         cache_id[i] = -2;
  52.         queue_id[i] = -2;
  53.         cache_distance[i] = 100000;
  54.         queue_distance[i] = 100000;
  55.         cache_prev[i] = -2;
  56.         queue_prev[i] = -2;
  57.         for (var j=0; j < 100; j++) {
  58.             queue_links_id[i][j] = -2;
  59.             queue_links_weight[i][j] = -2.0;
  60.             cache_links_id[i][j] = -2;
  61.             cache_links_weight[i][j] = -2.0;
  62.         }
  63.     }
  64. }
  65.  
  66. var init_edges_cpp = function() {
  67.     for (var i=0; i < 3000; i++) {
  68.         edges_start[i] = -2;
  69.         edges_end[i] = -2;
  70.         edges_len[i] = -2.0;
  71.     }
  72.  
  73.     for (var i=0; i < 1000; i++) {
  74.         for (var j=0; j < 100; j++) {
  75.             g_links_id[i][j] = -2;
  76.             g_links_weight[i][j] = -2.0;
  77.         }
  78.     }
  79. }
  80.  
  81. var add_vert_cpp = function(index, vert) {
  82.     vertices[index] = vert
  83. }
  84.  
  85. var add_edge_cpp = function(index, start, end, len) {
  86.     edges_start[index] = start;
  87.     edges_end[index] = end;
  88.     edges_len[index] = len;
  89. }
  90.  
  91. var fill_graph_cpp = function() {
  92.     for (var i=0; i < 3000; i++) {
  93.         var s = edges_start[i];
  94.         var e = edges_end[i];
  95.         var len = edges_len[i];
  96.  
  97.         if (s == -2) {
  98.             break
  99.         }
  100.  
  101.         var links_len = 0
  102.  
  103.         for (var j=0; j < 100; j++) {
  104.             if (g_links_id[s][j] == -2) {
  105.                 links_len = j
  106.                 break;
  107.             }
  108.         }
  109.  
  110.         g_links_id[s][links_len] = e;
  111.         g_links_weight[s][links_len] = len
  112.  
  113.         for (var j=0; j < 100; j++) {
  114.             if (g_links_id[e][j] == -2) {
  115.                 links_len = j
  116.                 break;
  117.             }
  118.         }
  119.         g_links_id[e][links_len] = s;
  120.         g_links_weight[e][links_len] = len
  121.     }
  122. }
  123.  
  124. var get_dists_cpp = function(a, L=165) {
  125.    
  126.    
  127.    // initialization
  128.  
  129.    i = L;
  130.    while (--i >= 0) {
  131.  
  132.         for (var j = 0; j < 100; j++) {
  133.             //console.log()
  134.             if (g_links_id[i][j] == -2) {
  135.  
  136.                 break
  137.             }
  138.             cache_links_id[i][j] = g_links_id[i][j];
  139.             cache_links_weight[i][j] = g_links_weight[i][j];
  140.        }
  141.  
  142.        cache_id[i] = i
  143.    }
  144.  
  145.  
  146.    queue_id[0] = cache_id[a]
  147.    cache_distance[a] = 0
  148.    queue_distance[0] = cache_distance[a]
  149.    queue_prev[0] = queue_prev[a]
  150.    for (var j=0; j < 100; j++) {
  151.         if (cache_links_id[a][j] == -2) {
  152.             queue_links_id_len[0] = j;
  153.             break;
  154.         }
  155.         queue_links_id[0][j] = cache_links_id[a][j]
  156.         queue_links_weight[0][j] = cache_links_weight[a][j]
  157.    }
  158.    
  159.  
  160.    
  161.    i=0
  162.    var queue_len = 1;
  163.    while (i < queue_len) {
  164.         node_id = queue_id[i]
  165.         node_distance = queue_distance[i]
  166.         node_prev = queue_prev[i]
  167.  
  168.         var j = queue_links_id_len[i];
  169.  
  170.         while (--j >= 0) {
  171.             link_id = queue_links_id[i][j]
  172.             link_weight = queue_links_weight[i][j]
  173.  
  174.             c_id = cache_id[link_id]
  175.             c_distance = cache_distance[link_id]
  176.             c_prev = cache_prev[link_id]
  177.  
  178.             d = node_distance + link_weight
  179.  
  180.             if (d < c_distance) {
  181.                 cache_prev[link_id] = node_id
  182.                 cache_distance[link_id] = d
  183.  
  184.                 last_ind = queue_len;
  185.                 queue_id[last_ind] = cache_id[link_id]
  186.                 queue_distance[last_ind] = cache_distance[link_id]
  187.                 //console.log(last_ind, queue_links_id[last_ind])
  188.                 for (var k=0; k < 100; k++) {
  189.                     if (cache_links_id[link_id][k] == -2) {
  190.                         queue_links_id_len[last_ind] = k;
  191.                         break
  192.                     }
  193.                    
  194.                     queue_links_id[last_ind][k] = cache_links_id[link_id][k]
  195.                     queue_links_weight[last_ind][k] = cache_links_weight[link_id][k]
  196.                 }
  197.                 queue_prev[last_ind] = cache_prev[link_id]
  198.                 queue_len++;
  199.             }
  200.  
  201.         }
  202.         i++
  203.    }
  204.  
  205. }
  206.  
  207. // начальная вершина
  208. var s = 157;
  209.  
  210.  
  211.  
  212.  
  213. init_edges_cpp();
  214.  
  215. for (var i in all_edges) {
  216.     var a = all_edges[i][0]
  217.     var b = all_edges[i][1]
  218.     var len = all_edges[i][2]
  219.  
  220.     add_edge_cpp(i, a, b, len)
  221. }
  222.  
  223. fill_graph_cpp();
  224.  
  225. init_cpp();
  226.  
  227. init_cpp()
  228. var times = [];
  229.  
  230. for (var j=0; j < 100000; j++) {
  231.     var s_t = performance.now()
  232.     get_dists_cpp(s)
  233.     var dur = (performance.now() - s_t)
  234.     times.push(dur)
  235. }
  236. console.log(arrAvg(times));
  237. document.write(arrAvg(times));
  238.  
  239. </script>
  240. </body>
  241. </html>
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!