data-structure-typed - npm Package Compare versions

Comparing version 1.45.1 to 1.45.2

benchmark/report.json

 {
+  "comparation": {
+    "benchmarks": [
+      {
+        "test name": "SRC 10,000 add",
+        "time taken (ms)": "0.59",
+        "executions per sec": "1701.78",
+        "sample deviation": "3.28e-5"
+      },
+      {
+        "test name": "CJS 10,000 add",
+        "time taken (ms)": "0.61",
+        "executions per sec": "1648.70",
+        "sample deviation": "6.98e-5"
+      },
+      {
+        "test name": "MJS 10,000 add",
+        "time taken (ms)": "0.59",
+        "executions per sec": "1691.86",
+        "sample deviation": "2.44e-5"
+      },
+      {
+        "test name": "SRC PQ 10,000 add & pop",
+        "time taken (ms)": "4.97",
+        "executions per sec": "201.19",
+        "sample deviation": "1.37e-4"
+      },
+      {
+        "test name": "CJS PQ 10,000 add & pop",
+        "time taken (ms)": "4.93",
+        "executions per sec": "202.70",
+        "sample deviation": "5.60e-5"
+      },
+      {
+        "test name": "MJS PQ 10,000 add & pop",
+        "time taken (ms)": "4.98",
+        "executions per sec": "200.74",
+        "sample deviation": "4.39e-4"
+      }
+    ],
+    "testName": "comparation"
+  },
   "avl-tree": {
@@ -6,4 +47,4 @@ "benchmarks": [
         "test name": "10,000 add randomly",
-        "time taken (ms)": "33.34",
-        "executions per sec": "29.99",
+        "time taken (ms)": "32.27",
+        "executions per sec": "30.99",
         "sample deviation": "0.00"
@@ -13,4 +54,4 @@ },
         "test name": "10,000 add & delete randomly",
-        "time taken (ms)": "72.30",
-        "executions per sec": "13.83",
+        "time taken (ms)": "73.67",
+        "executions per sec": "13.57",
         "sample deviation": "0.00"
@@ -20,4 +61,4 @@ },
         "test name": "10,000 addMany",
-        "time taken (ms)": "49.50",
-        "executions per sec": "20.20",
+        "time taken (ms)": "41.81",
+        "executions per sec": "23.92",
         "sample deviation": "0.00"
@@ -27,5 +68,5 @@ },
         "test name": "10,000 get",
-        "time taken (ms)": "27.23",
-        "executions per sec": "36.73",
-        "sample deviation": "7.19e-4"
+        "time taken (ms)": "29.21",
+        "executions per sec": "34.24",
+        "sample deviation": "0.00"
       }
@@ -39,28 +80,28 @@ ],
         "test name": "1,000 add randomly",
-        "time taken (ms)": "12.20",
-        "executions per sec": "81.97",
-        "sample deviation": "8.36e-5"
+        "time taken (ms)": "13.82",
+        "executions per sec": "72.38",
+        "sample deviation": "0.00"
       },
       {
         "test name": "1,000 add & delete randomly",
-        "time taken (ms)": "15.93",
-        "executions per sec": "62.77",
-        "sample deviation": "2.09e-4"
+        "time taken (ms)": "16.01",
+        "executions per sec": "62.45",
+        "sample deviation": "5.80e-4"
       },
       {
         "test name": "1,000 addMany",
-        "time taken (ms)": "10.36",
-        "executions per sec": "96.56",
-        "sample deviation": "2.01e-4"
+        "time taken (ms)": "12.30",
+        "executions per sec": "81.33",
+        "sample deviation": "0.01"
       },
       {
         "test name": "1,000 get",
-        "time taken (ms)": "18.43",
-        "executions per sec": "54.26",
-        "sample deviation": "4.67e-4"
+        "time taken (ms)": "19.75",
+        "executions per sec": "50.63",
+        "sample deviation": "0.01"
       },
       {
         "test name": "1,000 dfs",
-        "time taken (ms)": "154.61",
-        "executions per sec": "6.47",
+        "time taken (ms)": "157.12",
+        "executions per sec": "6.36",
         "sample deviation": "0.00"
@@ -70,11 +111,11 @@ },
         "test name": "1,000 bfs",
-        "time taken (ms)": "57.73",
-        "executions per sec": "17.32",
-        "sample deviation": "0.01"
+        "time taken (ms)": "56.72",
+        "executions per sec": "17.63",
+        "sample deviation": "4.27e-4"
       },
       {
         "test name": "1,000 morris",
-        "time taken (ms)": "258.47",
-        "executions per sec": "3.87",
-        "sample deviation": "0.00"
+        "time taken (ms)": "334.97",
+        "executions per sec": "2.99",
+        "sample deviation": "0.03"
       }
@@ -88,10 +129,10 @@ ],
         "test name": "10,000 add randomly",
-        "time taken (ms)": "29.44",
-        "executions per sec": "33.96",
-        "sample deviation": "3.99e-4"
+        "time taken (ms)": "28.30",
+        "executions per sec": "35.34",
+        "sample deviation": "0.00"
       },
       {
         "test name": "10,000 add & delete randomly",
-        "time taken (ms)": "72.35",
-        "executions per sec": "13.82",
+        "time taken (ms)": "67.47",
+        "executions per sec": "14.82",
         "sample deviation": "0.00"
@@ -101,4 +142,4 @@ },
         "test name": "10,000 addMany",
-        "time taken (ms)": "29.76",
-        "executions per sec": "33.60",
+        "time taken (ms)": "29.25",
+        "executions per sec": "34.18",
         "sample deviation": "0.00"
@@ -108,5 +149,5 @@ },
         "test name": "10,000 get",
-        "time taken (ms)": "28.53",
-        "executions per sec": "35.05",
-        "sample deviation": "5.76e-4"
+        "time taken (ms)": "30.53",
+        "executions per sec": "32.75",
+        "sample deviation": "0.01"
       }
@@ -120,4 +161,4 @@ ],
         "test name": "100,000 add",
-        "time taken (ms)": "90.42",
-        "executions per sec": "11.06",
+        "time taken (ms)": "96.67",
+        "executions per sec": "10.34",
         "sample deviation": "0.01"
@@ -127,11 +168,11 @@ },
         "test name": "100,000 add & delete randomly",
-        "time taken (ms)": "223.52",
-        "executions per sec": "4.47",
-        "sample deviation": "0.02"
+        "time taken (ms)": "224.85",
+        "executions per sec": "4.45",
+        "sample deviation": "0.01"
       },
       {
         "test name": "100,000 getNode",
-        "time taken (ms)": "38.67",
-        "executions per sec": "25.86",
-        "sample deviation": "0.00"
+        "time taken (ms)": "40.83",
+        "executions per sec": "24.49",
+        "sample deviation": "2.73e-4"
       }
@@ -146,10 +187,10 @@ ],
         "time taken (ms)": "0.11",
-        "executions per sec": "9499.56",
-        "sample deviation": "5.09e-6"
+        "executions per sec": "9364.63",
+        "sample deviation": "1.25e-5"
       },
       {
         "test name": "1,000 addEdge",
-        "time taken (ms)": "6.37",
-        "executions per sec": "157.04",
-        "sample deviation": "8.13e-4"
+        "time taken (ms)": "6.18",
+        "executions per sec": "161.78",
+        "sample deviation": "1.26e-4"
       },
@@ -159,21 +200,21 @@ {
         "time taken (ms)": "0.05",
-        "executions per sec": "2.15e+4",
-        "sample deviation": "1.20e-6"
+        "executions per sec": "2.12e+4",
+        "sample deviation": "4.19e-6"
       },
       {
         "test name": "1,000 getEdge",
-        "time taken (ms)": "22.44",
-        "executions per sec": "44.56",
-        "sample deviation": "0.00"
+        "time taken (ms)": "25.98",
+        "executions per sec": "38.50",
+        "sample deviation": "0.01"
       },
       {
         "test name": "tarjan",
-        "time taken (ms)": "213.53",
-        "executions per sec": "4.68",
-        "sample deviation": "0.01"
+        "time taken (ms)": "240.23",
+        "executions per sec": "4.16",
+        "sample deviation": "0.02"
       },
       {
         "test name": "tarjan all",
-        "time taken (ms)": "215.75",
-        "executions per sec": "4.63",
+        "time taken (ms)": "227.36",
+        "executions per sec": "4.40",
         "sample deviation": "0.00"
@@ -183,5 +224,5 @@ },
         "test name": "topologicalSort",
-        "time taken (ms)": "175.51",
-        "executions per sec": "5.70",
-        "sample deviation": "0.01"
+        "time taken (ms)": "185.85",
+        "executions per sec": "5.38",
+        "sample deviation": "0.00"
       }
@@ -195,11 +236,11 @@ ],
         "test name": "10,000 set",
-        "time taken (ms)": "0.76",
-        "executions per sec": "1308.63",
-        "sample deviation": "1.65e-5"
+        "time taken (ms)": "1.00",
+        "executions per sec": "1001.31",
+        "sample deviation": "1.82e-5"
       },
       {
         "test name": "10,000 set & get",
-        "time taken (ms)": "1.03",
-        "executions per sec": "966.59",
-        "sample deviation": "2.21e-5"
+        "time taken (ms)": "1.54",
+        "executions per sec": "650.14",
+        "sample deviation": "4.87e-5"
       }
@@ -213,11 +254,11 @@ ],
         "test name": "10,000 add & pop",
-        "time taken (ms)": "4.65",
-        "executions per sec": "214.92",
-        "sample deviation": "1.18e-4"
+        "time taken (ms)": "6.97",
+        "executions per sec": "143.49",
+        "sample deviation": "5.27e-4"
       },
       {
         "test name": "10,000 fib add & pop",
-        "time taken (ms)": "367.35",
-        "executions per sec": "2.72",
-        "sample deviation": "0.01"
+        "time taken (ms)": "378.40",
+        "executions per sec": "2.64",
+        "sample deviation": "0.05"
       }
@@ -231,17 +272,17 @@ ],
         "test name": "1,000,000 unshift",
-        "time taken (ms)": "222.80",
-        "executions per sec": "4.49",
-        "sample deviation": "0.06"
+        "time taken (ms)": "224.55",
+        "executions per sec": "4.45",
+        "sample deviation": "0.07"
       },
       {
         "test name": "1,000,000 unshift & shift",
-        "time taken (ms)": "174.60",
-        "executions per sec": "5.73",
-        "sample deviation": "0.04"
+        "time taken (ms)": "182.17",
+        "executions per sec": "5.49",
+        "sample deviation": "0.06"
       },
       {
         "test name": "1,000,000 insertBefore",
-        "time taken (ms)": "309.21",
-        "executions per sec": "3.23",
-        "sample deviation": "0.07"
+        "time taken (ms)": "342.63",
+        "executions per sec": "2.92",
+        "sample deviation": "0.08"
       }
@@ -255,4 +296,4 @@ ],
         "test name": "10,000 push & pop",
-        "time taken (ms)": "214.75",
-        "executions per sec": "4.66",
+        "time taken (ms)": "222.42",
+        "executions per sec": "4.50",
         "sample deviation": "0.01"
@@ -262,5 +303,5 @@ },
         "test name": "10,000 insertBefore",
-        "time taken (ms)": "250.45",
-        "executions per sec": "3.99",
-        "sample deviation": "0.01"
+        "time taken (ms)": "248.39",
+        "executions per sec": "4.03",
+        "sample deviation": "0.00"
       }
@@ -274,5 +315,5 @@ ],
         "test name": "10,000 refill & poll",
-        "time taken (ms)": "11.44",
-        "executions per sec": "87.43",
-        "sample deviation": "1.80e-4"
+        "time taken (ms)": "11.83",
+        "executions per sec": "84.55",
+        "sample deviation": "1.45e-4"
       }
@@ -286,5 +327,5 @@ ],
         "test name": "10,000 add & pop",
-        "time taken (ms)": "12.41",
-        "executions per sec": "80.57",
-        "sample deviation": "1.56e-4"
+        "time taken (ms)": "10.79",
+        "executions per sec": "92.72",
+        "sample deviation": "2.01e-4"
       }
@@ -298,11 +339,11 @@ ],
         "test name": "1,000,000 push",
-        "time taken (ms)": "219.15",
-        "executions per sec": "4.56",
-        "sample deviation": "0.04"
+        "time taken (ms)": "231.33",
+        "executions per sec": "4.32",
+        "sample deviation": "0.06"
       },
       {
         "test name": "1,000,000 shift",
-        "time taken (ms)": "26.76",
-        "executions per sec": "37.37",
-        "sample deviation": "0.00"
+        "time taken (ms)": "27.64",
+        "executions per sec": "36.17",
+        "sample deviation": "0.01"
       }
@@ -316,4 +357,4 @@ ],
         "test name": "1,000,000 push",
-        "time taken (ms)": "45.17",
-        "executions per sec": "22.14",
+        "time taken (ms)": "46.16",
+        "executions per sec": "21.66",
         "sample deviation": "0.01"
@@ -323,4 +364,4 @@ },
         "test name": "1,000,000 push & shift",
-        "time taken (ms)": "80.41",
-        "executions per sec": "12.44",
+        "time taken (ms)": "82.18",
+        "executions per sec": "12.17",
         "sample deviation": "0.00"
@@ -335,4 +376,4 @@ }
         "test name": "1,000,000 push",
-        "time taken (ms)": "43.67",
-        "executions per sec": "22.90",
+        "time taken (ms)": "45.45",
+        "executions per sec": "22.00",
         "sample deviation": "0.01"
@@ -342,5 +383,5 @@ },
         "test name": "1,000,000 push & pop",
-        "time taken (ms)": "48.18",
-        "executions per sec": "20.76",
-        "sample deviation": "0.00"
+        "time taken (ms)": "50.10",
+        "executions per sec": "19.96",
+        "sample deviation": "0.01"
       }
@@ -354,4 +395,4 @@ ],
         "test name": "100,000 push",
-        "time taken (ms)": "60.46",
-        "executions per sec": "16.54",
+        "time taken (ms)": "46.25",
+        "executions per sec": "21.62",
         "sample deviation": "0.00"
@@ -361,4 +402,4 @@ },
         "test name": "100,000 getWords",
-        "time taken (ms)": "83.13",
-        "executions per sec": "12.03",
+        "time taken (ms)": "65.17",
+        "executions per sec": "15.34",
         "sample deviation": "0.00"
@@ -365,0 +406,0 @@ }

CHANGELOG.md

@@ -11,3 +11,3 @@ # Changelog
 
-## [v1.45.1](https://github.com/zrwusa/data-structure-typed/compare/v1.35.0...main) (upcoming)
+## [v1.45.2](https://github.com/zrwusa/data-structure-typed/compare/v1.35.0...main) (upcoming)
 
@@ -14,0 +14,0 @@ ### Changes

COMMANDS.md

@@ -8,2 +8,5 @@ # Commands
 - `npm install` Installs all dependencies and creates the folder `node_modules`, that is needed for all following commands.
+- `npm run lint` Lint src/ and test/ codebase (using ESLint)
+- `npm run format` Pretty src/ and test/ codebase (using Prettier)
+- `npm run inspect` Check src/ and test/ codebase (using TSC and ESLint)
 - `npm run changelog` Update CHANGELOG.md
@@ -14,3 +17,5 @@ - `npm login` + `npm publish` To publish a new release. Be sure to run npm run package first.
 
-- `npm test` Run all unit tests (using Jest) with reporting coverage
+- `npm test` or `npm run test:unit` Run all unit tests (using Jest) with reporting coverage
+- `npm test:perf` Run all performance tests (using Benchmark.js) with reporting results
+- `npm run test:perf -- priority-queue.test` Run specific performance test
 
@@ -17,0 +22,0 @@ [//]: # (- `npm run coverage-badge` Updates code coverage badge inside `README.md`)

dist/cjs/data-structures/heap/heap.js

@@ -274,15 +274,24 @@ "use strict";
     bubbleUp(index) {
-        const element = this.nodes[index];
+        // const element = this.nodes[index];
+        // while (index > 0) {
+        //   const parentIndex = (index - 1) >> 1;
+        //   const parent = this.nodes[parentIndex];
+        //   if (this.comparator(element, parent) < 0) {
+        //     this.nodes[index] = parent;
+        //     this.nodes[parentIndex] = element;
+        //     index = parentIndex;
+        //   } else {
+        //     break;
+        //   }
+        // }
+        const item = this.nodes[index];
         while (index > 0) {
-            const parentIndex = Math.floor((index - 1) / 2);
-            const parent = this.nodes[parentIndex];
-            if (this.comparator(element, parent) < 0) {
-                this.nodes[index] = parent;
-                this.nodes[parentIndex] = element;
-                index = parentIndex;
-            }
-            else {
+            const parent = (index - 1) >> 1;
+            const parentItem = this.nodes[parent];
+            if (this.comparator(parentItem, item) <= 0)
                 break;
-            }
+            this.nodes[index] = parentItem;
+            index = parent;
         }
+        this.nodes[index] = item;
     }
@@ -301,4 +310,4 @@ /**
     sinkDown(index) {
-        const leftChildIndex = 2 * index + 1;
-        const rightChildIndex = 2 * index + 2;
+        const leftChildIndex = index << 1 | 1;
+        const rightChildIndex = leftChildIndex + 1;
         const length = this.nodes.length;
@@ -305,0 +314,0 @@ let targetIndex = index;

dist/mjs/data-structures/heap/heap.js

@@ -271,15 +271,24 @@ /**
     bubbleUp(index) {
-        const element = this.nodes[index];
+        // const element = this.nodes[index];
+        // while (index > 0) {
+        //   const parentIndex = (index - 1) >> 1;
+        //   const parent = this.nodes[parentIndex];
+        //   if (this.comparator(element, parent) < 0) {
+        //     this.nodes[index] = parent;
+        //     this.nodes[parentIndex] = element;
+        //     index = parentIndex;
+        //   } else {
+        //     break;
+        //   }
+        // }
+        const item = this.nodes[index];
         while (index > 0) {
-            const parentIndex = Math.floor((index - 1) / 2);
-            const parent = this.nodes[parentIndex];
-            if (this.comparator(element, parent) < 0) {
-                this.nodes[index] = parent;
-                this.nodes[parentIndex] = element;
-                index = parentIndex;
-            }
-            else {
+            const parent = (index - 1) >> 1;
+            const parentItem = this.nodes[parent];
+            if (this.comparator(parentItem, item) <= 0)
                 break;
-            }
+            this.nodes[index] = parentItem;
+            index = parent;
         }
+        this.nodes[index] = item;
     }
@@ -298,4 +307,4 @@ /**
     sinkDown(index) {
-        const leftChildIndex = 2 * index + 1;
-        const rightChildIndex = 2 * index + 2;
+        const leftChildIndex = index << 1 | 1;
+        const rightChildIndex = leftChildIndex + 1;
         const length = this.nodes.length;
@@ -302,0 +311,0 @@ let targetIndex = index;

package.json

 {
   "name": "data-structure-typed",
-  "version": "1.45.1",
+  "version": "1.45.2",
   "description": "Data Structures of Javascript & TypeScript. Binary Tree, BST, Graph, Heap, Priority Queue, Linked List, Queue, Deque, Stack, AVL Tree, Tree Multiset, Trie, Directed Graph, Undirected Graph, Singly Linked List, Doubly Linked List, Max Heap, Max Priority Queue, Min Heap, Min Priority Queue.",
@@ -5,0 +5,0 @@ "main": "dist/cjs/index.js",

README.md

@@ -737,48 +737,51 @@ # Data Structure Typed
 <div class="json-to-html-collapse clearfix 0">
+      <div class='collapsible level0' ><span class='json-to-html-label'>comparation</span></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>SRC 10,000 add</td><td>0.59</td><td>1701.78</td><td>3.28e-5</td></tr><tr><td>CJS 10,000 add</td><td>0.61</td><td>1648.70</td><td>6.98e-5</td></tr><tr><td>MJS 10,000 add</td><td>0.59</td><td>1691.86</td><td>2.44e-5</td></tr><tr><td>SRC PQ 10,000 add & pop</td><td>4.97</td><td>201.19</td><td>1.37e-4</td></tr><tr><td>CJS PQ 10,000 add & pop</td><td>4.93</td><td>202.70</td><td>5.60e-5</td></tr><tr><td>MJS PQ 10,000 add & pop</td><td>4.98</td><td>200.74</td><td>4.39e-4</td></tr></table></div>
+    </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>avl-tree</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add randomly</td><td>33.34</td><td>29.99</td><td>0.00</td></tr><tr><td>10,000 add & delete randomly</td><td>72.30</td><td>13.83</td><td>0.00</td></tr><tr><td>10,000 addMany</td><td>49.50</td><td>20.20</td><td>0.00</td></tr><tr><td>10,000 get</td><td>27.23</td><td>36.73</td><td>7.19e-4</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add randomly</td><td>32.27</td><td>30.99</td><td>0.00</td></tr><tr><td>10,000 add & delete randomly</td><td>73.67</td><td>13.57</td><td>0.00</td></tr><tr><td>10,000 addMany</td><td>41.81</td><td>23.92</td><td>0.00</td></tr><tr><td>10,000 get</td><td>29.21</td><td>34.24</td><td>0.00</td></tr></table></div>
     </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>binary-tree</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000 add randomly</td><td>12.20</td><td>81.97</td><td>8.36e-5</td></tr><tr><td>1,000 add & delete randomly</td><td>15.93</td><td>62.77</td><td>2.09e-4</td></tr><tr><td>1,000 addMany</td><td>10.36</td><td>96.56</td><td>2.01e-4</td></tr><tr><td>1,000 get</td><td>18.43</td><td>54.26</td><td>4.67e-4</td></tr><tr><td>1,000 dfs</td><td>154.61</td><td>6.47</td><td>0.00</td></tr><tr><td>1,000 bfs</td><td>57.73</td><td>17.32</td><td>0.01</td></tr><tr><td>1,000 morris</td><td>258.47</td><td>3.87</td><td>0.00</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000 add randomly</td><td>13.82</td><td>72.38</td><td>0.00</td></tr><tr><td>1,000 add & delete randomly</td><td>16.01</td><td>62.45</td><td>5.80e-4</td></tr><tr><td>1,000 addMany</td><td>12.30</td><td>81.33</td><td>0.01</td></tr><tr><td>1,000 get</td><td>19.75</td><td>50.63</td><td>0.01</td></tr><tr><td>1,000 dfs</td><td>157.12</td><td>6.36</td><td>0.00</td></tr><tr><td>1,000 bfs</td><td>56.72</td><td>17.63</td><td>4.27e-4</td></tr><tr><td>1,000 morris</td><td>334.97</td><td>2.99</td><td>0.03</td></tr></table></div>
     </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>bst</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add randomly</td><td>29.44</td><td>33.96</td><td>3.99e-4</td></tr><tr><td>10,000 add & delete randomly</td><td>72.35</td><td>13.82</td><td>0.00</td></tr><tr><td>10,000 addMany</td><td>29.76</td><td>33.60</td><td>0.00</td></tr><tr><td>10,000 get</td><td>28.53</td><td>35.05</td><td>5.76e-4</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add randomly</td><td>28.30</td><td>35.34</td><td>0.00</td></tr><tr><td>10,000 add & delete randomly</td><td>67.47</td><td>14.82</td><td>0.00</td></tr><tr><td>10,000 addMany</td><td>29.25</td><td>34.18</td><td>0.00</td></tr><tr><td>10,000 get</td><td>30.53</td><td>32.75</td><td>0.01</td></tr></table></div>
     </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>rb-tree</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 add</td><td>90.42</td><td>11.06</td><td>0.01</td></tr><tr><td>100,000 add & delete randomly</td><td>223.52</td><td>4.47</td><td>0.02</td></tr><tr><td>100,000 getNode</td><td>38.67</td><td>25.86</td><td>0.00</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 add</td><td>96.67</td><td>10.34</td><td>0.01</td></tr><tr><td>100,000 add & delete randomly</td><td>224.85</td><td>4.45</td><td>0.01</td></tr><tr><td>100,000 getNode</td><td>40.83</td><td>24.49</td><td>2.73e-4</td></tr></table></div>
     </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>directed-graph</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000 addVertex</td><td>0.11</td><td>9499.56</td><td>5.09e-6</td></tr><tr><td>1,000 addEdge</td><td>6.37</td><td>157.04</td><td>8.13e-4</td></tr><tr><td>1,000 getVertex</td><td>0.05</td><td>2.15e+4</td><td>1.20e-6</td></tr><tr><td>1,000 getEdge</td><td>22.44</td><td>44.56</td><td>0.00</td></tr><tr><td>tarjan</td><td>213.53</td><td>4.68</td><td>0.01</td></tr><tr><td>tarjan all</td><td>215.75</td><td>4.63</td><td>0.00</td></tr><tr><td>topologicalSort</td><td>175.51</td><td>5.70</td><td>0.01</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000 addVertex</td><td>0.11</td><td>9364.63</td><td>1.25e-5</td></tr><tr><td>1,000 addEdge</td><td>6.18</td><td>161.78</td><td>1.26e-4</td></tr><tr><td>1,000 getVertex</td><td>0.05</td><td>2.12e+4</td><td>4.19e-6</td></tr><tr><td>1,000 getEdge</td><td>25.98</td><td>38.50</td><td>0.01</td></tr><tr><td>tarjan</td><td>240.23</td><td>4.16</td><td>0.02</td></tr><tr><td>tarjan all</td><td>227.36</td><td>4.40</td><td>0.00</td></tr><tr><td>topologicalSort</td><td>185.85</td><td>5.38</td><td>0.00</td></tr></table></div>
     </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>hash-map</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 set</td><td>0.76</td><td>1308.63</td><td>1.65e-5</td></tr><tr><td>10,000 set & get</td><td>1.03</td><td>966.59</td><td>2.21e-5</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 set</td><td>1.00</td><td>1001.31</td><td>1.82e-5</td></tr><tr><td>10,000 set & get</td><td>1.54</td><td>650.14</td><td>4.87e-5</td></tr></table></div>
     </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>heap</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add & pop</td><td>4.65</td><td>214.92</td><td>1.18e-4</td></tr><tr><td>10,000 fib add & pop</td><td>367.35</td><td>2.72</td><td>0.01</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add & pop</td><td>6.97</td><td>143.49</td><td>5.27e-4</td></tr><tr><td>10,000 fib add & pop</td><td>378.40</td><td>2.64</td><td>0.05</td></tr></table></div>
     </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>doubly-linked-list</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 unshift</td><td>222.80</td><td>4.49</td><td>0.06</td></tr><tr><td>1,000,000 unshift & shift</td><td>174.60</td><td>5.73</td><td>0.04</td></tr><tr><td>1,000,000 insertBefore</td><td>309.21</td><td>3.23</td><td>0.07</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 unshift</td><td>224.55</td><td>4.45</td><td>0.07</td></tr><tr><td>1,000,000 unshift & shift</td><td>182.17</td><td>5.49</td><td>0.06</td></tr><tr><td>1,000,000 insertBefore</td><td>342.63</td><td>2.92</td><td>0.08</td></tr></table></div>
     </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>singly-linked-list</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 push & pop</td><td>214.75</td><td>4.66</td><td>0.01</td></tr><tr><td>10,000 insertBefore</td><td>250.45</td><td>3.99</td><td>0.01</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 push & pop</td><td>222.42</td><td>4.50</td><td>0.01</td></tr><tr><td>10,000 insertBefore</td><td>248.39</td><td>4.03</td><td>0.00</td></tr></table></div>
     </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>max-priority-queue</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 refill & poll</td><td>11.44</td><td>87.43</td><td>1.80e-4</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 refill & poll</td><td>11.83</td><td>84.55</td><td>1.45e-4</td></tr></table></div>
     </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>priority-queue</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add & pop</td><td>12.41</td><td>80.57</td><td>1.56e-4</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>10,000 add & pop</td><td>10.79</td><td>92.72</td><td>2.01e-4</td></tr></table></div>
     </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>deque</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>219.15</td><td>4.56</td><td>0.04</td></tr><tr><td>1,000,000 shift</td><td>26.76</td><td>37.37</td><td>0.00</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>231.33</td><td>4.32</td><td>0.06</td></tr><tr><td>1,000,000 shift</td><td>27.64</td><td>36.17</td><td>0.01</td></tr></table></div>
     </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>queue</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>45.17</td><td>22.14</td><td>0.01</td></tr><tr><td>1,000,000 push & shift</td><td>80.41</td><td>12.44</td><td>0.00</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>46.16</td><td>21.66</td><td>0.01</td></tr><tr><td>1,000,000 push & shift</td><td>82.18</td><td>12.17</td><td>0.00</td></tr></table></div>
     </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>stack</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>43.67</td><td>22.90</td><td>0.01</td></tr><tr><td>1,000,000 push & pop</td><td>48.18</td><td>20.76</td><td>0.00</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>1,000,000 push</td><td>45.45</td><td>22.00</td><td>0.01</td></tr><tr><td>1,000,000 push & pop</td><td>50.10</td><td>19.96</td><td>0.01</td></tr></table></div>
     </div><div class="json-to-html-collapse clearfix 0">
       <div class='collapsible level0' ><span class='json-to-html-label'>trie</span></div>
-      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 push</td><td>60.46</td><td>16.54</td><td>0.00</td></tr><tr><td>100,000 getWords</td><td>83.13</td><td>12.03</td><td>0.00</td></tr></table></div>
+      <div class="content"><table style="display: table; width:100%; table-layout: fixed;"><tr><th>test name</th><th>time taken (ms)</th><th>executions per sec</th><th>sample deviation</th></tr><tr><td>100,000 push</td><td>46.25</td><td>21.62</td><td>0.00</td></tr><tr><td>100,000 getWords</td><td>65.17</td><td>15.34</td><td>0.00</td></tr></table></div>
     </div>
 
 [//]: # (No deletion!!! End of Replace Section)

src/data-structures/heap/heap.ts

@@ -308,14 +308,24 @@ /**
   protected bubbleUp(index: number): void {
-    const element = this.nodes[index];
+    // const element = this.nodes[index];
+    // while (index > 0) {
+    //   const parentIndex = (index - 1) >> 1;
+    //   const parent = this.nodes[parentIndex];
+    //   if (this.comparator(element, parent) < 0) {
+    //     this.nodes[index] = parent;
+    //     this.nodes[parentIndex] = element;
+    //     index = parentIndex;
+    //   } else {
+    //     break;
+    //   }
+    // }
+
+    const item = this.nodes[index];
     while (index > 0) {
-      const parentIndex = Math.floor((index - 1) / 2);
-      const parent = this.nodes[parentIndex];
-      if (this.comparator(element, parent) < 0) {
-        this.nodes[index] = parent;
-        this.nodes[parentIndex] = element;
-        index = parentIndex;
-      } else {
-        break;
-      }
+      const parent = (index - 1) >> 1;
+      const parentItem = this.nodes[parent];
+      if (this.comparator(parentItem, item) <= 0) break;
+      this.nodes[index] = parentItem;
+      index = parent;
     }
+    this.nodes[index] = item;
   }
@@ -336,4 +346,4 @@
   protected sinkDown(index: number): void {
-    const leftChildIndex = 2 * index + 1;
-    const rightChildIndex = 2 * index + 2;
+    const leftChildIndex = index << 1 | 1;
+    const rightChildIndex = leftChildIndex + 1;
     const length = this.nodes.length;
@@ -340,0 +350,0 @@ let targetIndex = index;

test/performance/data-structures/binary-tree/rb-tree.test.ts

@@ -11,3 +11,3 @@ import { RedBlackTree } from '../../../../src';
 const arr = getRandomIntArray(HUNDRED_THOUSAND, 0, HUNDRED_THOUSAND, true);
-const competitor = new OrderedMap<number, number>();
+const cOrderedMap = new OrderedMap<number, number>();
 
@@ -22,5 +22,5 @@ suite.add(`${HUNDRED_THOUSAND.toLocaleString()} add`, () => {
 if (isCompetitor) {
-  suite.add(`${HUNDRED_THOUSAND.toLocaleString()} competitor add`, () => {
+  suite.add(`${HUNDRED_THOUSAND.toLocaleString()} CPT add`, () => {
     for (let i = 0; i < arr.length; i++) {
-      competitor.setElement(arr[i], arr[i]);
+      cOrderedMap.setElement(arr[i], arr[i]);
     }
@@ -27,0 +27,0 @@ });

test/performance/data-structures/hash/hash-map.test.ts

@@ -18,3 +18,3 @@ import { HashMap } from '../../../../src';
 if (isCompetitor) {
-  suite.add(`${TEN_THOUSAND.toLocaleString()} competitor set`, () => {
+  suite.add(`${TEN_THOUSAND.toLocaleString()} CPT set`, () => {
     const hm = new CHashMap<number, number>();
@@ -38,3 +38,3 @@
 if (isCompetitor) {
-  suite.add(`${TEN_THOUSAND.toLocaleString()} competitor set & get`, () => {
+  suite.add(`${TEN_THOUSAND.toLocaleString()} CPT set & get`, () => {
     const hm = new CHashMap<number, number>();
@@ -41,0 +41,0 @@

test/performance/data-structures/linked-list/doubly-linked-list.test.ts

@@ -18,3 +18,3 @@ import { DoublyLinkedList, DoublyLinkedListNode } from '../../../../src';
 if (isCompetitor) {
-  suite.add(`${LINEAR.toLocaleString()} competitor unshift`, () => {
+  suite.add(`${LINEAR.toLocaleString()} CPT unshift`, () => {
     const list = new CLinkedList<number>();
@@ -21,0 +21,0 @@

test/performance/data-structures/priority-queue/priority-queue.test.ts

@@ -22,3 +22,3 @@ import { PriorityQueue as CPriorityQueue } from 'js-sdsl';
 if (isCompetitor) {
-  suite.add(`${TEN_THOUSAND.toLocaleString()} competitor add & pop`, () => {
+  suite.add(`${TEN_THOUSAND.toLocaleString()} CPT add & pop`, () => {
     const pq = new CPriorityQueue<number>();
@@ -25,0 +25,0 @@

test/performance/data-structures/queue/deque.test.ts

@@ -17,3 +17,3 @@ import { Deque } from '../../../../src';
 if (isCompetitor) {
-  suite.add(`${LINEAR.toLocaleString()} competitor push`, () => {
+  suite.add(`${LINEAR.toLocaleString()} CPT push`, () => {
     const deque = new CDeque<number>();
@@ -20,0 +20,0 @@ for (let i = 0; i < LINEAR; i++) {

test/performance/data-structures/queue/queue.test.ts

@@ -18,3 +18,3 @@ import { Queue } from '../../../../src';
 if (isCompetitor) {
-  suite.add(`${LINEAR.toLocaleString()} competitor push`, () => {
+  suite.add(`${LINEAR.toLocaleString()} CPT push`, () => {
     const queue = new CQueue<number>();
@@ -21,0 +21,0 @@

test/performance/data-structures/stack/stack.test.ts

@@ -18,3 +18,3 @@ import { Stack } from '../../../../src';
 if (isCompetitor) {
-  suite.add(`${LINEAR.toLocaleString()} competitor push`, () => {
+  suite.add(`${LINEAR.toLocaleString()} CPT push`, () => {
     const queue = new CStack<number>();
@@ -38,3 +38,3 @@
 if (isCompetitor) {
-  suite.add(`${LINEAR.toLocaleString()} competitor push & pop`, () => {
+  suite.add(`${LINEAR.toLocaleString()} CPT push & pop`, () => {
     const queue = new CStack<number>();
@@ -41,0 +41,0 @@

test/performance/reportor.ts

@@ -8,2 +8,17 @@ import * as Benchmark from 'benchmark';
 
+
+const args = process.argv.slice(2);
+
+const { GREEN, BOLD, END, YELLOW, GRAY, CYAN, BG_YELLOW } = Color;
+
+const getRelativePath = (file: string) => {
+  return path.relative(__dirname, file);
+}
+const coloredLabeled = (label: string, file: string) => {
+  const relativeFilePath = getRelativePath(file);
+  const directory = path.dirname(relativeFilePath);
+  const fileName = path.basename(relativeFilePath);
+  return `${BG_YELLOW} ${label} ${END} ${GRAY}${directory}/${END}${CYAN}${fileName}${END}`;
+}
+
 const parentDirectory = path.resolve(__dirname, '../..');
@@ -13,4 +28,18 @@ const reportDistPath = path.join(parentDirectory, 'benchmark');
 const testDir = path.join(__dirname, 'data-structures');
-const testFiles = fastGlob.sync(path.join(testDir, '**', '*.test.ts'));
+const allFiles = fastGlob.sync(path.join(testDir, '**', '*.test.ts'));
+let testFiles: string[] = [];
+if (args.length > 0) {
+  console.log(`arguments: ${args.join(' ')}`)
 
+  testFiles = allFiles.filter(file =>
+    args.every(word => file.includes(word))
+  );
+
+  console.log(`${testFiles.map(file => coloredLabeled('Matched', file)).join(`
+`)}`);
+} else {
+  testFiles = allFiles;
+}
+
+
 const report: { [key: string]: any } = {};
@@ -21,3 +50,2 @@
 const performanceTests: PerformanceTest[] = [];
-const { GREEN, BOLD, END, YELLOW, GRAY, CYAN, BG_YELLOW } = Color;
 
@@ -113,3 +141,3 @@ testFiles.forEach((file: string) => {
   fs.writeFileSync(htmlFilePath, html);
-  console.log(`Performance ${BOLD}${GREEN}report${END} file generated in ${BOLD}${GREEN}${reportDistPath}${END}`);
+  console.log(`Performance ${BOLD}${GREEN}report${END} file generated in file://${BOLD}${GREEN}${htmlFilePath}${END}`);
 };
@@ -142,3 +170,3 @@
       } else {
-        console.log(`The content has been successfully replaced in ${BOLD}${GREEN}${filePath}!${END}`);
+        console.log(`The content has been successfully replaced in file://${BOLD}${GREEN}${filePath}${END}`);
       }
@@ -151,7 +179,5 @@ });
   const { suite, testName, file } = item;
-  const relativeFilePath = path.relative(__dirname, file);
-  const directory = path.dirname(relativeFilePath);
-  const fileName = path.basename(relativeFilePath);
-  console.log(`${BG_YELLOW} Running ${END} ${GRAY}${directory}/${END}${CYAN}${fileName}${END}`);
 
+  console.log(coloredLabeled('Running', file));
+
   if (suite) {
@@ -158,0 +184,0 @@ let runTime = 0;

test/unit/data-structures/heap/heap.test.ts

@@ -260,1 +260,39 @@ import { FibonacciHeap, MaxHeap, MinHeap } from '../../../../src';
 });
+
+// describe('Competitor performance compare', () => {
+//   const minHeap = new MinHeap<number>();
+//   const cHeap = new CHeap<number>();
+//   const cPQ = new PriorityQueue<number>(undefined, (a, b) => a - b);
+//   const n = 10000;
+//
+//   it('should add performance well', () => {
+//     const heapCost = calcRunTime(() => {
+//       for (let i = 0; i < n; i++) {
+//         minHeap.add(i);
+//       }
+//     })
+//
+//     console.log(`heapCost: ${heapCost}`)
+//   });
+//
+//   it('should add performance well', () => {
+//
+//     const cHeapCost = calcRunTime(() => {
+//       for (let i = 0; i < n; i++) {
+//         cHeap.push(i);
+//       }
+//     })
+//
+//     console.log(`cHeapCost: ${cHeapCost}`)
+//   });
+//
+//   it('should add performance well', () => {
+//
+//     const cPQCost = calcRunTime(() => {
+//       for (let i = 0; i < n; i++) {
+//         cPQ.push(i);
+//       }
+//     })
+//     console.log(`cPQCost: ${cPQCost}`)
+//   });
+// });

test/utils/index.ts

@@ -8,1 +8,2 @@ export * from './number';
 export * from './string';
+export * from './performanc';

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

3903691

increased by0.28%

Number of package files

790

increased by0.25%

Lines of code

73987

increased by0.33%

Number of lines in readme file

786

increased by0.38%

No dependency changes