How to delete parts of an array?

Question

How to delete the 0s within the array and reduce array to array.length - (array[i] == 0).length entries that the return is uint256[]: 1,2,3? (array[i] == 0).length not works, it just should show that it needs to be variable.

uint[] array = [1,0,2,0,3,0,0]; 
function remove() public returns(uint[]) {
    for (uint i; i < array.length-1; i++){
        if (array[i] == 0){
            array[i] = array[i+1];
        }
    }
    delete array[array.length-1];
    array.length--;
    return array;
} 
// => 0: uint256[]: 1,2,2,3,3,0

Answer 1

The short answer is Don't do it.

I realize it's a contrived example, so this isn't exactly what you want to accomplish in a real-world scenario. Even so, in my opinion, it's worth mentioning that this is a bad approach and there are other approaches that are more appropriate for public blockchains in general, and Ethereum in particular. I will share some alternatives that may be helpful to others, as well as discourage pursuit of this path.

What is the problem?

This question is approximately about reorganizing/splicing an array like other languages do. Other languages run on hardware that can easily push values around in memory at vanishingly low cost, so if one wants to shuffle things around the cost is felt mainly in terms of performance. Ethereum is not hardware that can do such things at vanishing low cost. It's approximately the opposite.

At best, we would be reorganzing a memory array with many thousands of replicas double-checking each others' computations and this will be expensive. More likely, we would be reorganizing storage and the cost will be more akin to a database reorganization with, again, many thousands of replicas engaged.

Even bigger problem

The process won't scale. This, for(i=0; i<n; i++) is an antipattern, where n is not bounded by a maximum sufficiently small to ensure that the process can complete without hitting the block gasLimit.

The gasLimit is like a maximum allowable computational heaviness, above which the transaction will simply fail. In other words, if one makes a heavy process, Ethereum will simply reject it. That means an inefficient process might work for a while and then fail at a certain number of rows. That would be like a database that explodes at a certain n number of records. Not good.

Main takeaway: We can't use patterns designed for exponentially cheaper hardware on a platform that charges actual money for every computational step. We have to optimize for the minimal number of state changes.

A solution to that problem is to ensure that all functions complete in O(1) ... one operation, consistent gas cost at any scale. It means avoiding unbounded iteration and unbounded recursion. This leads to different design patterns.

The contrived example

We don't know exactly why you want to rearrange the array. My purpose here is to illustrate alternatives so you won't want to do that.

In the example, you start with a hard-coded input.

uint[] array = [1,0,2,0,3,0,0];

An O(1) response would be:

function remove() public returns(uint[]) {
  return [1,2,3];
}

I realize that's not especially useful, but neither is the hard coding of the initial state.

Catch inputs

In your real-world case, you probably won't hard code the initial state, otherwise you would organize it first. You could catch 0 on the way into the array.

require(value>0);

Reorganize as you go

Possibly the issue is that non-zero values change to zero because of some sort of transition. In this case, you could treat the list as an unordered list of non-zero values. You would move the last item on the list (never zero) to the row to delete, then reduce the list length by 1. This delete pattern is described here: https://medium.com/@robhitchens/solidity-crud-part-2-ed8d8b4f74ec

The important thing is that such an update would complete at a consistent gas cost at any scale. The gas for the incremental reorganization would be paid by whomever wants to write a zero to the list.

Incentivize organic maintenance

Perhaps the ongoing perfect integrity of the list isn't important but you'd like it cleaned up from time to time as a sort of garbage collection. You could reframe this as an incentive system. Instead of one monolithic reorganization that is expected to fix everything (precisely what needs to be avoided), a function that allows a single step. For example, a function to remove a single 0.

Such a function could be invoked by either the owner (pays gas), or opened up to any participant willing to pay for gas. Why would anyone do that? Consider adding a bounty of some sort to compensate for helping with maintenance. In case this sounds radical, it's approximately how the Ethereum Alarm Clock provides a cron-like function. Someone (anyone) triggers the necessary action in return for a little payment.

These are variations on a general theme of inverting control - clients do iteration and recursion while the contract functions perform fixed-cost incremental steps, taking care to always leave the contract in a valid state.

Avoid the big reorganization

Without a doubt, staying organized as we go is preferrable, and we should carefully think about the data structure.

As a general rule of thumb, whenever you feel inclined to search for something (for(i=0; i<n; i++) consider using pointers to immediately locate the required item (i=pointer[row]). Those need to be set up during create, update and delete so the retrieval is a single step.

Is a dynamic array even the ideal choice?

Is sorting even important? Seldom. Have a look over here: https://medium.com/solidified/the-joy-of-minimalism-in-smart-contract-design-b67fb4073422

Hope it helps.

Answer 2

You would need to implement code into your contract, that does what every high level language implementation of what you intend to do does:

Loop through the array, remove the data at the position of the index, and rearrange everything else to be packed tightly.

You can modify this quicksort algorithm for solidity to ignore the size of your numbers, but put all 0s to one side (please correct me of left or right would be better in terms of storage functionality). After that, you loop through the array and remove the 0s kind of like this.

I hope this gives you enough inspiration on whst to do. :)