Finding the insertion point in a list

**Matimus** · Mar 16 '07, 06:25 PM

Re: Finding the insertion point in a list

You might look at the bisect module (part of the standard
distribution).

**kyosohma@gmail.com** · Mar 16 '07, 06:45 PM

Re: Finding the insertion point in a list

On Mar 16, 12:59 pm, tkp...@hotmail. com wrote:

I have an ordered list e.g. x = [0, 100, 200, 1000], and given any
positive integer y, I want to determine its appropriate position in
the list (i.e the point at which I would have to insert it in order to
keep the list sorted. I can clearly do this with a series of if
statements:
>
if y<x[1]:
n = 0
elif y < x[2]:
n = 1
elif y < x[3]:
n = 2
else:
n = 3
>
Or with a generator comprehension
n = sum ( y>x[i] for i in range(len(x)) ) - 1
>
But there has to be a cleaner way, as the first approach is unwieldy
and does not adapt to changing list lengths, and the second is not
obvious to a casual reader of the code.
>
My list will typically have 2 to 5 items, so speed is not a huge
issue. I'd appreciate your guidance.
>
Sincerely
>
Thomas Philips

One way to do this would be to use the cmp built-in and loop over the
items in the list. Maybe something like this:

x = [0, 100, 200, 1000]
numLst = len(x)
count = 0
for i in range(numLst):
resultOfCmp = cmp(newNum, x[count])
if resultOfCmp == -1:
print i
x.insert(count, newNum)
break
count += 1

# Where newNum is the one to be inserted.

It's a hack, but it might get the ol' creative juices flowing.

Mike

**Paul McGuire** · Mar 16 '07, 07:35 PM

Re: Finding the insertion point in a list

On Mar 16, 12:59 pm, tkp...@hotmail. com wrote:

I have an ordered list e.g. x = [0, 100, 200, 1000], and given any
positive integer y, I want to determine its appropriate position in
the list (i.e the point at which I would have to insert it in order to
keep the list sorted. I can clearly do this with a series of if
statements:
>
if y<x[1]:
n = 0
elif y < x[2]:
n = 1
elif y < x[3]:
n = 2
else:
n = 3
>
Or with a generator comprehension
n = sum ( y>x[i] for i in range(len(x)) ) - 1
>
But there has to be a cleaner way, as the first approach is unwieldy
and does not adapt to changing list lengths, and the second is not
obvious to a casual reader of the code.
>
My list will typically have 2 to 5 items, so speed is not a huge
issue. I'd appreciate your guidance.
>
Sincerely
>
Thomas Philips

List "will typically have 2 to 5 items"? Keep it simple!

x.append(y)
x.sort()

-- Paul

**kyosohma@gmail.com** · Mar 16 '07, 07:45 PM

Re: Finding the insertion point in a list

On Mar 16, 2:32 pm, "Paul McGuire" <p...@austin.rr .comwrote:

On Mar 16, 12:59 pm, tkp...@hotmail. com wrote:
>
>
>

I have an ordered list e.g. x = [0, 100, 200, 1000], and given any
positive integer y, I want to determine its appropriate position in
the list (i.e the point at which I would have to insert it in order to
keep the list sorted. I can clearly do this with a series of if
statements:

>

if y<x[1]:
n = 0
elif y < x[2]:
n = 1
elif y < x[3]:
n = 2
else:
n = 3

>

Or with a generator comprehension
n = sum ( y>x[i] for i in range(len(x)) ) - 1

>

But there has to be a cleaner way, as the first approach is unwieldy
and does not adapt to changing list lengths, and the second is not
obvious to a casual reader of the code.

>

My list will typically have 2 to 5 items, so speed is not a huge
issue. I'd appreciate your guidance.

>

Sincerely

>

Thomas Philips

>
List "will typically have 2 to 5 items"? Keep it simple!
>
x.append(y)
x.sort()
>
-- Paul

I thought doing an append and sort was a good idea too, but the
question entailed knowing the insertion point, so I skipped it.
Thanks!

**7stud** · Mar 16 '07, 08:15 PM

Re: Finding the insertion point in a list

How about:

-----------
x = [0, 100, 200, 1000]
y = -1
inserted = False

for i in range(len(x)):
if(y <= x[i]):
x.insert(i, y)
inserted = True
break
if(not inserted): x.append(y)

print x
------------

**Matimus** · Mar 16 '07, 08:35 PM

Re: Finding the insertion point in a list

On Mar 16, 11:20 am, "Matimus" <mccre...@gmail .comwrote:

You might look at the bisect module (part of the standard
distribution).

Here is an example:

>>from bisect import insort
>>x = [0,100,200,1000]
>>insort(x,10 )
>>x

[0, 10, 100, 200, 1000]

**tobiaskk@mac.com** · Mar 16 '07, 08:55 PM

Re: Finding the insertion point in a list

Or like this:

x = [0, 100, 200, 1000]
y = 435
for n, i in enumerate(x):
if y < i:
n = n - 1
break
x.insert(n + 1, y)

If you decide to stick with

n = sum ( y>x[i] for i in range(len(x)) ) - 1

Replace it with:

n = sum(y i for i in x) - 1

Tobias K.

**Paul Rubin** · Mar 17 '07, 02:25 AM

Re: Finding the insertion point in a list

tkpmep@hotmail. com writes:

Or with a generator comprehension
n = sum ( y>x[i] for i in range(len(x)) ) - 1
>
But there has to be a cleaner way, as the first approach is unwieldy
and does not adapt to changing list lengths, and the second is not
obvious to a casual reader of the code.

How about:

n = len([y t for t in x])

**Steven D'Aprano** · Mar 17 '07, 06:05 AM

Re: Finding the insertion point in a list

On Fri, 16 Mar 2007 18:17:08 -0800, Paul Rubin wrote:

tkpmep@hotmail. com writes:

>Or with a generator comprehension
>n = sum ( y>x[i] for i in range(len(x)) ) - 1
>>
>But there has to be a cleaner way, as the first approach is unwieldy
>and does not adapt to changing list lengths, and the second is not
>obvious to a casual reader of the code.

>
How about:
>
n = len([y t for t in x])

(1) It's wrong. That always returns the length of the list. Perhaps you
meant something like this?

len(["anything will do" for t in x if y t])

or even

len(filter(lamb da t, y=y: y>t, x))

(2) It's barely more comprehensible than the alternative that the Original
Poster rejected for being insufficiently clear.

Since (almost) everyone insists on ignoring the bisect module and
re-inventing the wheel, here's my wheel:

def find(alist, n):
"""Return the position where n should be inserted in a sorted list."""
if alist != sorted(alist):
raise ValueError('lis t must be sorted')
where = None
for i in range(len(alist )):
if where is not None:
break
alist.insert(i, n)
if alist == sorted(alist):
where = i
del alist[i]
if where is None:
where = len(alist)
return where

Here's another dodgy implementation:

def find(alist, n):
return sorted(alist + [n]).index(n)

It's especially good for large lists. Not!

--
Steven.

**Paul Rubin** · Mar 17 '07, 06:25 AM

Re: Finding the insertion point in a list

Steven D'Aprano <steve@REMOVE.T HIS.cybersource .com.auwrites:

(1) It's wrong. That always returns the length of the list. Perhaps you
meant something like this?
len(["anything will do" for t in x if y t])

Yeah, that's what I meant.

**Paul Rubin** · Mar 17 '07, 06:45 AM

Re: Finding the insertion point in a list

Steven D'Aprano <steve@REMOVE.T HIS.cybersource .com.auwrites:

or even
>
len(filter(lamb da t, y=y: y>t, x))

How about

min(i for i,t in enumerate(x) if t >= y)

or

max(i for i,t in enumerate(x) if t <= y)

Those are actually pretty direct.

**Martin Blume** · Mar 17 '07, 10:15 AM

Re: Finding the insertion point in a list

"7stud" schrieb

How about:
>
-----------
x = [0, 100, 200, 1000]
y = -1
inserted = False
>
for i in range(len(x)):
if(y <= x[i]):
x.insert(i, y)
inserted = True
break
if(not inserted): x.append(y)
>
print x
------------
>

You can get rid of the sentinel "inserted" using the
else clause of the for loop:

for i in range(len(x)):
if (y <= x[i]):
x.insert(i, y)
break
else: x.append(y)

Python is cool :-)

IMHO. HTH.
Martin

**John Machin** · Mar 17 '07, 10:35 AM

Re: Finding the insertion point in a list

On Mar 17, 5:42 pm, Paul Rubin <http://phr...@NOSPAM.i nvalidwrote:

Steven D'Aprano <s...@REMOVE.TH IS.cybersource. com.auwrites:

or even

>

len(filter(lamb da t, y=y: y>t, x))

>
How about
>
min(i for i,t in enumerate(x) if t >= y)
>
or
>
max(i for i,t in enumerate(x) if t <= y)
>
Those are actually pretty direct.

I'd hate to see "indirect". Worse, the min-using gizmoid crashes when
y x[-1] -- all your ifs are belong to False.

>>x

[0, 100, 200, 1000]

>>tests = [0, 1, 100, 150, 1000, 2000]
>>[(y, max(i for i,t in enumerate(x) if t <= y)) for y in tests]

[(0, 0), (1, 0), (100, 1), (150, 1), (1000, 3), (2000, 3)]

Looks OK, iff one is happy with the OP's strange usage of "insert
point".

>>xc = x[:]
>>xc.insert(1 , 150)
>>xc

[0, 150, 100, 200, 1000]

Whoops.

Try this for size:

>>[(y, sum(t <= y for t in x)) for y in tests]

[(0, 1), (1, 1), (100, 2), (150, 2), (1000, 4), (2000, 4)]

Cheers,
John

**Steve Holden** · Mar 17 '07, 10:55 AM

Re: Finding the insertion point in a list

Paul Rubin wrote:

Steven D'Aprano <steve@REMOVE.T HIS.cybersource .com.auwrites:

>or even
>>
>len(filter(lam bda t, y=y: y>t, x))

>
>
How about
>
min(i for i,t in enumerate(x) if t >= y)
>
or
>
max(i for i,t in enumerate(x) if t <= y)
>
Those are actually pretty direct.

How about a solution (like the bisect one suggested almost as soon as
this thread started) that doesn't iterate over the whole list.

Having said which, for the promoted use cases I agree that the append()
and sort() paradigm wins hands down until it starts to make a real and
observable difference to the run time.

regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
Recent Ramblings http://holdenweb.blogspot.com

Finding the insertion point in a list

Finding the insertion point in a list

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment