# how to implement a really efficient bitvector sorting in python

Filed under:
|
|
|
##### bitvector

Hello guys!

Actually this is an interesting topic from programming pearls, sorting 10 digits telephone numbers in a limited memory with an efficient algorithm. You can find the whole story here

What I am interested in is just how fast the implementation could be in python. I have done a naive implementation with the module bitvector. The code is as following:

``````from BitVector import BitVector
import timeit
import random
import time
import sys

def sort(input_li):
return sorted(input_li)

def vec_sort(input_li):
bv = BitVector( size = len(input_li) )
for i in input_li:
bv[i] = 1

res_li = []
for i in range(len(bv)):
if bv[i]:
res_li.append(i)

return res_li

if __name__ == "__main__":
test_data = range(int(sys.argv[1]))
print 'test_data size is:', sys.argv[1]
random.shuffle(test_data)

start = time.time()
sort(test_data)
elapsed = (time.time() - start)
print "sort function takes " + str(elapsed)
start = time.time()
vec_sort(test_data)
elapsed = (time.time() - start)
print "sort function takes " + str(elapsed)
start = time.time()
vec_sort(test_data)
elapsed = (time.time() - start)
print "vec_sort function takes " + str(elapsed)
``````

I have tested from array size 100 to 10,000,000 in my macbook(2GHz Intel Core 2 Duo 2GB SDRAM), the result is as following:

• test_data size is: 1000
• sort function takes 0.000274896621704
• vec_sort function takes 0.00383687019348

• test_data size is: 10000

• sort function takes 0.00380706787109
• vec_sort function takes 0.0371489524841

• test_data size is: 100000

• sort function takes 0.0520560741425
• vec_sort function takes 0.374383926392

• test_data size is: 1000000

• sort function takes 0.867373943329
• vec_sort function takes 3.80475401878

• test_data size is: 10000000

• sort function takes 12.9204008579
• vec_sort function takes 38.8053860664

What disappoints me is that even when the test_data size is 100,000,000, the sort function is still faster than vec_sort. Is there any way to accelerate the vec_sort function?

© Stack Overflow or respective owner

• #### unmet dependencies in Ubuntu 12.04

I tried today to install a dvb-card on my Ubuntu 12.04 (Linux blauhai-linux 3.2.0-25-generic #40-Ubuntu SMP Wed May 23 20:30:51 UTC 2012 x86_64 x86_64 x86_64 GNU/Linux ). The installation failed with an error. After that, i tried to install python (it was already installed but i got this error): linux:~\$… >>> More

• #### How can I get sikuli-ide to work?

I installed sikuli-ide with sudo apt-get install sikuli-ide Everything was fine until I tried to start it from the terminal. I typed sikuli-ide But the only response I got was [info] locale: en_US The application was not started, furthermore there is no desktop file and sikuli-ide does not… >>> More

• #### Getting PATH right for python after MacPorts install

as seen on Super User - Search for 'Super User'
I can't import some python libraries (PIL, psycopg2) that I just installed with MacPorts. I looked through these forums, and tried to adjust my PATH variable in \$HOME/.bash_profile in order to fix this but it did not work. I added the location of PIL and psycopg2 to PATH. I know that Terminal is… >>> More

• #### call python with system() in R to run a python script emulating the python console

as seen on Stack Overflow - Search for 'Stack Overflow'
I want to pass a chunk of Python code to Python in R with something like system('python ...'), and I'm wondering if there is an easy way to emulate the python console in this case. For example, suppose the code is "print 'hello world'", how can I get the output like this in R? >>> print… >>> More

• #### Python - Calling a non python program from python?

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I am currently struggling to call a non python program from a python script. I have a ~1000 files that when passed through this C++ program will generate ~1000 outputs. Each output file must have a distinct name. The command I wish to run is of the form: program_name -input -output -o1 -o2… >>> More

• #### Jpeg Algorithm vs BMP Algorithm?

as seen on Super User - Search for 'Super User'
I'm just wonder, what the differences are between creating a BMP file algorithm and JPG file algorithm ? If you know the others images' format algorithm, please post them. Thanks. >>> More

• #### word disambiguation algorithm (Lesk algorithm)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hii.. Can anybody help me to find an algorithm in Java code to find synonyms of a search word based on the context and I want to implement the algorithm with WordNet database. For example, "I am running a Java program". From the context, I want to find the synonyms for the word "running", but the… >>> More

• #### Search algorithm (with a sort algorithm already implemented)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, Im doing a Java application and Im facing some doubts in which concerns performance. I have a PriorityQueue which guarantees me the element removed is the one with greater priority. That PriorityQueue has instances of class Event (which implements Comparable interface). Each Event is associated… >>> More

• #### Is there any algorithm for finding LINES by PIXEL COLORS on picture?

as seen on Stack Overflow - Search for 'Stack Overflow'
So I have Image like this I want to get something like this (I hevent drawn all lines I want but I hope you can get my idea) I need algorithm for finding all straight lines on it by just reading colors of pixels. No hard math, no Haar, no Hough. Some algorithm which would be based on points… >>> More

• #### collsion issues with quadtree [on hold]

as seen on Game Development - Search for 'Game Development'
So i implemented a Quad tree in Java for my 2D game and everything works fine except for when i run my collision detection algorithm, which checks if a object has hit another object and which side it hit.My problem is 80% of the time the collision algorithm works but sometimes the objects just go… >>> More