Russian Qt Forum
Ноябрь 23, 2024, 05:41 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Russian Qt Forum > Forum > Программирование > Алгоритмы > Проблемы с большим массивом
Страниц: [1]   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Проблемы с большим массивом  (Прочитано 5995 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« : Февраль 18, 2010, 00:49 »
Добрый вечер

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

Спасибо
Записан
voronElf
Гость
« Ответ #1 : Февраль 18, 2010, 07:22 »
Пока в голову не пришло ничего лучшего, идея "в лоб": по элементу же можно найти указатель в массиве указателей.  идем по массиву указателей. Если текущий элемента не на своем месте, то меняем местами текущий элемент с тем , который должен быть на этом месте. Вариант из разряда "медленно но верно".

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

Сообщений: 11445


Просмотр профиля
« Ответ #2 : Февраль 18, 2010, 11:01 »
Цитата: voronElf от Февраль 18, 2010,  07:22
ПС: не очень понял, если память под массив элементов выделена кусками, то как можно говорить о порядке элементов ? Или еще учитывается порядок кусков памяти ?
Нет, все легально, куски могут быть распределены в любом порядке. Выглядит это примерно так
Код:
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
Гость
« Ответ #3 : Февраль 18, 2010, 13:21 »
Цитировать
но по адресу я не могу знать индекс
проход по списку указателей, на каком индексе совпал  адрес, тот индекс и берем

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


Цитировать
не переставляется
ну тут уж алгоритмически как обычно не учтена какая-нибудь мелочь, рушащая всю структуру. Просто отлаживать
« Последнее редактирование: Февраль 18, 2010, 13:29 от voronElf » Записан
voronElf
Гость
« Ответ #4 : Февраль 18, 2010, 13:24 »
Но эт все мелочи, мне больше про куски памяти интереснее. Не понимаю как можно реализовать индексацию (и сортировку), если данные лежат в нескольких разных кусках памяти. Я бы понял если это реализовывать как раз массивом указателей. Но тогда зачем его удалять? Можт стоит реализовать хранилище массивом указателей (тогда проблема перестановки элементов отпадет просто) ?
« Последнее редактирование: Февраль 18, 2010, 13:27 от voronElf » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #5 : Февраль 18, 2010, 15:00 »
Цитата: voronElf от Февраль 18, 2010,  07:22
Пока в голову не пришло ничего лучшего, идея "в лоб": по элементу же можно найти указатель в массиве указателей.  идем по массиву указателей. Если текущий элемента не на своем месте, то меняем местами текущий элемент с тем , который должен быть на этом месте. Вариант из разряда "медленно но верно".
Обмен здесь вообще не пляшет - ведь обменивая, мы заставляем указатель ссылаться уже на другой элемент. Есть алгоритм, который берет затираемый элемент "в карман" - но он не работает если я не могу превратить адрес в индекс.

Цитата: voronElf от Февраль 18, 2010,  13:24
Но эт все мелочи, мне больше про куски памяти интереснее. Не понимаю как можно реализовать индексацию (и сортировку), если данные лежат в нескольких разных кусках памяти. Я бы понял если это реализовывать как раз массивом указателей. Но тогда зачем его удалять? Можт стоит реализовать хранилище массивом указателей (тогда проблема перестановки элементов отпадет просто) ?
Про индексацию таких данных я написал выше, ничего необычного нет - напр. QList тоже хранит данные в разных местах. Др. дело что мне не резон распределять блок памяти для каждого элемента 24 байта. А выделить данные одним куском не могу - ОС не дает. Вот и храню в блоках. Таскать массив указателей смысла нет - он нужен только на этапе подготовки данных.

Ладно, пока сделал через файл, дальше видно будет.
Записан
voronElf
Гость
« Ответ #6 : Февраль 19, 2010, 07:57 »
Извиняй, посмотрел внимательнее как индексируешь, дошло  Улыбающийся

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

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

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

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

ППС: через файл можт эффективнее получится, эти перестановки - медленное дело.
« Последнее редактирование: Февраль 19, 2010, 08:18 от voronElf » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #7 : Февраль 19, 2010, 18:06 »
Сделал, все очень просто:

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

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

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

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

Код:
int i, limit = array.size();
for (i = 0; i < limit; ++i)
 while (array[ i ].index != i)
  Swap(array[ i ], array[array[ i ].index]);
Это заметно быстрее сортировки
« Последнее редактирование: Февраль 19, 2010, 19:18 от Igors » Записан
Страниц: [1]   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


Страница сгенерирована за 0.059 секунд. Запросов: 22.