Solidity Arrays – Most Efficient Way to Compare Items in Different Arrays

arraysblockchainsoliditystorage

Within a Solidity Smart Contract, I have 2 arrays that need to be compared. I would like the output to be 3 different arrays that can be used for other logic within the contract.

Example of the arrays:

contract myLists {

    string[5] public listOne = ['AAA','BBB','CCC','DDD','EEE'];
    string[5] public listTwo = ['AAA','BBB','DDD','FFF','GGG'];

}

The outputs should be:

#Output 1: items in listTwo that do not exist in listOne   
string[] public output1['FFF','GGG']
#Output 2: items in listTwo that exist in listOne
string[] public output2['AAA','BBB','DDD']
#Output 3: items in listOne that do not exist in listTwo
string[] public output3['CCC','EEE']

From all my research, it seems array functionality is quite limited in Solidity and the only way may be a for loop.

What is the most gas efficient way to achieve this with arrays. Alternatively, is there a more efficient approach using a different method of storage e.g. Structs?

Thanks.

Best Answer

I've probably made some minor mistakes here but you get the jist of it. Use keccak256(abi.encodePacked("ABC")) to be able to compare strings. Then loop through one element of list2 at a time and compare that to all the elements in list1, when it sees an element that is the same, it adds that to the new list, breaks out of the inner loop and goes to the next element in list2 and compares that to all elements in list1.. and so on.


    //Output: items in listTwo that exist in listOne
    function compare() public view returns(string[] memory) {
        // write to memory to save gas when looping through
        string[5] memory list1 = listOne; 
        string[5] memory list2 = listTwo;

        string[] memory l2Inl1;
        uint nonce;
        for(uint i; i < 5; i++){
            for(uint j; j < 5; j++){
                if(keccak256(abi.encodePacked(list2[i])) == keccak256(abi.encodePacked(list1[j]))){
                    l2Inl1[nonce] = list2[i];
                    nonce++;
                    break
                }
            } 
        }
        return l2Inl1;
    }

You would need to construct something like this for each output that you need. Depending on what chain you run this, the gas cost of running keccak256(abi.encodePacked()) on every string might get costly. I would consider doing this off chain. Or first converting the strings to (or from the start using) a list of bytes, which you can compare. However, converting them back might return unexpected results, it all depends on your use case, which I don't know. But This should hopefully give you some ideas at least!

Related Solutions

Storage – Storing SHA-256 64 Byte String in Solidity

I would chop it up into two bytes32 client-side and re-assemble it client-side. The simplest form might be:

bytes32 part1;
bytes32 part2;

This is as economical as it gets, and can be passed around between contracts if needed.

Hope it helps.

p.s. If you don't need to recall them and only need to validate their existence (from some other off-chain source or claim), hashing them into a single bytes32 would provide enough precision and 50% gas reduction.

[Ethereum] How Do i Splice An Array in Solidity

You may want a linked list.

Removing an element and then shifting all the others over is the best way to deal with this using an array. (BTW, I'm pretty sure that's how JavaScript's splice works, too.) Using a linked list would allow you to efficiently remove an element.

That said, do you also need to insert elements and preserve sorted order? If so, how are you doing the insert? (That also sounds like an O(n) operation.) You could consider other data structures, like a heap or a balanced tree, or you could sort on-demand on the client. It all depends on what your scenario is.

EDIT

In response to the question edit, this is fine, but think about the expected ratio of deleted items to existing items. If, after much use, you have 10 items with 10,000 deleted items in between them, you'll find this is extremely inefficient. A linked list doesn't have this problem.

Also consider using exists = true instead of deleted = false. This may save gas depending on the expected use.

EDIT 2

A hastily-thrown-together doubly linked list implementation. Please test before using. :-)

pragma solidity ^0.4.21;

contract DoublyLinkedList {
    struct Node {
        bytes payload;
        uint256 next;
        uint256 prev;
    }

    uint256 nextNodeID = 1;  // 0 is a sentinel value.
    mapping(uint256 => Node) nodes;
    uint256 head;
    uint256 tail;
    uint256 count = 0;

    function append(bytes payload) public {
        if (tail == 0) {
            // 0 is a sentinel. tail == 0 means head == 0 and the list is empty.
            head = nextNodeID;
            tail = nextNodeID;
            nodes[nextNodeID].payload = payload;
        } else {
            nodes[tail].next = nextNodeID;
            nodes[nextNodeID].payload = payload;
            nodes[nextNodeID].prev = tail;
            tail = nextNodeID;
        }
        nextNodeID += 1;
        count += 1;
    }

    function validNode(uint256 nodeID) internal view returns (bool) {
        return nodeID == head || nodes[nodeID].prev != 0;
    }

    function remove(uint256 nodeID) public {
        require(validNode(nodeID));

        Node storage node = nodes[nodeID];

        // Update head and tail.
        if (tail == nodeID) {
            tail = nodes[nodeID].prev;
        }
        if (head == nodeID) {
            head = nodes[nodeID].next;
        }

        // Update previous node's next pointer.
        if (node.prev != 0) {
            nodes[node.prev].next = node.next;
        }

        // Update next node's previous pointer.
        if (node.next != 0) {
            nodes[node.next].prev = node.prev;
        }

        // Reclaim storage for the removed node.
        delete nodes[nodeID];

        count -= 1;
    }

    function getNodeIDs() public view returns (uint256[] ids) {
        ids = new uint256[](count);

        uint256 current = head;
        for (uint256 i = 0; i < count; i++) {
            ids[i] = current;
            current = nodes[current].next;
        }
    }

    function getPayload(uint256 nodeID) public view returns (bytes) {
        require(validNode(nodeID));

        return nodes[nodeID].payload;
    }
}

Best Answer

Related Solutions

Storage – Storing SHA-256 64 Byte String in Solidity

[Ethereum] How Do i Splice An Array in Solidity

Related Topic