Python data structure

Question

I know very little about programming, so this is a case of not knowing where to look for the answer. I am looking to create a data structure like the following:

vertexTopology = {vertexIndex: {clusterIndexes: intersection point}}

however cluster indexes in reality is a set consisting of the indexes of the clusters. So what I really have now is:

vertexTopology = {5: [[(1, 2, 3), intx_1], 
                      [(2, 3, 4), intx_2]]
                  6: [[(1, 2, 3), intx_3]]
                  ...}

How can I create a unique index associated to each cluster set AND its vertex index? Something like:

vertexTopology = {5: {index associated with (1, 2, 3) AND vertex 5, intx_1}, 
                     {index associated with (2, 3, 4) AND vertex 5, intx_2},
                  6: {index associated with (1, 2, 3) AND vertex 6, intx_3}]
                  ...}

I'm not sure that what I am looking to do is best achieve with dictionaries, so any suggestion is much welcomed!

Bellow is an image of a four point intersection, just so you can picture a bit what I dealing with.

Four point intersection

What properties does your index need to have? IIUC, the tuple ((1,2,3), 5) would itself be a viable index; it's simple, hashable, sortable, etc. Or you do want an integer? — DSM
– DSM, Commented Oct 9, 2013 at 17:38
Well you might be correct about that. The problem is I don't really know where collisions can happen, so I was kinda for a fail-safe approach. @EveryEvery's solution seems easy to implement. I'll go with that and test it thoroughly. — grasshopper
– grasshopper, Commented Oct 9, 2013 at 17:49
@grasshopper if you don't need some number or string for index, you can use tuple for key directly. it's more easy :-) — Curry
– Curry, Commented Oct 9, 2013 at 17:58
@grasshopper: if you use the tuple itself, there won't be any dangerous collisions. There may be hash collisions, but that's an implementation detail behind the scenes: you'll never get the wrong value associated with the key. If you try to replace the key by your own hash, then you could have dangerous collisions of the sort that I gave, because you're throwing information away. [Similarly for the frozenset, which is even better because then you don't have to worry about the order.] — DSM
– DSM, Commented Oct 9, 2013 at 19:47

Noctua · Accepted Answer · 2013-10-09 17:36:16Z

6

There's a thing in Python called a frozen set. That's a set you can use as an index in a dictionary.

vertexTopology = {
    5: {
        (frozenset({1, 2, 3}), 5): intx_1,
        (frozenset({2, 3, 4}), 5): intx_2
    },
    6: {
        (frozenset({1, 2, 3}), 5): intx_3
    },
    ...
}

Unlike sets, frozensets are unmutable. That's why they can be used as an index.

answered Oct 9, 2013 at 17:36

Noctua

5,2381 gold badge20 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

grasshopper Over a year ago

I had tried using set as the key of the dictionary, but it didn't work. Glad you told me of using frozenset as a key.

Curry · Accepted Answer · 2013-10-09 17:50:29Z

3

use hash() for generate index for cluster set and vertex index. tuple is hashable type.

vertexTopology = {5: {hash(((1, 2, 3),5)): intx_1, 
                      hash(((2, 3, 4),5)): intx_2},
                  6: {hash(((1, 2, 3),6)): intx_3},
                  ...}

or use tuple as key

vertexTopology = {5: {((1, 2, 3),5): intx_1, 
                      ((2, 3, 4),5): intx_2},
                  6: {((1, 2, 3),6): intx_3},
                  ...}

if you data use set, tuple() can make tuple from set easily

s = set([1, 2, 3])    # s is set
t = tuple(s)    # t is tuple

UPDATE:

if you want other hash method. str() is easy solution.

In [41]: import hashlib

In [42]: hashed = hashlib.sha512(str(((1, 2, 3), 4))).digest()

In [43]: hashed
Out[43]:
'mtE7\xf6N\xfc\xca\xc7\xb1\x0fA\x86|\xbe9j\xbb\xdf\xbaa\xd1\x05V\x84\xe8S\xfb\xe1\x16\xe05\x89,C\xa8\x94n\xae\x1e\n\xc0Y-)\xfa\xceG D\xe0C\xc9\xef\xb0\x8eCk\xe3`\xc2s\x97\xec'

edited Oct 9, 2013 at 17:50

answered Oct 9, 2013 at 17:33

Curry

8955 silver badges15 bronze badges

8 Comments

grasshopper Over a year ago

oh wow thanks! :D I kinda thought of a hash, but was using hashlib.sha224 () and it only seems to take strings. Didn't know hash() existed, or that it took tuples.

DSM Over a year ago

This could lead to unexpected collisions. For example, hash(((0,34,89),6)) == hash(((9,79,76),9)) for me.

Curry Over a year ago

all hash algorithm can have collision. if you want, you can use more safe hash algorithm.

grasshopper Over a year ago

@DSM . Gotcha! Given what I am working on, I'm pretty sure this can happen.

DSM Over a year ago

@EveryEvery: I guess what I'm getting at is that there's no need to throw information away by using the hash here when there are risk-free options.

|

Collectives™ on Stack Overflow

Python data structure

2 Answers 2

1 Comment

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related