Creating a list with holes

L

Larry Martell

I think I know the answer is no, but is there any package that allows
creating a list with holes in it? E.g. I'd want to do something like:

x[10] = 12
x[20] = 30

I'm thinking of something like defaultdict but for lists (I know
that's very different, but ... )

Thanks!
-larry
 
E

eneskristo

I think I know the answer is no, but is there any package that allows

creating a list with holes in it? E.g. I'd want to do something like:



x[10] = 12

x[20] = 30



I'm thinking of something like defaultdict but for lists (I know

that's very different, but ... )



Thanks!

-larry

Hello Larry!

The thing is, where to put the holes? A costum function can be made if you want the hole to be placed for example:
1. In random
2. Every nth hole(Or with another sequence)
3. In the beginning or end.

Please tell me how do you want them, and I will try my best to help!
- Enes
 
R

Roy Smith

Larry Martell said:
I think I know the answer is no, but is there any package that allows
creating a list with holes in it? E.g. I'd want to do something like:

x[10] = 12
x[20] = 30

Whenever you ask, "What data structure do I want", you need to be able
to answer, "What operations do I want to perform?, and, "What
constraints do I have on memory use?"

Why do you want holes? Is the issue that you're storing sparse data and
don't want to waste memory on unused keys? If so, a dictionary should
do you fine.

Do you need to be able to read the values back out in a specific order?
You can still do that with a dictionary if you're willing to re-sort the
keys; that's O(n log n) on the number of keys, but if n is small, it
doesn't matter.
 
L

Larry Martell

I think I know the answer is no, but is there any package that allows

creating a list with holes in it? E.g. I'd want to do something like:

x[10] = 12
x[20] = 30

I'm thinking of something like defaultdict but for lists (I know

that's very different, but ... )

Hello Larry!

The thing is, where to put the holes? A costum function can be made if you want the hole to be placed for example:
1. In random
2. Every nth hole(Or with another sequence)
3. In the beginning or end.

Please tell me how do you want them, and I will try my best to help!

The holes would be between the items I put in. In my example above, if
I assigned to [10] and [20], then the other items ([0..9] and
[11..19]) would have None.
 
C

Chris Angelico

Why do you want holes? Is the issue that you're storing sparse data and
don't want to waste memory on unused keys? If so, a dictionary should
do you fine.

Do you need to be able to read the values back out in a specific order?
You can still do that with a dictionary if you're willing to re-sort the
keys; that's O(n log n) on the number of keys, but if n is small, it
doesn't matter.

There's another factor, which is iteration time. Maybe you don't care
about the memory usage, but compare these:

foo = [None]*1000
foo[123] = 234
foo[543] = 432

for key,value in enumerate(foo):
if value: print("Slot %d is %d"%(key,value))

# versus

foo = {}
foo[123] = 234
foo[543] = 432

for key in sorted(foo.keys()):
value = foo[key]
if value: print("Slot %d is %d"%(key,value))

Which one's going to be faster? The dictionary, by far, in this
example. I'm not sure how populated the list would have to be to beat
it (as the dict will get slower on O(n log n) on keys, as you mention,
while the list will run at O(n) on the highest element, which may well
be a constant), but it's something to consider.

ChrisA
 
D

Denis McMahon

The holes would be between the items I put in. In my example above, if I
assigned to [10] and [20], then the other items ([0..9] and [11..19])
would have None.

So a standard dictionary does this returning None (or any other default
value you care to pass it) as long as you use the dict.get(key[,default])
method rather than dict[key] to return the value.

See also:

http://stackoverflow.com/questions/6130768/return-none-if-dictionary-key-
is-not-available
 
L

Larry Martell

The holes would be between the items I put in. In my example above, if I
assigned to [10] and [20], then the other items ([0..9] and [11..19])
would have None.
dic = { 10:6, 20:11}
dic.get(10) 6
dic.get(14)
dic.get(27,"oh god there's nothing here") "oh god there's nothing here"
dic.get(99,None)
dic.get(168,False) False
dic.get(20,"Boo Yah") 11

So a standard dictionary does this returning None (or any other default
value you care to pass it) as long as you use the dict.get(key[,default])
method rather than dict[key] to return the value.

See also:

http://stackoverflow.com/questions/6130768/return-none-if-dictionary-key-
is-not-available

Thanks, but I know all that about dicts. I need to use a list for
compatibility with existing code.
 
R

Roy Smith

Larry Martell said:
Thanks, but I know all that about dicts. I need to use a list for
compatibility with existing code.

Generalizing what I think the situation is, "A dict is the best data
structure for the parsing phase, but I need a list later to hand off to
legacy interfaces".

No problem. Parse the data using a dict, then convert the dict to a
list later. I haven't been following all the details here, but just
wanted to point out that using different data structures to hold the
same data at different phases of a program is a perfectly reasonable
approach.
 
D

Denis McMahon

Generalizing what I think the situation is, "A dict is the best data
structure for the parsing phase, but I need a list later to hand off to
legacy interfaces".

No problem. Parse the data using a dict, then convert the dict to a
list later. I haven't been following all the details here, but just
wanted to point out that using different data structures to hold the
same data at different phases of a program is a perfectly reasonable
approach.

Indeed, assuming the requirement is to have a list of some length n units
representing integer keys into a range of values from start to end, and
he creates a dict initially:

list = [ dict.get(x,None) for x in range(start,end + 1) ]

Examples:
dic = {1:"fred", 9:"jim", 15:"susan", 25:"albert" }
l = [ dic.get(x,None) for x in range(1,20) ]
l
['fred', None, None, None, None, None, None, None, 'jim', None, None,
None, None, None, 'susan', None, None, None, None]
l = [ dic.get(x,None) for x in range(-10,50) ]
l
[None, None, None, None, None, None, None, None, None, None, None, 'fred',
None, None, None, None, None, None, None, 'jim', None, None, None, None,
None, 'susan', None, None, None, None, None, None, None, None, None,
'albert', None, None, None, None, None, None, None, None, None, None,
None, None, None, None, None, None, None, None, None, None, None, None,
None, None]60

then the value of l[offset] will either be None or some string depending
on the offset into the list
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top