Поиск транспонирования очень, очень большой матрицы

У меня есть этот огромный 2-мерный массив данных. Он хранится в порядке строк:Поиск транспонирования очень, очень большой матрицы

A (1,1) A (1,2) A (1,3) ..... A (n-2, n) A (n-1, n) А (п, п)

Я хочу, чтобы изменить его в порядок столбцов (1,1) А (2,1) А (3,1) ..... А

А (п, п -2) A (n, n-1) A (n, n)

Набор данных довольно велик - больше, чем поместится в ОЗУ на компьютере. (n составляет около 10000, но каждый элемент данных занимает около 1 Кб.)

Кто-нибудь знает гладкие или эффективные алгоритмы для этого?

источник

2011-12-14 Stephen Montgomery-Smith

Какой язык программирования/приложение? – SuperTron

Где хранится матрица, если она слишком велика для хранения в ОЗУ? Во время исполнения вещи хранятся в ОЗУ. – Dimme

n = 10000 означает 10000x10000x1KB = 100 ГБ. –

Создать n пустые файлы (зарезервировать достаточно места для n элементов, если можно). Итерации через оригинальную матрицу. Добавить элемент (i,j) в файл j. Когда вы закончите с этим, добавьте файлы, которые вы только что написали.

источник

2011-12-15 13:24:42 Raphael

Я думаю, что «n пустых» файлов не такая хорошая идея. Вам нужно создать около 10 000 файлов. Некоторые файловые системы даже не допускают, чтобы многие файлы в каталоге, а другие использовали неиспользуемые методы базы данных для перечисления файлов в каталоге. Поэтому прежде всего вам нужно использовать очень умную файловую систему, которая использует B-деревья или что-то в этом роде, чтобы перечислить свои каталоги. (Возможно, некоторые из файловых систем linux делают это.) –

Далее, когда вы пишете файлы, вы будете писать примерно до 10 000 различных мест на жестком диске в круговой форме. Это, скорее всего, полностью соберет любую схему кэширования диска, используемую либо операционной системой, либо дисковым оборудованием. И эта проблема будет сохраняться, даже если у вас есть один файл с n пустыми слотами, предварительно зарезервированными. –

С другой стороны, мой друг прислал мне электронное письмо, в котором он на самом деле пробовал этот метод, и он действительно пошел быстрее, чем я думал. Поэтому я беру обратно то, что я сказал - ваше решение, безусловно, стоит попробовать. –

Вам нужен класс Matrix, чтобы ваше приложение обращалось к матрице через экземпляр класса. Тогда транспозиция может просто установить флаг, который меняет индексы при доступе к элементу. Мгновенный транспонирование!

источник

2011-12-14 22:07:05

Данные будут храниться в файле на жестком диске. Я хочу программу, которая читает этот файл, и записывает транспонирование данных в другой файл. –

Кроме того, я, вероятно, преувеличивал спецификации размера файла. Вероятно, он будет ближе к 10GB, чем 100GB. Но определенно более 4 ГБ. –

Наконец, я собираюсь написать эту программу на C++. –

Наивный способ - просто прочитать файл 10000 раз и найти соответствующие столбцы для каждой строки. Это должно быть легко реализовать, но я не знаю, сколько времени потребуется для запуска программы.

В ваших комментариях вы упомянули вывод другого файла, который затем следует сортировать с помощью sort. Это плохая идея, так как навсегда понадобится сортировать такой большой файл. Сортировка - сложная (или, по крайней мере, ресурсоемкая) проблема, поэтому обобщение транспонирования в сортировку, вероятно, является неправильным способом.

источник

2011-12-15 00:13:16

Что касается идеи сортировки - я провел с ней эксперименты, а программа сортировки unix довольно сложна. Например, если файл невероятно велик, он разбивает его на множество небольших файлов, сортирует каждый из них и затем объединяет их. Я тестировал его с файлами, большими, чем оперативная память на компьютере, и он работает довольно хорошо. –

Это называется методом «разделяй и властвуй», и в основном это то, что делает mergesort и quicksort (хотя большую часть времени вы делите проблему в памяти, а не на диск, но основной принцип тот же). –

Кстати, я беру обратно то, что я сказал о линейном времени. Перемещение файла будет в квадратичное время (более длинный файл умножается на большее количество итераций), поэтому, по-моему, метод сортировки кажется жизнеспособным решением. –

Поиск транспонирования очень, очень большой матрицы

ответ

Смежные вопросы