- What is the time complexity of creating new cats? (constant or linear w nr of cats).
It is pretty much constant since the operations that the function has to perform are always the same. I did notice minor variances in the gas execution cost depending on the number of digits that one inputs for the genes unit, the bigger the number it cost slightly more, but overall the discrepancy is too little and I assume that is related to the size of the unit and how it is stored. But overall the time complexity is constant O(1).
Also, can someone explain to me why adding the first element to an array is always a more expensive transaction than the rest?
- What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
It is a linear time complexity or of O(n), this is because the function will always have to iterate one more time per element added to the array. In terms of gas consumption, Iâve recorded that the execution cost increments by 3019 gas for every new cat added to the array.
- How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
We could implement a mapping that links an address to the collection of tokens that it owns. That way whenever we need to query all the cats that an address has, the execution cost will be constant because it will not have to loop through the entire array of tokens to find the desired one.
I manage to do part of the assignment on my own, but couldnât because I was trying to avoid having to use a loop at all, only to find out that there no other way of deleting the desired ID. But it was very interesting to really grasp the core understanding that time complexity cost only matters whenever we are adding information to the blockchain.
Benefits:
It allows us to have a constant time complexity function.
Drawnbacks:
It makes a lot more expensive the creation of tokens and the transfer of tokens.
Iâll leave the code down below:
pragma solidity ^0.8.0;
contract kittyContract{
// DECLARATIONS
string public constant name = "TestKitties";
string public constant symbol = "TK";
mapping (uint => address) public kittyIndexToOwner;
mapping (address => uint) public ownershipTokenCount;
mapping (address => uint[]) catsOwnedBy;
struct Kitty{
uint256 genes;
uint64 birthTime;
uint32 mumID;
uint32 dadID;
uint16 generation;
}
Kitty[] kitties;
// EVENT
event Transfer(address indexed from, address indexed to, uint indexed tokenIndex);
event Birth(address owner, uint256 kittenID, uint256 mumID, uint256 dadID, uint256 genes);
// FUNCTIONS
function balanceOf(address _owner) external view returns(uint256){
return ownershipTokenCount[_owner];
}
function totalSupply() public view returns(uint256){
return kitties.length;
}
function owns(address _claimant, uint256 _tokenID) internal view returns(bool){
return kittyIndexToOwner[_tokenID] == _claimant;
}
function createKittyGen0(uint256 _genes) public returns (uint256) {
return _createKitty(0, 0, 0, _genes, msg.sender);
}
function _createKitty( uint256 _mumID, uint256 _dadID, uint256 _generation, uint256 _genes,
address _owner
) private returns(uint256){
Kitty memory _kitty = Kitty({
genes: _genes,
birthTime: uint64(block.timestamp),
mumID: uint32(_mumID),
dadID: uint32(_dadID),
generation: uint16(_generation)
});
kitties.push(_kitty);
uint256 newKittenID = kitties.length - 1;
_transfer(address(0), _owner, newKittenID);
emit Birth(_owner, newKittenID, _mumID, _dadID, _genes);
return newKittenID;
}
function transfer(address _to, uint256 _tokenID) external {
require(_to != address(0));
require(_to != address(this));
require(owns(msg.sender, _tokenID));
_transfer(msg.sender, _to, _tokenID);
}
function getAllCatsFor(address _owner) external view returns(uint[] memory){
return catsOwnedBy[_owner];
}
// INTERNAL/PRIVATE FUNCTIONS
function _transfer(address _from, address _to, uint256 _tokenID) internal {
ownershipTokenCount[_to] ++;
kittyIndexToOwner[_tokenID] = _to;
catsOwnedBy[_to].push(_tokenID);
if(_from != address(0)){
ownershipTokenCount[_from]--;
_deleteCat(_from, _tokenID);
}
emit Transfer(_from, _to, _tokenID);
}
function _deleteCat(address _owner, uint256 _tokenID) internal {
uint256 lastID = catsOwnedBy[_owner][catsOwnedBy[_owner].length - 1];
for (uint256 i = 0; i < catsOwnedBy[_owner].length; i++){
if (catsOwnedBy[_owner][i] == _tokenID){
catsOwnedBy[_owner][i] = lastID;
catsOwnedBy[_owner].pop();
}
}
}
}
