ObjectList.append is O(n²): the duplicate check rebuilds a list of ids on every call #1927

Describe the bug
Each append to an ObjectList (and so to Segment.spiketrains, Segment.analogsignals, etc.) takes time proportional to the length of the list. Building a list of n objects therefore takes O(n²). This also slows down any IO that appends objects such as, NixIO.read_all_blocks().

This inefficiency is related to the _contains function (neo/core/objectlist.py:51), called by ObjectList._handle_append. _contains builds a temporary list of the ids of every item on each call and then searches it linearly:

def _contains(self, obj):
    if self._items is None:
        obj_ids = []
    else:
        obj_ids = [id(item) for item in self._items]
    return id(obj) in obj_ids

Here is a suggested change that keeps the semantics and drops the temporary list, it is still O(n) per call:

def  _contains(self, obj):
    return self._items is not None and any(item is obj for item in self._items)

Another solution that reach O(1) is to keep in ObjectList a set of ids alongside _items. That set would have to be updated in every method that mutates _items.

On a (un)related matter (I can create a separated issue for this), extend and __iadd__ don't check for duplicates within the iterable being added (mylist.extend([a, a]) succeeds). I don't think this is the expected behavior.

To Reproduce

import time
import neo, quantities as pq
from neo.core.spiketrainlist import SpikeTrainList

for n in (2500, 5000, 10000, 20000):
    trains = [neo.SpikeTrain([1.0] * pq.ms, t_stop=10 * pq.ms) for _ in range(n)]
    stl = SpikeTrainList()
    start = time.perf_counter()
    for st in trains:
        stl.append(st)
    t = time.perf_counter() - start
    print(f"{n:>6} appends: {t:6.2f}s  ({t / n * 1e6:6.1f} us per append)")

neo 0.14.5, :

  2500 appends:   0.21s  (  85.7 us per append)
  5000 appends:   0.86s  ( 172.6 us per append)
 10000 appends:   1.75s  ( 175.1 us per append)
 20000 appends:   7.49s  ( 374.7 us per append)

Expected behaviour
_contains should be at least O(n)

Environment:

• OS: Linux mint 22.3 (Ubuntu 24.04)
• Python version: 3.12
• Neo version: 0.14.5
• NumPy version: 2.5.3

Additional context
This problem was uncovered during the refactor of simulation results structure for the BSB dbbs-lab/bsb#299