1. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2003
Posts
35
Rep Power
15

Ordered arrays

Is there a property I can set on an array so that it always maintains order? For example, if I had the array [0, 2, 3, 4, 5, ... 9999], and I happen to insert '1' could it automagically put 1 between 0 and 2? I could write code to traverse the array one element at a time until I find the correct index to insert at, and call insert on that index, but that's still somewhat inefficient because it's written in Python. Now before you flame me for that comment, I'm looking for a built-in property or function of Python because it would be written in C (aren't all underlying internals of Python written in C?), which would be faster than the Python solution I proposed, that's all.

If not, I'll search-and-insert myself. Thanks!

-theperfectsoup
2. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2002
Posts
89
Rep Power
16
>>> a = [0,2,3,4,5,6,7]
>>> a.append(1)
>>> a
[0, 2, 3, 4, 5, 6, 7, 1]
>>> a.sort()
>>> a
[0, 1, 2, 3, 4, 5, 6, 7]
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2003
Posts
35
Rep Power
15
Originally posted by jimmy2k1
>>> a = [0,2,3,4,5,6,7]
>>> a.append(1)
>>> a
[0, 2, 3, 4, 5, 6, 7, 1]
>>> a.sort()
>>> a
[0, 1, 2, 3, 4, 5, 6, 7]

I know I could do this, but if the array has tens of thousands of elements (as mine does), the overhead of calling the sort function to order the entire array -- just to insert one new value -- is impractical. With thousands of elements, in this case, iterating to the first element would require just one step, and inserting another step, while forcing a sort could be on the order of n*logn, depending on how arrays are implemented.

Although the sort function called above is implemented in C, so the performance hit might not be too unbearable... Hrmmm...

-theperfectsoup
4. Python built-in's should be writen in C yes. The Python team is currently working on making all built-in types classes (started in 2.2) but I believe this is still be done in C.. it seems silly for them not to be.

http://www.python.org/2.2.3/descrintro.html

Just for referance Sort works with aphabetical char's and strings aswell as alphanumeric (as 2k showed).

>>> l = ['ruby', 'perl', 'lua', 'python', 'php']
>>> l
['ruby', 'perl', 'lua', 'python', 'php']
>>> l.sort()
>>> l
['lua', 'perl', 'php', 'python', 'ruby']
>>>

You can also pass your own compare functions to sort!

Mark.
Last edited by netytan; August 14th, 2003 at 10:24 AM.
5. If you have so many results then it even C would take time to handle it. I've read there have been cases where programs have expericanced a speed increase after being rewritten in Python (I'm not sure of the details though) . If sort is to slow for you then you could try..

Storing lists of a specifide length - say 1000 - inside a dictionary. This would make is simple to access a small number of results at a time. Assuming your working with numbers then you could have a dictionary like this.

{'0000-1000': ['numbers', 'up', 'to', '1000'], '1000-2000': ['numbers', 'up', 'to', '2000']}

This is just one approch but it would work considerably faster than using sort on a list of 1,000,000 number, simply because by using this method, sort can be applied to a smaller number or elements

Hope this makes sence,

Mark.
6. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2002
Posts
89
Rep Power
16
if you want to speed up your code, you can try using Psyco or Boost and anything else meant to speed up Python code. I've never used them but I hear they can give you a significant speed-up.
7. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2003
Location
Alexandria, VA
Posts
5
Rep Power
0
This is one of those situations where you know that someone, somewhere _must_ have solved the problem already. I did a little poking around and discovered the bisect module. I'm pretty sure this is exactly what you're looking for. Much, much more efficient than resorting after every insert. Check out the documentation here:

http://www.python.org/doc/current/li...le-bisect.html
8. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2003
Posts
35
Rep Power
15
FiveGrainJa, you are my hero. I was looking for this, a sort of binary-search routine for finding the correct insertion point, but came up empty handed. Guess I should have combed the library reference more carefully...

Thanks again!
-theperfectsoup