Higher-performance method do this type of insert from python?

Question

Given two arrays hashes and table, for each value in hashes I want to store the position of the element at the element's value's offset in the array table. Here is the naïve algorithm:

def insert_n(table,hashes): for x in xrange(len(hashes)): table[hashes[x]]=x

This is extremely slow. Psyco helps some here, but hardly.

Numpy has a solution:

numpy.insert(table,numpy.arange(len(hashes)),hashes)

But according to my benchmarks, this is still extremely slow for such a simple operation. Is there a faster way to perform this that can be used from python?

Some additional example code:

import numpy from time import time table_size=2**20 hashes_size=2**19 table=numpy.zeros(table_size,dtype=numpy.uint32) hashes=numpy.fromstring(numpy.random.bytes((hashes_size)*4), dtype=numpy.uint32)%table_size t0=time() numpy.insert(table,numpy.arange(len(hashes)),hashes) print time()-t0

You're aware that if there are multiple instances of one hash, then the table will point to the last one only? — Tor Valamo
– Tor Valamo, Commented Dec 15, 2009 at 15:26
Yes, it's for a type of caching system where it's perfectly fine to trade off the higher speed for losing some of the values due to collision. Newer entries will assumed to be more probable cache hits anyway. — user213060
– user213060, Commented Dec 15, 2009 at 16:32
What is up with the edits on this question, and why don't you accept answers, OP? — Roman
– Roman, Commented Jan 10, 2010 at 18:28

interjay · Accepted Answer · 2009-12-15 19:12:23Z

This is fast and simple (assuming table and hashes are numpy.uint32 arrays):

table[hashes] = numpy.arange(len(hashes), dtype=numpy.uint32)

You may want to compare the speed with this:

table[hashes] = xrange(len(hashes))

By the way, numpy.insert does not do the same thing as the for-loop you posted.

Completely right, I was using insert when I meant to use put (which is equivalent to your slicing assignment.) You got it.

Collectives™ on Stack Overflow

Higher-performance method do this type of insert from python?

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related