1

I have a dynamic set consisting of a data series on the order of hundreds of objects, where each series must be identified (by integer) and consists of elements, also identified by an integer. Each element is a custom class.

I used a defaultdict to created a nested (2-D) dictionary. This enables me to quickly access a series and individual elements by key/ID. I needed to be able to add and delete elements and entire series, so the dict served me well. Also note that the IDs do not have to be sequential, due to add/delete. The IDs are important since they are unique and referenced elsewhere through my application.

For example, consider the following data set with keys/IDs,

[1][1,2,3,4,5]
[2][1,4,10]
[4][1]

However, now I realize I want to be able to insert elements in a series, but the dictionary doesn't quite support it. For example, I'd like to be able to insert a new element between 3 and 4 for series 1, causing the IDs above it (from 4,5) to increment (to 5,6):

[1][1,2,3,4,5] becomes
[1][1,2,3,4(new),5,6]

The order matters since the elements are part of a sequential series. I realize that this would be easier with a nested list since it supports insert(), but then I would be forced to iterate over the entire 2-D array to get element indices right?

What would be the most optimal way to implement this data structure in Python?

Brandon J
  • 51
  • 6
  • Why can't you insert your new value and then just sort the list? `[1].push(new)` and then `[1].sort()`? – tkone Jan 04 '12 at 18:44
  • @tkone I'm not using lists right now, I'm using a nested dictionary. – Brandon J Jan 04 '12 at 18:53
  • According to your code, you're using lists. Lists are defined in Python with the `[]` notation. Dictionaries are `{}`. Additionally, if those are supposed to be dicts you've only got keys and no values for your dicts. – tkone Jan 04 '12 at 18:56
  • @tkone I was just showing the IDs/keys used to index my data in the explanation, not the actual code syntax, hence the brackets []. – Brandon J Jan 04 '12 at 19:15
  • @BrandonJ: So, is `[1,2,3,4,5]` an actual index, or just all of the possible indices of that series? Actually, which part of `[1][1,2,3,4,5]` is the key, and which is the ID? – voithos Jan 04 '12 at 19:31

1 Answers1

0

I think what you want is a dict with array values:

dict = {1:[...],3:[...], ....}

You can then operate on the arrays as you please. If the array values are sequential ints just use:

dict[key].append(vals)
dict[key].sort()

Don't worry about the speed unless you find out it's a problem. Premature optimization is the root of all evil.

In fact, don't even sort your dict vals until you have to, if you want to be really efficient.

joel3000
  • 1,249
  • 11
  • 22