Guest User

Untitled

a guest
Jan 18th, 2018
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.30 KB | None | 0 0
  1. {
  2. "cells": [
  3. {
  4. "cell_type": "code",
  5. "execution_count": 1,
  6. "metadata": {
  7. "collapsed": true
  8. },
  9. "outputs": [],
  10. "source": [
  11. "using Base.Threads, BenchmarkTools, Distances"
  12. ]
  13. },
  14. {
  15. "cell_type": "code",
  16. "execution_count": 2,
  17. "metadata": {},
  18. "outputs": [
  19. {
  20. "data": {
  21. "text/plain": [
  22. "4"
  23. ]
  24. },
  25. "execution_count": 2,
  26. "metadata": {},
  27. "output_type": "execute_result"
  28. }
  29. ],
  30. "source": [
  31. "nthreads()"
  32. ]
  33. },
  34. {
  35. "cell_type": "code",
  36. "execution_count": 3,
  37. "metadata": {},
  38. "outputs": [
  39. {
  40. "data": {
  41. "text/plain": [
  42. "4-element Array{Int64,1}:\n",
  43. " 2\n",
  44. " 3\n",
  45. " 4\n",
  46. " 5"
  47. ]
  48. },
  49. "execution_count": 3,
  50. "metadata": {},
  51. "output_type": "execute_result"
  52. }
  53. ],
  54. "source": [
  55. "addprocs()"
  56. ]
  57. },
  58. {
  59. "cell_type": "code",
  60. "execution_count": 4,
  61. "metadata": {},
  62. "outputs": [
  63. {
  64. "data": {
  65. "text/plain": [
  66. "pdist (generic function with 1 method)"
  67. ]
  68. },
  69. "execution_count": 4,
  70. "metadata": {},
  71. "output_type": "execute_result"
  72. }
  73. ],
  74. "source": [
  75. "function pdist(x, y)\n",
  76. " n = length(x)\n",
  77. " dist = zeros(n, n)\n",
  78. " for j in 1:n\n",
  79. " for i in 1:n\n",
  80. " dist[i,j] = (x[i] - x[j])^2 + (y[i] - y[j])^2 |> sqrt\n",
  81. " end\n",
  82. " end\n",
  83. " return dist\n",
  84. "end"
  85. ]
  86. },
  87. {
  88. "cell_type": "code",
  89. "execution_count": 46,
  90. "metadata": {},
  91. "outputs": [
  92. {
  93. "data": {
  94. "text/plain": [
  95. "pdist_inbounds (generic function with 1 method)"
  96. ]
  97. },
  98. "execution_count": 46,
  99. "metadata": {},
  100. "output_type": "execute_result"
  101. }
  102. ],
  103. "source": [
  104. "function pdist_inbounds(x, y)\n",
  105. " n = length(x)\n",
  106. " dist = zeros(n, n)\n",
  107. " for j in 1:n\n",
  108. " for i in 1:n\n",
  109. " @inbounds dist[i,j] = (x[i] - x[j])^2 + (y[i] - y[j])^2 |> sqrt\n",
  110. " end\n",
  111. " end\n",
  112. " return dist\n",
  113. "end"
  114. ]
  115. },
  116. {
  117. "cell_type": "code",
  118. "execution_count": 5,
  119. "metadata": {},
  120. "outputs": [
  121. {
  122. "data": {
  123. "text/plain": [
  124. "pdist_hypot (generic function with 1 method)"
  125. ]
  126. },
  127. "execution_count": 5,
  128. "metadata": {},
  129. "output_type": "execute_result"
  130. }
  131. ],
  132. "source": [
  133. "function pdist_hypot(x, y)\n",
  134. " n = length(x)\n",
  135. " dist = zeros(n, n)\n",
  136. " for j in 1:n\n",
  137. " for i in 1:n\n",
  138. " dist[i,j] = hypot(x[i] - x[j], y[i] - y[j])\n",
  139. " end\n",
  140. " end\n",
  141. " return dist\n",
  142. "end"
  143. ]
  144. },
  145. {
  146. "cell_type": "code",
  147. "execution_count": 6,
  148. "metadata": {},
  149. "outputs": [
  150. {
  151. "data": {
  152. "text/plain": [
  153. "pdist_thread (generic function with 1 method)"
  154. ]
  155. },
  156. "execution_count": 6,
  157. "metadata": {},
  158. "output_type": "execute_result"
  159. }
  160. ],
  161. "source": [
  162. "function pdist_thread(x, y)\n",
  163. " n = length(x)\n",
  164. " dist = zeros(n, n)\n",
  165. " @threads for j in 1:n\n",
  166. " for i in 1:n\n",
  167. " dist[i,j] = (x[i] - x[j])^2 + (y[i] - y[j])^2 |> sqrt\n",
  168. " end\n",
  169. " end\n",
  170. " return dist\n",
  171. "end"
  172. ]
  173. },
  174. {
  175. "cell_type": "code",
  176. "execution_count": 35,
  177. "metadata": {},
  178. "outputs": [
  179. {
  180. "data": {
  181. "text/plain": [
  182. "pdist_proc (generic function with 1 method)"
  183. ]
  184. },
  185. "execution_count": 35,
  186. "metadata": {},
  187. "output_type": "execute_result"
  188. }
  189. ],
  190. "source": [
  191. "function pdist_proc(x, y)\n",
  192. " n = length(x)\n",
  193. " dist = SharedMatrix{Float64}(n,n,init=0.0)\n",
  194. " @parallel for j in 1:n\n",
  195. " for i in 1:n\n",
  196. " dist[i,j] = (x[i] - x[j])^2 + (y[i] - y[j])^2 |> sqrt\n",
  197. " end\n",
  198. " end\n",
  199. " return dist\n",
  200. "end"
  201. ]
  202. },
  203. {
  204. "cell_type": "code",
  205. "execution_count": 8,
  206. "metadata": {},
  207. "outputs": [
  208. {
  209. "data": {
  210. "text/plain": [
  211. "pdist_thread_inbounds (generic function with 1 method)"
  212. ]
  213. },
  214. "execution_count": 8,
  215. "metadata": {},
  216. "output_type": "execute_result"
  217. }
  218. ],
  219. "source": [
  220. "function pdist_thread_inbounds(x, y)\n",
  221. " n = length(x)\n",
  222. " dist = zeros(n, n)\n",
  223. " @threads for j in 1:n\n",
  224. " for i in 1:n\n",
  225. " @inbounds dist[i,j] = (x[i] - x[j])^2 + (y[i] - y[j])^2 |> sqrt\n",
  226. " end\n",
  227. " end\n",
  228. " return dist\n",
  229. "end"
  230. ]
  231. },
  232. {
  233. "cell_type": "code",
  234. "execution_count": 9,
  235. "metadata": {},
  236. "outputs": [
  237. {
  238. "data": {
  239. "text/plain": [
  240. "pdist_thread_inbounds_sp (generic function with 1 method)"
  241. ]
  242. },
  243. "execution_count": 9,
  244. "metadata": {},
  245. "output_type": "execute_result"
  246. }
  247. ],
  248. "source": [
  249. "function pdist_thread_inbounds_sp(x::Vector{Float64}, y::Vector{Float64})\n",
  250. " n = length(x)\n",
  251. " dist = zeros(n, n)\n",
  252. " @threads for j in 1:n\n",
  253. " for i in 1:n\n",
  254. " @inbounds dist[i,j] = (x[i] - x[j])^2 + (y[i] - y[j])^2 |> sqrt\n",
  255. " end\n",
  256. " end\n",
  257. " return dist\n",
  258. "end"
  259. ]
  260. },
  261. {
  262. "cell_type": "code",
  263. "execution_count": 11,
  264. "metadata": {},
  265. "outputs": [
  266. {
  267. "data": {
  268. "text/plain": [
  269. "pdist_thread_hypot (generic function with 1 method)"
  270. ]
  271. },
  272. "execution_count": 11,
  273. "metadata": {},
  274. "output_type": "execute_result"
  275. }
  276. ],
  277. "source": [
  278. "function pdist_thread_hypot(x, y)\n",
  279. " n = length(x)\n",
  280. " dist = zeros(n, n)\n",
  281. " @threads for j in 1:n\n",
  282. " for i in 1:n\n",
  283. " dist[i,j] = hypot(x[i] - x[j], y[i] - y[j])\n",
  284. " end\n",
  285. " end\n",
  286. " return dist\n",
  287. "end"
  288. ]
  289. },
  290. {
  291. "cell_type": "code",
  292. "execution_count": 12,
  293. "metadata": {
  294. "collapsed": true
  295. },
  296. "outputs": [],
  297. "source": [
  298. "n = 100\n",
  299. "x, y = rand(n), rand(n);"
  300. ]
  301. },
  302. {
  303. "cell_type": "code",
  304. "execution_count": 13,
  305. "metadata": {},
  306. "outputs": [
  307. {
  308. "data": {
  309. "text/plain": [
  310. "BenchmarkTools.Trial: \n",
  311. " memory estimate: 78.20 KiB\n",
  312. " allocs estimate: 2\n",
  313. " --------------\n",
  314. " minimum time: 62.063 μs (0.00% GC)\n",
  315. " median time: 67.215 μs (0.00% GC)\n",
  316. " mean time: 74.850 μs (3.95% GC)\n",
  317. " maximum time: 2.004 ms (90.67% GC)\n",
  318. " --------------\n",
  319. " samples: 10000\n",
  320. " evals/sample: 1"
  321. ]
  322. },
  323. "execution_count": 13,
  324. "metadata": {},
  325. "output_type": "execute_result"
  326. }
  327. ],
  328. "source": [
  329. "@benchmark pdist(x,y)"
  330. ]
  331. },
  332. {
  333. "cell_type": "code",
  334. "execution_count": 47,
  335. "metadata": {},
  336. "outputs": [
  337. {
  338. "data": {
  339. "text/plain": [
  340. "BenchmarkTools.Trial: \n",
  341. " memory estimate: 78.20 KiB\n",
  342. " allocs estimate: 2\n",
  343. " --------------\n",
  344. " minimum time: 36.741 μs (0.00% GC)\n",
  345. " median time: 39.696 μs (0.00% GC)\n",
  346. " mean time: 41.591 μs (0.00% GC)\n",
  347. " maximum time: 780.681 μs (0.00% GC)\n",
  348. " --------------\n",
  349. " samples: 10000\n",
  350. " evals/sample: 1"
  351. ]
  352. },
  353. "execution_count": 47,
  354. "metadata": {},
  355. "output_type": "execute_result"
  356. }
  357. ],
  358. "source": [
  359. "@benchmark pdist_inbounds(x,y)"
  360. ]
  361. },
  362. {
  363. "cell_type": "code",
  364. "execution_count": 14,
  365. "metadata": {},
  366. "outputs": [
  367. {
  368. "data": {
  369. "text/plain": [
  370. "BenchmarkTools.Trial: \n",
  371. " memory estimate: 78.27 KiB\n",
  372. " allocs estimate: 3\n",
  373. " --------------\n",
  374. " minimum time: 25.954 μs (0.00% GC)\n",
  375. " median time: 29.194 μs (0.00% GC)\n",
  376. " mean time: 58.706 μs (5.58% GC)\n",
  377. " maximum time: 17.391 ms (0.00% GC)\n",
  378. " --------------\n",
  379. " samples: 10000\n",
  380. " evals/sample: 1"
  381. ]
  382. },
  383. "execution_count": 14,
  384. "metadata": {},
  385. "output_type": "execute_result"
  386. }
  387. ],
  388. "source": [
  389. "@benchmark pdist_thread(x,y)"
  390. ]
  391. },
  392. {
  393. "cell_type": "code",
  394. "execution_count": 16,
  395. "metadata": {},
  396. "outputs": [
  397. {
  398. "data": {
  399. "text/plain": [
  400. "BenchmarkTools.Trial: \n",
  401. " memory estimate: 78.27 KiB\n",
  402. " allocs estimate: 3\n",
  403. " --------------\n",
  404. " minimum time: 13.056 μs (0.00% GC)\n",
  405. " median time: 21.805 μs (0.00% GC)\n",
  406. " mean time: 82.652 μs (4.41% GC)\n",
  407. " maximum time: 33.319 ms (0.00% GC)\n",
  408. " --------------\n",
  409. " samples: 10000\n",
  410. " evals/sample: 1"
  411. ]
  412. },
  413. "execution_count": 16,
  414. "metadata": {},
  415. "output_type": "execute_result"
  416. }
  417. ],
  418. "source": [
  419. "@benchmark pdist_thread_inbounds(x,y)"
  420. ]
  421. },
  422. {
  423. "cell_type": "code",
  424. "execution_count": 17,
  425. "metadata": {
  426. "scrolled": true
  427. },
  428. "outputs": [
  429. {
  430. "data": {
  431. "text/plain": [
  432. "BenchmarkTools.Trial: \n",
  433. " memory estimate: 78.27 KiB\n",
  434. " allocs estimate: 3\n",
  435. " --------------\n",
  436. " minimum time: 13.045 μs (0.00% GC)\n",
  437. " median time: 21.896 μs (0.00% GC)\n",
  438. " mean time: 30.416 μs (11.45% GC)\n",
  439. " maximum time: 7.469 ms (0.00% GC)\n",
  440. " --------------\n",
  441. " samples: 10000\n",
  442. " evals/sample: 1"
  443. ]
  444. },
  445. "execution_count": 17,
  446. "metadata": {},
  447. "output_type": "execute_result"
  448. }
  449. ],
  450. "source": [
  451. "@benchmark pdist_thread_inbounds_sp(x,y)"
  452. ]
  453. },
  454. {
  455. "cell_type": "code",
  456. "execution_count": 44,
  457. "metadata": {},
  458. "outputs": [
  459. {
  460. "name": "stdout",
  461. "output_type": "stream",
  462. "text": [
  463. " 0.002618 seconds (1.06 k allocations: 49.031 KiB)\n"
  464. ]
  465. }
  466. ],
  467. "source": [
  468. "@time pdist_proc(x,y);"
  469. ]
  470. },
  471. {
  472. "cell_type": "code",
  473. "execution_count": 19,
  474. "metadata": {},
  475. "outputs": [
  476. {
  477. "data": {
  478. "text/plain": [
  479. "BenchmarkTools.Trial: \n",
  480. " memory estimate: 78.20 KiB\n",
  481. " allocs estimate: 2\n",
  482. " --------------\n",
  483. " minimum time: 120.076 μs (0.00% GC)\n",
  484. " median time: 137.538 μs (0.00% GC)\n",
  485. " mean time: 140.645 μs (0.00% GC)\n",
  486. " maximum time: 234.016 μs (0.00% GC)\n",
  487. " --------------\n",
  488. " samples: 10000\n",
  489. " evals/sample: 1"
  490. ]
  491. },
  492. "execution_count": 19,
  493. "metadata": {},
  494. "output_type": "execute_result"
  495. }
  496. ],
  497. "source": [
  498. "@benchmark pdist_hypot(x,y)"
  499. ]
  500. },
  501. {
  502. "cell_type": "code",
  503. "execution_count": 20,
  504. "metadata": {},
  505. "outputs": [
  506. {
  507. "data": {
  508. "text/plain": [
  509. "BenchmarkTools.Trial: \n",
  510. " memory estimate: 78.27 KiB\n",
  511. " allocs estimate: 3\n",
  512. " --------------\n",
  513. " minimum time: 43.035 μs (0.00% GC)\n",
  514. " median time: 45.851 μs (0.00% GC)\n",
  515. " mean time: 49.708 μs (0.00% GC)\n",
  516. " maximum time: 11.202 ms (0.00% GC)\n",
  517. " --------------\n",
  518. " samples: 10000\n",
  519. " evals/sample: 1"
  520. ]
  521. },
  522. "execution_count": 20,
  523. "metadata": {},
  524. "output_type": "execute_result"
  525. }
  526. ],
  527. "source": [
  528. "@benchmark pdist_thread_hypot(x,y)"
  529. ]
  530. },
  531. {
  532. "cell_type": "code",
  533. "execution_count": 21,
  534. "metadata": {},
  535. "outputs": [
  536. {
  537. "data": {
  538. "text/plain": [
  539. "BenchmarkTools.Trial: \n",
  540. " memory estimate: 89.34 KiB\n",
  541. " allocs estimate: 205\n",
  542. " --------------\n",
  543. " minimum time: 92.835 μs (0.00% GC)\n",
  544. " median time: 98.546 μs (0.00% GC)\n",
  545. " mean time: 101.390 μs (0.00% GC)\n",
  546. " maximum time: 1.467 ms (0.00% GC)\n",
  547. " --------------\n",
  548. " samples: 10000\n",
  549. " evals/sample: 1"
  550. ]
  551. },
  552. "execution_count": 21,
  553. "metadata": {},
  554. "output_type": "execute_result"
  555. }
  556. ],
  557. "source": [
  558. "a = [x'; y']\n",
  559. "@benchmark pairwise(Euclidean(), a, a)"
  560. ]
  561. },
  562. {
  563. "cell_type": "code",
  564. "execution_count": 22,
  565. "metadata": {},
  566. "outputs": [
  567. {
  568. "data": {
  569. "text/plain": [
  570. "true"
  571. ]
  572. },
  573. "execution_count": 22,
  574. "metadata": {},
  575. "output_type": "execute_result"
  576. }
  577. ],
  578. "source": [
  579. "pdist(x,y) ≈ pdist_hypot(x,y) ≈ pdist_thread(x,y) ≈ pdist_thread_hypot(x,y) ≈ pairwise(Euclidean(), [x'; y'], [x'; y'])"
  580. ]
  581. }
  582. ],
  583. "metadata": {
  584. "kernelspec": {
  585. "display_name": "Julia 0.6.1",
  586. "language": "julia",
  587. "name": "julia-0.6"
  588. },
  589. "language_info": {
  590. "file_extension": ".jl",
  591. "mimetype": "application/julia",
  592. "name": "julia",
  593. "version": "0.6.2"
  594. },
  595. "toc": {
  596. "nav_menu": {},
  597. "number_sections": true,
  598. "sideBar": true,
  599. "skip_h1_title": false,
  600. "toc_cell": false,
  601. "toc_position": {},
  602. "toc_section_display": "block",
  603. "toc_window_display": false
  604. }
  605. },
  606. "nbformat": 4,
  607. "nbformat_minor": 2
  608. }
Add Comment
Please, Sign In to add comment