Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I've got a simple program written in Golang that takes a map as input and tries to solve the travelling salesman problem by using a genetic algorithm. My Crossover method is a real performance killer due to intense use of make() (allocate memory / will provoke the GC).

What I'd like to do - and yet failed to do is outsource the creation of newGenes. pCrossover and therefore the size of newGenes will be the same over all calls of the function, so I'd like to avoid creating that slice again and again.

I am also interested in any suggestions for improvements of my coding style in Golang and other performance improvements I can take a look at.

My source is at Github.

Here is an excerpt of the function I am trying to improve:

func (ts *TravellingSalesman) Crossover() {
    // Crossover        
    var nCrossover = int(ts.pCrossover * float64(ts.nGenes))
    var newGenes = make([]ga.Gene, nCrossover)
    for i:=0; i < nCrossover; i++ {
        newGenes[i].Data = make([]int, ts.geneLength)
        n := rand.Intn(ts.nGenes)
        m := rand.Intn(ts.nGenes)

        currentCity := ts.genes[n].Data[0];
        newGenes[i].Data[0] = currentCity
        for k:=1; k < ts.geneLength; k++ {
            nextN := findNextCity(&(ts.genes[n].Data), currentCity)
            nextM := findNextCity(&(ts.genes[m].Data), currentCity)

            existN := isInArray(&(newGenes[i].Data), nextN)
            existM := isInArray(&(newGenes[i].Data), nextM)

            // n exists, m doesnt -> take m
            if existN && !existM {
                newGenes[i].Data[k] = nextM
                currentCity = nextM
            } else if !existN && existM {
                newGenes[i].Data[k] = nextN
                currentCity = nextN
            } else if existN && existM {
                nextRandom := findNextRandomCity(newGenes[i].Data[0:k], &(ts.genes[n].Data))
                newGenes[i].Data[k] = nextRandom
                currentCity = nextRandom
            } else {
                // If both didn't exist, take the shorter one               
                distN := ts.distMatrix.GetDistance(currentCity-1, nextN-1)
                distM := ts.distMatrix.GetDistance(currentCity-1, nextM-1)

                // Take the shorter route
                if distN < distM {
                    newGenes[i].Data[k] = nextN
                    currentCity = nextN
                } else {
                    newGenes[i].Data[k] = nextM
                    currentCity = nextM
                }
            }
        }
    }

    copy(ts.genes, newGenes)
}
share|improve this question
add comment

1 Answer 1

How about using a slice for Gene.Data?

You just allocate

var allData := make([]int, nCrossover * ts.geneLength)

before entering the for loop and assign

newGenes[i].Data = allData[i * ts.geneLength: (i + 1) * ts.geneLength]

You'd cut down on the amount of allocations (and system calls) without changing much else (except findNextCity and isInArray - but they should be written to accept slices instead of array pointers anyway).

And you'd follow the advice given by the languages creators in Effective Go.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.