Toggle navigation
MeasureThat.net
Create a benchmark
Tools
Feedback
FAQ
Register
Log In
Find Island
(version: 0)
Comparing performance of:
num1 vs num2
Created:
5 years ago
by:
Guest
Jump to the latest result
Tests:
num1
const L = true; const W = false; const world = [ [L, W, L, W, L, L], [L, L, L, W, L, W], [L, W, W, W, L, L], [W, W, W, W, W, L], [W, L, L, L, W, L], [W, W, W, W, W, L], [W, W, W, W, L, L], [W, W, W, W, L, L], ]; const height = world.length; const width = world[0].length; // Each island gets a number 1 or more. // Some islands are the same number. const idMap = {}; const idCounts = {}; const totalCounts = {}; let maxIslandId = 0; function newId() { const id = ++maxIslandId; idMap[id] = id; idCounts[id] = 0; totalCounts[id] = 0; return id; } const cellIdMap = Array.from(new Array(height), () => new Array(width).fill(0)); function getIdOfCell(y, x) { if (y < 0 || x < 0) return 0; return cellIdMap[y][x]; } // Assign Ids to the grid. for (let y = 0; y < height; ++y) { for (let x = 0; x < width; ++x) { if (world[y][x] === W) continue; const topId = getIdOfCell(y - 1, x); const leftId = getIdOfCell(y, x - 1); if (topId && leftId && topId !== leftId) { // Two islands become one. Left wins. idMap[topId] = leftId; } const id = leftId || topId || newId(); cellIdMap[y][x] = id; // Count island. ++idCounts[id]; } } const finalIdMemo = {}; function getMappedId(id) { if (id in finalIdMemo) { return finalIdMemo[id]; } let mappedId = id; while (mappedId !== idMap[mappedId]) { mappedId = idMap[mappedId]; } const finalId = mappedId; // Store the mapping result for faster // future calculation. mappedId = id; do { finalIdMemo[mappedId] = finalId; mappedId = idMap[mappedId]; } while (mappedId !== idMap[mappedId]); return finalId; } // Total island counts for (const id in idCounts) { totalCounts[getMappedId(id)] += idCounts[id]; }
num2
const L = true; const W = false; const world = [ [L, W, L, W, L, L], [L, L, L, W, L, W], [L, W, W, W, L, L], [W, W, W, W, W, L], [W, L, L, L, W, L], [W, W, W, W, W, L], [W, W, W, W, L, L], [W, W, W, W, L, L], ]; const height = world.length; const width = world[0].length; const visitedSet = new Set(); let largestIsland = []; let currentIsland = []; function traverseIsland(world, x, y) { var _a, _b, _c, _d; const toVisitStack = [[x, y]]; const currentIsland = []; while (toVisitStack.length) { const [currentX, currentY] = toVisitStack.shift(); currentIsland.push([currentX, currentY]); if (currentX === 0 || currentY === 0 || currentY === width - 1 || currentX === height - 1) { return []; } if (!visitedSet.has(`${currentX},${currentY + 1}`) && ((_a = world === null || world === void 0 ? void 0 : world[currentX]) === null || _a === void 0 ? void 0 : _a[currentY + 1])) { toVisitStack.push([currentX, currentY + 1]); } if (!visitedSet.has(`${currentX},${currentY - 1}`) && ((_b = world === null || world === void 0 ? void 0 : world[currentX]) === null || _b === void 0 ? void 0 : _b[currentY - 1])) { toVisitStack.push([currentX, currentY + 1]); } if (!visitedSet.has(`${currentX + 1},${currentY}`) && ((_c = world === null || world === void 0 ? void 0 : world[currentX + 1]) === null || _c === void 0 ? void 0 : _c[currentY])) { toVisitStack.push([currentX, currentY + 1]); } if (!visitedSet.has(`${currentX - 1},${currentY}`) && ((_d = world === null || world === void 0 ? void 0 : world[currentX - 1]) === null || _d === void 0 ? void 0 : _d[currentY])) { toVisitStack.push([currentX, currentY + 1]); } visitedSet.add(`${currentX},${currentY + 1}`); visitedSet.add(`${currentX},${currentY - 1}`); visitedSet.add(`${currentX + 1},${currentY}`); visitedSet.add(`${currentX - 1},${currentY}`); } return currentIsland; } for (let x = 1; x < height - 1; x++) { for (let y = 1; y < width - 1; y++) { const hasVisited = visitedSet.has(`${x},${y}`); visitedSet.add(`${x},${y}`); if (!hasVisited) { if (world[x][y]) { const currentIsland = traverseIsland(world, x, y); if (currentIsland.length > largestIsland.length) { largestIsland = currentIsland; } } } } }
Rendered benchmark preparation results:
Suite status:
<idle, ready to run>
Run tests (2)
Previous results
Fork
Test case name
Result
num1
num2
Fastest:
N/A
Slowest:
N/A
Latest run results:
No previous run results
This benchmark does not have any results yet. Be the first one
to run it!
Autogenerated LLM Summary
(model
llama3.2:3b
, generated one year ago):
Based on the provided JavaScript code snippet, it appears to be implementing a flood fill algorithm to find the largest island in a given grid represented by a 2D array (`world`). The code uses a Set (`visitedSet`) to keep track of visited cells and a stack-based approach to traverse the grid. To answer your question, I'll need more information about what you're trying to accomplish or what specific aspect of the code you'd like me to analyze. However, I can provide some general insights: 1. **Algorithm complexity**: The algorithm has a time complexity of O(n^2), where n is the number of cells in the grid, since it visits each cell at most once. 2. **Memory usage**: The code uses a Set to keep track of visited cells, which adds a linear factor to the memory usage. However, this is unavoidable due to the nature of the algorithm. If you're looking for performance optimization or would like me to suggest modifications to improve the code's efficiency, I can try to provide some suggestions.
Related benchmarks:
point in triangle
point in triangle
duplicate removing
Testando
Haversine performance
Comments
Confirm delete:
Do you really want to delete benchmark?