Fastest dict/map method when 'key' is already a hash?

[DeaD_EyE]

You can learn here: https://borgbackup.readthedocs.io/en/stable/
They made a tool like yours, but they optimized parts with Cython.

Sortedcontainers may help, because the items are inserted in the right order.

A simple example with Lists in Python:

class SortedList(list):

    def append(self, value):
        idx = bisect.bisect(self, value)
        super().insert(idx, value)

    def extend(self, iterable):
        for element in iterable:
            self.append(element)

    def __setitem__(self, idx, value):
        del self[idx]
        self.append(value)

    def insert(self, idx, value):
        raise NotImplementedError

    def sort(self):
        raise NotImplementedError

To check how much memory a datastructure takes, you should read this article.

Test results with 1e6 elements:

Output:
Dict-Dicts: 361.39 MiB
Dict-Namedtuple: 201.17 MiB
List-List 192.35 MiB
List-Tuple: 177.10 MiB

Test-Code:

# use get_size from example

import os
import sys
from collections import namedtuple

 
def test_dirrent_sizes():
    entry = {'path': 'path'*10, 'size': 1234, 'mtime': 'mtime'}
    st = namedtuple('file', entry.keys())
    length = range(int(1e6))
    print('Dict-Dicts:', end=' ')
    size = get_size({os.urandom(64): entry.copy() for _ in length}) / 1024**2
    print(f'{size:.2f} MiB')
    print('Dict-Namedtuple:', end=' ')
    size = get_size({os.urandom(64): st(*entry.values()) for _ in length}) / 1024**2
    print(f'{size:.2f} MiB')
    print('List-List', end=' ')
    size = get_size([[os.urandom(64), *entry.values()] for _ in length]) / 1024**2
    print(f'{size:.2f} MiB')
    print('List-Tuple:', end=' ')
    size = get_size([(os.urandom(64), *entry.values()) for _ in length]) / 1024**2
    print(f'{size:.2f} MiB')

Making the structures smaller and a automatic sorting by appending a new element, should speed up everything.