[Ethereum] best practice for airdrops and gas usage

I tried to write an airdrop contract which takes a list of recipients and a list of balances and then can be commanded to airdrop all at once. With code below I can launch a single transaction able to drop tokens to 100 addresses at once. It cost around 3.5M gas, which is huge and close to the maximum per transaction. Launching a single transfer with my particular token costs around 58k gas. So the batch is more efficient using only 60% of the gas needed by multiple transactions yet I'm bit disappointed because I expected a much bigger saving. I'm looking for a better strategy if any.

pragma solidity ^0.4.17;


import "zeppelin-solidity/contracts/token/ERC20Basic.sol";


contract Airdrop{
    address[] public recipients;
    uint256[] public balances;
    ERC20Basic public token;
  address owner;


    function Airdrop(address _token) public{
        require(_token != address(0));
        token = ERC20Basic(_token);
    owner = msg.sender;
    }

    function setRecipientsAndBalances(address[] _recipients, uint256[] _balances) public {
        require(_recipients.length == _balances.length);
    require(msg.sender == owner);
        recipients = _recipients;
        balances = _balances;
    }

    function doAirdrop() public returns(uint){
      require(msg.sender == owner);
        require(recipients.length>0);
        for(uint i=0; i < recipients.length; i++){
            if(token.balanceOf(this)>=balances[i]){
                token.transfer(recipients[i],balances[i]);
            }
            else{
                return i;
            }
        }
        return recipients.length;
    }

}

Then I tried to launch with a script like this (code is not complete)

  it('should do massive airdrop to cause gas issues', async function () {

    //an empty array
    var a = [];

    //generate 100 integers and push in a
    for (i=100;i<200;i++) a.push(i);

    //generate 100 0x addresses appending the integers
    const addr = a.map(x => "0x0000000000000000000000000000000000000" + x );

    console.log(addr);

    //generate an array of balances all equal to 1000
    let balances = addr.map(x => 1000);
    console.log(balances);    

    //call the airdrop contract to set the recipients and balances
    await this.airdrop.setRecipientsAndBalances(addr,balances).should.be.fulfilled;

    //call the airdrop to finally airdrop
    let result = await this.airdrop.doAirdrop();

    //write gas on the console
    console.log("gasUsed:"+result.receipt.gasUsed);

  });

I get a gas usage of 3.5ml gas