Re: List insertion cost

[Diez B. Roggisch]

Lucas P Melo wrote:

> Hello,
> I would like to know how much it costs to insert an element into a list
> using this operation:
> a[2:2] = [ 1 ]
> i. e, what is the complexity of the operation above (given that len(a) =
> n)?

O(n) I'd say. You need to copy nearly the whole list, and sometimes
re-allocate it's storage (they are internally stored as arrays of object
references)

Diez
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: List insertion cost

[Lucas P Melo]

Robert Kern wrote:
O(n). Python lists are contiguous arrays in memory, and everything 
after the insertion point needs to be moved. Raymond Hettinger has a 
good talk about the implementation of Python lists and other container 
objects.


http://www.youtube.com/watch?v=hYUsssClE94
http://www.pycon.it/static/stuff/slides/core-python-containers-under-hood.ppt 


Thanks. :)

--
http://mail.python.org/mailman/listinfo/python-list

Re: List insertion cost

[Robert Kern]

On 2009-07-21 14:21, Lucas P Melo wrote:

Hello,
I would like to know how much it costs to insert an element into a list
using this operation:
a[2:2] = [ 1 ]
i. e, what is the complexity of the operation above (given that len(a) =
n)?


O(n). Python lists are contiguous arrays in memory, and everything after the 
insertion point needs to be moved. Raymond Hettinger has a good talk about the 
implementation of Python lists and other container objects.


http://www.youtube.com/watch?v=hYUsssClE94
http://www.pycon.it/static/stuff/slides/core-python-containers-under-hood.ppt

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
 that is made terrible by our own mad attempt to interpret it as though it had
 an underlying truth."
  -- Umberto Eco

--
http://mail.python.org/mailman/listinfo/python-list

Re: List insertion cost

[Daniel Stutzbach]

On Tue, Jul 21, 2009 at 2:21 PM, Lucas P Melo  wrote:

> I would like to know how much it costs to insert an element into a list
> using this operation:
> a[2:2] = [ 1 ]
> i. e, what is the complexity of the operation above (given that len(a) =
> n)?
>

O(n)

If you want O(log n), you can use the blist extension type from
http://pypi.python.org/pypi/blist/

--
Daniel Stutzbach, Ph.D.
President, Stutzbach Enterprises, LLC 
-- 
http://mail.python.org/mailman/listinfo/python-list

List insertion cost

[Lucas P Melo]

Hello,
I would like to know how much it costs to insert an element into a list 
using this operation:

a[2:2] = [ 1 ]
i. e, what is the complexity of the operation above (given that len(a) = n)?

Thanks.
--
http://mail.python.org/mailman/listinfo/python-list

Re: list insertion question

[Paul Rubin]

[EMAIL PROTECTED] writes:

> hi
> i have a list (after reading from a file), say
> data = [ 'a','b','c','d','a','b','e','d']
> 
> I wanted to insert a word after every 'a', and before every 'd'. so i
> use enumerate this list:
> for num,item in enumerate(data):
> if "a" in item:
>   data.insert(num+1,"aword")
> if "d" in item:
> data.insert(num-1,"dword") #this fails
> but the above only inserts after 'a' but not before 'd'.  What am i
> doing wrong? is there better way?thanks

As others have said, you're mutating the list while iterating through
it, which can give whacked results.  Also, even if you operate on a
copy of the list, that algorithm uses quadratic time because of all
the insertions into the list.  These days I like to write in the style

def g():
   for w in data:
 if 'd' in w: yield 'dword'
 yield w
 if 'a' in w: yield 'aword'
data = list(g(data))

instead of using list.append as someone else suggested.  The iterator
approach is probably a bit slower but can be seen as a bit cleaner,
depending on your stylistic preferences.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: list insertion question

[attn . steven . kuo]

On Apr 16, 6:05 pm, [EMAIL PROTECTED] wrote:
> hi
> i have a list (after reading from a file), say
> data = [ 'a','b','c','d','a','b','e','d']
>
> I wanted to insert a word after every 'a', and before every 'd'. so i
> use enumerate this list:
> for num,item in enumerate(data):
> if "a" in item:
> data.insert(num+1,"aword")
> if "d" in item:
> data.insert(num-1,"dword") #this fails
> but the above only inserts after 'a' but not before 'd'.  What am i
> doing wrong? is there better way?thanks


Traverse the list from highest index
to lowest index:

data = [ 'a', 'b', 'c', 'd', 'a', 'b', 'e', 'd' ]

print data
for idx, value in reversed(list(enumerate(data))):
if value == 'a':
data.insert(idx+1, 'aword')
elif value == 'd':
data.insert(idx, 'dword')

print data

# OR

last_idx = len(data) - 1

for idx in range(last_idx+1):
ridx = last_idx - idx
if data[ridx] == 'a':
data.insert(ridx+1, 'aword')
elif data[ridx] == 'd':
data.insert(ridx, 'dword')

print data

--
Hope this helps,
Steven

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: list insertion question

[[EMAIL PROTECTED]]

On Apr 17, 9:47 am, Michael Hoffman <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> > hi
> > i have a list (after reading from a file), say
> > data = [ 'a','b','c','d','a','b','e','d']
>
> > I wanted to insert a word after every 'a', and before every 'd'. so i
> > use enumerate this list:
> > for num,item in enumerate(data):
> > if "a" in item:
> >data.insert(num+1,"aword")
> > if "d" in item:
> > data.insert(num-1,"dword") #this fails
> > but the above only inserts after 'a' but not before 'd'.  What am i
> > doing wrong? is there better way?thanks
>
> If you modify a list while you are iterating over it, you may get
> unexpected results (an infinite loop in this case for me). Also ("a" in
> item) will match "aword" since "a" is a component of it. I imagine you
> mean (item == "a").
>
> Try this:
>
> output = []
> for item in data:
>  if item == "d":
>  output.append("dword")
>  output.append(item)
>  if item == "a":
>  output.append("aword")
>
>  >>> output
> ['a', 'aword', 'b', 'c', 'dword', 'd', 'a', 'aword', 'b', 'e', 'dword', 'd']
> --
> Michael Hoffman

Infinite loop for me too! ^_^, should think of it b4 pressing F5.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: list insertion question

[Michael Hoffman]

[EMAIL PROTECTED] wrote:
> hi
> i have a list (after reading from a file), say
> data = [ 'a','b','c','d','a','b','e','d']
> 
> I wanted to insert a word after every 'a', and before every 'd'. so i
> use enumerate this list:
> for num,item in enumerate(data):
> if "a" in item:
>   data.insert(num+1,"aword")
> if "d" in item:
> data.insert(num-1,"dword") #this fails
> but the above only inserts after 'a' but not before 'd'.  What am i
> doing wrong? is there better way?thanks

If you modify a list while you are iterating over it, you may get 
unexpected results (an infinite loop in this case for me). Also ("a" in 
item) will match "aword" since "a" is a component of it. I imagine you 
mean (item == "a").

Try this:

output = []
for item in data:
 if item == "d":
 output.append("dword")
 output.append(item)
 if item == "a":
 output.append("aword")

 >>> output
['a', 'aword', 'b', 'c', 'dword', 'd', 'a', 'aword', 'b', 'e', 'dword', 'd']
-- 
Michael Hoffman
-- 
http://mail.python.org/mailman/listinfo/python-list

list insertion question

[eight02645999]

hi
i have a list (after reading from a file), say
data = [ 'a','b','c','d','a','b','e','d']

I wanted to insert a word after every 'a', and before every 'd'. so i
use enumerate this list:
for num,item in enumerate(data):
if "a" in item:
data.insert(num+1,"aword")
if "d" in item:
data.insert(num-1,"dword") #this fails
but the above only inserts after 'a' but not before 'd'.  What am i
doing wrong? is there better way?thanks

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: list insertion

[Randy Bush]

>>hold = self.next
>>self.next = DaClass(value)
>>self.next.next = hold
>>
>> but i suspect (from print statement insertions) that the result
>> is not as i expect.  as the concept and code should be very
>> common, as i am too old for pride, i thought i would ask.
> I think you're fine.

indeed.  the bug was elsewhere.  i got confused and tried to
look-ahead too far when i could have just recursed.  i threw
away the too-clever code and replaced it with one line.  i
love it when that happens.

randy

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: list insertion

[Bengt Richter]

On Tue, 23 Aug 2005 20:58:11 -0700, Randy Bush <[EMAIL PROTECTED]> wrote:

>i am trying to insert into a singly linked list
>
>hold = self.next
>self.next = DaClass(value)
>self.next.next = hold
>
>but i suspect (from print statement insertions) that the result
>is not as i expect.  as the concept and code should be very
>common, as i am too old for pride, i thought i would ask.
>
I think you're fine. Here's some possible context for your code:

 >>> class DaClass(object):
 ... def __init__(self, value):
 ... self.value = value
 ... self.next = None
 ... def values(self):
 ... while True:
 ... yield self.value
 ... if self.next is None: break
 ... self = self.next
 ... def insert(self, value):
 ... hold = self.next
 ... self.next = DaClass(value)
 ... self.next.next = hold
 ... return self
 ... def __repr__(self):
 ... return ''%(' -> '.join(map(repr, self.values(
 ...
 ...
 >>> sll = DaClass(1)
 >>> sll
 
 >>> sll.insert(2)
  2>
 >>> sll
  2>
 >>> sll.insert('a')
  'a' -> 2>
 >>> sll.next
  2>
 >>> sll.next.insert('b')
  'b' -> 2>
 >>> sll
  'a' -> 'b' -> 2>

Regards,
Bengt Richter
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: list insertion

[Randy Bush]

>> hold = self.next
>> self.next = DaClass(value)
>> self.next.next = hold
> shouldn't that last line be this?
>   self.next.prev = hold

single threaded list

> What did you expect, and what did you ovserve?

i will try to distill a case

randy

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: list insertion

[Ross Wilson]

On Tue, 23 Aug 2005 20:58:11 -0700, Randy Bush wrote:

> i am trying to insert into a singly linked list
> 
> hold = self.next
> self.next = DaClass(value)
> self.next.next = hold
> 
> but i suspect (from print statement insertions) that the result
> is not as i expect.  as the concept and code should be very
> common, as i am too old for pride, i thought i would ask.
> 
> mahalo,
> randy

The example above looks like it would work, as long as other
stuff you _don't_ show is fine.  Specifically, how do you 
handle the case when the list is empty?

Better to show a more complete example with output and how that
is not what you expect.

Ross
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: list insertion

[Sybren Stuvel]

Randy Bush enlightened us with:
> hold = self.next
> self.next = DaClass(value)
> self.next.next = hold

shouldn't that last line be this?
self.next.prev = hold

> but i suspect (from print statement insertions) that the result is
> not as i expect.

What did you expect, and what did you ovserve?

Sybren
-- 
The problem with the world is stupidity. Not saying there should be a
capital punishment for stupidity, but why don't we just take the
safety labels off of everything and let the problem solve itself? 
 Frank Zappa
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: list insertion

[Jordan Rastrick]

What you've posted looks right, more or less.

To get any sort of meaningful feedback, you really need to post a full
version of your code, including the print statements, what's being
printed, and why you think this shows the code is not working. What
you've shown is far too little for anybody else to work with.

Regards,
Jordan


Randy Bush:
> i am trying to insert into a singly linked list
>
> hold = self.next
> self.next = DaClass(value)
> self.next.next = hold
>
> but i suspect (from print statement insertions) that the result
> is not as i expect.  as the concept and code should be very
> common, as i am too old for pride, i thought i would ask.
> 
> mahalo,
> randy

-- 
http://mail.python.org/mailman/listinfo/python-list

list insertion

[Randy Bush]

i am trying to insert into a singly linked list

hold = self.next
self.next = DaClass(value)
self.next.next = hold

but i suspect (from print statement insertions) that the result
is not as i expect.  as the concept and code should be very
common, as i am too old for pride, i thought i would ask.

mahalo,
randy

-- 
http://mail.python.org/mailman/listinfo/python-list