Created
January 13, 2022 16:46
-
-
Save Melvillian/02e87b8d960034c643b40764652ccef3 to your computer and use it in GitHub Desktop.
A Solidity contract comparing the O(n) algorithm for removing an element from an array and preserving sortedness, and a O(1) algorithm that does not keep the array sorted
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // SPDX-License-Identifier: GPL-3.0 | |
| pragma solidity ^0.8.10; | |
| contract ArraySortingExample { | |
| address[] public users; | |
| // simple function to add an address to the users array | |
| function push(address user) public { | |
| users.push(user); | |
| } | |
| // removes an address at the given index by shifting | |
| // all other values over | |
| function removeSlow(uint256 _index) public { | |
| require(_index < users.length, "GasOptimizations: _index is out of bounds"); | |
| // index = 1 | |
| // [1,2,3,4] | |
| for (uint256 i = _index; i < users.length - 1; i++) { | |
| users[i] = users[i + 1]; | |
| } | |
| // [1,3,4] | |
| } | |
| function removeFast(uint256 _index) public { | |
| require(_index < users.length, "GasOptimizations: _index is out of bounds"); | |
| // index = 1 | |
| // [1,2,3,4] | |
| users[_index] = users[users.length - 1]; | |
| // [1, 4, 3, 4] | |
| users.pop(); | |
| // [1,4,3] | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment