The Big Programming Thread - Page 647

On July 03 2015 17:50 sabas123 wrote:

Show nested quote +

On July 03 2015 11:25 Blisse wrote:

On July 03 2015 00:33 netherh wrote:

On July 02 2015 18:13 Blisse wrote:
Not really. Foreach loops are backed by Iterators anyways.

The language is Java if that helps.

What does your profiler say about what's taking up all the time?

the nested for loops costs about as much as the contains operations

turns out it was probably the algorithm efficiency, nested for loops are bad. we figured out a more effective solution, i'll share after the deadline passes if y'all are interested because it's actually pretty neat

You made me curious, so please share it

    private static List<Triangle> enumerateTriangles(final List<Integer>[] biggerNeighbours, int initialPosition, int step) {
        final List<Triangle> triangles = new ArrayList<Triangle>();

        for (int smallVertex = initialPosition; smallVertex < biggerNeighbours.length; smallVertex += step) {

            List<Integer> smallNeighbours = biggerNeighbours[smallVertex];

            for (int mediumVertex : smallNeighbours) {

                // from sorted ordering and pre-processing, all elements in smallNeighbours are larger than smallVertex

                List<Integer> mediumNeighbours = biggerNeighbours[mediumVertex];

                // small and medium are sorted min->max
                // iterate two pointers backwards from max->min searching for equal elements

                Integer i_s = smallNeighbours.size()-1;
                Integer i_m = mediumNeighbours.size()-1;

                while (i_s >= 0 && i_m >= 0) {

                    final int check_s = smallNeighbours.get(i_s);
                    final int check_m = mediumNeighbours.get(i_m);

                    if (check_m <= smallVertex || check_s <= mediumVertex) {
                        break;
                    }

                    if (check_s < check_m) {
                        --i_m;
                    } else if (check_s > check_m) {
                        --i_s;
                    } else {
                        triangles.add(new Triangle(smallVertex, mediumVertex, check_m));
                        --i_s;
                        --i_m;
                    }
                }
            }
        }

        return triangles;
    }