What is the most efficient way to compare items in 2 different arrays using Solidity?

Question

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.

Answer 1

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!

Answer 2

here a solution with an exist mapping. of course, the code cannot be used as it is because of the extremely high gas cost. in reality you wouldnt store all of your data in storage. also some pieces should be replaced with yul

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

    mapping (string => bool) listOneContains;
    mapping (string => bool) listTwoContains;

    // #Output 1: items in listTwo that do not exist in listOne   
    string[] public output1;
    // #Output 2: items in listTwo that exist in listOne
    string[] public output2;
    //#Output 3: items in listOne that do not exist in listTwo
    string[] public output3;

    constructor(){
        for(uint256 i = 0;i<listOne.length;){//just if "one" and "two" have the same length; else u would use a second for loop
            listOneContains[listOne[i]] = true;
            listTwoContains[listTwo[i]] = true;
            unchecked{
                i++;
            }
        }

        for(uint256 i = 0;i<listOne.length;){//just if "one" and "two" have the same length; else u would need seperated loops
            if(!listOneContains[listTwo[i]]){
                output1.push(listTwo[i]);
            }
            if(listOneContains[listTwo[i]]){
                output2.push(listTwo[i]);
            }
            if(!listTwoContains[listOne[i]]){
                output3.push(listOne[i]);
            }
            unchecked{
                i++;
            }
        }

    }
}

Answer 3

Recently did this in the following way: https://github.com/1inch/farming/blob/c0d617188d6e8be1fb0fa2d8bb85a62f7b1db42d/contracts/ERC20Farmable.sol#L116-L146

Answer 4

Array operation like you said is pretty limited in Solidity. Another way to achieve what you want is to do off-chain calculation since both listOne and listTwo are public, you can then feed the off-chain calculation result to whatever need it.