Come si può considerare questo codice performante?

0

Mi sono imbattuto in questo codice (Java) ieri e non riesco a capire perché qualcuno lo avrebbe fatto in qualsiasi lingua.

In quale scenario, linguaggio, delusione paranoica "rimuovendo" i valori da un ArrayList come questo migliorano le prestazioni? Cerca di evitare di essere trascinato nella progettazione generale del lavoratore. So che è brutto e dovrebbe essere diverso, ma sto cercando di capire se c'è un motivo per scrivere un metodo di 'rimozione' in questo modo.

Alcuni punti di chiarimento:

  • tradeIdList non contiene valori duplicati
  • Viene popolato nel costruttore e non viene mai letto fino a quando l'operatore non ha terminato.
  • La classe che legge questo risultato stampa semplicemente il contenuto in un file di registro.

    TradeIdWorker di classe pubblica implementa Runnable {     elenco privato tradeIdList = new ArrayList ();     ....

    public void run(){
        // Copy the tradeIdList to an array (No I do not know why)
        for (int tradeId : tradeIdArray){
            ....
            // Once processed, remove it
            removeProcessedTradeId(tradeId);
    }
    
    /**
     * Set Trade id to zero (for performance)
     */
    private void removeProcessedTradeId(int tradeId) {
        for (int index = 0; index < tradeIdList.size(); index++) {
            if (tradeIdList.get(index).intValue() == tradeId) {
                tradeIdList.set(index, 0);
            }
        }
    }
    

Per cercare di capire perché ho aggiunto un caso d'uso del mondo reale dal sistema. L'arraylist di tradeIds non contiene mai duplicati.

public static void main(String[] args) {
    testNormalRemove();
    testPerformantRemove();
}

private static void testNormalRemove() {
    ArrayList<Integer> aList = new ArrayList<Integer>();

    for (int i = 0; i < 1000000; i++) {
        aList.add(i);
    }

    long start = System.currentTimeMillis();

    for (int i = 0; i < aList.size(); i += 1000) {
        aList.remove((Object) i);
    }

    long end = System.currentTimeMillis();
    System.out.println("Normal Took: " + (end - start)); // 1700ms
}

private static void testPerformantRemove() {
    ArrayList<Integer> aList = new ArrayList<Integer>();

    for (int i = 0; i < 1000000; i++) {
        aList.add(i);
    }

    long start = System.currentTimeMillis();

    for (int i = 0; i < aList.size(); i += 1000) {
        for (int index = 0; index < aList.size(); index++) {
            if (aList.get(index).intValue() == i) {
                aList.set(index, 0);
            }
        }
    }

    long end = System.currentTimeMillis();
    System.out.println("Performant Took: " + (end - start)); // 4800ms
}
    
posta beirtipol 09.03.2016 - 11:55
fonte

1 risposta

6

La rimozione di un elemento in un ArrayList richiede lo spostamento di tutti gli elementi rimanenti con un indice più in basso di uno. Contrassegnare un elemento con uno zero no.

Quindi se N è il numero di elementi in tradeIdList e M è il numero di elementi in tradeIdArray, questo approccio è O (M × N) mentre in realtà la rimozione degli elementi su ogni iterazione di M è O (M × N²).

Tipicamente ci sarebbe un passaggio finale per rimuovere tutti i valori oscurati, che sarebbe O (N) e quindi non aumentare la complessità.

Questo vale per il caso generale - il codice itera su tutto l'elenco di array, azzerando qualsiasi occorrenza dell'ID. Se si può supporre che ci sia una sola occorrenza, allora non ci sarà differenza nei tempi.

Nel seguito, i test confrontano un insieme di input con ripetizioni.

import java.util.*;

public class Programmers312172 {
    public static void main (String ... args) {
        Worker[] workers = {new TradeIdWorker(), new RemoveWorker(), new ZeroOnceWorker(), new RemoveOnceWorker()};

        for (int run = 0; run < 10; ++run) {
            for ( Worker worker : workers )
                worker.prepare();

            for ( Worker worker : workers ) {
                long start = System.nanoTime();
                worker.run();
                long end = System.nanoTime();
                System.out.printf("%-24s  %12dns\n", worker, end-start);
            }
        }
    }

    static int[] prepareInputs (List<Integer> tradeIdList) {
        Random  r = new Random(0);
        int[]   tradeIdArray = new int[1000];

        for(int i=0; i < 100000; ++i)
            tradeIdList.add(r.nextInt(2000));

        for(int i=0; i < 1000; ++i)
            tradeIdArray[i] = i;

        return tradeIdArray;
    }

    public abstract static class Worker {
        protected List<Integer> tradeIdList = new ArrayList<Integer>();
        private int[] tradeIdArray;

        public void prepare() {
            tradeIdArray = prepareInputs(tradeIdList);
        }

        public void run(){
            for (int tradeId : tradeIdArray)
                removeProcessedTradeId(tradeId);
        }

        protected abstract void removeProcessedTradeId(int tradeId);
    }            

    public static class TradeIdWorker extends Worker {
        @Override
        protected void removeProcessedTradeId(int tradeId) {
            for (int index = 0; index < tradeIdList.size(); index++) {
                if (tradeIdList.get(index).intValue() == tradeId) {
                    tradeIdList.set(index, 0);
                }
            }
        }
        @Override
        public String toString() { return "zero all"; }
    }            
    public static class ZeroOnceWorker extends Worker {
        @Override
        protected void removeProcessedTradeId(int tradeId) {
            for (int index = 0; index < tradeIdList.size(); index++) {
                if (tradeIdList.get(index).intValue() == tradeId) {
                    tradeIdList.set(index, 0);
                    break;
                }
            }
        }
        @Override
        public String toString() { return "zero once"; }
    }            
    public static class RemoveWorker extends Worker {
        protected void removeProcessedTradeId(int tradeId) {
            Integer toRemove = tradeId;
            while(tradeIdList.remove(toRemove));
        }
        @Override
        public String toString() { return "remove all"; }
    }            
    public static class RemoveOnceWorker extends Worker {
        protected void removeProcessedTradeId(int tradeId) {
            tradeIdList.remove((Integer)tradeId);
        }
        @Override
        public String toString() { return "remove once"; }
    }
}

Questo dà valori come

zero all                    1136905192ns
remove all                 13162226491ns
zero once                      6587605ns
remove once                   70135769ns

Altri dati cambieranno le relazioni, ma in genere ci saranno aumenti di velocità simili. Dato che il valore sarà tipicamente colpito nel primo 2% degli elementi, zero una volta può fermarsi dopo aver iterato oltre il 2% della lista, ma rimuovere una volta deve spostare il restante 98% in basso, quindi deve scorrere su tutta la lista. Probabilmente potresti anche trovare input che non mostrano alcun miglioramento (ad esempio, una singola occorrenza, rimuovi in ordine inverso dalla fine), ma in generale l'azzeramento sarà migliore.

    
risposta data 09.03.2016 - 12:23
fonte

Leggi altre domande sui tag