I'm confused about the title: your description sounds like accessing items in an NpzFile is linear, and iterating is quadratic, am I missing something?
 
Given the definition of __iter__ in terms of self.files, and of self.files in terms of self._files (roughly self.files = [name.removesuffix(".npy") for name in self._files]), I think making self._files a set or frozenset would only be a factor of two or so for a file containing mostly .npy files like np.savez makes. If you then changed the second comparison to elif f"{key:s}.npy" in self._files: ... instead of the current check on self.files, I think that would give the O(n)->O(1) speedup you want. (you may wish to apply the same changes to __contains__)

You could alternately define self._files as a mapping from names passed to archive member names (self._files = dict(zip(self.files, self._files)) | dict(zip(self._files, self._files))) and define __getitem__ in terms of that.

Your other option would be to redefine items() in terms of zipfile.Path.iterdir() and have your code use that instead, which would work better if you use most of those thousands of files every loop, than if you load only a small fraction of the archive members any given loop. Re-defining items() would probably be easier if you moved the contents of the if member conditional in __getitem__ to a private helper function for re-use.

... after some tinkering:

I tried both of my first two suggestions, and reading 600 1000-element arrays is still slower than reading a single array with half a million elements, nearly the same speed with my changes as with the default NumPy implementation.

If there are simple fixes, we can entertain them, but I'm going to suggest that this use case is well out of scope of what the format is intended to accomplish. There are better options out there.

@DWesl , yes: I would expect f[key] to be $O(1)$ not $O(n)$ for a mapping. This turns iterating over all keys quadratic.

@DWesl, @rkern: The simple solution is indeed to convert _files into a set, which I think is a simple fix and happy to send a patch. I was just asking if there were any ideas about how to handle files since I'm not a heavy numpy user. It looks like I should just leave it as is. I have worked around the issue by writing my own npz loader using zipfile and returning a dict.

Here's code that demonstrates the problem:

#!/usr/bin/env python3

import numpy as np
from io import BytesIO
import timeit

sz = 50

for N in [10, 100, 1000, 10000, 100000]:
    out = [np.random.rand(sz) for _ in range(N)]

    memfile = BytesIO()
    np.savez(memfile, *out) # will save arrays as arr_0, arr_1, ...

    memfile.seek(0)
    npf = np.load(memfile, allow_pickle=True)

    gl = {'N': N, 'npf': npf}

    print(N)
    print("first:", timeit.timeit('npf["arr_0"]', number=30, globals=gl))
    print("last:", timeit.timeit(f'npf["arr_{N-1}"]', number=30, globals=gl))
    print("iteration:", timeit.timeit(f'for i in range(N): npf[f"arr_{{i}}"]', number=30, globals=gl))

Here's output on my machine:

10
first: 0.015982249984517694
last: 0.008983943029306829
iteration: 0.0914917589398101
100
first: 0.008222291944548488
last: 0.011221515014767647
iteration: 0.8333280109800398
1000
first: 0.008200841024518013
last: 0.014114694902673364
iteration: 8.74759975890629
10000
first: 0.015102061908692122
last: 0.02731273602694273
iteration: 149.15660362993367
100000
first: 0.06533248000778258
last: 0.1074293979909271
... still running for over 15 minutes now ...

Notice how the time to access the last element depends on the number of files, and how the time for iteration quickly blows up.

I think we should just apply the simple fix (without changing self.files as public API). I might honestly just go with a dict to do the .npy -> key dance once and store it in a mapping.

The format really shouldn't be used here probably, but I agree that doesn't mean that access should unnecessarily scale O(n).

Thank you, I'll open a pull request with fix soon.

Point taken about NPZ not being ideal for our use case, but I was in the process of converting NPZ to the new format when I discovered that I could make it work with minimal changes and and thought I might alert upstream.