Проблемы с большим массивом

[Igors]

Добрый вечер

Имею большой массив данных (гигабайты). Распределяю память для него кусками. Сделал свой контейнер, могу использовать оператор []. С массивом надо делать разные хитрые перестановки, сортировки и.т.п. Для этого делаю линейный массив указателей (одним блоком памяти) на элементы массива. Сделал с указателями все что хотел. Теперь осталось переставить элементы в массиве данных в том же порядке как они следуют в массиве указателей (и избавиться от массива указателей который больше не нужен). Использовать новый массив данных не могу - не лезет по памяти. А как переставить "на месте" - не могу сообразить. Есть идеи - подскажите.

Спасибо

[voronElf]

Пока в голову не пришло ничего лучшего, идея "в лоб": по элементу же можно найти указатель в массиве указателей.  идем по массиву указателей. Если текущий элемента не на своем месте, то меняем местами текущий элемент с тем , который должен быть на этом месте. Вариант из разряда "медленно но верно".

ПС: не очень понял, если память под массив элементов выделена кусками, то как можно говорить о порядке элементов ? Или еще учитывается порядок кусков памяти ?

[Igors]

ПС: не очень понял, если память под массив элементов выделена кусками, то как можно говорить о порядке элементов ? Или еще учитывается порядок кусков памяти ?

Нет, все легально, куски могут быть распределены в любом порядке. Выглядит это примерно так

Код:

template <class T>
struct ChunkArray {
...
 T & operator [] ( size_t index )  { return mChunk[index / COUNT_IN_CHUNK][index % COUNT_IN_CHUNK]; }
...
// data members
 vector <T *> mChunk;  // вектор указателей на выделенные блоки
};

Это можно сортировать, но по адресу я не могу знать индекс. Ладно, записал индекс в сам элемент <T>, но почему-то "не переставляется" 

[voronElf]

но по адресу я не могу знать индекс

проход по списку указателей, на каком индексе совпал  адрес, тот индекс и берем

медленно конечно, но добавлять в элемент индекс - трата памяти. Тут уж выбирать приходится (ну или найти другой подход)

не переставляется

ну тут уж алгоритмически как обычно не учтена какая-нибудь мелочь, рушащая всю структуру. Просто отлаживать

[voronElf]

Но эт все мелочи, мне больше про куски памяти интереснее. Не понимаю как можно реализовать индексацию (и сортировку), если данные лежат в нескольких разных кусках памяти. Я бы понял если это реализовывать как раз массивом указателей. Но тогда зачем его удалять? Можт стоит реализовать хранилище массивом указателей (тогда проблема перестановки элементов отпадет просто) ?

[Igors]

Пока в голову не пришло ничего лучшего, идея "в лоб": по элементу же можно найти указатель в массиве указателей.  идем по массиву указателей. Если текущий элемента не на своем месте, то меняем местами текущий элемент с тем , который должен быть на этом месте. Вариант из разряда "медленно но верно".

Обмен здесь вообще не пляшет - ведь обменивая, мы заставляем указатель ссылаться уже на другой элемент. Есть алгоритм, который берет затираемый элемент "в карман" - но он не работает если я не могу превратить адрес в индекс.

Но эт все мелочи, мне больше про куски памяти интереснее. Не понимаю как можно реализовать индексацию (и сортировку), если данные лежат в нескольких разных кусках памяти. Я бы понял если это реализовывать как раз массивом указателей. Но тогда зачем его удалять? Можт стоит реализовать хранилище массивом указателей (тогда проблема перестановки элементов отпадет просто) ?

Про индексацию таких данных я написал выше, ничего необычного нет - напр. QList тоже хранит данные в разных местах. Др. дело что мне не резон распределять блок памяти для каждого элемента 24 байта. А выделить данные одним куском не могу - ОС не дает. Вот и храню в блоках. Таскать массив указателей смысла нет - он нужен только на этапе подготовки данных.

Ладно, пока сделал через файл, дальше видно будет.

[voronElf]

Извиняй, посмотрел внимательнее как индексируешь, дошло  

Насчет QList да, в разных местах, но в нем есть как раз массив указателей (у Шлее вычитал).

Ну а теперь про обмен:

обменивая, мы заставляем указатель ссылаться уже на другой элемент

конечно, поэтому при обмене кроме смены самих элементов обязательно нужно менять и указатели (порядок остается только логический, по содержимому элемента). Меняется позиция элемента в памяти - значит меняется и указатель на этот элемент.

Есть алгоритм, который берет затираемый элемент "в карман" - но он не работает если я не могу превратить адрес в индекс.

Конечно обмен идет через "карман". а превратить адрес в индекс не вижу проблемы. Индекс имеется ввиду в массиве указателей , а не индекс элемента. Есть массив указателей, есть значение указателя - это же просто поиск в массиве по значению (например, для класса QVector метод indexOf это делает). А индексы элементов (внешняя индексация которая) тебе для обмена не нужны, есть ведь напрямую адреса памяти всех элементов.

ПС: или мы грим о разных вещах и друг друга немного не понимаем ? задачка конечно нетривиальная ...

ППС: через файл можт эффективнее получится, эти перестановки - медленное дело.

[Igors]

Сделал, все очень просто:

- пройдя по массиву указателей, вписать в каждый элемент его "место" где он должен находиться (индекс в массиве указателей)

- сортировать по вписанному индексу

Тему можно закрывать, нет тут ничего полезного, просто меня переклинило  

Edit: если известно "место куда поставить" (индекс), то сортировка не есть лучшее решение

Код:

int i, limit = array.size();
for (i = 0; i < limit; ++i)
 while (array[ i ].index != i)
  Swap(array[ i ], array[array[ i ].index]);

Это заметно быстрее сортировки