5

I was planning on implementing a heap data structure for efficient popping of the highest valued node. I am wondering if it is expensive gas-wise to constantly move values around ("bubble up") to maintain O(log n) running time?

CTRL+F "shape invariant" http://www.cs.cornell.edu/courses/cs2112/2015fa/lectures/lecture.html?id=heaps

Also, are there any plans to make a data structures library for Solidity?

5

Every time you write a non-zero-valued word to a location that was previously zero, you pay 20,000 gas. Every time you update a location from one non-zero value to another, you pay 5,000 gas. Writing a zero to a non-zero location gives you a 15,000 gas refund, but only from the gas you're spending in that transaction (i.e. you can't end up with more ether than you started with).

Reading a storage location costs 50 gas, so you'll have to decide whether it's cheaper to use a heap or just read through all your data items. Probably the more items you store, the more worthwhile the heap will be.

In some cases you may be able to get away with using almost zero gas. To do that, make a constant function that reads all the values and returns the location of the highest value. Calling a constant function via the javascript API runs the code locally instead of on the blockchain. Have your javascript UI do that, and then call a non-constant function that takes the location as a parameter and then performs whatever updates you need.

| improve this answer | |
  • Could you give an example of a simple constant function? I don't really get it. – Nicolas Massart Jun 14 '16 at 20:42
  • 1
    Let's say you're storing an unsorted list of numbers and want to find the largest one. You can write a function that loops through all the numbers and returns the largest, and by marking the function "constant," it will run locally on your machine if it's called directly, instead of by a non-constant function in a contract. You'd declare the function as "function getLargest() public constant returns(uint)". – Dennis Peterson Jun 14 '16 at 21:05
  • But you can't have a unique entry point then. You have to call the constant function and then given the result call the non constant function using the previous result as parameter. So you have to call two functions to get the job done. Am I right? – Nicolas Massart Jun 14 '16 at 21:13
  • 1
    Sure. But you get to call the first one for free. You can save a lot of gas by moving computations off-chain this way. – Dennis Peterson Jun 14 '16 at 23:15
  • 1
    Of course it only works if users can't cause trouble by submitting the wrong value to the second function. – Dennis Peterson Jun 14 '16 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.