21

Re: Трохи про оптимізацію

*BRAVO*  *WALL*  *BRAVO*  *WALL*  *BRAVO*  *WALL*
Визнаю себе ідіотом і зобов'язуюся, як матиму час і натхнення, дописати ще варіант на numpy.

Прихований текст

Але все ж прошу мені не "тикати"

Подякували: A.N.Onim1

22

Re: Трохи про оптимізацію

Зробив тести в C++ і в Python3 для масиву розміром 10кк (як і ТС, але виправив те що враховувався час генерації масиву)

Python

All ok!
FindMinMax:
  2.5829478835999993
FindMinMaxCached:
  1.6286650834
FindMinMaxPythonic:
  0.7048105503999992
FindMinMaxFast:
  2.3426939266000004

C++

findMinMaxStd
  0.0313584
findMinMaxCached
  0.0254080
findMinMax
  0.0293312

Різниця на два порядка... якось дофіга. Може хтось має змогу перевірити на PyPy?

Подякували: leofun01, koala, MynameIS_Ros3

23

Re: Трохи про оптимізацію

NumPy

[code=python]import random
import time
import timeit
import numpy as np

def FindMinMax(bigArray):
    minIndex = 0
    maxIndex = 0
    for i in range(len(bigArray)):
        if bigArray[i] > bigArray[maxIndex]:
            maxIndex = i
        if bigArray[i] < bigArray[minIndex]:
            minIndex = i
    return minIndex,bigArray[minIndex],maxIndex,bigArray[maxIndex]

def FindMinMaxCached(bigArray):
    minIndex = 0
    maxIndex = 0
    minValue = bigArray[0]
    maxValue = bigArray[0]
    for i in range(len(bigArray)):
        if bigArray[i] > maxValue:
            maxIndex = i
            maxValue = bigArray[i]
        if bigArray[i] < minValue:
            minIndex = i
            minValue = bigArray[i]
    return minIndex,minValue,maxIndex,maxValue

def FindMinMaxPythonic(bigArray):
    minValue = min(bigArray)
    maxValue = max(bigArray)
    return bigArray.index(minValue), minValue, bigArray.index(maxValue), maxValue

def FindMinMaxFast(bigArray):
    minIndex = min(range(len(bigArray)), key=bigArray.__getitem__)
    maxIndex = max(range(len(bigArray)), key=bigArray.__getitem__)
    return minIndex, bigArray[minIndex], maxIndex, bigArray[maxIndex]

def FindMinMaxNumPy(bigArray):
    minIndex = np.argmin(bigArray)
    maxIndex = np.argmax(bigArray)
    minValue = bigArray[minIndex]
    maxValue = bigArray[maxIndex]
    return minIndex, minValue, maxIndex, maxValue

def genArray(size):
    random.seed()
    return [random.randint(-2000000000, 2000000000) for i in range(size)]


def test():
    bigArray = genArray(1000000)
    r1 = FindMinMax(bigArray)
    r2 = FindMinMaxCached(bigArray)
    r3 = FindMinMaxPythonic(bigArray)
    r4 = FindMinMaxFast(bigArray)
    r5 = FindMinMaxNumPy(bigArray)
    if r1 == r2 == r3 == r4 == r5:
        print("All ok!")
    else:
        print(r1,r2,r3,r4,"not equal!")

test()

sampleArray = genArray(10000000)

def callTimeit(func):
    print(func+':')
    print('  ', timeit.timeit(func+'(sampleArray)', 'from __main__ import sampleArray,'+func, time.process_time, 5)/5)

for func in ['FindMinMaxNumPy', 'FindMinMax', 'FindMinMaxCached', 'FindMinMaxPythonic', 'FindMinMaxFast']:
    callTimeit(func)[/code]

Результати

All ok!
FindMinMaxNumPy:
   3.4724071652
FindMinMax:
   2.3258506204
FindMinMaxCached:
   1.8022502906000013
FindMinMaxPythonic:
   1.1550818297999996
FindMinMaxFast:
   2.3675598256

Що я роблю не так?

Подякували: koala1

24

Re: Трохи про оптимізацію

Go навіть плюси взуває

Прихований текст
package main

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


func arrayMaxMinLoop(bigArray []int) (int, int, int, int) {
    minIndex := 0
    maxIndex := 0
    minValue := bigArray[0]
    maxValue := bigArray[0]

    for i, _ := range bigArray {

        if bigArray[i] > maxValue {
            maxIndex = i
            maxValue = bigArray[i]
        }

        if bigArray[i] < minValue{
            minIndex = i
            minValue = bigArray[i]
        }
    }

    return minIndex,minValue,maxIndex,maxValue
}


func run_test(array []int){
    arrayMaxMinLoop(array)
}


func BenchmarkMinMax(b *testing.B) {
    rand.Seed(time.Now().UnixNano())
    var count = 1000000
    var array = make([]int, count)

    for i := 0; i < count; i++ {
        array[i] = rand.Int()
    }

    b.ResetTimer()
    for n := 0; n < b.N; n++ {
           run_test(array)
    }
}

go test -bench=. показав:
BenchmarkMinMax-4        1000       1679301 ns/op

0.001679301 сек товариші :)