наследование списка, чтобы использовать его метод сортировки на месте

Question

Я пытаюсь отсортировать содержимое нескольких файлов (иногда перемещая строку из одного файла в другой)

Я хотел бы использовать встроенную адаптивную сортировку слиянием, которая является атрибутом list. Я пытался унаследовать метод от list, но я не знаю, нужно ли ему больше __len__, __getitem__ и __setitem__. Да. Я хочу отсортировать на месте.

FYI, вот мой код (если он помогает объяснить, что я делаю), порядок, когда я вызываю .sort (), не изменяется. Если я добавлю свой собственный метод bubble_sort, написанный на python, он будет работать, но ужасно медленно:

class Memwrap(list):
    def __init__(self, prefix, folder='.', chunksize=None):

        fns = [fn for fn in os.listdir(folder) if fn.startswith(prefix)]
        fns.sort()
        self.files = [open(os.path.join(folder,fn), 'r+') for fn in fns]
        self.mmaps = [mmap.mmap(f.fileno(), 0) for f in self.files]
        self.sizes = [mm.size() for mm in self.mmaps]
        if chunksize is None:
            self.chunksize = len(self.mmaps[0].readline())
        else:
            self.chunksize = chunksize


    def _mm_from_idx(self, idx):
        bidx = self.chunksize*idx
        lo = 0
        for m,s in zip(self.mmaps, self.sizes):
            hi = lo + s
            if lo <= bidx < hi:
                return bidx-lo, m
            lo = hi

    def __getitem__(self, idx):
        bidx, mmap = self._mm_from_idx(idx)        
        return mmap[bidx:bidx+self.chunksize]

    def __setitem__(self, idx, val):
        assert len(val) == self.chunksize
        bidx, mmap = self._mm_from_idx(idx)
        mmap[bidx:bidx+self.chunksize] = val

    def __len__(self):
        assert not sum(self.sizes)%self.chunksize
        return sum(self.sizes)/self.chunksize


    def bubble_sort(self):
        for i in xrange(0, len(self) - 1):
            swap_test = False
            for j in range(0, len(self) - i - 1):
                if self[j] > self[j + 1]:
                    self[j], self[j + 1] = self[j + 1], self[j]  # swap
                swap_test = True
            if swap_test == False:
                break
        self.flush()


    def flush(self):
        for mm in self.mmaps:
            mm.flush()

    def close(self):
        self.flush()
        for mm in self.mmaps:
            mm.close()
        for f in self.files:
            f.close()

Answer 1

Фактический код сортировки списка доступен здесь (около строки 2000): https://github.com/python-git/python/blob/master/Objects/listobject.c

Насколько я могу судить, невозможно использовать этот код с другим механизмом хранения.

Вы можете сделать свой алгоритм сортировки быстрее (используя быструю сортировку и т. Д.) Или использовать модуль ctypes для взаимодействия с алгоритмом сортировки на основе C (например, http://tomoyo.sourceforge.jp/cgi-bin/lxr/source/lib/sort.c).

Наконец, вы можетеиспользуйте приложение сортировки linux для сортировки данных (используя модуль подпроцесса, если вы хотите управлять им в Python). sort filea fileb filec, вероятно, будет быстрее, чем все, что вы можете сделать в Python, mmap или нет.

Answer 2

Вы неправильно понимаете, что делает наследование от list.

Ваш Memwrap не просто получает интерфейс list, он является списком (который находится в памятиструктура как массив объектов Python, которые не могут быть непосредственно выражены в Python).Затем вы добавляете несколько дополнительных членов экземпляра и переопределяете некоторые list методы для общения с вашими членами вместо обычных данных экземпляра list (потому что вы никогда не вызываете реализации базового класса).Обратите внимание, что Memwrap все еще содержит данные экземпляра, унаследованные от list, но что касается данных, они остаются пустым списком со связанными атрибутами.

Бывает, что многие изОперации над встроенными типами реализованы в C и просто используют данные уровня C напрямую, а не через хуки уровня Python (например, __getitem__).Таким образом, хотя этот вид наследования для интерфейса может работать для классов уровня Python (хотя на самом деле это хак), он обычно не для встроенных типов.Это, конечно, не то, что вы «должны» делать с типами создания подклассов;более вероятно, что вы создадите list, который работает немного по-другому (вы можете добавить значения по умолчанию, дополнительные методы, метаданные и т. д.), чем то, что вы делаете совершенно другое, что разделяет интерфейс.Для этого посмотрите ABC в модуле collections.

Я не понимаю, как вы можете использовать встроенную сортировку list, не имея на самом деле list.Предполагается, что отображаемые в память файлы должны быть быстрее, чем делать тонны небольших вызовов на уровне ОС, но для сортировки вы, по сути, читаете и переписываете все файлы в любом случае, так что я не могу понять, как вы получите этоидти быстрее, чем делать это;читать все файлы в память, сортировать их, а затем записывать результаты в файлы.

Ваш трюк с использованием mmaps для сортировки на месте файлов, содержащих куски данных фиксированного размера, довольно умен, новам действительно нужно использовать C полностью, чтобы заставить его работать и быть быстрым.В Python нет операции для сортировки файлов на месте (это довольно непонятная операция, поскольку это невозможно, если вы не предполагаете, что блоки данных имеют какой-то фиксированный размер), вы не можете получить сортировку list, чтобы сделать это длявы, и реализация такого рода самостоятельно в Python обязательно будет медленнее, чем хорошая реализация на C.Тем не менее, это должна быть операция ввода-вывода, а не вычисления, так что вы уверены на самом деле можно сделать работу намного быстрее, чем пузырьковая сортировка?

Answer 3

Метод сортировки списков написан на C (в CPython) и поэтому вообще не нуждается в использовании __getitem__ и _ _setitem__ методов.Если бы он использовал эти методы, он бы сильно замедлил обычный list.sort ()

Вы можете сохранить индексы файлов в списке и использовать встроенную сортировку списка с функцией key, чтобы сделать некоторыеработы для вас