-
What is the time complexity of creating new cats? (constant or linear w nr of cats).
-
What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
-
How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
4 Likes
@filip First I would like to mention that the initial source code is not linked for this assignment nor for the ERC20 assignment. I had to find it manually from Filips GitHub.
Perhaps you guys can put links to the code in connection with the assignment.
Now for this assignment.
What is the time complexity of creating new cats? (constant or linear w nr of cats)
The time complexity is constant O(1) based on the information I can gather from the contract.
This is based on the knowledge that you really have access to the id of the mom and dad.
Right now the function is only called once in the createKittyGen0 function, and the function is in itself private so the over all time complexity is dependent on the calling function.
But to run the createKitty function itself has the time complexity O(1)
What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats)
Based on the function displayed in the video the time complexity is linear time O(n), since we have to check all the positions in the array before we return.
How could the storage design be changed to make the getAllCats function constant?
I would do something like this:
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;
// Remove the ownershipTokenCount mapping since we can calculate this number by the new mapping
// map the owners address to the ids of the cats that he owns
mapping (address => uint256[]) ownersCats;
function balanceOf(address owner) external view returns (uint256 balance){
return ownersCats[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);
}
// Part of the assignment
function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
// Just return the cats in the mapping for the given caller
cats = ownersCats[_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 {
// Map the cat to the new owner
kittyIndexToOwner[_tokenId] = _to;
// Push the id of the cat to the list if ids for the user
ownersCats[_to].push(_tokenId);
// Remove the id of the cat from the list of the precious order if it was not a newly generated cat
if (_from != address(0)) {
_removeOwnership(_from, _tokenId);
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
// Removes the id of the cat from the previous owners list
function _removeOwnership(address _owner, uint256 _tokenId) internal {
// Loop though the owned cats of the given address
for (uint i = 0; i < ownersCats[_owner].length; i++) {
// If the cat was found
if (ownersCats[_owner][i] == _tokenId) {
// Replace the cat by copying the last cat to this position
ownersCats[_owner][i] = ownersCats[_owner][ownersCats[_owner].length-1];
// Remove the duplicate
ownersCats[_owner].pop();
// Return from the function to save gas since we have done all we should
return;
}
}
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
So what are the pros and cons to this approach?
Pros
The getAllCatsFor function is now executed in constant time and saves a lot of gas.
Before we had to loop though the whole array that could grow a lot over time.
Although it is an external view function we don’t have to care about the gas except if the caller is another contract. So by optimizing the function we not only puts less load on the network but also ensures that those who will end up paying for the transaction will pay as little as possible.
Cons
We introduce another function with linear time although the size of it will be a lot smaller and we are only looking for one index instead of many, so if we are lucky or if the previous owner only has one cat the execution is now in constant time O(1), if not then, it will be somewhere in between O(1) to O(n).
If one wants to be really nerdy to improve this function, one can do some research if it is more probable for a previous owner to sell a newly acquired cat than a cat acquired long ago. In that case it might be beneficial to start looping from the end of the contract.
7 Likes
What is the time complexity of creating new cats? (constant or linear w nr of cats).
Creating a new KittenToken is of constant time complexity. It will always take the same procedure and therefore the same execution time, no matter how many kittens there already are in the kittiesArray.
What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
The getAllCats function is certainly linear, as we loop through the entire array to find all Tokens owned by a given address. The longer the array, the longer the execution time of this function.
Solution
We can minimize this execution time by implementing a mapping that points from the catOwners address to a uint array that stores the tokenIDs of the owned KittieTokens. Now, instead of looping through the entire Kitties array of the contract, we can access and return all KittieTokenIDs owned by a given address instantly. But, this solution comes with the cost of implementing an additional, linear, function that will allow us to remove a Token from the catsOwned array. This new function will have to be linear, as we have to loop through the catsOwned array to find the TokenID we want to delete.
ERC721KittiesAssignment .sol catsOwned mapping solution
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; //Array to store all created kitties. Each Kittie is a unique Token.
mapping (uint256 => address) public kittyIndexToOwner; //TokenID mapped to owner address
// ownershipTokenCount is replaced by new Array: catsOwned which will give tokencount by calling catsOwned.length
// mapping (address => uint256) ownershipTokenCount; //Mapps how many kitties an address owns.
mapping (address => uint256[]) catsOwned;
function balanceOf(address owner) external view returns (uint256 balance){
// return ownershipTokenCount[owner]; //replaced by:
return catsOwned[owner].length;
}
function totalSupply() public view returns (uint) { //returns how many kittieTokens exist
return kitties.length;
}
function ownerOf(uint256 _tokenId) external view returns (address) //Show who owns specific KittieToken
{
return kittyIndexToOwner[_tokenId];
}
function transfer(address _to,uint256 _tokenId) external //Transfers a kittieToken to another address -- see _transfer fuction!
{
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){ //Gets all Cats for given Address
//New Solution:
cats = catsOwned[_owner];
// OLD CODE:
// uint[] memory result = new uint[](ownershipTokenCount[_owner]);
// uint counter = 0;
// for (uint i = 0; i < kitties.length; i++) {
// if (kittyIndexToOwner[i] == _owner) {
// result[counter] = i;
// counter++;
// }
// }
// return result;
}
function createKittyGen0(uint256 _genes) public returns (uint256) {
return _createKitty(0, 0, 0, _genes, msg.sender);
}
function _createKitty( //Creates new KittyToken
uint256 _mumId,
uint256 _dadId,
uint256 _generation,
uint256 _genes,
address _owner
) private returns (uint256) {
Kitty memory _kitty = Kitty({ //creating new Kitty struct!
genes: _genes,
birthTime: uint64(block.timestamp),
mumId: uint32(_mumId),
dadId: uint32(_dadId),
generation: uint16(_generation)
});
kitties.push(_kitty); //pushing new struct to KittyTokensArray!
uint256 newKittenId = kitties.length - 1; //newKittenID is array.length -1 because of zero indexing!
emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);
_transfer(address(0), _owner, newKittenId); //transfers new kitten to it's owner
return newKittenId;
}
function _transfer(address _from, address _to, uint256 _tokenId) internal { //Actual transfer of KittieTokens
// ownershipTokenCount[_to]++; //Replaced by catsOwned //Increases ownershipCount of recipientr
catsOwned[_to].push(_tokenId); //New solution
kittyIndexToOwner[_tokenId] = _to; //Sets recipient as new owner of Token
if (_from != address(0)) { //If not sent from address 0, ( 0 is in case of newly created Token!!),
removeCat(_from, _tokenId); //decrease ownershipCount of sender!
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function removeCat(address _owner, uint256 _tokenId) internal {
for (uint i = 0; i < catsOwned[_owner].length; i++){ //look up every entry of catsOwned
if (catsOwned[_owner][i] == _tokenId){ //If _tokenId is found
catsOwned[_owner][i] = catsOwned[_owner][catsOwned[_owner].length - 1]; //replace requested TokenId with last position in Array! (catsOwned[_owner][catsOwned[_owner].length - 1])
catsOwned[_owner].pop(); //remove last position in array!
}
}
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) { //returns true if given address owns Token with given ID.
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
Resume:
This solution can help to reduce execution time, as looping through the ownedCats array, in case of deletion of a TokenID, will most certainly take less time than looping through the entire Kitties array of the contract just to return all TokenIDs owned. The downside of this solution is certainly that we have to bring in another linear function to remove a cat from the catsOwned array. Although it is possible that this newly created array grows to the same size as the Kittie Tokens Array, which stores all kittie structs ever created, it can be considered as rather unlikely. The big downside I see though is that the getAllCats function is view only, which is free. The createKitty and _transfer function though are costly functions that need gas. All in all, it is better to wait a little longer on a free function than to make a costly function more complex and more expensive.
5 Likes
1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
The time complexity for creating new cats as far as I can tell is O(1) as the function does not involve computation using a dynamically-sized array.
2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
The time complexity for the getAllCatsFor function is linear based on the number of cats. This is because the function must interate through the entire kitties array and enumerate the number of cats owned by the caller.
3. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
I would make the following changes in the design of this contract:
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;
//removed ownershipTokenCount and replaced with ownerKitties mapping
mapping (address => Kitty[]) public catsOwned
function balanceOf(address owner) external view returns (uint256 balance){
//Updated function to reference catsOwned array length
return catsOwned[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[]){
return catsOwned[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 {
//Updated function with catsOwned and delete functionality
if (_from != address(0)) {
deleteCat(_from, _tokenId);
}
catsOwned[_to].push(_tokenId);
kittyIndexToOwner[_tokenId] = _to;
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function deleteCat(address _owner, uint256 _tokenId) internal {
for (uint256 i = 0; i < catsOwned[_owner].length; i++){ //loop through the array of the owner
if (catsOwned[_owner][i] == _tokenId){ //if the token id in the array matches the one provided
catsOwned[_owner][i] = catsOwned[_owner][catsOwned[_owner].length - 1];// Set the array member at that index equal to the member of the array
catsOwned[_owner].pop();// delete the last member of the array
}
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
As cats are created, their ids are added to each owner’s cat array in the catsOwned mapping. This makes the getAllCatsFor function constant, because no matter how large each id array becomes, we are still performing the same operation, catsOwned[address], to retrieve all the cats that they own.
The benefit of this approach is it conserves gas when using the getAllCatsFor function, as you are no longer looping through and filtering the full cat array. A drawback for this solution is that we need to introduce another linear function that allows us to delete a cat from an owner’s array in the catsOwned mapping when we call the transfer function.
1 Like
-
Time complexity to create new cats is constant - the kitty is added to the end of the kitties array
-
Time complexity of getAllCatsFor function is linear - the kitties array is iterated
-
Instead of iterating the kittie array a mapping could be used to map the owner address to an array of kitty tokenIds, this also replaces the need for the ownershipTokenCount mapping. However removing a kitty means removing the tokenId from the new mapped array, which is linear and ugly
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;
mapping (address => uint256[]) ownersKitties;
function balanceOf(address owner) external view returns (uint256 balance){
return ownersKitties[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 ownersKitties[_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 {
kittyIndexToOwner[_tokenId] = _to;
ownersKitties[_to].push(_tokenId);
if (_from != address(0)) {
uint len = ownersKitties[_from].length;
for (uint i = 0; i < len; i++) {
if (ownersKitties[_from][i] == _tokenId) {
ownersKitties[_from][i] = ownersKitties[_from][len - 1];
ownersKitties[_from].pop();
break;
}
}
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
1 Like
-
What is the time complexity of creating new cats? (constant or linear w nr of cats). — constant since it’s simply added
-
What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats). — linear since it grows with array size since function gets cat by looping through whole array
-
How could the storage design be changed to make the getAllCats function constant? Implement your idea. Then discuss the benefits and drawbacks of your implementation and post everything in the forum. — do this by making map of address to array of owned cat ids so the map as each address pointing to an array of owned cat ids, this way getAllCats can simply return the array based on the owner address in the map.
But this adds another linear function as we have to still loop through the array of owned cats of an address when we want to remove it when transferring ownership
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;
//mapping (address => uint256) ownershipTokenCount;
//map of address to array of cat ids owned
mapping (address => uint[]) ownedKitties;
function balanceOf(address owner) external view returns (uint256 balance){
//return ownershipTokenCount[owner];
return ownedKitties[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){
/*
uint[] memory result = new uint[](ownershipTokenCount[_owner]);
uint counter = 0;
for (uint i = 0; i < kitties.length; i++) {
if (kittyIndexToOwner[i] == _owner) {
result[counter] = i;
counter++;
}
} */
//simply return owned Kitties array of owner address
return ownedKitties[_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 {
//ownershipTokenCount[_to]++;
kittyIndexToOwner[_tokenId] = _to;
ownedKitties[_to].push(_tokenId); //add transfered kitty to mapped array of owner address
if (_from != address(0)) {
_removeKitty(_from, _tokenId); //call function to remove kitty from previous owner
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
//function to remove kitty from previous owner array
function _removeKitty(address _prevOwner, uint256 _tokenId) internal returns (bool) {
for(uint i = 0; i < ownedKitties[_prevOwner].length; i++) {
if(ownedKitties[_prevOwner][i] == _tokenId) { //once id found,
ownedKitties[_prevOwner][i] = ownedKitties[_prevOwner][ownedKitties[_prevOwner].length-1]; //overwrite id with last id in array
ownedKitties[_prevOwner].pop(); //pop last position
return true;
}
}
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
1 Like
- Constant
- Linear
- By adding a mapping of owner to a an array of cat’s they own. The tradeoff is more storage costs and also more complex handling of the transfer function. Benefit is a quick lookup of all cats of an owner.
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;
mapping (address => uint256) ownershipTokenCount;
mapping (address => uint256[]) ownerKitties;
function balanceOf(address owner) external view returns (uint256 balance){
return ownershipTokenCount[owner];
}
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){
/*uint[] memory result = new uint[](ownershipTokenCount[_owner]);
uint counter = 0;
for (uint i = 0; i < kitties.length; i++) {
if (kittyIndexToOwner[i] == _owner) {
result[counter] = i;
counter++;
}
}*/
return ownerKitties[_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 {
ownershipTokenCount[_to]++;
kittyIndexToOwner[_tokenId] = _to;
// add kitten to new owners kitty array
ownerKitties[_to].push(_tokenId);
if (_from != address(0)) {
ownershipTokenCount[_from]--;
// remove kitten from old owners kitty array
_removeFromOwnwerKitties(_from, _tokenId);
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _removeFromOwnwerKitties(address _owner, uint256 _tokenId) internal {
// find kitty index
uint tokenlocation;
for (uint i = 0; i < ownerKitties[_owner].length; i++) {
if (ownerKitties[_owner][i] == _tokenId) {
tokenlocation = i;
}
}
// Overwrite with final kitty in array
ownerKitties[_owner][tokenlocation]=ownerKitties[_owner][ownerKitties[_owner].length-1];
// remove last element
ownerKitties[_owner].pop();
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
1 Like
1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
Constant, each new cat will be added to the end of kitties array.
2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
Linear, the function have to iterate through the kitties to get all cats owned by a user.
3. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
Could be through a mapping from address to an integer array where we could storage the ID of the cats the user owns.
mapping (address => uint256[]) ownedKitties;
Then we could just return the array from the mapping like this:
function getAllCatsFor(address _owner) external view returns (uint[] memory){
return ownedKitties[_owner];
}
Carlos Z.
3 Likes
-
The time required to create new cats is constant and independent of the amount of previously created cats as the operation of pushing to the array is always the same.
-
getAllCatsFor gets more expensive the more cats there are as the search in the array gets longer.
-
An array could be created for each owner containing the cats the owner has. These arrays could be mapped to the owner addresses and returned on demand without having to search through the cats of all the owners, which is the main benefit. As a drawback, we have more complexity, especially when the cat ownership needs to be transferred, which includes deleting from the previous owner’s array. Here my 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;
mapping (address => uint256) ownershipTokenCount;
mapping (address => uint[]) ownershipDisplay; ////////////////////////////
function balanceOf(address owner) external view returns (uint256 balance){
return ownershipTokenCount[owner];
}
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){
uint[] memory result = ownershipDisplay[_owner];
return result;
}
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{
ownershipTokenCount[_to]++;
kittyIndexToOwner[_tokenId] = _to;
if (_from != address(0)) {
ownershipTokenCount[_from]--;
}
for (uint i = 0; i < ownershipDisplay[_from].length; i++) {
if (ownershipDisplay[_from][i] == _tokenId) {
uint temp = ownershipDisplay[_from][ownershipDisplay[_from].length - 1];
ownershipDisplay[_from][i] = temp;
ownershipDisplay[_from].pop;
}
}
ownershipDisplay[_to].push(_tokenId);
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
}
1 Like
Here are my answers for the ERC721 assignment:
1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
Constant
2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
Linear - time needed will grow as the array grows in size
3. How could the storage design be changed to make the getAllCats function constant? Implement your idea. Then discuss the benefits and drawbacks of your implementation and post everything in the forum.
Create a mapping from the owner’s address to an array with the owned cat’s IDs.
Return that array when the getAllCatsFor() function is called.
Pros: faster time to get all the cats of an owner, overall costs may be lower for iterating through a smaller owner’s array compared to iterate through the entire kitties[] array
Cons: more code and more complexity to the code, still have the costs of sorting through the array in the new function needed to remove the cat ID from an owner’s array
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;
mapping (address => uint256) ownershipTokenCount;
// new mapping for getting owner's cats
mapping (address => uint[]) ownersKitties;
function balanceOf(address owner) external view returns (uint256 balance){
return ownershipTokenCount[owner];
}
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){
/*
uint[] memory result = new uint[](ownershipTokenCount[_owner]);
uint counter = 0;
for (uint i = 0; i < kitties.length; i++) {
if (kittyIndexToOwner[i] == _owner) {
result[counter] = i;
counter++;
}
}
*/
// returns array with all the owner's cats
return ownersKitties[_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 {
ownershipTokenCount[_to]++;
kittyIndexToOwner[_tokenId] = _to;
if (_from != address(0)) {
ownershipTokenCount[_from]--;
// calls function to remove ID from owner's array
removeOwnersKitty(_from, _tokenId);
}
// adds ID to owner's array
ownersKitties[_to].push(_tokenId);
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
// function to remove ID from old owner's array
function removeOwnersKitty(address _oldOwner, uint _tokenId) internal {
for(uint i = 0; i < ownersKitties[_oldOwner].length; i++) {
if(ownersKitties[_oldOwner][i] == _tokenId){
ownersKitties[_oldOwner][i] = ownersKitties[_oldOwner][ownersKitties[_oldOwner].length - 1];
ownersKitties[_oldOwner].pop();
}
}
}
}
1 Like
-
It is Constant Time complexity, since only adding.
-
It is Linear, since there is an iteration through the array.
New Mapping for the owner’s address with an array of Cat’s ID.
Chaning getAAllCatsFor() to just return the array.
Pros: Cheaper and faster way to return what is expected on getAllCatsFor.
Cons: still had to use the array loop when transferring the cat.
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 (address => uint256[]) myCats;
mapping (uint256 => address) public kittyIndexToOwner;
function balanceOf(address owner) external view returns (uint256 balance){
return myCats[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 myCats[_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 {
kittyIndexToOwner[_tokenId] = _to;
myCats[_to].push(_tokenId);
if (_from != address(0)) {
_removeOwner(_from, _tokenId);
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
function _removeOwner(address _owner, uint256 _tokenId) internal {
for (uint i = 0; i < myCats[_owner].length; i++) {
if (myCats[_owner][i] == _tokenId) {
myCats[_owner][i] = myCats[_owner][myCats[_owner].length - 1];
myCats[_owner].pop();
return;
}
}
}
}
1 Like
- New kitty creation operation has constant complexity. We just create kitty instance and put it in the end of array
- getAllCatsFor has linear complexity. We iterate over entire kitty array in order to find all kitties with certain owner.
- We can use array of kitties ids in the ownershipTokenCount mapping.
Here is my improved contract
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;
mapping (address => uint256[]) ownershipToken;
function balanceOf(address owner) external view returns (uint256 balance){
return ownershipToken[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 ownershipToken[_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 {
_grantOwnership(_to, _tokenId);
kittyIndexToOwner[_tokenId] = _to;
if (_from != address(0)) {
_rejectOwnership(_from, _tokenId);
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
function _rejectOwnership(address _owner, uint256 _tokenId) internal {
uint256 tokenPosition;
for (uint i = 0; i < ownershipToken[_owner].length; i++) {
if (ownershipToken[_owner][i] == _tokenId) {
tokenPosition = i;
break;
}
}
ownershipToken[_owner][tokenPosition] = ownershipToken[_owner][ownershipToken[_owner].length-1];
ownershipToken[_owner].pop();
}
function _grantOwnership(address _newOwner, uint256 _tokenId) internal {
ownershipToken[_newOwner].push(_tokenId);
}
}
As a main drawback we now have array operation in the transfer instead of GetAllCatsFor. I assume this is still improvement because theoretically users will call GetAllCatsFor much more frequently than transfer.
1 Like
What is the time complexity of creating new cats? (constant or linear w nr of cats).
Creating a new cat requires a constant number of operations that does not depend on the number of already existing cats.
What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
The time complexity getAllCatsFor is linear and has a direct linear relationship with the number of already existing cats since we have to go through the entire array to perform this task.
How could the storage design be changed to make the getAllCats function constant? Implement your idea. Then discuss the benefits and drawbacks of your implementation and post everything in the forum.
We could add another mapping that would map the owner address to a uint[] of all the cats owned by the owner. This would require more memory and be a little more expensive to call _createKitty and to call _transfer cats, but would give us a constant time complexity to access all cats owned by a specific address.
Click to View my 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;
mapping (address => uint256) ownershipTokenCount;
mapping (address => uint[]) public ownerToKitties;
function balanceOf(address owner) external view returns (uint256 balance){
return ownershipTokenCount[owner];
}
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 ownerToKitties[_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 {
ownershipTokenCount[_to]++;
kittyIndexToOwner[_tokenId] = _to;
// Adding new kitty to owner array of kitties
ownerToKitties[_to].push(_tokenId);
if (_from != address(0)) {
ownershipTokenCount[_from]--;
removeKittyFromOwnedArray(_from, _tokenId);
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
function removeKittyFromOwnedArray(address owner, uint kitty_id) internal {
uint length = ownerToKitties[owner].length;
for(uint i = 0; i < length; i++) {
if(ownerToKitties[owner][i] == kitty_id) {
ownerToKitties[owner][i] = ownerToKitties[owner][length-1];
ownerToKitties[owner].pop();
return;
}
}
}
}
1 Like
A succicnt article on “Big O” order of operations and complexity theory..
I can’t help but associate that with the anime by the same name.
The crazier the associations the better for long-term memory’s sake.
Let’s begin by adding a mapping to an array of owned cats for every user. Now we’re burning stoarage to solve this processing speed problem. It’s getting more expensive, not less.
But that allows refactoring of the offending function to a trivial order zero (constant):
But the complexity just re-appears in the transfer function. But its cheaper here because its looping over only one user’s clowder, not the entire population. It’s still O(1), but the data set is drastically reduced. There needs to be a check against transfering from one user to the other if the giving user has the kitten in question in their clowder. By its position the require should be an invariant and use assert(), but I prefer to use require() and return a useful error message.
But in the end this solution charges all users the extra storage to solve a Big-O problem in a view function. Worse: it moves the Big-O problem to a function that charges gas. It’s nifty…but not sensible.
Here’s my final code listing to round out all the links in this group of my Solidity notes pictured above.
1 Like
-
Constant for creating new cats.
-
Linear w nr of cats - As the kitties array grows, the number of times the for loop must run to getAllCats for a specific owner does with it.
-
My implementation uses 1 additional mapping and changes 1 of the mappings to map to an array of all the tokens owned by an address.
This avoids the need to loop through all the kitties at any point.
I did some testing with my code, and found that my implementation returns duplicates in the getAllCatsForOwner response 
i.e. for an address that owns kittie id 1 and 2 it returns 2,2,1,1. I don’t know why this is yet…
pragma solidity ^0.8.0;
contract CryptoContract {
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 from Kittie ID to index in global array
//Only needed if setting a token Id in mint/constructor function.
//mapping(uint256 => uint256) internal kittyIdIndex;
mapping (uint256 => address) public kittyIndexToOwner;
//mapping from Kitty ID to its inde in the owner kitties list
mapping(address => uint256[]) internal ownerToKittyIds;
//mapping from Kitty ID to its index in the Owner Kitties List.
mapping (uint256 => uint256) public kittyIndexToOwnerIndex;
function balanceOf(address owner) external view returns (uint256 balance){
return ownerToKittyIds[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 tokenOfOwnerByIndex(
address _owner,
uint256 _index
) external view returns (uint256){
require(_index < ownerToKittyIds[_owner].length, "Invalid Index");
return ownerToKittyIds[_owner][_index];
}
function _getOwnerKittyCount(address _owner) internal virtual view returns (uint256){
return ownerToKittyIds[_owner].length;
}
function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
uint[] memory result = new uint[](_getOwnerKittyCount(_owner));
for (uint i = 0; i < ownerToKittyIds[_owner].length; i++) {
result[i] = ownerToKittyIds[_owner][i];
}
return result;
}
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;
//add to owner - kitty mapping
kittyIndexToOwner[newKittenId] = _owner;
//add to owners Kittys array
ownerToKittyIds[_owner].push(newKittenId);
//add position in owners kitty list to mapping
kittyIndexToOwnerIndex[newKittenId] = ownerToKittyIds[_owner].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 {
//ownershipTokenCount[_to]++;
ownerToKittyIds[_to].push(_tokenId);
//add to owner - kitty mapping
kittyIndexToOwner[_tokenId] = _to;
//kittyIndexToOwner[_tokenId] = _to;
kittyIndexToOwnerIndex[_tokenId] = ownerToKittyIds[_to].length-1;
if (_from != address(0)) {
uint kittyIdToSave = ownerToKittyIds[_from][ownerToKittyIds[_from].length - 1];
for (uint i = 0; i < ownerToKittyIds[_from].length; i++) {
if (_tokenId == ownerToKittyIds[_from][i]){
ownerToKittyIds[_from][i] = kittyIdToSave;
ownerToKittyIds[_from].pop();
}
}
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
bool owns = false;
for (uint i = 0; i < ownerToKittyIds[_claimant].length; i++) {
if (_tokenId == ownerToKittyIds[_claimant][i]){owns=true;}
if (owns == true){ return owns;}
}
return false;
}
}
1 Like
I get that there is additional storage with the new mapping but I think overall the efficiency is improved because of never needing to loop through the entire kitties array.
1 Like
@dan-i
Q: How do you create a Kitty in the contract(createKittyGen0 function). Do you just input any number like 1 or 2, etc. Or do you input any array of numbers like [0,0,1]?
Q: what does birthTime: uint(block.timestamp) actually do? I don’t see any sort of timestamp being returned when after creating kitten.
…basically, how can you measure how long it took for the function to be executed?
Sorry, I am getting frustrated…how is everyone measuring the time complexity? Just by gas consumption?
Hi @bjamRez
Q: How do you create a Kitty in the contract(createKittyGen0 function). Do you just input any number like 1 or 2, etc. Or do you input any array of numbers like [0,0,1]?
The createKittyGen0 has one parameter uint256 therefore it asks a number not an array.
function createKittyGen0(uint256 _genes) public returns (uint256) {
return _createKitty(0, 0, 0, _genes, msg.sender);
}
what does birthTime: uint(block.timestamp) actually do? I don’t see any sort of timestamp being returned when after creating kitten.
The birthTime property of the Kitty struct saves the timestamp of the kitty birth time.
You can set the kitty array as public, create a kitty and inspect it as in my screenshot below, you will see the birthTime populated with the timestamp.
birthTime: uint64(block.timestamp),
1 Like
1. What is the time complexity of creating new cats? (constant or linear w nr of cats).
The time of excecution as a function of number of new cats created is constant. Regardless on how many kittens have been created it will take the same time.
2. What is the time complexity of the getAllCatsFor function? (constant or linear w nr of cats).
Since the function getAllCatsFor is an array that grows in sice. Querying information requires a for loop that iterates over its length. Therefore its excecution time scales linearly with array length.
3. How could the storage design be changed to make the getAllCats function constant? Discuss benefits and drawbacks with your implementation.
We can circumvent this issue byn avoiding a for loop over getAllCats. For this we can use an extra mapping that maps owner address to an array of kitties Id.
We need to alter the mapping that stores kitty id, now it maps to a struct
// index of NFT to owner address
struct kittyIndex2Owner_struct{
address adrs;
uint256 pointer;
}
mapping(uint256 => kittyIndex2Owner_struct) public kittyIndex2Owner;
displaying all kitties owned by an address is easy. However, what is challenging now is to edit the tokens from the extra mapping array. To solve this I have used the replace and pop logic, follow steps a) to e)
function _transfer(address _from, address _to, uint256 _tokenId) internal {
NtokensOwned[_to] += 1;
kittyIndex2Owner[_tokenId].adrs = _to;
if (_from != address(0)){
NtokensOwned[_from] -= 1;
uint256 pointer2delete = kittyIndex2Owner[_tokenId].pointer; // a) grab the pointer of the cat of the array for the sender
uint256 elem2reuse = tokensOwned[_from][tokensOwned[_from].length -1]; // b) grab the last element in the cats-owned sender's array
tokensOwned[_from][pointer2delete] = elem2reuse; // c) replace b) id in the cats-owned sender's array
tokensOwned[_from].pop(); // d) pop the last element in the sender's array
tokensOwned[_to].push(_tokenId); // e) append the token id to the receiver's array
}
tokensOwned[_to].push(_tokenId); // if sending from address(0) do e) as well
emit Transfer(_from, _to, _tokenId);
}
My complete solution is
// SPDX-License-Identifier: GPL-3.0
pragma solidity >=0.8.2;
// ERC721 standard for NFTs
contract KittyContract{
string public constant name = "TestKitties";
string public constant symbol = "TK";
//------------------------------------------------------
// events
event Transfer(address indexed from, address indexed to, uint256 tokenId);
event Birth(
address owner,
uint256 kittenId,
uint32 momId,
uint32 dadId,
uint256 genes);
//--------------------------------------------------------
// Data Storage for crypto-kitties
struct Kitty{
uint256 genes;
uint64 birthTime;
uint32 momId;
uint32 dadId;
uint16 generation;
}
Kitty[] kitties;
// index of NFT to owner address
struct kittyIndex2Owner_struct{
address adrs;
uint256 pointer;
}
mapping(uint256 => kittyIndex2Owner_struct) public kittyIndex2Owner;
// address of owner to Number of NFTs owned
mapping(address => uint256) NtokensOwned;
// address of owner to all kittens owned (array)
mapping(address => uint256[]) tokensOwned;
//--------------------------------------------------------
// functions query info of the NFT owners account (crypto kitties)
/*
// @dev balanceOf: returns the number of crypto kitties tokens owned by input address
// @param _owner: address of the account to ask its balance
*/
function balanceOf(address _owner) external view returns (uint256 _balance){
_balance = NtokensOwned[_owner];
}
function ownerOf(uint256 _tokenId) external view returns(address _owner){
_owner = kittyIndex2Owner[_tokenId].adrs;
}
function _owns(address _claimer, uint256 _tokenId) internal view returns(bool){
return kittyIndex2Owner[_tokenId].adrs == _claimer;
}
/*
// time-wise inefficient, iterates over an increasing array
function getAllCatsFor(address _owner) public view returns(uint[] memory cats){
uint[] memory result = new uint[](NtokensOwned[_owner]);
uint counter = 0;
for (uint i=0; i<kitties.length; i++){
if (kittyIndex2Owner[i] == _owner){
result[counter] += 1;
counter += 1;
}
}
return result;
}
*/
function getAllCatsFor(address _owner) public view returns(uint[] memory){
return tokensOwned[_owner];
}
//------------------------------------------------------------
// functions to create NFTs
function totalSupply() public view returns(uint256 _TotSupply){
_TotSupply = kitties.length;
}
function _createKitty(
uint32 _momId,
uint32 _dadId,
uint16 _generation,
uint256 _genes,
address _owner
) private returns(uint256){
Kitty memory _kitty = Kitty({
genes: _genes,
birthTime: uint64(block.timestamp),
momId: uint32(_momId),
dadId: uint32(_dadId),
generation: uint16(_generation)
});
kitties.push(_kitty);
uint256 newKittenId = kitties.length + 1;
emit Birth(_owner, newKittenId, _momId, _dadId, _genes);
_transfer(address(0), _owner, newKittenId);
return newKittenId;
}
//------------------------------------------------------------
// Create genesis kitten
function createKittyGen0(uint256 _genes) public returns (uint256) {
return _createKitty(0, 0, 0, _genes, msg.sender);
}
// function to create kitties after genesis
function createKitty(
uint32 _momId,
uint32 _dadId,
uint16 _generation,
uint256 _genes,
address _owner
) public returns (uint256){
require(kitties.length != 0, "Genesis cat needs to be created before creating new cats");
return _createKitty(_momId, _dadId, _generation, _genes, _owner);
}
//------------------------------------------------------------
// functions to transact NFTs
/*
// @dev _transfer:
*/
function _transfer(address _from, address _to, uint256 _tokenId) internal {
NtokensOwned[_to] += 1;
kittyIndex2Owner[_tokenId].adrs = _to;
if (_from != address(0)){
NtokensOwned[_from] -= 1;
uint256 pointer2delete = kittyIndex2Owner[_tokenId].pointer; // a) grab the pointer of the cat of the array for the sender
uint256 elem2reuse = tokensOwned[_from][tokensOwned[_from].length -1]; // b) grab the last element in the cats-owned sender's array
tokensOwned[_from][pointer2delete] = elem2reuse; // c) replace b) id in the cats-owned sender's array
tokensOwned[_from].pop(); // d) pop the last element in the sender's array
tokensOwned[_to].push(_tokenId); // e) append the token id to the receiver's array
}
tokensOwned[_to].push(_tokenId); // if sending from address(0) do e) as well
emit Transfer(_from, _to, _tokenId);
}
/*
// @dev transfer: tranfers an NFT from one account to another
// @param _to: receiver address
// @param _tokenId: Id of the token
*/
function transfer(address _to, uint256 _tokenId) external{
require(_to != address(0), "Not a valid address");
require(_to != address(this), "Can not auto-trnasfer");
require(_owns(msg.sender, _tokenId), "This address is not the owner");
_transfer(msg.sender, _to, _tokenId);
}
}
1 Like
1. What is the time complexity of creating new cats?
Creating new cats has a constant time complexity, its always an array.push.
2. What is the time complexity of the getAllCatsFor function?
The time complexity of getAllCatsFor is linear because the execution time will be longer and longer as the kitties array grows.
3. How could the storage design be changed to make the getAllCats function constant?
There are several good possible designs, but mine is not one of them xD, here it goes:
Summary
pragma solidity ^0.8.2;
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;
uint collectionId;
}
Kitty[] kitties;
mapping (uint256 => address) public kittyIndexToOwner;
mapping (address => uint256) ownershipTokenCount;
mapping (address => uint[]) collection;
function balanceOf(address owner) external view returns (uint256 balance){
return ownershipTokenCount[owner];
}
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), "addres 0");
require(_to != address(this), "this");
require(_owns(msg.sender, _tokenId), "owns");
_transfer(msg.sender, _to, _tokenId);
}
function getAllCatsFor(address _owner) external view returns (uint[] memory cats){
return collection[_owner];
}
function createKittyGen0(uint256 _genes) public returns (uint256) {
return _createKitty(0, 0, 0, 0, _genes, msg.sender);
}
function _createKitty(
uint256 _mumId,
uint256 _dadId,
uint256 _generation,
uint _collectionId,
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),
collectionId: uint(_collectionId)
});
kitties.push(_kitty);
uint256 newKittenId = kitties.length - 1;
kitties[newKittenId].collectionId = newKittenId;
emit Birth(_owner, newKittenId, _mumId, _dadId, _genes);
_transfer(address(0), _owner, newKittenId);
return newKittenId;
}
function _transfer(address _from, address _to, uint256 _tokenId) internal {
ownershipTokenCount[_to]++;
kittyIndexToOwner[_tokenId] = _to;
collection[_to].push(_tokenId);
if (_from != address(0)) {
ownershipTokenCount[_from]--;
uint idBefore = kitties[_tokenId].collectionId;
kitties[_tokenId].collectionId = collection[_to].length - 1;
delete collection[_from][idBefore];
uint toMove = collection[_from].length - 1;
collection[_from][idBefore] = toMove;
collection[_from].pop();
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
function getCollection(uint tokenId) public view returns(uint collect){
return kitties[tokenId].collectionId;
}
}
Pros : The time complexity of the getAllCats function is now constant.
Cons: This implementation was really bad, i created 2 new state variables, i am not sure but i would say around 4 new local variables, and the overall complexity of the contract is higher, but specially the complexity of the function _transfer is much higher now, making it prone to errors and really expensive because _transfer is going to be used like 1T times.
It indeed has a fatal flaw D:, it fails to update the collectionId of the kitty that we shift when we delete the collectionId of the kitty that wwe sold, its hard for me to explain but this is not workign properly, and fixing it somehow will add even MORE complexity to this already unnecessarily complex thing, so im gonna change the approach, cause this one was a reaaaally bad approach
new code is here, it is still more complex than the original, but less complex than my first try and this one actually works xD
Summary
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;
mapping (address => uint256) ownershipTokenCount;
mapping (address => uint[]) collection;
mapping(uint => uint) indxInCollection;
function balanceOf(address owner) external view returns (uint256 balance){
return ownershipTokenCount[owner];
}
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 collection[_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 {
ownershipTokenCount[_to]++;
collection[_to].push(_tokenId);
uint idBefore = indxInCollection[_tokenId];
indxInCollection[_tokenId] = collection[_to].length - 1;
kittyIndexToOwner[_tokenId] = _to;
if (_from != address(0)) {
ownershipTokenCount[_from]--;
delete collection[_from][idBefore];
uint shift = collection[_from][collection[_from].length - 1];
indxInCollection[shift] = idBefore;
collection[_from][idBefore] = collection[_from].length - 1;
collection[_from].pop();
}
// Emit the transfer event.
emit Transfer(_from, _to, _tokenId);
}
function _owns(address _claimant, uint256 _tokenId) internal view returns (bool) {
return kittyIndexToOwner[_tokenId] == _claimant;
}
function GetindxInCollection(uint _tokenId)public view returns(uint id){
return indxInCollection[_tokenId];
}
}
I created two new state variables and only had to change the _transfer function, big improvement from my very bad first try, where i modified all the minting functions and the _transfer function.
1 Like