InsertSort Benchmark

InsertSort.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

#define TIMES 10000
#define SIZE 1000

void printArray(int *list, int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", list[i]);
    }
    printf("\n");
}

void makeRandList(int *arr, int len)
{
    for (int i = 0; i < len; i++)
    {
        arr[i] = (int)(rand() * 100.0f / (1.0f + RAND_MAX));
    }
}

void moveNum(int *nums, int oldPos, int newPos)
{
    int insertData = nums[oldPos];
    for (int i = oldPos; i > newPos; i--)
    {
        nums[i] = nums[i - 1];
    }
    nums[newPos] = insertData;
}

void runInsertSort(int *nums, int len)
{
    for (int i = 0; i < len; i++)
    {
        int target = nums[i];
        for (int j = 0; j < i; j++)
        {
            if (target < nums[j])
            {
                moveNum(nums, i, j);
                break;
            }
        }
    }
}

int main()
{
    srand(time(NULL));

    struct timeval s, e;
    gettimeofday(&s, NULL);

    for (int i = 0; i < TIMES; i++)
    {
        int data[SIZE];
        makeRandList(data, SIZE);
        runInsertSort(data, SIZE);
    }

    gettimeofday(&e, NULL);
    printf("time: %lf[sec]\n", (e.tv_sec - s.tv_sec) + (e.tv_usec - s.tv_usec) * 1.0E-6);
    return 0;
}

InsertSort.go

package main

import (
	"fmt"
	"math/rand"
	"time"
)

const TIMES = 10000
const SIZE = 1000

func main() {
	fmt.Println("Insert Sort by using slices")
	BenchFuncSeconds(func() {
		rand.Seed(time.Now().UnixNano())

		for i := 0; i < TIMES; i++ {
			nums := makeRandList(SIZE)
			runInsertSort(nums, moveNumByUsingSlices)
		}
	})

	fmt.Println("Insert Sort")
	BenchFuncSeconds(func() {
		rand.Seed(time.Now().UnixNano())

		for i := 0; i < TIMES; i++ {
			nums := makeRandList(SIZE)
			runInsertSort(nums, moveNum)
		}
	})
}

func BenchFuncSeconds(f func()) {
	st := time.Now()
	f()
	ed := time.Now()

	fmt.Printf("Time %v\n", ed.Sub(st))
}

func makeRandList(size int) []int {
	nums := make([]int, 0, size)
	for j := 0; j < size; j++ {
		nums = append(nums, rand.Intn(100))
	}
	return nums
}

func runInsertSort(nums []int, move func(nums []int, oldPos int, newPos int)) {
	for i := 1; i < len(nums); i++ {
		target := nums[i]
		for j := 0; j < i; j++ {
			if target < nums[j] {
				move(nums, i, j)
				break
			}
		}
	}
}

func moveNumByUsingSlices(nums []int, oldPos int, newPos int) {
	moveData := nums[oldPos]
	nums = append(nums[:oldPos], nums[oldPos + 1:]...)
	nums = append(nums[:newPos + 1], nums[newPos:]...)
	nums[newPos] = moveData
}

func moveNum(nums []int, oldPos int, newPos int) {
	insertData := nums[oldPos]
	for i := oldPos; i > newPos; i-- {
		nums[i] = nums[i - 1]
	}
	nums[newPos] = insertData
}

InsertSort.jl

const TIMES = 10000;
const SIZE = 1000;

makeRandList() = rand(0:100, SIZE)

function moveNum!(nums, oldPos, newPos)
    insertData = nums[oldPos]
    for i in oldPos:-1:(newPos + 1)
        nums[i] = nums[i - 1]
    end
    nums[newPos] = insertData
end

function runInsertSort1!(nums)
    for i in 1:length(nums)
        target = nums[i]
        for j in 1:(i - 1)
            if target < nums[j]
                moveNum!(nums, i, j)
                break
            end
        end
    end
end

function runInsertSort2!(nums)
    for i in 1:length(nums)
        target = nums[i]
        for j in 1:(i - 1)
            if target < nums[j]
                deleteat!(nums, i)
                insert!(nums, j, target)
                break
            end
        end
    end
end

function run1()
    for i in 1:TIMES
        nums = makeRandList()
        runInsertSort1!(nums)
    end
end
function run2()
    for i in 1:TIMES
        nums = makeRandList()
        runInsertSort2!(nums)
    end
end

function main()
    @time run1()
    @time run2()
end

main()

InsertSort.py

import random
import time

TIMES = 10000
SIZE = 1000


def makeRandList(): return [random.randrange(0, 100) for i in range(SIZE)]


def moveNum(nums, oldPos, newPos):
    insertData = nums[oldPos]
    for i in range(oldPos, newPos, -1):
        nums[i] = nums[i - 1]
    nums[newPos] = insertData


def runInsertSort1(nums):
    for i in range(len(nums)):
        target = nums[i]
        for j in range(i):
            if target < nums[j]:
                moveNum(nums, i, j)
                break


def runInsertSort2(nums):
    for i in range(1, len(nums)):
        target = nums[i]
        for j in range(i):
            if target < nums[j]:
                nums.pop(i)
                nums.insert(j, target)
                break


def showTime(func):
    start = time.time()
    func()
    end = time.time()
    print("time: {0}".format(end - start) + "sec")


def runBenchmark1():
    for _ in range(TIMES):
        nums = makeRandList()
        runInsertSort1(nums)


def runBenchmark2():
    for _ in range(TIMES):
        nums = makeRandList()
        runInsertSort2(nums)


showTime(runBenchmark1)
showTime(runBenchmark2)

InsertSort.ts

const TIMES = 10000;
const SIZE = 1000;

function makeRandList() {
  let nums = Array<number>(SIZE);
  for (let i = 0; i < SIZE; i++) {
    nums[i] = Math.floor(Math.random() * 100);
  }
  return nums;
}

function runInsertSort(
  nums: number[],
  move: (nums: number[], oldPos: number, newPos: number) => void
) {
  for (let i = 1; i < nums.length; i++) {
    let target = nums[i];
    for (let j = 0; j < i; j++) {
      if (target < nums[j]) {
        move(nums, i, j);
        break;
      }
    }
  }
}

function moveNumBySplice(nums: number[], oldPos: number, newPos: number) {
  let moveData = nums[oldPos];
  nums.splice(oldPos, 1);
  nums.splice(newPos, 0, moveData);
}

function moveNum(nums: number[], oldPos: number, newPos: number) {
  let insertData = nums[oldPos];
  for (let i = oldPos; i > newPos; i--) {
    nums[i] = nums[i - 1];
  }
  nums[newPos] = insertData;
}

function runBenchmark() {
  console.time('InsertSort (Normal)');
  for (let i = 0; i < TIMES; i++) {
    let nums = makeRandList();
    runInsertSort(nums, moveNum);
  }
  console.timeEnd('InsertSort (Normal)');

  console.time('InsertSort (Splice)');
  for (let i = 0; i < TIMES; i++) {
    let nums = makeRandList();
    runInsertSort(nums, moveNumBySplice);
  }
  console.timeEnd('InsertSort (Splice)');
}

runBenchmark();

実行結果(参考)

10000回実行しても、1秒前後ブレたりするのであくまで参考程度に。

実行環境

MacBook Pro (Retina, 13-inch, Early 2015)
Core i5-5257U, 16GB RAM

C言語

time: 13.066611[sec] (-O2)
time: 2.038166[sec] (-O3)
time: 2.016563[sec] (-Ofast)

Go

Insert Sort by using slices
Time 3.652894683s
Insert Sort
Time 4.701886531s

slice使った方がコピーによるオーバーヘッドが大きいかと思いきやそうでもない…？

Julia

  3.941864 seconds (10.00 k allocations: 77.515 MiB, 0.16% gc time)
  2.480625 seconds (20.00 k allocations: 230.713 MiB, 0.63% gc time)

消して挿入した方が愚直にループで上書きするより速い(メモリはかなり食ってしまうが)

Python

Python 標準処理系

time: 429.25018787384033sec
time: 165.28382420539856sec

PyPy

time: 13.30287218093872sec
time: 10.851818084716797sec

Juliaと同じく

TypeScript

InsertSort (Normal): 7278.898ms
InsertSort (Splice): 9042.718ms

Spliceを使うと明らかに遅い