#StackBounty: #magento2 #javascript #performance #knockoutjs Magento 2: javascript elements load slowly

Bounty: 150

Checkout forms, gallery on product pages, and more elements loaded by javascript take up to 4 seconds to load.

What can be done to make javascript elements load faster?

Update:

I’m using a custom theme which inherits from Blank theme. I’ve not added additional JS files, only made minor changes to them for translation purposes.
All caches are enabled.
It is a live site in production mode.

Pages loading times:

Category and product pages: 5 to 6 seconds.
Cart and checkout: 9 to 10 seconds. (is it normal?)

On product pages, product images are the last to load. This can be annoying for the user. Is it possible to make them load faster / before other elements on the page?

product page
category page


Get this bounty!!!

#StackBounty: #windows-10 #cpu #performance #hyper-threading How does the Windows 10 scheduler deal with Hyper Threading since Core Par…

Bounty: 50

I’m running Windows 10 (1607) on an Intel Xeon E3-1231v3 CPU (Haswell, 4 physical cores, 8 logical cores).

When I first had Windows 7 installed on this machine, I could observe that four out of eight logical cores were parked until an application needed more than 4 threads. One can check with Windows resource monitor whether cores are parked or not (example).
As far as I understand, this is an important technique to keep the threads balanced across physical cores, as explained on the Microsoft website: “the Core Parking algorithm and infrastructure is also used to balance processor performance between logical processors on Windows 7 client systems with processors that include Intel Hyper-Threading Technology.

However after upgrading to Windows 10, I noticed that there is no core parking. All logical cores are active all the time and when you run an application using less than four threads you can see how the scheduler equally distributes them across all logical cpu cores. Microsoft employees have confirmed that Core Parking is disabled in Windows 10.

But I wonder why? What was the reason for this? Is there a replacement and if yes, how does it look like? Has Microsoft implemented a new scheduler strategy that made core parking obsolete?


Appendix:

Here is an example on how core parking introduced in Windows 7 can benefit performance (in comparison to Vista which didn’t have core parking feature yet). What you can see is that on Vista, HT (Hyper Threading) harms performance while on Windows 7 it doesn’t:

enter image description here

enter image description here

(source)

I tried to enable Core Parking as mentioned here, but what I observed was that the Core Parking algorithm isn’t Hyper Threading aware anymore. It parked cores 4,5,6,7, while it should have parked core 1,3,5,7 to avoid that threads are assigned to the same physical core. Windows enumerates cores in such a way that two successive indices belong to the same physical core. Very strange. It seems Microsoft has messed this up fundamentally. And no one noticed…

Furthermore, I did some CPU benchmarks using exactly 4 threads.

CPU affinity set to all cores (Windows defualt):

Average running time: 17.094498, standard deviation: 2.472625

CPU affinity set to every other core (so that it runs on different physical cores, best possible scheduling):

Average running time: 15.014045, standard deviation: 1.302473

CPU affinity set to the worst possible scheduling (four logical cores on two physical cores):

Average running time: 20.811493, standard deviation: 1.405621

So there is a performance difference. And you can see that the Windows defualt scheduling ranks between the best and worst possible scheduling, as we would expect it to happen with a non-hyperthreading aware scheduler. However, as pointed out in the comments, there may be other causes responsible for this, like fewer context switches, inference by monitoring applications, etc. So we still don’t have a definitive answer here.

Source code for my benchmark:

#include <stdlib.h>
#include <Windows.h>
#include <math.h>

double runBenchmark(int num_cores) {
  int size = 1000;
  double** source = new double*[size];
  for (int x = 0; x < size; x++) {
    source[x] = new double[size];
  }
  double** target = new double*[size * 2];
  for (int x = 0; x < size * 2; x++) {
    target[x] = new double[size * 2];
  }
  #pragma omp parallel for num_threads(num_cores)
  for (int x = 0; x < size; x++) {
    for (int y = 0; y < size; y++) {
      source[y][x] = rand();
    }
  }
  #pragma omp parallel for num_threads(num_cores)
  for (int x = 0; x < size-1; x++) {
    for (int y = 0; y < size-1; y++) {
      target[x * 2][y * 2] = 0.25 * (source[x][y] + source[x + 1][y] + source[x][y + 1] + source[x + 1][y + 1]);
    }
  }
  double result = target[rand() % size][rand() % size];
  for (int x = 0; x < size * 2; x++) delete[] target[x];
  for (int x = 0; x < size; x++) delete[] source[x];
  delete[] target;
  delete[] source;
  return result;
}

int main(int argc, char** argv)
{
  int num_cores = 4;
  system("pause");  // So we can set cpu affinity before the benchmark starts 
  const int iters = 1000;
  double avgElapsedTime = 0.0;
  double elapsedTimes[iters];
  for (int i = 0; i < iters; i++) {
    LARGE_INTEGER frequency;
    LARGE_INTEGER t1, t2;
    QueryPerformanceFrequency(&frequency);
    QueryPerformanceCounter(&t1);
    runBenchmark(num_cores);
    QueryPerformanceCounter(&t2);
    elapsedTimes[i] = (t2.QuadPart - t1.QuadPart) * 1000.0 / frequency.QuadPart;
    avgElapsedTime += elapsedTimes[i];
  }
  avgElapsedTime = avgElapsedTime / iters;
  double variance = 0;
  for (int i = 0; i < iters; i++) {
    variance += (elapsedTimes[i] - avgElapsedTime) * (elapsedTimes[i] - avgElapsedTime);
  }
  variance = sqrt(variance / iters);
  printf("Average running time: %f, standard deviation: %f", avgElapsedTime, variance);
  return 0;
}


Get this bounty!!!

#StackBounty: #magento-1.7 #database #api #rest #performance Creating an API to communicate directly with Magento DB

Bounty: 50

We have been using the Magento Rest API to communicate between external systems and Magento. Painfully, we have discovered that the REST API does not scale well. Specifically, often times requests time-out when requesting large amounts of data (say, about fifty products). We are using version 1.7.0.2.

One solution we are investigating is creating a custom API not written using Magento for the purpose of reading/writing into Magento.

  • Is this a solution typically used?
  • If so, any packages that simplify read/write operations from Magneto EAV tables?
  • If not, are there any ways to speed up the Magento REST API?

We are in the process of scaling and speed is very important to us.


Get this bounty!!!

#StackBounty: #javascript #performance #animation #canvas #raycasting Hoc462 – A Raycaster

Bounty: 50

For the past week, I’ve been making a raycaster in JS and if you want a live demo, you can try it here. It ran smoothly before I added variable height walls but now it is very slow (~15 FPS) so I want to know how to make it run faster.

I’d also like it if somebody would review the code normally so that I can improve it further.

var ctx = c.getContext("2d");
var mapCtx = minimap.getContext("2d");
var MINI_MAP_SCALE = 8;
var OUTSIDE_THE_MAP = -1;
var NO_HIT = 0;
var IS_HIT = 1;
var X_HIT = 0;
var Y_HIT = 1;
var UP = 1;
var DOWN = -1;
var LEFT = -1;
var RIGHT = 1;
var TEXTURED_WALL = 10;
var COLORED_WALL = 11;
var SPRITE = 12;
var SORT_BY_DISTANCE = (a, b) => {return b.distance - a.distance};
function drawMiniMap() {
    if (minimap.width !== player.map.width * MINI_MAP_SCALE || minimap.height !== player.map.height * MINI_MAP_SCALE) {
        minimap.width = player.map.width * MINI_MAP_SCALE;
        minimap.height = player.map.height * MINI_MAP_SCALE;
    }
    mapCtx.fillStyle = "white";
    mapCtx.fillRect(0, 0, minimap.width, minimap.height);
    for (var y = 0; y < player.map.height; y++)
        for (var x = 0; x < player.map.width; x++)
            if (player.map.get(x, y) > 0) {
                mapCtx.fillStyle = "rgb(200, 200, 200)";
                mapCtx.fillRect(
                    x * MINI_MAP_SCALE,
                    y * MINI_MAP_SCALE,
                    MINI_MAP_SCALE, MINI_MAP_SCALE
                );
            }
    updateMiniMap();
}
function updateMiniMap() {
    player.map.sprites.forEach(sprite => {
        mapCtx.fillStyle = "rgb(0, 200, 200)";
        mapCtx.fillRect(
            sprite.x * MINI_MAP_SCALE,
            sprite.z * MINI_MAP_SCALE,
            MINI_MAP_SCALE, MINI_MAP_SCALE
        );
        mapCtx.fillStyle = "black";
        mapCtx.fillRect(
            player.x * MINI_MAP_SCALE - 2,
            player.y * MINI_MAP_SCALE - 2,
            4, 4
        );
    });
    mapCtx.beginPath();
    mapCtx.moveTo(player.x * MINI_MAP_SCALE, player.y * MINI_MAP_SCALE);
    mapCtx.lineTo(
        (player.x + Math.cos(player.rot) * 4) * MINI_MAP_SCALE,
        (player.y + Math.sin(player.rot) * 4) * MINI_MAP_SCALE
    );
    mapCtx.stroke();
}
class Player {
    constructor() {
        this.x = 0;
        this.y = 0;
        this.dirX = 1
        this.dirY = 0; 
        this.planeX = 0;
        this.planeY = 0.66;
        this.dir = 0;
        this.rot = 0;
        this.speed = 0;
        this.moveSpeed = 0.4;
        this.rotSpeed = 6 * Math.PI / 180;
        this.map = null;
        return this;
    }
    move() {
        var moveStep = this.speed * this.moveSpeed;
        this.rot += this.dir * this.rotSpeed;
        var newX = this.x + Math.cos(player.rot) * moveStep;
        var newY = this.y + Math.sin(player.rot) * moveStep;
        var currentMapBlock = this.map.get(newX|0, newY|0);
        if (currentMapBlock === OUTSIDE_THE_MAP || currentMapBlock > 0) {
            this.stopMoving();
            return;
        };
        this.x = newX;
        this.y = newY;
        this.rotateDirectionAndPlane(this.dir * this.rotSpeed);
        return this;
    }
    rotateDirectionAndPlane(angle) {
        var oldDirX = this.dirX;
        this.dirX = this.dirX * Math.cos(angle) - this.dirY * Math.sin(angle);
        this.dirY = oldDirX * Math.sin(angle) + this.dirY * Math.cos(angle);
        var oldPlaneX = this.planeX;
        this.planeX = this.planeX * Math.cos(angle) - this.planeY * Math.sin(angle);
        this.planeY = oldPlaneX * Math.sin(angle) + this.planeY * Math.cos(angle);
        this.stopMoving();
    }
    setXY(x, y) {
        this.x = x;
        this.y = y;
        return this;
    }
    setRot(angle) {
        var difference = angle - this.rot;
        this.rot = angle;
        this.rotateDirectionAndPlane(difference);
        return this;
    }
    startMoving(direction) {
        switch (direction) {
            case "up":
                this.speed = UP; break;
            case "down":
                this.speed = DOWN; break;
            case "left":
                this.dir = LEFT; break;
            case "right":
                this.dir = RIGHT; break;
        }
        return this;
    }
    stopMoving() {
        this.speed = 0;
        this.dir = 0;
        return this;
    }
    castRays() {
        this.move();
        var visibleSprites = [];
        var zBuffer = [];
        Object.keys(this.map.wallTypes).forEach(typeID => {
            this.castRaysToSpecifiedWallType(this.map.wallTypes[typeID], zBuffer);
        });
        this.map.sprites.forEach(sprite => {
            var spriteX = sprite.x - this.x;
            var spriteY = sprite.z - this.y;
            var invDet = 1 / (this.planeX * this.dirY - this.dirX * this.planeY);
            var transformX = invDet * (this.dirY * spriteX - this.dirX * spriteY);
            var transformY = invDet * (-this.planeY * spriteX + this.planeX * spriteY);
            if (transformY > 0) {
                var spriteScreenX = (c.width / 2) * (1 + transformX / transformY);
                var spriteHeight = Math.abs(c.height / transformY);
                var imaginedHeight = sprite.y * spriteHeight;
                var drawStartY = -imaginedHeight / 2 + c.height / 2 - imaginedHeight;
                var drawEndY = imaginedHeight / 2 + c.height / 2 - imaginedHeight;
                var spriteWidth = Math.abs(c.height / transformY);
                var drawStartX = -spriteWidth / 2 + spriteScreenX;
                var drawEndX = spriteWidth / 2 + spriteScreenX;
                var spriteImage = sprite.texture;
                var texHeight = spriteImage.image.height;
                var texWidth = spriteImage.image.width;
                zBuffer.push({
                    type: SPRITE,
                    drawX: drawStartX,
                    drawY: drawStartY,
                    texture: spriteImage,
                    width: spriteWidth,
                    height: spriteHeight,
                    distance: transformY
                });
            }
        });
        return zBuffer.sort(SORT_BY_DISTANCE);
    }
    castRaysToSpecifiedWallType(wallType, zBuffer) {
        for (var x = 0; x < c.width; x++) {
            var cameraX = 2 * x / c.width - 1;
            var rayPosX = this.x;
            var rayPosY = this.y;
            var rayDirX = this.dirX + this.planeX * cameraX;
            var rayDirY = this.dirY + this.planeY * cameraX;
            var mapX = rayPosX | 0;
            var mapY = rayPosY | 0;
            var deltaDistX = Math.sqrt(1 + (rayDirY * rayDirY) / (rayDirX * rayDirX));
            var deltaDistY = Math.sqrt(1 + (rayDirX * rayDirX) / (rayDirY * rayDirY));
            var stepX = 0;
            var stepY = 0;
            var sideDistX = 0;
            var sideDistY = 0;
            var wallDistance = 0;
            var giveUp = false;
            if (rayDirX < 0) {
                stepX = -1;
                sideDistX = (rayPosX - mapX) * deltaDistX;
            } else {
                stepX = 1;
                sideDistX = (mapX + 1 - rayPosX) * deltaDistX;
            }
            if (rayDirY < 0) {
                stepY = -1;
                sideDistY = (rayPosY - mapY) * deltaDistY;
            } else {
                stepY = 1;
                sideDistY = (mapY + 1 - rayPosY) * deltaDistY;
            }
            var hit = NO_HIT;
            var side = X_HIT;
            while (hit === NO_HIT) {
                if (sideDistX < sideDistY) {
                    sideDistX += deltaDistX;
                    mapX += stepX;
                    side = X_HIT;
                } else {
                    sideDistY += deltaDistY;
                    mapY += stepY;
                    side = Y_HIT;   
                }
                var currentMapBlock = this.map.get(mapX, mapY);
                if (currentMapBlock === OUTSIDE_THE_MAP || this.map.wallTypes[currentMapBlock] === wallType) {
                    hit = IS_HIT;
                    if (currentMapBlock === OUTSIDE_THE_MAP) {
                        giveUp = true;
                    }
                }
            }
            if (giveUp) {continue;}
            if (side === X_HIT) {
                wallDistance = (mapX - rayPosX + (1 - stepX) / 2) / rayDirX;
            } else {
                wallDistance = (mapY - rayPosY + (1 - stepY) / 2) / rayDirY;
            }
            var color = wallType.color;
            var wallHeight = wallType.height;
            var lineHeight = c.height / wallDistance;
            var drawEnd = lineHeight / 2 + c.height / 2;
            lineHeight *= wallHeight < 0 ? 0 : wallHeight;
            var drawStart = drawEnd - lineHeight;
            var exactHitPositionX = rayPosY + wallDistance * rayDirY;
            var exactHitPositionY = rayPosX + wallDistance * rayDirX;
            if (side === X_HIT) {
                var wallX = exactHitPositionX;
            } else {
                var wallX = exactHitPositionY;
            }
            var currentBuffer = {};
            zBuffer.push(currentBuffer);
            currentBuffer.side = side;
            currentBuffer.start = drawStart;
            currentBuffer.end = drawEnd;
            currentBuffer.x = x; 
            currentBuffer.distance = wallDistance;
            if (color instanceof Texture) {
                currentBuffer.type = TEXTURED_WALL;
                var texture = color;
                currentBuffer.texture = texture;
                wallX -= wallX | 0;
                var textureX = wallX * texture.image.width;
                if ((side === X_HIT && rayDirX > 0) || (side === Y_HIT && rayDirY < 0)) {
                    textureX = texture.image.width - textureX - 1;
                }
                currentBuffer.textureX = textureX;
            } else {
                currentBuffer.type = COLORED_WALL;
                currentBuffer.color = color;
            }
        }

    }
    render(zBuffer) {
        zBuffer.forEach(currentBuffer => {
            var side = currentBuffer.side;
            var drawStart = currentBuffer.start;
            var drawEnd = currentBuffer.end;
            var {
                side,
                texture,
                textureX,
                color,
                x,
                drawX,
                drawY,
                width,
                height,
                start: drawStart,
                end: drawEnd
            } = currentBuffer;
            var lineHeight = drawEnd - drawStart;
            if (currentBuffer.type === TEXTURED_WALL) {
                ctx.globalAlpha = 1;
                ctx.fillStyle = "black";
                ctx.fillRect(x, drawStart, 1, lineHeight);
                if (side === Y_HIT) {
                    ctx.globalAlpha = .7;
                } else {
                    ctx.globalAlpha = 1;
                }
                ctx.drawImage(texture.image, textureX, 0, 1, texture.image.height, x, drawStart, 1, lineHeight);
            } else if (currentBuffer.type === COLORED_WALL) {
                ctx.globalAlpha = 1;
                ctx.fillStyle = "black";
                ctx.fillRect(x, drawStart, 1, lineHeight);
                if (side === Y_HIT) {
                    ctx.globalAlpha = .7;
                } else {
                    ctx.globalAlpha = 1;
                }
                ctx.fillStyle = "rgb("+color[0]+", "+color[1]+", "+color[2]+")";
                ctx.fillRect(x, drawStart, 1, lineHeight);
            } else if (currentBuffer.type === SPRITE) {
                ctx.globalAlpha = 1;
                ctx.drawImage(texture.image, 0, 0, texture.image.width, texture.image.height, drawX, drawY, width, height);
            }
        });

    }
}
class Grid {
    constructor(wallGrid, wallTextures, sprites) {
        this.wallGrid = wallGrid;
        this.height = wallGrid.length;
        this.width = this.height === 0 ? 0 : wallGrid[0].length;
        this.wallTypes = wallTextures || {};
        this.sprites = sprites || [];
        return this;
    }
    get(x, y) {
        x = x | 0;
        y = y | 0;
        var currentMapBlock = this.wallGrid[y];
        if (currentMapBlock === undefined) return OUTSIDE_THE_MAP;
        currentMapBlock = currentMapBlock[x];
        if (currentMapBlock === undefined) return OUTSIDE_THE_MAP;
        return currentMapBlock;
    }

}
class Texture {
    constructor(src, width, height) {
        this.image = new Image();
        this.image.src = src;
        width ? this.image.width = width : 0;
        height ? this.image.height = height : 0;
    }
}
class Sprite {
    constructor(texture, x, y, z){
        this.texture = texture;
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

class Wall {
    constructor(height, color) {
        this.height = height;
        this.color = color;
    }
}
var player = new Player();
player.x = player.y = 3;
player.map = new Grid([
    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,1,0,1,0,1,0,0,0,1],
    [1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1],
    [1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,1,1,2,1,1,0,0,0,0,1,0,1,0,1,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,2,1,0,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,1,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
], {'1': new Wall(2, new Texture('walls.png')), '2': new Wall(4, [255, 0, 0]) }, [new Sprite(new Texture('walls.png'), 4, 1, 4)]);
var keyCodes = {
    "38": "up",
    "40": "down",
    "37": "left",
    "39": "right"
}
document.addEventListener("keydown", function(e) {
    player.startMoving(keyCodes[e.keyCode]);
});
document.addEventListener("keyup", function(e) {
    player.stopMoving(keyCodes[e.keyCode]);
});
var isDragging = false;
c.addEventListener("mousedown", startDragging);
window.addEventListener("mouseup", endDragging);
c.addEventListener("touchstart", startDragging);
c.addEventListener("touchend", endDragging);
c.addEventListener("mousemove", whileDragging);
c.addEventListener("touchmove", whileDragging);
var mouseX = 0;
var pmouseX = 0;
var mouseY = 0;
var pmouseY = 0;
function whileDragging(e) {
    var event;
    e.preventDefault();
    if (e.touches) {
        event = e.touches[0];
    } else {
        event = e;
    }
    pmouseX = mouseX;
    pmouseY = mouseY;
    mouseX = event.pageX - c.offsetLeft;
    mouseY = event.pageY - c.offsetTop;
    if (isDragging) {
        player.setRot(player.rot + (mouseX - pmouseX) / c.width * 2);
        player.speed = -(mouseY - pmouseY) / c.height * 15;
    }
}
function startDragging(e) {
    var event;
    e.preventDefault();
    if (e.touches) {
        event = e.touches[0];
    } else {
        event = e;
    }
    mouseX = event.pageX - c.offsetLeft;
    mouseY = event.pageY - c.offsetTop;
    isDragging = true;
}
function endDragging(e) {
    e.preventDefault();
    isDragging = false;
}
function renderLoop() {
    ctx.clearRect(0, 0, c.width, c.height);
    player.render(player.castRays());
}
requestAnimationFrame(function animate() {
    if (c.clientWidth !== c.width || c.clientHeight !== c.height) {
        c.width = c.clientWidth;
        c.height = c.clientHeight;
    }
    renderLoop();
    drawMiniMap();
    requestAnimationFrame(animate);
});


Get this bounty!!!

#StackBounty: #performance #php #authentication #laravel #steam Steam Auth for Laravel

Bounty: 100

I’m not expert on OpenID, so i don’t know if my package is correct and safe. I’ve realized that after login on Steam community, take about 2/3 seconds to return to my page. It’s my issue or is from steam?

{
/**
 * The application instance.
 *
 * @var IlluminateContractsFoundationApplication
 */
private $app;
/**
 * The HTTP Client instance.
 *
 * @var GuzzleHttpClient
 */
private $httpClient;
/**
 * The custom parameters to be sent with the request.
 *
 * @var array
 */
private $parameters = [];
/**
 * The type of the encoding in the query.
 *
 * @var int Can be either PHP_QUERY_RFC3986 or PHP_QUERY_RFC1738.
 */
private $encodingType = PHP_QUERY_RFC3986;
/**
 * Create a new Steamlite manager instance.
 *
 * @param IlluminateContractsFoundationApplication $app
 * @return void
 */
public function __construct(Application $app)
{
    $this->app = $app;
}
/**
 * {@inheritdoc}
 */
public function redirect()
{
    return new RedirectResponse($this->getAuthUrl());
}
/**
 * {@inheritdoc}
 */
public function user()
{
    if ($this->hasInvalidSignature($query = $this->app['request']->query())) {
        throw new InvalidSignatureException();
    }
    return $this->mapUserToObject($this->getUserByToken($this->getAccessToken($query)));
}
/**
 * Get the raw user for the given access token.
 *
 * @param string $token
 * @return array
 */
private function getUserByToken($token)
{
    $userUrl = 'https://api.steampowered.com/ISteamUser/GetPlayerSummaries/v0002/?key='.$this->app['config']['services.steam']['key'].'&steamids='.$token;
    $response = $this->getHttpClient()->get($userUrl);
    $user = json_decode($response->getBody(), true);
    return Arr::get($user, 'response.players.0');
}
/**
 * Map the raw user array to a User instance.
 *
 * @param array $user
 * @return Lai0nSteamliteUser
 */
private function mapUserToObject(array $user)
{
    return (new User)->setRaw($user)->map([
        'id' => $user['steamid'], 'nickname' => $user['personaname'], 'name' => Arr::get($user, 'realname', null),
        'avatar' => $user['avatar'], 'visibility' => $user['communityvisibilitystate'],
    ]);
}
/**
 * Parse the access token from identity url.
 *
 * @param array $query
 * @return string
 */
private function getAccessToken(array $query)
{
    preg_match('//id/(d+)$/i', $query['openid_identity'], $matches);
    return $matches[1];
}
/**
 * Get the URL for the steam authentication screen.
 *
 * @return string
 */
private function getAuthUrl()
{
    return $this->buildAuthUrl('https://steamcommunity.com/openid/login');
}
/**
 * Build the authentication URL with the OpenID and custom parameters.
 *
 * @param string $url
 * @return string
 */
private function buildAuthUrl($url)
{
    return $url.'?'.http_build_query($this->getCodeFields(), '', '&', $this->encodingType);
}
/**
 * Get the GET parameters for the code request.
 *
 * @return array
 */
private function getCodeFields()
{
    $fields = [
        'openid.ns' => 'http://specs.openid.net/auth/2.0',
        'openid.mode' => 'checkid_setup',
        'openid.realm' => $this->app['config']['app.url'],
        'openid.return_to' => $this->app['config']['services.steam']['redirect'],
        'openid.identity' => 'http://specs.openid.net/auth/2.0/identifier_select',
        'openid.claimed_id' => 'http://specs.openid.net/auth/2.0/identifier_select',
    ];
    return array_merge($fields, $this->parameters);
}
/**
 * Determine if the current request has a mismatching signature.
 *
 * @param array $query
 * @return bool
 */
private function hasInvalidSignature(array $query)
{
    $postKey = (version_compare(ClientInterface::VERSION, '6') === 1) ? 'form_params' : 'body';
    $response = $this->getHttpClient()->post('https://steamcommunity.com/openid/login', [
        $postKey => $this->getCheckAuthFields($query)
    ]);
    return preg_match('/is_valids*:s*false/i', $response->getBody());
}
/**
 * Get the fields for check authentication.
 *
 * @param array $query
 * @return array
 */
private function getCheckAuthFields(array $query)
{
    $fields = [];
    foreach ($query as $index => $item) {
        $position = strpos($index, '_');
        if ($position !== false) {
            $index = substr_replace($index, '.', $position, strlen('_'));
        }
        $fields[$index] = $item;
    }
    $fields['openid.mode'] = 'check_authentication';
    return $fields;
}
/**
 * Get a instance of the Guzzle HTTP client.
 *
 * @return GuzzleHttpClient
 */
private function getHttpClient()
{
    if (is_null($this->httpClient)) {
        $this->httpClient = new Client();
    }
    return $this->httpClient;
}
/**
 * Set the Guzzle HTTP client instance.
 *
 * @param GuzzleHttpClient $client
 * @return $this
 */
public function setHttpClient(Client $client)
{
    $this->httpClient = $client;
    return $this;
}
/**
 * Set the custom parameters of the request.
 *
 * @param array $parameters
 * @return $this
 */
public function with(array $parameters)
{
    $this->parameters = $parameters;
    return $this;
}


Get this bounty!!!

#StackBounty: #performance #comparative-review #swift #combinatorics On Knuth's "Algorithm L" to generate permutations in…

Bounty: 50

I needed a method to generate all permutations of given elements, so I decided to
implement “Algorithm L (Lexicographic permutation generation)” from
Donald E. Knuth, “GENERATING ALL PERMUTATIONS”
in Swift. The labels L2, L3, L4 refer to the steps in Knuth’s algorithm:

extension Array where Element: Comparable {

    /// Replaces the array by the next permutation of its elements in lexicographic
    /// order.
    ///
    /// It uses the "Algorithm L (Lexicographic permutation generation)" from
    ///    Donald E. Knuth, "GENERATING ALL PERMUTATIONS"
    ///    http://www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz
    ///
    /// - Returns: `true` if there was a next permutation, and `false` otherwise
    ///   (i.e. if the array elements were in descending order).

    mutating func permute() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count <= 1 {
            return false
        }

        // L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j
        // exists.
        var j = count - 2
        while j >= 0 && self[j] > self[j+1] {
            j -= 1
        }
        if j == -1 {
            return false
        }

        // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
        var l = count - 1
        while self[j] > self[l] {
            l -= 1
        }
        swap(&self[j], &self[l])

        // L4: Reverse elements j+1 ... count-1:
        var lo = j + 1
        var hi = count - 1
        while lo < hi {
            swap(&self[lo], &self[hi])
            lo += 1
            hi -= 1
        }
        return true
    }
}

This worked correctly in all my tests, here is a simple example:

do {
    var a = ["a", "b", "c"]
    repeat {
        print(a)
    } while a.permute()
}

Output:

["a", "b", "c"]
["a", "c", "b"]
["b", "a", "c"]
["b", "c", "a"]
["c", "a", "b"]
["c", "b", "a"]

Then I tried to utilize existing methods from the Swift standard library to reduce
the code, which lead to this implementation (called permute2 only to distinguish it
from the first one):

extension Array where Element: Comparable {

    mutating func permute2() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count <= 1 {
            return false
        }

        // L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j
        // exists.
        guard let j = indices.reversed().dropFirst()
            .first(where: { self[$0] <= self[$0 + 1] })
        else { return false }

        // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
        let l = indices.reversed()
            .first(where: { self[j] <= self[$0] })!
        swap(&self[j], &self[l])

        // L4: Reverse elements j+1 ... count-1:
        replaceSubrange(j+1..<count, with: self[j+1..<count].reversed())
        return true
    }
}

All loops are replaced by single statements which are almost self-explaining. So this
looks nice, but what about the performance?

For benchmarking, the $ 10! = 3628800 $ permutations of 10 elements are computed:

let N = 10
var count = 0
let start = Date()
var a = Array(1...N)
repeat {
    count += 1
} while a.permute() // or a.permute2()
let end = Date()
print(count, end.timeIntervalSince(start))

The results (on a 1.2 GHz Intel Core m5 MacBook, compiled in Release mode) are

  • using the “iterative” permute(): 0.03 seconds
  • using the “functional” permute2(): 3 seconds

i.e. the functional method is slower by a factor of 100.

An alternative would be a non-mutating method which returns the next permutation
or nil:

extension Array where Element: Comparable {

    func nextPermutation() -> Array? {
        if count <= 1 { return nil }

        var j = count - 2
        while j >= 0 && self[j] > self[j+1] { j -= 1 }
        if j == -1 { return nil }

        var a = self // Now we need a mutable copy.
        var l = count - 1
        while self[j] > self[l] { l -= 1 }
        swap(&a[j], &a[l])

        var lo = j + 1
        var hi = count - 1
        while lo < hi {
            swap(&a[lo], &a[hi])
            lo += 1
            hi -= 1
        }
        return a
    }
}

The benchmark for the non-mutating version is

let N = 10
var count = 0
let start = Date()
var a = Array(1...N)
repeat {
    count += 1
    guard let b = a.nextPermutation() else { break }
    a = b
} while true
let end = Date()
print(count, end.timeIntervalSince(start))

and takes approx. 0.9 seconds on my MacBook, so this is considerably slower than the
mutating method permute().

All feedback is welcome, in particular (but not restricted to):

  • Naming of the methods and variables.
  • Swifty-ness of the implementation.
  • Iterative vs functional approach: Is it possible to use the (existing) functional
    methods without losing performance?
  • Mutating vs. non-mutating method: Which API is clearer? Can we make the non-mutating
    method as fast as the mutating one?

Remark: I also implemented a Sequence-based enumeration, this
is posted as a separate question Sequence-based enumeration of permutations in lexicographic order.


Get this bounty!!!

#StackBounty: #performance #comparative-review #swift #combinatorics On Knuth's "Algorithm L" to generate permutations in…

Bounty: 50

I needed a method to generate all permutations of given elements, so I decided to
implement “Algorithm L (Lexicographic permutation generation)” from
Donald E. Knuth, “GENERATING ALL PERMUTATIONS”
in Swift. The labels L2, L3, L4 refer to the steps in Knuth’s algorithm:

extension Array where Element: Comparable {

    /// Replaces the array by the next permutation of its elements in lexicographic
    /// order.
    ///
    /// It uses the "Algorithm L (Lexicographic permutation generation)" from
    ///    Donald E. Knuth, "GENERATING ALL PERMUTATIONS"
    ///    http://www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz
    ///
    /// - Returns: `true` if there was a next permutation, and `false` otherwise
    ///   (i.e. if the array elements were in descending order).

    mutating func permute() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count <= 1 {
            return false
        }

        // L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j
        // exists.
        var j = count - 2
        while j >= 0 && self[j] > self[j+1] {
            j -= 1
        }
        if j == -1 {
            return false
        }

        // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
        var l = count - 1
        while self[j] > self[l] {
            l -= 1
        }
        swap(&self[j], &self[l])

        // L4: Reverse elements j+1 ... count-1:
        var lo = j + 1
        var hi = count - 1
        while lo < hi {
            swap(&self[lo], &self[hi])
            lo += 1
            hi -= 1
        }
        return true
    }
}

This worked correctly in all my tests, here is a simple example:

do {
    var a = ["a", "b", "c"]
    repeat {
        print(a)
    } while a.permute()
}

Output:

["a", "b", "c"]
["a", "c", "b"]
["b", "a", "c"]
["b", "c", "a"]
["c", "a", "b"]
["c", "b", "a"]

Then I tried to utilize existing methods from the Swift standard library to reduce
the code, which lead to this implementation (called permute2 only to distinguish it
from the first one):

extension Array where Element: Comparable {

    mutating func permute2() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count <= 1 {
            return false
        }

        // L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j
        // exists.
        guard let j = indices.reversed().dropFirst()
            .first(where: { self[$0] <= self[$0 + 1] })
        else { return false }

        // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
        let l = indices.reversed()
            .first(where: { self[j] <= self[$0] })!
        swap(&self[j], &self[l])

        // L4: Reverse elements j+1 ... count-1:
        replaceSubrange(j+1..<count, with: self[j+1..<count].reversed())
        return true
    }
}

All loops are replaced by single statements which are almost self-explaining. So this
looks nice, but what about the performance?

For benchmarking, the $ 10! = 3628800 $ permutations of 10 elements are computed:

let N = 10
var count = 0
let start = Date()
var a = Array(1...N)
repeat {
    count += 1
} while a.permute() // or a.permute2()
let end = Date()
print(count, end.timeIntervalSince(start))

The results (on a 1.2 GHz Intel Core m5 MacBook, compiled in Release mode) are

  • using the “iterative” permute(): 0.03 seconds
  • using the “functional” permute2(): 3 seconds

i.e. the functional method is slower by a factor of 100.

An alternative would be a non-mutating method which returns the next permutation
or nil:

extension Array where Element: Comparable {

    func nextPermutation() -> Array? {
        if count <= 1 { return nil }

        var j = count - 2
        while j >= 0 && self[j] > self[j+1] { j -= 1 }
        if j == -1 { return nil }

        var a = self // Now we need a mutable copy.
        var l = count - 1
        while self[j] > self[l] { l -= 1 }
        swap(&a[j], &a[l])

        var lo = j + 1
        var hi = count - 1
        while lo < hi {
            swap(&a[lo], &a[hi])
            lo += 1
            hi -= 1
        }
        return a
    }
}

The benchmark for the non-mutating version is

let N = 10
var count = 0
let start = Date()
var a = Array(1...N)
repeat {
    count += 1
    guard let b = a.nextPermutation() else { break }
    a = b
} while true
let end = Date()
print(count, end.timeIntervalSince(start))

and takes approx. 0.9 seconds on my MacBook, so this is considerably slower than the
mutating method permute().

All feedback is welcome, in particular (but not restricted to):

  • Naming of the methods and variables.
  • Swifty-ness of the implementation.
  • Iterative vs functional approach: Is it possible to use the (existing) functional
    methods without losing performance?
  • Mutating vs. non-mutating method: Which API is clearer? Can we make the non-mutating
    method as fast as the mutating one?

Remark: I also implemented a Sequence-based enumeration, this
is posted as a separate question Sequence-based enumeration of permutations in lexicographic order.


Get this bounty!!!

#StackBounty: #performance #comparative-review #swift #combinatorics On Knuth's "Algorithm L" to generate permutations in…

Bounty: 50

I needed a method to generate all permutations of given elements, so I decided to
implement “Algorithm L (Lexicographic permutation generation)” from
Donald E. Knuth, “GENERATING ALL PERMUTATIONS”
in Swift. The labels L2, L3, L4 refer to the steps in Knuth’s algorithm:

extension Array where Element: Comparable {

    /// Replaces the array by the next permutation of its elements in lexicographic
    /// order.
    ///
    /// It uses the "Algorithm L (Lexicographic permutation generation)" from
    ///    Donald E. Knuth, "GENERATING ALL PERMUTATIONS"
    ///    http://www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz
    ///
    /// - Returns: `true` if there was a next permutation, and `false` otherwise
    ///   (i.e. if the array elements were in descending order).

    mutating func permute() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count <= 1 {
            return false
        }

        // L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j
        // exists.
        var j = count - 2
        while j >= 0 && self[j] > self[j+1] {
            j -= 1
        }
        if j == -1 {
            return false
        }

        // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
        var l = count - 1
        while self[j] > self[l] {
            l -= 1
        }
        swap(&self[j], &self[l])

        // L4: Reverse elements j+1 ... count-1:
        var lo = j + 1
        var hi = count - 1
        while lo < hi {
            swap(&self[lo], &self[hi])
            lo += 1
            hi -= 1
        }
        return true
    }
}

This worked correctly in all my tests, here is a simple example:

do {
    var a = ["a", "b", "c"]
    repeat {
        print(a)
    } while a.permute()
}

Output:

["a", "b", "c"]
["a", "c", "b"]
["b", "a", "c"]
["b", "c", "a"]
["c", "a", "b"]
["c", "b", "a"]

Then I tried to utilize existing methods from the Swift standard library to reduce
the code, which lead to this implementation (called permute2 only to distinguish it
from the first one):

extension Array where Element: Comparable {

    mutating func permute2() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count <= 1 {
            return false
        }

        // L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j
        // exists.
        guard let j = indices.reversed().dropFirst()
            .first(where: { self[$0] <= self[$0 + 1] })
        else { return false }

        // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
        let l = indices.reversed()
            .first(where: { self[j] <= self[$0] })!
        swap(&self[j], &self[l])

        // L4: Reverse elements j+1 ... count-1:
        replaceSubrange(j+1..<count, with: self[j+1..<count].reversed())
        return true
    }
}

All loops are replaced by single statements which are almost self-explaining. So this
looks nice, but what about the performance?

For benchmarking, the $ 10! = 3628800 $ permutations of 10 elements are computed:

let N = 10
var count = 0
let start = Date()
var a = Array(1...N)
repeat {
    count += 1
} while a.permute() // or a.permute2()
let end = Date()
print(count, end.timeIntervalSince(start))

The results (on a 1.2 GHz Intel Core m5 MacBook, compiled in Release mode) are

  • using the “iterative” permute(): 0.03 seconds
  • using the “functional” permute2(): 3 seconds

i.e. the functional method is slower by a factor of 100.

An alternative would be a non-mutating method which returns the next permutation
or nil:

extension Array where Element: Comparable {

    func nextPermutation() -> Array? {
        if count <= 1 { return nil }

        var j = count - 2
        while j >= 0 && self[j] > self[j+1] { j -= 1 }
        if j == -1 { return nil }

        var a = self // Now we need a mutable copy.
        var l = count - 1
        while self[j] > self[l] { l -= 1 }
        swap(&a[j], &a[l])

        var lo = j + 1
        var hi = count - 1
        while lo < hi {
            swap(&a[lo], &a[hi])
            lo += 1
            hi -= 1
        }
        return a
    }
}

The benchmark for the non-mutating version is

let N = 10
var count = 0
let start = Date()
var a = Array(1...N)
repeat {
    count += 1
    guard let b = a.nextPermutation() else { break }
    a = b
} while true
let end = Date()
print(count, end.timeIntervalSince(start))

and takes approx. 0.9 seconds on my MacBook, so this is considerably slower than the
mutating method permute().

All feedback is welcome, in particular (but not restricted to):

  • Naming of the methods and variables.
  • Swifty-ness of the implementation.
  • Iterative vs functional approach: Is it possible to use the (existing) functional
    methods without losing performance?
  • Mutating vs. non-mutating method: Which API is clearer? Can we make the non-mutating
    method as fast as the mutating one?

Remark: I also implemented a Sequence-based enumeration, this
is posted as a separate question Sequence-based enumeration of permutations in lexicographic order.


Get this bounty!!!

#StackBounty: #performance #comparative-review #swift #combinatorics On Knuth's "Algorithm L" to generate permutations in…

Bounty: 50

I needed a method to generate all permutations of given elements, so I decided to
implement “Algorithm L (Lexicographic permutation generation)” from
Donald E. Knuth, “GENERATING ALL PERMUTATIONS”
in Swift. The labels L2, L3, L4 refer to the steps in Knuth’s algorithm:

extension Array where Element: Comparable {

    /// Replaces the array by the next permutation of its elements in lexicographic
    /// order.
    ///
    /// It uses the "Algorithm L (Lexicographic permutation generation)" from
    ///    Donald E. Knuth, "GENERATING ALL PERMUTATIONS"
    ///    http://www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz
    ///
    /// - Returns: `true` if there was a next permutation, and `false` otherwise
    ///   (i.e. if the array elements were in descending order).

    mutating func permute() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count <= 1 {
            return false
        }

        // L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j
        // exists.
        var j = count - 2
        while j >= 0 && self[j] > self[j+1] {
            j -= 1
        }
        if j == -1 {
            return false
        }

        // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
        var l = count - 1
        while self[j] > self[l] {
            l -= 1
        }
        swap(&self[j], &self[l])

        // L4: Reverse elements j+1 ... count-1:
        var lo = j + 1
        var hi = count - 1
        while lo < hi {
            swap(&self[lo], &self[hi])
            lo += 1
            hi -= 1
        }
        return true
    }
}

This worked correctly in all my tests, here is a simple example:

do {
    var a = ["a", "b", "c"]
    repeat {
        print(a)
    } while a.permute()
}

Output:

["a", "b", "c"]
["a", "c", "b"]
["b", "a", "c"]
["b", "c", "a"]
["c", "a", "b"]
["c", "b", "a"]

Then I tried to utilize existing methods from the Swift standard library to reduce
the code, which lead to this implementation (called permute2 only to distinguish it
from the first one):

extension Array where Element: Comparable {

    mutating func permute2() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count <= 1 {
            return false
        }

        // L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j
        // exists.
        guard let j = indices.reversed().dropFirst()
            .first(where: { self[$0] <= self[$0 + 1] })
        else { return false }

        // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
        let l = indices.reversed()
            .first(where: { self[j] <= self[$0] })!
        swap(&self[j], &self[l])

        // L4: Reverse elements j+1 ... count-1:
        replaceSubrange(j+1..<count, with: self[j+1..<count].reversed())
        return true
    }
}

All loops are replaced by single statements which are almost self-explaining. So this
looks nice, but what about the performance?

For benchmarking, the $ 10! = 3628800 $ permutations of 10 elements are computed:

let N = 10
var count = 0
let start = Date()
var a = Array(1...N)
repeat {
    count += 1
} while a.permute() // or a.permute2()
let end = Date()
print(count, end.timeIntervalSince(start))

The results (on a 1.2 GHz Intel Core m5 MacBook, compiled in Release mode) are

  • using the “iterative” permute(): 0.03 seconds
  • using the “functional” permute2(): 3 seconds

i.e. the functional method is slower by a factor of 100.

An alternative would be a non-mutating method which returns the next permutation
or nil:

extension Array where Element: Comparable {

    func nextPermutation() -> Array? {
        if count <= 1 { return nil }

        var j = count - 2
        while j >= 0 && self[j] > self[j+1] { j -= 1 }
        if j == -1 { return nil }

        var a = self // Now we need a mutable copy.
        var l = count - 1
        while self[j] > self[l] { l -= 1 }
        swap(&a[j], &a[l])

        var lo = j + 1
        var hi = count - 1
        while lo < hi {
            swap(&a[lo], &a[hi])
            lo += 1
            hi -= 1
        }
        return a
    }
}

The benchmark for the non-mutating version is

let N = 10
var count = 0
let start = Date()
var a = Array(1...N)
repeat {
    count += 1
    guard let b = a.nextPermutation() else { break }
    a = b
} while true
let end = Date()
print(count, end.timeIntervalSince(start))

and takes approx. 0.9 seconds on my MacBook, so this is considerably slower than the
mutating method permute().

All feedback is welcome, in particular (but not restricted to):

  • Naming of the methods and variables.
  • Swifty-ness of the implementation.
  • Iterative vs functional approach: Is it possible to use the (existing) functional
    methods without losing performance?
  • Mutating vs. non-mutating method: Which API is clearer? Can we make the non-mutating
    method as fast as the mutating one?

Remark: I also implemented a Sequence-based enumeration, this
is posted as a separate question Sequence-based enumeration of permutations in lexicographic order.


Get this bounty!!!

#StackBounty: #performance #comparative-review #swift #combinatorics On Knuth's "Algorithm L" to generate permutations in…

Bounty: 50

I needed a method to generate all permutations of given elements, so I decided to
implement “Algorithm L (Lexicographic permutation generation)” from
Donald E. Knuth, “GENERATING ALL PERMUTATIONS”
in Swift. The labels L2, L3, L4 refer to the steps in Knuth’s algorithm:

extension Array where Element: Comparable {

    /// Replaces the array by the next permutation of its elements in lexicographic
    /// order.
    ///
    /// It uses the "Algorithm L (Lexicographic permutation generation)" from
    ///    Donald E. Knuth, "GENERATING ALL PERMUTATIONS"
    ///    http://www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz
    ///
    /// - Returns: `true` if there was a next permutation, and `false` otherwise
    ///   (i.e. if the array elements were in descending order).

    mutating func permute() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count <= 1 {
            return false
        }

        // L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j
        // exists.
        var j = count - 2
        while j >= 0 && self[j] > self[j+1] {
            j -= 1
        }
        if j == -1 {
            return false
        }

        // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
        var l = count - 1
        while self[j] > self[l] {
            l -= 1
        }
        swap(&self[j], &self[l])

        // L4: Reverse elements j+1 ... count-1:
        var lo = j + 1
        var hi = count - 1
        while lo < hi {
            swap(&self[lo], &self[hi])
            lo += 1
            hi -= 1
        }
        return true
    }
}

This worked correctly in all my tests, here is a simple example:

do {
    var a = ["a", "b", "c"]
    repeat {
        print(a)
    } while a.permute()
}

Output:

["a", "b", "c"]
["a", "c", "b"]
["b", "a", "c"]
["b", "c", "a"]
["c", "a", "b"]
["c", "b", "a"]

Then I tried to utilize existing methods from the Swift standard library to reduce
the code, which lead to this implementation (called permute2 only to distinguish it
from the first one):

extension Array where Element: Comparable {

    mutating func permute2() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count <= 1 {
            return false
        }

        // L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j
        // exists.
        guard let j = indices.reversed().dropFirst()
            .first(where: { self[$0] <= self[$0 + 1] })
        else { return false }

        // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
        let l = indices.reversed()
            .first(where: { self[j] <= self[$0] })!
        swap(&self[j], &self[l])

        // L4: Reverse elements j+1 ... count-1:
        replaceSubrange(j+1..<count, with: self[j+1..<count].reversed())
        return true
    }
}

All loops are replaced by single statements which are almost self-explaining. So this
looks nice, but what about the performance?

For benchmarking, the $ 10! = 3628800 $ permutations of 10 elements are computed:

let N = 10
var count = 0
let start = Date()
var a = Array(1...N)
repeat {
    count += 1
} while a.permute() // or a.permute2()
let end = Date()
print(count, end.timeIntervalSince(start))

The results (on a 1.2 GHz Intel Core m5 MacBook, compiled in Release mode) are

  • using the “iterative” permute(): 0.03 seconds
  • using the “functional” permute2(): 3 seconds

i.e. the functional method is slower by a factor of 100.

An alternative would be a non-mutating method which returns the next permutation
or nil:

extension Array where Element: Comparable {

    func nextPermutation() -> Array? {
        if count <= 1 { return nil }

        var j = count - 2
        while j >= 0 && self[j] > self[j+1] { j -= 1 }
        if j == -1 { return nil }

        var a = self // Now we need a mutable copy.
        var l = count - 1
        while self[j] > self[l] { l -= 1 }
        swap(&a[j], &a[l])

        var lo = j + 1
        var hi = count - 1
        while lo < hi {
            swap(&a[lo], &a[hi])
            lo += 1
            hi -= 1
        }
        return a
    }
}

The benchmark for the non-mutating version is

let N = 10
var count = 0
let start = Date()
var a = Array(1...N)
repeat {
    count += 1
    guard let b = a.nextPermutation() else { break }
    a = b
} while true
let end = Date()
print(count, end.timeIntervalSince(start))

and takes approx. 0.9 seconds on my MacBook, so this is considerably slower than the
mutating method permute().

All feedback is welcome, in particular (but not restricted to):

  • Naming of the methods and variables.
  • Swifty-ness of the implementation.
  • Iterative vs functional approach: Is it possible to use the (existing) functional
    methods without losing performance?
  • Mutating vs. non-mutating method: Which API is clearer? Can we make the non-mutating
    method as fast as the mutating one?

Remark: I also implemented a Sequence-based enumeration, this
is posted as a separate question Sequence-based enumeration of permutations in lexicographic order.


Get this bounty!!!