Hi All, On Fri, May 23, 2008 at 4:50 PM, Andrea Gavana wrote: > Hi Peter & All, > > On Fri, May 23, 2008 at 4:16 PM, Peter Creasey wrote: >> Hi Andrea, >> >> 2008/5/23 "Andrea Gavana" <[EMAIL PROTECTED]>: >>> And so on. The probelm with this approach is that I lose the original >>> indices for which I want all the inequality tests to succeed: >> >> To have the original indices you just need to re-index your indices, as it >> were >> >> idx = flatnonzero(xCent >= xMin) >> idx = idx[flatnonzero(xCent[idx] <= xMax)] >> idx = idx[flatnonzero(yCent[idx] >= yMin)] >> idx = idx[flatnonzero(yCent[idx] <= yMax)] >> ... >> (I haven't tested this code, apologies for bugs) >> >> However, there is a performance penalty for doing all this re-indexing >> (I once fell afoul of this), and if these conditions "mostly" evaluate >> to True you can often be better off with one of the solutions already >> suggested. > > Thank you for your answer. I have tried your suggestion, and the > performances are more or less comparable with the other NumPy > implementations (yours is roughly 1.2 times slower than the others), > but I do gain some advantage when the subgrids are very small (i.e., > most of the values in the first array are already False). I'll go and > implement your solution when I have many small subgrids in my model.
I have added a few more implementations for this issue. One think that
stroke me was that I could actually use sorted arrays for my xCent,
yCent and zCent vectors, so I came up with a solution which uses
numpy.searchsorted but the speed is more or less as it was without
sorting. The specific function is this:
def MultipleBoolean13():
""" Numpy solution 5 (Andrea). """
searchsorted = numpy.searchsorted
indxStart, indxEnd = searchsorted(xCentS, [xMin, xMax])
indyStart, indyEnd = searchsorted(yCentS, [yMin, yMax])
indzStart, indzEnd = searchsorted(zCentS, [zMin, zMax])
xInd = numpy.zeros((nCells), dtype=numpy.bool)
yInd = xInd.copy()
zInd = xInd.copy()
xInd[xIndices[indxStart:indxEnd]] = True
yInd[yIndices[indyStart:indyEnd]] = True
zInd[zIndices[indzStart:indzEnd]] = True
xyzReq = numpy.nonzero(xInd & yInd & zInd)[0]
Where xCentS, yCentS and zCentS are the sorted arrays. I don't see any
easy way to optimize this method, so I'd like to know if it is
possible to code it better than I did. I have done some testing and
timings of all the solutions we came up until now (12
implementations), and this is what I get (please notice the nice work
or ascii art :-D :-D ):
*******************
* SUMMARY RESULTS *
*******************
---------------------------------------------------------------------
Number Of Cells: 50000
---------------------------------------------------------------------
| Rank | Method Name | Execution Time | Relative Slowness |
---------------------------------------------------------------------
1 NumPy 5 (Andrea) 0.00562803 1.00000
2 NumPy 1 (Francesc) 0.00563365 1.00100
3 NumPy 2 (Nathan) 0.00577322 1.02580
4 NumPy 4 (Nathan-Vector) 0.00580577 1.03158
5 Fortran 6 (James) 0.00660514 1.17361
6 Fortran 3 (Alex) 0.00709856 1.26129
7 Fortran 5 (James) 0.00748726 1.33035
8 Fortran 2 (Mine) 0.00748816 1.33051
9 Fortran 1 (Mine) 0.00775906 1.37864
10 Fortran 4 {Michael) 0.00777685 1.38181
11 NumPy 3 (Peter) 0.01253662 2.22753
12 Cython (Stefan) 0.01597804 2.83901
---------------------------------------------------------------------
---------------------------------------------------------------------
Number Of Cells: 100000
---------------------------------------------------------------------
| Rank | Method Name | Execution Time | Relative Slowness |
---------------------------------------------------------------------
1 NumPy 5 (Andrea) 0.01080372 1.00000
2 NumPy 2 (Nathan) 0.01109147 1.02663
3 NumPy 1 (Francesc) 0.01114189 1.03130
4 NumPy 4 (Nathan-Vector) 0.01214118 1.12380
5 Fortran 6 (James) 0.01351264 1.25074
6 Fortran 5 (James) 0.01368450 1.26665
7 Fortran 3 (Alex) 0.01373010 1.27087
8 Fortran 2 (Mine) 0.01415306 1.31002
9 Fortran 1 (Mine) 0.01425558 1.31951
10 Fortran 4 {Michael) 0.01443192 1.33583
11 NumPy 3 (Peter) 0.02463268 2.28002
12 Cython (Stefan) 0.04298108 3.97836
---------------------------------------------------------------------
---------------------------------------------------------------------
Number Of Cells: 150000
---------------------------------------------------------------------
| Rank | Method Name | Execution Time | Relative Slowness |
---------------------------------------------------------------------
1 NumPy 1 (Francesc) 0.01613255 1.00000
2 NumPy 5 (Andrea) 0.01619734 1.00402
3 NumPy 2 (Nathan) 0.01647855 1.02145
4 NumPy 4 (Nathan-Vector) 0.01779452 1.10302
5 Fortran 3 (Alex) 0.02064676 1.27982
6 Fortran 2 (Mine) 0.02382278 1.47669
7 Fortran 4 {Michael) 0.02404563 1.49050
8 Fortran 5 (James) 0.02734487 1.69501
9 Fortran 6 (James) 0.02762538 1.71240
10 Fortran 1 (Mine) 0.03028402 1.87720
11 NumPy 3 (Peter) 0.03625735 2.24746
12 Cython (Stefan) 0.07515276 4.65845
---------------------------------------------------------------------
---------------------------------------------------------------------
Number Of Cells: 200000
---------------------------------------------------------------------
| Rank | Method Name | Execution Time | Relative Slowness |
---------------------------------------------------------------------
1 NumPy 5 (Andrea) 0.02187359 1.00000
2 NumPy 1 (Francesc) 0.02309221 1.05571
3 NumPy 2 (Nathan) 0.02323452 1.06222
4 NumPy 4 (Nathan-Vector) 0.02378610 1.08743
5 Fortran 3 (Alex) 0.02792134 1.27649
6 Fortran 2 (Mine) 0.03119301 1.42606
7 Fortran 4 {Michael) 0.03221007 1.47256
8 Fortran 5 (James) 0.03584257 1.63862
9 Fortran 6 (James) 0.03627464 1.65838
10 Fortran 1 (Mine) 0.04048422 1.85083
11 NumPy 3 (Peter) 0.04765184 2.17851
12 Cython (Stefan) 0.09927396 4.53853
---------------------------------------------------------------------
---------------------------------------------------------------------
Number Of Cells: 250000
---------------------------------------------------------------------
| Rank | Method Name | Execution Time | Relative Slowness |
---------------------------------------------------------------------
1 NumPy 5 (Andrea) 0.02651608 1.00000
2 NumPy 1 (Francesc) 0.02864898 1.08044
3 NumPy 2 (Nathan) 0.02933160 1.10618
4 NumPy 4 (Nathan-Vector) 0.02960466 1.11648
5 Fortran 3 (Alex) 0.03427299 1.29254
6 Fortran 2 (Mine) 0.03848291 1.45130
7 Fortran 4 {Michael) 0.03919467 1.47815
8 Fortran 6 (James) 0.04430585 1.67091
9 Fortran 5 (James) 0.04765620 1.79726
10 Fortran 1 (Mine) 0.04914228 1.85330
11 NumPy 3 (Peter) 0.05981760 2.25590
12 Cython (Stefan) 0.12797177 4.82619
---------------------------------------------------------------------
---------------------------------------------------------------------
Number Of Cells: 300000
---------------------------------------------------------------------
| Rank | Method Name | Execution Time | Relative Slowness |
---------------------------------------------------------------------
1 NumPy 5 (Andrea) 0.03365729 1.00000
2 NumPy 1 (Francesc) 0.03470315 1.03107
3 NumPy 2 (Nathan) 0.03519601 1.04572
4 NumPy 4 (Nathan-Vector) 0.03529574 1.04868
5 Fortran 3 (Alex) 0.04167365 1.23818
6 Fortran 2 (Mine) 0.04653522 1.38262
7 Fortran 4 {Michael) 0.04711222 1.39976
8 Fortran 6 (James) 0.05287650 1.57103
9 Fortran 5 (James) 0.05686667 1.68958
10 Fortran 1 (Mine) 0.05913682 1.75703
11 NumPy 3 (Peter) 0.07183072 2.13418
12 Cython (Stefan) 0.15876811 4.71720
---------------------------------------------------------------------
******************************
* ELAPSED TIME: 64.828 Seconds *
******************************
Just in case someone is interested in it, I attach the source code of
the implementations I have so far. Thank you vey much for your
suggestions!
Andrea.
"Imagination Is The Only Weapon In The War Against Reality."
http://xoomer.alice.it/infinity77/
# Begin Code
import time
import numpy
from timeit import Timer
# FORTRAN modules
from MultipleBooleanFortran import multipleboolean3, multipleboolean4
from MultipleBooleanFortran import multipleboolean7, multipleboolean8
from MultipleBooleanFortran import multipleboolean10, multipleboolean11
# Cython implementation
from MultipleBooleanCython import multipleboolean6
# Define some constraints for X, Y, Z (constants all over the tests)
xMin, xMax = 250.0, 700.0
yMin, yMax = 1000.0, 1900.0
zMin, zMax = 120.0, 300.0
# And a couple of vectors to hold them (needed by a Fortran solution)
xyzMin = [xMin, yMin, zMin]
xyzMax = [xMax, yMax, zMax]
def MultipleBoolean2():
""" Numpy solution 1 (Francesc). """
xyzReq = (xCent >= xMin) & (xCent <= xMax) & \
(yCent >= yMin) & (yCent <= yMax) & \
(zCent >= zMin) & (zCent <= zMax)
xyzReq = numpy.nonzero(xyzReq)[0]
def MultipleBoolean3():
""" Fortran solution 1 (Mine). """
xyzReq = multipleboolean3(xCent, yCent, zCent, xMin, xMax, yMin, yMax,
zMin, zMax, nCells)
xyzReq = numpy.nonzero(xyzReq)[0]
def MultipleBoolean4():
""" Fortran solution 2 (Mine). """
xyzReq = multipleboolean4(xCent, yCent, zCent, xMin, xMax, yMin, yMax,
zMin, zMax, nCells)
xyzReq = numpy.nonzero(xyzReq)[0]
def MultipleBoolean5():
""" Numpy solution 2 (Nathan). """
xyzReq = (xCent >= xMin)
xyzReq &= (xCent <= xMax)
xyzReq &= (yCent >= yMin)
xyzReq &= (yCent <= yMax)
xyzReq &= (zCent >= zMin)
xyzReq &= (zCent <= zMax)
xyzReq = numpy.nonzero(xyzReq)[0]
def MultipleBoolean6():
""" Cython solution (Stefan). """
xyzReq = multipleboolean6(xCent, xMin, xMax, yCent, yMin, yMax, zCent,
zMin, zMax)
xyzReq = numpy.nonzero(xyzReq)[0]
def MultipleBoolean7():
""" Fortran solution 3 (Alex). """
xyzReq = multipleboolean7(xyzCent, xyzMin, xyzMax, nCells)
xyzReq = numpy.nonzero(xyzReq)[0]
def MultipleBoolean8():
""" Fortran solution 4 (Michael). """
xyzReq = multipleboolean8(xCent, yCent, zCent, xMin, xMax, yMin, yMax,
zMin, zMax, nCells)
xyzReq = numpy.nonzero(xyzReq)[0]
def MultipleBoolean9():
""" Numpy solution 3 (Peter) . """
flatnonzero = numpy.flatnonzero
idx = flatnonzero(xCent >= xMin)
idx = idx[flatnonzero(xCent[idx] <= xMax)]
idx = idx[flatnonzero(yCent[idx] >= yMin)]
idx = idx[flatnonzero(yCent[idx] <= yMax)]
idx = idx[flatnonzero(zCent[idx] >= zMin)]
idx = idx[flatnonzero(zCent[idx] <= zMax)]
def MultipleBoolean10():
""" Fortran solution 5 (Michael). """
xyzReq = multipleboolean10(xCent, yCent, zCent, xMin, xMax, yMin, yMax,
zMin, zMax, nCells)
xyzReq = numpy.nonzero(xyzReq)[0]
def MultipleBoolean11():
""" Fortran solution 6 (Michael). """
xyzReq = multipleboolean11(xCent, yCent, zCent, xMin, xMax, yMin, yMax,
zMin, zMax, nCells)
xyzReq = numpy.nonzero(xyzReq)[0]
def MultipleBoolean12():
""" Numpy solution 3 (Nathan). """
xyzReq = (xyzCent2[0, :] >= xyzMin[0])
xyzReq &= (xyzCent2[0, :] <= xyzMax[0])
xyzReq &= (xyzCent2[1, :] >= xyzMin[1])
xyzReq &= (xyzCent2[1, :] <= xyzMax[1])
xyzReq &= (xyzCent2[2, :] >= xyzMin[2])
xyzReq &= (xyzCent2[2, :] <= xyzMax[2])
xyzReq = numpy.nonzero(xyzReq)[0]
def MultipleBoolean13():
""" Numpy solution 5 (Andrea). """
searchsorted = numpy.searchsorted
indxStart, indxEnd = searchsorted(xCentS, [xMin, xMax])
indyStart, indyEnd = searchsorted(yCentS, [yMin, yMax])
indzStart, indzEnd = searchsorted(zCentS, [zMin, zMax])
xInd = numpy.zeros((nCells), dtype=numpy.bool)
yInd = xInd.copy()
zInd = xInd.copy()
xInd[xIndices[indxStart:indxEnd]] = True
yInd[yIndices[indyStart:indyEnd]] = True
zInd[zIndices[indzStart:indzEnd]] = True
xyzReq = numpy.nonzero(xInd & yInd & zInd)[0]
def intersect(a, b):
""" return the intersection of two lists """
return list(set(a) & set(b))
def GenerateInputs(nCells):
# Generate random centroids for the cells
xCent = 1000.0*numpy.random.rand(nCells)
yCent = 2500.0*numpy.random.rand(nCells)
zCent = 400.0*numpy.random.rand(nCells)
# These are needed for multipleboolean7 and multipleboolean8
xyzCent = numpy.empty((nCells, 3))
xyzCent[:, 0] = xCent
xyzCent[:, 1] = yCent
xyzCent[:, 2] = zCent
xyzCent2 = numpy.empty((3, nCells))
xyzCent2[0, :] = xCent
xyzCent2[1, :] = yCent
xyzCent2[2, :] = zCent
indices = range(len(xCent))
xCentSorted = xCent.copy()
xCentSorted = zip(xCentSorted, indices)
xCentSorted = sorted(xCentSorted)
yCentSorted = yCent.copy()
yCentSorted = zip(yCentSorted, indices)
yCentSorted = sorted(yCentSorted)
zCentSorted = zCent.copy()
zCentSorted = zip(zCentSorted, indices)
zCentSorted = sorted(zCentSorted)
ravel = numpy.ravel
xCentS, xIndices = ravel([x[0] for x in xCentSorted]), ravel([x[1] for x in
xCentSorted])
yCentS, yIndices = ravel([y[0] for y in yCentSorted]), ravel([y[1] for y in
yCentSorted])
zCentS, zIndices = ravel([z[0] for z in zCentSorted]), ravel([z[1] for z in
zCentSorted])
return xCent, yCent, zCent, xyzCent, xyzCent2, xCentS, yCentS, zCentS,
xIndices, yIndices, zIndices
def FormatTime(timerDict):
methodNames = ["NumPy 1 (Francesc)", "NumPy 2 (Nathan)", "Cython (Stefan)",
"Fortran 1 (Mine)", "Fortran 2 (Mine)", "Fortran 3 (Alex)",
"Fortran 4 {Michael)", "NumPy 3 (Peter)", "Fortran 5
(James)",
"Fortran 6 (James)", "NumPy 4 (Nathan-Vector)", "NumPy 5
(Andrea)"]
nCells = timerDict.keys()
nCells.sort()
print "\n\n"
print "*"*19
print "* SUMMARY RESULTS *"
print "*"*19, "\n"
topText = "| Rank | Method Name | Execution Time | Relative
Slowness |"
separator = "-"*len(topText)
maxLen = max([len(text) for text in methodNames])
for cells in nCells:
print separator
print ("Number Of Cells: %d "%cells).center(len(topText))
print separator
print topText
print separator
ranking = sorted(timerDict[cells])
maxSpeed = ranking[0][0]
counter = 1
for timer, methodNumber in ranking:
name = methodNames[methodNumber]
print "%4d %s %0.8f %0.5f"% \
(counter, name.center(maxLen), timer, timer/maxSpeed)
counter += 1
print separator
print
print
timerDict = {}
repeat = 10
startTime = time.time()
for nCells in xrange(50000, 350000, 50000):
xCent, yCent, zCent, xyzCent, xyzCent2, xCentS, yCentS, zCentS, xIndices,
yIndices, zIndices = GenerateInputs(nCells)
t = Timer("MultipleBoolean2()", "from __main__ import MultipleBoolean2")
t1 = t.timeit(number=repeat)/repeat
t = Timer("MultipleBoolean5()", "from __main__ import MultipleBoolean5")
t2 = t.timeit(number=repeat)/repeat
t = Timer("MultipleBoolean6()", "from __main__ import MultipleBoolean6")
t3 = t.timeit(number=repeat)/repeat
t = Timer("MultipleBoolean3()", "from __main__ import MultipleBoolean3")
t4 = t.timeit(number=repeat)/repeat
t = Timer("MultipleBoolean4()", "from __main__ import MultipleBoolean4")
t5 = t.timeit(number=repeat)/repeat
t = Timer("MultipleBoolean7()", "from __main__ import MultipleBoolean7")
t6 = t.timeit(number=repeat)/repeat
t = Timer("MultipleBoolean8()", "from __main__ import MultipleBoolean8")
t7 = t.timeit(number=repeat)/repeat
t = Timer("MultipleBoolean9()", "from __main__ import MultipleBoolean9")
t8 = t.timeit(number=repeat)/repeat
t = Timer("MultipleBoolean10()", "from __main__ import MultipleBoolean10")
t9 = t.timeit(number=repeat)/repeat
t = Timer("MultipleBoolean11()", "from __main__ import MultipleBoolean11")
t10 = t.timeit(number=repeat)/repeat
t = Timer("MultipleBoolean12()", "from __main__ import MultipleBoolean12")
t11 = t.timeit(number=repeat)/repeat
t = Timer("MultipleBoolean13()", "from __main__ import MultipleBoolean13")
t12 = t.timeit(number=repeat)/repeat
timerDict[nCells] = [(t1, 0), (t2, 1), (t3, 2), (t4, 3),
(t5, 4), (t6, 5), (t7, 6), (t8, 7),
(t9, 8), (t10, 9), (t11, 10), (t12, 11)]
FormatTime(timerDict)
print "*"*30
print "* ELAPSED TIME: %0.5g Seconds *"%(time.time() - startTime)
print "*"*30, "\n\n"
# End Code
MultipleBooleanCython.pyx
Description: Binary data
numpy.pxi
Description: Binary data
python.pxi
Description: Binary data
MultipleBooleanFortran.f90
Description: Binary data
_______________________________________________ Numpy-discussion mailing list Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
