1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
Creating 1 cat costs: 115.603 in gas.
The second cat costs: 85.603.
The third cat costs: 85.603.
The fourth cat costs: 85.603.
So this is constant except for creating it because we need to make up space in the blockchain to put the kitties in. But every time a new kitty is added the same computing power is used.
2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
Calling this function once costs: 12.479.
When the function is called again it costs: 14.898.
When the function is called again it costs: 17.317.
Wich is a difference of 2.419 every time a cat is added and this function gets called.
So this is linear.
3. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
pragma solidity ^0.8.0;
contract Kittycontract {
string public constant name = "TestKitties";
string public constant symbol = "TK";
event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);
event Birth(
address owner,
uint256 kittenId,
uint256 mumId,
uint256 dadId,
uint256 genes
);
struct Kitty {
uint256 genes;
uint64 birthTime;
uint32 mumId;
uint32 dadId;
uint16 generation;
}
Kitty[] kitties;
mapping (uint256 => address) public kittyIndexToOwner;
//change the original mapping to a mapping with the ids of the cats that a address owns.
mapping (address => uint256[]) OwnedCats;
function balanceOf(address owner) external view returns (uint256 balance){
return OwnedCats[owner].length;
}
function totalSupply() public view returns (uint) {
return kitties.length;
}
function ownerOf(uint256 _tokenId) external view returns (address)
{
return kittyIndexToOwner[_tokenId];
}
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 cats){
//return directly the mapping of the caller in the function.
cats = OwnedCats[_owner];
}
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;
emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);
_transfer(address(0), _owner, newKittenId);
return newKittenId;
}
function _transfer(address _from, address _to, uint256 _tokenId) internal {
// maping the cat of the owner.
kittyIndexToOwner[_tokenId] = _to;
//push the id of the cat to the list if ids for the user.
OwnedCats[_to].push(_tokenId);
//remove the id of the cat from the list of the previous order if it is not a new one.
if (_from != address(0)) {
_removeOwnership(_from, _tokenId);
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
//remove function to remove the cat from the previous owner list.
function _removeOwnership(address _owner, uint256 _tokenId) internal {
//loop through the owned cats of the given address
for (uint i = 0; i < OwnedCats[_owner].length; i++) {
//if the cat/nft was not found
if(OwnedCats[_owner][i] == _tokenId) {
//replace the cat by copying the last cat to this position
OwnedCats[_owner][i] = OwnedCats[_owner][OwnedCats[_owner].length-1];
//this removes the duplicate
OwnedCats[_owner].pop();
// and lastly return the function to save on gas
return;
}
}
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
pros:
The function GetAllCatsFor now saves a lot of gas because it is constant it doesnât have to loop over the whole array.
cons
this brings another linear function but this is less gas costly then the other function.
)