C++ 6.0; Большие массивы; отимизация по времени

[ezus]

Привет!

Есть 2 больших массива. Из них декартовым произведением получаю третий. Размер выходного массива может вылезать за допустимые пределы, но, к счастью, в процессе формирования он может оказаться существенно меньше произведения размеров 2-х входных массивов. Если памяти не хватает, то расчет прекращается, и пользователь должен задать более жесткие параметры на отсечение менее важных элементов.

Вопрос: какую структуру для хранения массивов выбрать?
Я рассматривал следующие варианты:
1.

Код:

ElementType* elements;
elements = new ElementType[size];

Все прекрасно, но я не знаю размеры результирующего массива, а максимум может не влезть в память. Затевать самому наращивание, перевыделение и переписывание памяти очень не хочется.

2.

Код:

CPtrArray elements;

Решает проблему нарашивания. Но каждый элемент создается через "new", что порождает потери на мелкое выделение памяти и фрагментацию. Конечно, для этого есть пулы, но опять неохота.

3.

Код:

CArray<ElementType,ElementType&> elements;

Решает проблему выделения памяти.
Но мне кажется, что любые манипуляции с элементами массива выполняются через переписывния элемента во временную память. А это очень большие затраты времени.
Надеюсь, что я ошибаюсь.

Возможно есть и другие варианты.

Буду рад любым комментариям.

[Finch]

Если используеш C++, то почему нельзя использовать обычные STL контейнеры. Например List. Правда, этот контейнер не позволяет произвольный доступ к элементам. По сути своей он представляет собой двухсвязанный список.

[Dimka]

Довольно путанное объяснение, но если это проблема хранения больших разреженных матриц (где несмотря на большие размеры мало элементов, а остальные есть NULL), то, разумеется, давно изобретены разные методы.

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

[ezus]

Довольно путанное объяснение, но если это проблема хранения больших разреженных матриц (где несмотря на большие размеры мало элементов, а остальные есть NULL), то, разумеется, давно изобретены разные методы.

Скорее не "путанное", а неполное. Если често, то я просто ждал уточняющих вопросов.

- действительно ли речь про разреженные матрицы?

Данные - это два линейных плотных массива объектов, каждый из которых содержит битовую маску.
Надо получить третий массив, содержащий новые объекты с маской = коньюнкции двух исходных масок.
Наверное, это можно представить в виде матрицы, но не вижу в этом большого смысла.

- каков характер доступа к элементам (равномерно рандомный, последовательный, рандомный в пределах региона матрицы, но последовательный обход регионов)?

Доступ последовательный - перебор всех пар из 2-х входных массивов.

- каков размер (оценка сверху - по максимуму и оценка в среднем - как обычно)?

Объявленного максимума не существует, но возможные размеры входных массивов порядка 5-10 тысяч. Вроде не много, но их произведение дает уже порядка 100 000 000, что не есть приятно. Как я уже писал, к счастью, в ходе произведения возможны существенные сокращения размеров выходного массива. Поэтому его размер заранее не известен.

Добавление: меня интересует оптимизация на больших размерах, т.к. на маленьких размерах прекрасно работает уже существующий алгоритм.

Добавлено через 6 минут и 8 секунд:

Если используеш C++, то почему нельзя использовать обычные STL контейнеры. Например List. Правда, этот контейнер не позволяет произвольный доступ к элементам. По сути своей он представляет собой двухсвязанный список.

1. "К сожалению" я работаю с MFC.
2. Обработка массива в основном последовательная, поэтому двухсвязанный список не самое оптимальное представление для этого.
3. Как я понимаю, организация данных в виде списка подразумевает многократное фрагментированное выделение памяти, чего я очень хочу избежать.

[Dimka]

ezus, 10 тыс битов? 1,2 тыс. байтов? И произведение 12,5 МиБ? Что тут экстремального?

Или ты всё-таки о чём-то другом говоришь?

Надо получить третий массив, содержащий новые объекты с маской = коньюнкции двух исходных масок.
Наверное, это можно представить в виде матрицы, но не вижу в этом большого смысла.

А это вообще надо? Может проще будет вычислять всякий раз, когда понадобится?

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

Это бред. Как раз для последовательного доступа связный список оптимален. Он неоптимален для рандомного доступа.

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

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

[ezus]

ezus, 10 тыс битов? 1,2 тыс. байтов? И произведение 12,5 МиБ? Что тут экстремального?

Или ты всё-таки о чём-то другом говоришь?

Нет, это 10 тыс байт. И с ними нет проблем. Проблема с выходным массивом в "100 000 000" байт.

Надо получить третий массив, содержащий новые объекты с маской = коньюнкции двух исходных масок.
Наверное, это можно представить в виде матрицы, но не вижу в этом большого смысла.

А это вообще надо? Может проще будет вычислять всякий раз, когда понадобится?

Надо.

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

Это бред. Как раз для последовательного доступа связный список оптимален. Он неоптимален для рандомного доступа.

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

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

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

Сколько выделять под стек?
Под все  "100 000 000" байт у меня нет памяти.

[sss]

ezus, зачем торопитесь отвечать? При чем тут стек.. Делайте растущий вектор. MFC позволяет использовать STL...

Добавлено через 30 секунд:
И 100 МБ не много, поверьте

[Dimka]

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

А перебор сколько раз происходит после построения? Если 1, и нет фазы "быстрая работа" после "медленной подготовки", то и смысла нет. Сразу вычисляешь и сразу используешь результат.

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

Проблема с выходным массивом в "100 000 000" байт.

Даже 100 МиБ - это вроде не так и много.

Под все  "100 000 000" байт у меня нет памяти.

Допустим.

Так что же получается в итоге? Тебе надо 100 Мб массив, на который ты тратить память не хочешь. Зачем этот массив нужен, я пока так и не понял. Если это вопрос времени, то время и память - это всегда ресурсы альтернативные. Т.е. экономя на одном, тратишь другое. Т.е. раз нет памяти, значит больше времени. И встаёт вопрос о чём?

Ну хорошо, сколько памяти готов выделить под задачу?

[ezus]

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

А перебор сколько раз происходит после построения? Если 1, и нет фазы "быстрая работа" после "медленной подготовки", то и смысла нет. Сразу вычисляешь и сразу используешь результат.

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

Нет никакого частичного использование. Массив является частью объекта, у которого своя жизнь, возможно выходящая за пределы конкретной сессии.

Проблема с выходным массивом в "100 000 000" байт.

Даже 100 МиБ - это вроде не так и много.

Под все  "100 000 000" байт у меня нет памяти.

Допустим.

Так что же получается в итоге? Тебе надо 100 Мб массив, на который ты тратить память не хочешь. Зачем этот массив нужен, я пока так и не понял. Если это вопрос времени, то время и память - это всегда ресурсы альтернативные. Т.е. экономя на одном, тратишь другое. Т.е. раз нет памяти, значит больше времени. И встаёт вопрос о чём?

Ну хорошо, сколько памяти готов выделить под задачу?

Виноват - поддался на провокацию.
 "100 000 000"  - это не байт, а элементов, каждый из которых в свою очередь содержит свою информацию размером в десятка раз и более. Так что памяти действительно не хватает.

[sss]

 "100 000 000"  - это не байт, а элементов, каждый из которых в свою очередь содержит свою информацию размером в десятка раз и более. Так что памяти действительно не хватает.

Создать словарь для похожих элементов.. Иначе ничего не делать..

Добавлено через 1 минуту и 26 секунд:
При таких объемах вы не то оптимизируете.. Вам не работу организации памяти, а подход сохранения надо переделывать

[ezus]

ezus, зачем торопитесь отвечать?

Тороплюсь - уж очень нужно.

При чем тут стек.. Делайте растущий вектор. MFC позволяет использовать STL...

Ключевое слово растущий.
Кроме того, добавление нового элемента может привести к удалению ранее созданных, что приводит к дырам в массиве. Конечно, можно параллельно организовать список пустот, но это дополнительные затраты времени.

У меня нет проблем реализовать это в принципе - я обратился за помощью в поиске наиболее оптимального варианта.

Добавлено через 1 минуту и 58 секунд:

Создать словарь для похожих элементов.. Иначе ничего не делать..

Что такое словарь похожих элементов?

[ezus]

При таких объемах вы не то оптимизируете.. Вам не работу организации памяти, а подход сохранения надо переделывать

Что можно предложить в замен попарного перебора, если нужен именно он?
Задача из области алгебр, и мне надо выполнить произведение двух скобок.

[sss]

Я бы создал объект раздел  CreateFileMapping. И двигал окно памяти

Словарь - как делают архиваторы...  Ищут частоту вхождения фрагментов текстов и из самых частых создают словарь. А в месте вставки не элемент, а индекс элемента в словаре..

[ezus]

sss, к сожалению, эти алгоритмы существенно тяжелее по времени, чем линейные

[Dimka]

"100 000 000"  - это не байт, а элементов, каждый из которых в свою очередь содержит свою информацию размером в десятка раз и более.

Так причём тут тогда биты?

Я же сразу спросил про разреженную матрицу: если true, есть какой-то объект-элемент, если false - NULL.

Поскольку NULL-ов много, хранить массив нет смысла. Достаточно иметь словарь пар "индекс-объект" (или даже исходные координаты в обоих массивах "индекс-индекс-объект"). Память на хранение указателей, содержащих NULL, не расходуется.

Однако указателей на 50 Мб - это не так и много. Значит проблема в чём-то другом.

Если на false тоже есть объект, но другой, то, как говорит sss, нужно группировать по подобию. Т.е. два словаря - один для true-объектов, другой для false-объектов.

Если же это всё вообще в память не лезет в принципе, тогда я не понимаю, о чём вообще речь? Тогда нет и массива, а нужно строить объект по потребности, или хранить это где-то на диске.

[ezus]

Еще раз спрошу.

Код:

CArray<ElementType,ElementType&> elements;
elements.SetSize(10,10);

elements[5].name = "ququ";   // A)

int x = elements[2].x;   // B)

Операторы присваения в случаях А и В работают на прямую с памятью массива или со временной памятью?

[Dimka]

ezus, должен с той же - раз ссылочный тип аргумента.

[ezus]

Есть 2 больших массива. Из них декартовым произведением получаю третий. Размер выходного массива может вылезать за допустимые пределы, но, к счастью, в процессе формирования он может оказаться существенно меньше произведения размеров 2-х входных массивов. Если памяти не хватает, то расчет прекращается, и пользователь должен задать более жесткие параметры на отсечение менее важных элементов.

Память выходного массива растет непрерывно в процессе формирования, и "Если памяти не хватает, то расчет прекращается,". Но мне надо тянуть до последнего, то есть брать максимум возможного.

sss, к сожалению, массивы принципиально последовательные, содержащие "непохожие" объекты.

Добавлено через 1 минуту и 47 секунд:

ezus, должен с той же - раз ссылочный тип аргумента.

Спасибо, возможно это и есть решение проблемы. Мне нужно было подтверждение и я его получил.
Спасибо.

[Dimka]

Память выходного массива растет непрерывно в процессе формирования, и "Если памяти не хватает, то расчет прекращается,". Но мне надо тянуть до последнего, то есть брать максимум возможного.

Т.е. нужна минимизация "накладных расходов" на хранение структур данных?

Ну в таком случае надо комбинировать связный список и массивы. Т.е. делать блоками из небольших массивов, между собой связанных в список. Тогда переаллокация массива по мере его роста не требуется. В том числе, если массиву некуда расти из-за фрагментации памяти, он не будет целиком копироваться в новое место, если он реально большой. В том числе, если память фрагментирована, непрерывный массив гораздо скорее упрётся в потолок, нежели отдельные кусочки.

[ezus]

Dimka, согласен, я так и собираюсь сделать.
Хотя адресацию придется делать самому, а это накладные расходы, если прятать ее в спец класс массива.
Если для перебора в непреравном участке использовать стандартную индексацию, тогда переход из участка в участок придется перенести на функциональный уровень, а это не хорошо с т.зр. объектного подхода.

[Dimka]

ezus, чего??

Тебе надо сделать класс типа ArrayList с перегруженным оператором [], который внешне выглядит как массив, а внутри сделать связный список из блоков-страниц. Для каждой указать смещение от 0 - т.е. 0 в блоке будет N от начала всего массива.

Это никаким боком не противоречит объектному подходу. Это даже в других языках уже сделано.

[ezus]

Тебе надо сделать класс типа ArrayList с перегруженным оператором [], который внешне выглядит как массив, а внутри сделать связный список из блоков-страниц. Для каждой указать смещение от 0 - т.е. 0 в блоке будет N от начала всего массива.

Это никаким боком не противоречит объектному подходу. Это даже в других языках уже сделано.

Я так понимаю, что в оригинале доступ к i-ому элементу получается через A+ii*sizeof(A), а перегруженный оператор сначала должен определить номер блока, затем найти его или пробегая по списку, или через массив косвенной адресации, и только потом получаем доступ к элементу массива через что-то подобное A+ii*sizeof(A).

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

[Dimka]

ezus, ты ж сам сказал, что всё однопроходное. Какая тогда разница, косвенная там адресация или прямая?

[ezus]

Да, наверное, ты прав.
За советы спасибо.

[sss]

Вообще - просто очень туманная задача.. Более четкое определение элементов может помочь. Если они не однотипны по размеру -  о каких вообще массивах может идти речь? Тогда смысла нет - только список разноразмерных буферов

[Dimka]

sss, самое туманное - как этим всем пользоваться, когда оно построено. Исходя из этого и нужно выбирать структуру. А об этом почти ничего не было сказано.

[ezus]

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