0909_comparing_UFDS.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyME4/wxGku1YjramC23gFht",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/lmcanavals/acomplex/blob/main/0909_comparing_UFDS.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 22,
      "metadata": {
        "id": "OajAMZmwqGYd"
      },
      "outputs": [],
      "source": [
        "class DisjointSet:\n",
        "    def __init__(self, n):\n",
        "        self.lst = [-1]*n\n",
        "\n",
        "    def find(self, a):\n",
        "        if self.lst[a] < 0:\n",
        "            return a\n",
        "        else:\n",
        "            parent = self.find(self.lst[a])\n",
        "            self.lst[a] = parent\n",
        "            return parent\n",
        "\n",
        "    def isSameSet(self, a, b):\n",
        "        return self.find(a) == self.find(b)\n",
        "\n",
        "    def union(self, a, b):\n",
        "        a = self.find(a)\n",
        "        b = self.find(b)\n",
        "        if a == b: return\n",
        "        if -self.lst[a] > -self.lst[b]:\n",
        "           self.lst[a] += self.lst[b]\n",
        "           self.lst[b] = a\n",
        "        else:\n",
        "           self.lst[b] += self.lst[a]\n",
        "           self.lst[a] = b"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%file 1.in\n",
        "a b c d e f g h i j\n",
        "a b\n",
        "b d\n",
        "c f\n",
        "c i\n",
        "j e\n",
        "g j"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "jZ9GPwf0rDx_",
        "outputId": "3e821395-ec72-47a1-bc24-df0e8c3635b4"
      },
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Writing 1.in\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "with open(\"1.in\") as f:\n",
        "    labels = f.readline().strip().split()\n",
        "    lbl2idx = {lbl: i for i, lbl in enumerate(labels)}\n",
        "    ds = DisjointSet(len(labels))\n",
        "    G = [[] for _ in range(len(labels))]\n",
        "    for line in f:\n",
        "        u, v = line.strip().split()\n",
        "        u, v = lbl2idx[u], lbl2idx[v]\n",
        "        ds.union(u, v)\n",
        "        G[u].append(v)\n",
        "        G[v].append(u)"
      ],
      "metadata": {
        "id": "1qCS8fberXx7"
      },
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def isFriend(a, b):\n",
        "    a, b = lbl2idx[a], lbl2idx[b]\n",
        "    return ds.isSameSet(a, b)\n",
        "\n",
        "def isDirectFriend(a, b):\n",
        "    a, b = lbl2idx[a], lbl2idx[b]\n",
        "    for v in G[a]:\n",
        "        if v == b:\n",
        "            return True\n",
        "    return False"
      ],
      "metadata": {
        "id": "L8tCNrdurwj5"
      },
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "isFriend(\"i\", \"f\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kXVnua7gtUe6",
        "outputId": "aea9b3b2-0968-44ba-f706-f568909eec24"
      },
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "isDirectFriend(\"i\", \"f\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "1e0qPxcmtYoI",
        "outputId": "c4d969a0-b06f-4c2d-e78b-585bb9dc8195"
      },
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "False"
            ]
          },
          "metadata": {},
          "execution_count": 9
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "isDirectFriend(\"i\", \"c\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "057G3F6FtfaM",
        "outputId": "32d570c6-8496-42f6-8a41-4bce480b4f87"
      },
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {},
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Test Case for Ejercicio 1: UFDS"
      ],
      "metadata": {
        "id": "eXsWnd9Iu-3q"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import random\n",
        "\n",
        "def test(DSClass, n=10000):\n",
        "    random.seed(42)\n",
        "    ds = DSClass(n)\n",
        "    for _ in range(n):\n",
        "        a = random.randint(0, n-1)\n",
        "        b = random.randint(0, n-1)\n",
        "        ds.union(a, b)"
      ],
      "metadata": {
        "id": "Fqb8Gw2ZtiYU"
      },
      "execution_count": 19,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "class DisjointSetQF:\n",
        "    def __init__(self, n):\n",
        "        self.lst = list(range(n))\n",
        "\n",
        "    def find(self, a):\n",
        "        return self.lst[a]\n",
        "\n",
        "    def isSameSet(self, a, b):\n",
        "        return self.find(a) == self.find(b)\n",
        "\n",
        "    def union(self, a, b):\n",
        "        a = self.find(a)\n",
        "        b = self.find(b)\n",
        "        if a == b: return\n",
        "        for i, p in enumerate(self.lst):\n",
        "            if a == i:\n",
        "                self.lst[i] = b"
      ],
      "metadata": {
        "id": "0ReOJtqtvgBR"
      },
      "execution_count": 25,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "class DisjointSetQU:\n",
        "    def __init__(self, n):\n",
        "        self.lst = list(range(n))\n",
        "\n",
        "    def find(self, a):\n",
        "        while a != self.lst[a]:\n",
        "            a = self.lst[a]\n",
        "        return a\n",
        "\n",
        "    def isSameSet(self, a, b):\n",
        "        return self.find(a) == self.find(b)\n",
        "\n",
        "    def union(self, a, b):\n",
        "        a = self.find(a)\n",
        "        b = self.find(b)\n",
        "        if a == b: return\n",
        "        self.lst[a] = b"
      ],
      "metadata": {
        "id": "6P21G1suzN-B"
      },
      "execution_count": 29,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "class DisjointSetWU:\n",
        "    def __init__(self, n):\n",
        "        self.lst = [-1]*n\n",
        "\n",
        "    def find(self, a):\n",
        "        if self.lst[a] < 0:\n",
        "            return a\n",
        "        else:\n",
        "            return self.find(self.lst[a])\n",
        "    #def find(self, a):\n",
        "    #    while self.lst[a] >= 0:\n",
        "    #        a = self.lst[a]\n",
        "    #    return a\n",
        "\n",
        "    def isSameSet(self, a, b):\n",
        "        return self.find(a) == self.find(b)\n",
        "\n",
        "    def union(self, a, b):\n",
        "        a = self.find(a)\n",
        "        b = self.find(b)\n",
        "        if a == b: return\n",
        "        if -self.lst[a] > -self.lst[b]:\n",
        "           self.lst[a] += self.lst[b]\n",
        "           self.lst[b] = a\n",
        "        else:\n",
        "           self.lst[b] += self.lst[a]\n",
        "           self.lst[a] = b\n"
      ],
      "metadata": {
        "id": "If08rtVx3AOQ"
      },
      "execution_count": 34,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "%timeit test(DisjointSet, n=1000_000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "X2e8nPJXvcIt",
        "outputId": "b6cfd9ed-e6f1-468b-e38d-8c083498acdb"
      },
      "execution_count": 38,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "3.12 s ± 379 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%timeit test(DisjointSetQF, n=1_000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7Wekb43tzHeQ",
        "outputId": "6f09e2d0-8698-4011-f3b1-e2ea8c212e07"
      },
      "execution_count": 28,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "41.3 ms ± 877 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%timeit test(DisjointSetQU, n=10_000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IFXRpE7A0W5j",
        "outputId": "e07dfcc2-9c21-492c-9602-a45e10b624ab"
      },
      "execution_count": 31,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "183 ms ± 16.4 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%timeit test(DisjointSetWU, n=1000_000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7qBAjTlJ2c1r",
        "outputId": "199c87e1-acb6-4bb0-c06a-a337ec777bec"
      },
      "execution_count": 39,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "3.11 s ± 255 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "09UaO6Dc3WgA"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}