✔ Listenelemente durch bitweise Verschiebung ?

[limago]

Wieso soll das einfacher sein? Die Division durch 2 ist sicher langsamer als das bitshiften um 1. Das Array statt der Liste finde ich gut, aber sonst finde ich die Lösung aufwendiger.

Gruß

 

[Thomas Darimont]

Hallo,

Wieso soll das einfacher sein? Die Division durch 2 ist sicher langsamer als das bitshiften um 1.

Na ja, ich finde /2 ist für die meisten Leute einfacher verständlich als >> 1 ... ;-) Ob das nun langsamer ist oder nicht hängt erstmal vom Compiler ab (bytecode gejitted-er Maschinenen Code), denn dieser könnte den Code auch entsprechend optimieren.
Weiterhin ist hier IMHO Lesbarkeit wichtiger als das der Code 2 Nanosekunden schneller ausgeführt wird.

Ich hasse nichts mehr als einen Fehler in Code suchen zu müssen, wo sich ein ehemaliger C++ Hacker mit einer eigenen Duffs Device Implementierung verewigen wollte...


Gruß Tom

 

[limago]

Lol, da stimme ich Dir grundsätzlich zu, aber 1. ist das Thema ja "Listenelemente durch bitweise Verschiebung" und 2. ist die Frage was ist einfacher, simpler Code oder gute Lesbarkeit?

Ich denke in diesem Fall ist der Algorithmus so simpel, das sich in Punkto Lesbarkeit beide Lösungen nix schenken.

Außerdem hätte ich in RL kommentiert, ganz ehrlich ;-)

Grüße

 

[Thomas Darimont]

Hallo,

na dann sind wir uns ja einig... ;-)

Gruß Tom

 

[takidoso]

hi ho,
mal eine sprachliche Frage ...
Was sind Duffs Devices und was ist RL
diese Ausdrücke kenne ich (noch) nicht.

Ahhh Duffs Device habe ich nun in wiki Pedia gefunden ok abgehakt, aber RL ist mi rnoch immer ein Rätsel.

 

[Thomas Darimont]

RL = Real Life AFAIK und IMHO ;-)

Gruß Tom

 

[Oliver Gierke]

Ich hab mich gestern auf der Fahrt in den Urlaub auch nochmal versucht und eine recht hübsche Lösung gefunden, wie ich finde:

/**
 * Utility class for implementations of {@code List}.
 * 
 * @author Oliver Gierke - gierke@synyx.de
 */
public class ListUtils {

    /**
     * Returns the a list with elements from the source list and selects the
     * elements on position of a binary decomposition of the given integer
     * number. E.g. a value of 15 will return the 1st, 2nd, 4th and 8th element
     * of the source list.
     * 
     * @param <T>
     * @param source
     * @param number
     * @return
     */
    public static <T> List<T> getBinaryElements(List<T> source, int number) {

        if (source.size() <= Integer.highestOneBit(number)) {
            throw new IllegalArgumentException(
                    "Given source list is to small for the given number!");
        }

        return getBinaryElementsRecursively(source, number, 1);
    }


    /**
     * Recursive implementation of {@code #getBinaryElements(List, int)}.
     * 
     * @param <T>
     * @param source
     * @param number
     * @param base
     * @return
     */
    private static <T> List<T> getBinaryElementsRecursively(List<T> source,
            int number, int base) {

        List<T> result = new ArrayList<T>();

        if (number % 2 == 1) {
            result.add(source.get(base));
        }

        if (2 > number) {
            return result;
        }

        result.addAll(getBinaryElementsRecursively(source, number / 2,
                base << 1));

        return result;
    }
}