Thread: Ordered arrays

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

    Join Date
    Jul 2003
    Posts
    35
    Rep Power
    12

    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. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2002
    Posts
    89
    Rep Power
    13
    >>> 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]
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    35
    Rep Power
    12
    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]
    Thanks for your response, jimmy2k1.

    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
  6. #4
  7. Hello World :)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Mar 2003
    Location
    Hull, UK
    Posts
    2,537
    Rep Power
    69
    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.
  8. #5
  9. Hello World :)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Mar 2003
    Location
    Hull, UK
    Posts
    2,537
    Rep Power
    69
    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.
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2002
    Posts
    89
    Rep Power
    13
    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.
  12. #7
  13. 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
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    35
    Rep Power
    12
    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

IMN logo majestic logo threadwatch logo seochat tools logo