{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"Distance Computation","version":"0.3.2","provenance":[{"file_id":"17r49CyXqliyiCg9PjqZ054b0BXojK-qI","timestamp":1558235558006},{"file_id":"1LlOwsp5zCV-dIfZRlmWMJfbeArUTclQo","timestamp":1558197890969}],"collapsed_sections":[]},"kernelspec":{"name":"python3","display_name":"Python 3"}},"cells":[{"cell_type":"code","metadata":{"id":"m2gRmBWeYgsF","colab_type":"code","outputId":"c2648fb0-a38a-4cfd-82c0-5613e899b970","executionInfo":{"status":"ok","timestamp":1565061490743,"user_tz":240,"elapsed":10219,"user":{"displayName":"David Fouhey","photoUrl":"","userId":"02572812228803709170"}},"colab":{"base_uri":"https://localhost:8080/","height":85}},"source":["#David Fouhey\n","#Computing distances a few ways\n","#UMich EECS 442 Fall 2019\n","\n","import numpy as np\n","import time\n","\n","\n","\n","if __name__ == \"__main__\":\n","    #Given two sets of points, compute the pairwise distances between them a \n","    #few different ways. Surprise surprise, it makes a huge difference how you\n","    #write this\n","    \n","    #dimension of the data points\n","    d = 128\n","    #Number of d-dimensional data points in each set\n","    N, M = 300, 400\n","    \n","    #N, M = 800, 1200 #(takes longer) 72.8151s / 6.1406s / 0.0274s\n","    \n","    #generate the two sets of points as Nxd and Mxd\n","    X = np.random.random(size=(N,d))\n","    Y = np.random.random(size=(M,d))\n","    \n","    ####################################\n","    #method 1, loop/loop/loop, use lists\n","    ####################################\n","    #\n","    #the for k in range(d) loop here really hurts\n","    \n","    #make a list of tuples (it's worse, it turns out to make them arrays)\n","    XList = [tuple(X[i,:]) for i in range(N)]\n","    YList = [tuple(Y[i,:]) for i in range(M)]\n","    D1 = np.zeros((N,M))\n","    \n","    #ok do it\n","    tic = time.time()\n","    for i in range(N):\n","      for j in range(M):\n","        dist = 0.0\n","        for k in range(d):\n","          dist += (XList[i][k] - YList[j][k])**2\n","        D1[i,j] = dist**0.5\n","    toc1 = time.time()-tic\n","    print(\"Method 0: %3.4fs\" % (toc1))\n","    \n","    ####################################\n","    #method 2, loop/loop, use np.linalg.norm to compute distance\n","    ####################################\n","    D2 = np.zeros((N,M))\n","    \n","    #ok do it\n","    tic = time.time()\n","    for i in range(N):\n","      for j in range(M):\n","        D2[i,j] = np.linalg.norm(X[i,:]-Y[j,:])\n","    toc2 = time.time()-tic\n","    print(\"Method 2: %3.4fs (Base is %.1fx slower)\" % (toc2,toc1/toc2))\n","    \n","    ####################################\n","    #method 3, no loops, just math\n","    ####################################\n","    tic = time.time()\n","    #Vectorized computation \n","    #\n","    #(XNorm+YNorm.T)_ij = \n","    #    ||X[i,:]||^2 + ||Y[j,:]||^2\n","    #(np.dot(X,Y.T))_ij = \n","    #    X[i,:]^T Y[j,:]\n","    #so in total it's:\n","    #   ||X[i,:]||^2 + ||Y[j,:]||^2 - 2*X[i,:]^T Y[j,:]\n","    \n","    #ok do it\n","    XNorm = np.sum(X**2,axis=1,keepdims=True) \n","    YNorm = np.sum(Y**2,axis=1,keepdims=True)\n","    D3 = (XNorm+YNorm.T-2*np.dot(X,Y.T))**0.5\n","    \n","    toc3 = time.time()-tic\n","    print(\"Method 3: %3.4fs (Base is %.1fx slower)\" % (toc3,toc1/toc3))\n","    \n","    if np.allclose(D1,D2) and np.allclose(D1,D3):\n","      print(\"All are basically the same answer\")\n","    else:\n","      print(\"Not all are close\")\n","    \n","    \n","    "],"execution_count":0,"outputs":[{"output_type":"stream","text":["Method 0: 9.0881s\n","Method 2: 0.7914s (Base is 11.5x slower)\n","Method 3: 0.0045s (Base is 2037.3x slower)\n","All are close\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"f4CeMmRhXG8y","colab_type":"text"},"source":[""]}]}