Python merge lists in place to maintain external references

Question

I am not sure if this is possible in Python, but performance to my application is critical and I have the following scenario.

I am attempting merge two disjoint sets with the following implementation. I have a dictionary of sorted lists, where the keys in the dictionary point to the sorted list which holds the value (by reference). Like this

l1 = [1, 2, 3]
l2 = [4, 5, 6]

d = {1: l1, 2: l1, 3: l1, 4: l2, 5: l2, 6: l2}

Now I want to merge the two lists in place such that each key in the dictionary refers to the same underlying list like

l1 = l2 = l1 + l2

But this won't affect the references held within the dictionary, since a new list is created.

Speed is critical here, so I don't want to create new lists and reassign references to each key in the dictionary.

EDIT

I would expect the following code to run without an assertion error after this operation

for v in d:
    assert d[v] is l1

I second what @RomanPerekhrest has asked. What exactly should you output be? Could you give an example? — Christian Dean, Dec 05 '16 at 21:34
@RomanPerekhrest The final result should be `for v in d: d[v] == l1` — shane, Dec 05 '16 at 21:35
@leaf Right, I mean each key will reference the same list, which should be the combined result of `l1` and `l2` — shane, Dec 05 '16 at 21:38
Instead of holding list references in your dict, hold indexes. That way you can replace the list and it won't matter. Holding references seems pretty fragile to me. — Paul Rooney, Dec 05 '16 at 21:38
@shane So would something like this work `nd = {key: l1 + l2 for key in d.keys()}`? — Christian Dean, Dec 05 '16 at 21:39
@leaf I think that's the *opposite* of what shane wants. The closest would be Patrick Haugh's answer. Also, no need for `d.keys` to iterate of dictionary keys. Just `d` will suffice. — juanpa.arrivillaga, Dec 05 '16 at 21:40
@leaf I am looking to avoid re-iterating over `d` if possible — shane, Dec 05 '16 at 21:41
@juanpa.arrivillaga I know `d` would suffice. I was being explicit for the for the OP's sake. — Christian Dean, Dec 05 '16 at 21:41
With `@Patrick Haugh's` suggestion, `d[4] is l1` is `False`, but `d[4]==l1` is `True`. That is `l1==l2` but their `ids` are not the same. — hpaulj, Dec 05 '16 at 21:53

score 2 · Accepted Answer · answered Dec 05 '16 at 21:41

2

References work similar to pointers: each one uniquely identifies an object, and only it. So, l1 and l2 that your dictionary elements hold are different references.

Thus, you can't magically make them the same without actually editing the dictionary.

All you can do is make l1 and l2 hold identical values.

answered Dec 05 '16 at 21:41

ivan_pozdeev

33,874
19
107
152

Fair, I suppose I am looking for a sort of double pointer as I would have in C++, which is not available in Python. Thanks for making this explicit. – shane Dec 05 '16 at 21:52
if I have 1000 elements keying to `px = &p1` and 1000 elements keying to `py = &p2`, and `p1` and `p2` are type `List *`, then I can combine the lists and set `p1` and `p2` to point to the new list without modifying the value of 2000 elements. I did say I did not want to create a new list, but that was slightly misleading since it would be impossible to combine the lists otherwise – shane Dec 05 '16 at 22:12
See - your dictionary items are not `List *` but `List **` here. And to check if they are the same, you don't compare their values but dereference them once and then compare. Likewise, to do that in Python, what your `dict` entries hold, `l1` and `l2`, should not be lists proper but "proxies", e.g. [like this](http://stackoverflow.com/questions/1145722/simulating-pointers-in-python), and you should not compare _them_ with `is` but the references they hold. – ivan_pozdeev Dec 05 '16 at 22:25
This, however, may be not pythonic unless you have other reasons to use "indirect references" besides performance gain ([which may even be nonexistent](http://stackoverflow.com/a/26820109/648265)): having two sets of values in a `dict` which are really the same kinda defeats the purpose of two sets of values (and of a `dict` in the first place). Python is consciously designed for programmer's performance at the cost of code performance - you first write clean and correct code and only then check if you need optimization. – ivan_pozdeev Dec 05 '16 at 22:52

Python merge lists in place to maintain external references

1 Answers1